Expedia Interview Question
Software Engineer in TestsCountry: United States
Interview Type: In-Person
1. For each node X in the given list,
1.1 create a corresponding node Y for the new list. Copy X's Data to Y's Data. The Y's
Next and Other both pointing to null.
1.2 Store X as key and Y as value in the map
2. Iterate over each entry in the map.
2.1 For key X , get value Y
2.2 Y-> Next = map.get(X->Next)
2.3 Y->Other = map.get(X->Other)
You deen to write serialization. I've written something simular in Java. All you need - it is resolve cyclic reference in order to reject infinite cycle copying. In java You can use identityHashCode and identityHashMap to store each node only once. And that build up list from them. You put the node to the identyty hash Map. Then you looks to pointer. If nodes they are referenced to are in the map - then store their hashcode else put theese node to map and store their hash code.
from
Node next -> some other node
to
Node next -> 0xAB23FD133
public Node copyList(Node head) {
if (head == null)
return null;
//Create a new node for each node in the original list.
//Also, create two index arrays, one for original list, one for new list
Node curr = head;
ArrayList<Node> originIndexArray = new ArrayList<Node>();
ArrayList<Node> newIndexArray = new ArrayList<Node>();
while (curr != null) {
Node node = new Node();
node.data = curr.data;
newIndexArray.add(node);
originIndexArray.add(curr);
curr = curr.next;
}
//Set next pointer of each node in the new list
for (int i = 0; i < newIndexArray.size(); i++) {
Node node = (Node) newIndexArray.get(i);
if (i + 1 < newIndexArray.size()) {
Node nextNode = (Node) newIndexArray.get(i+1);
node.next = nextNode;
} else {
node.next = null;
}
}
//Set other pointer of each node in the new list
for (int i = 0; i < originIndexArray.size(); i++) {
Node oNode = (Node) originIndexArray.get(i);
Node nNode = (Node) newIndexArray.get(i);
if (oNode.other != null) {
int k = originIndexArray.indexOf(oNode.other);
Node otherNode = (Node) newIndexArray.get(k);
nNode.other = otherNode;
} else {
nNode.other = null;
}
}
return (Node) newIndexArray.get(0);
}
We have originalList. Create a DupList with other as null, copy data and next.
Now loop through the Original and Dup lists:
if orig's other == null then dup's other = null;
else if orig's other == self then dup's other = self;
else
create another temp1 list = orig's head;
create another temp2 list = orig's head;
loop through temp 1 and 2, and check if temp1's next points to the orig's other
if yes then put dup's other = temp2's current pos
this will be n^2 solution.
// Java Implementation
// Algorithm of this code is Brandy code.
// Time complexity is O(n) and space is O(n)
private class Node {
int data;
Node next, other;
Node(int data) {
this.data = data;
this.next = this.other = null;
}
}
Node copyLinkedList(Node head) {
if (null == head) {
return null;
}
Node current = head;
while (null != current) {
Node temp = new Node(current.data);
temp.next = current.next;
current.next = temp;
current = temp.next;
}
current = head;
Node copiedList = head.next;
while(null != current) {
Node temp = current.next;
temp.other = current.other.next;
current.next = temp.next;
current = current.next;
temp = current.next;
}
return copiedList;
}
in the given link list make all the nodes pointing to itself by using other pointer
and while copying just put the data of every node by using node->other->data in new linklist
Now I might be under-thinking things here but if all "other" nodes point to only nodes within the same linked list, there is no need to do anything special; just start and head and copy everything
Node* copy(Node* head)
{
if(head==NULL)
return NULL;
Node* newHead=new Node(*head);
while(head->next)
{
newHead->next=new Node(*(head->next)); //assume a shallow copy constructor
head=head->next;
}
return newHead;
}
Now if "other" can point to any Node on any list and thus we need to reconstruct that entire sublist as well, then things get interesting. But that is for a another answer
- Brandy May 23, 2014