Amazon Interview Question
Software Engineer in TestsSee method 3
hxxp: //exclusiveminds.com/2010/03/05/copy-a-linked-list-with-next-and-arbit-pointer/
1. Copy each node and make original node point to new node (so there are two linked lists)
2. Make a third linked list. For each node, it stores the following address. For each node of linked list 2, node->randomeptr->randomptr.
3. Copy each randomeptr in linked list 2 back to original linked list.
4. Copy each address in third linked list to linked list 2.
Solution if i understood question correctly :)
package linkedlist;
public class Node implements Cloneable{ private String value;
private Node next;
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Object clone(){
try {
Node clonnedNode = (Node)super.clone();
clonnedNode.next= (Node)next.clone();
return clonnedNode;
}
catch(CloneNotSupportedException cnse){
return null;
}
}
}
I think it can be done in two passes.
public void clone()
{
// At this point all nodes are cloned and rand points to old node.
Node newNode = super.clone();
newNode.rand = thisNode;
map.store(oldNode,newNode);
Node next = clone.next();
// Now update the rand
newNode.rand = map.get(newNode.rand);
}
It can be done in one pass. You will need two hashmaps, one to keep track of the clones of each node and the other to keep track of the random pointer.
How about this.
let the list be
|---------|
1-2-3-4-5-6-7
|-------|
i.e. 1 pointing to 5 and 2 pointing to 7
Copy can be done in two passes
|------------------------|
1. 1-1'-2-2'-3-3'-4-4'-5-5'-6-6'-7-7'
|-------------------|
2. In this pass, isn't this easy to find out where 1 is pointing to and point 1' to 7'? In this pass itself, break the extra links and get the new linklist.
Sorry for last comment.
How about this.
let the list be
|---------|
1-2-3-4-5-6-7
|-------|
i.e. 1 pointing to 5 and 2 pointing to 7
Copy can be done in two passes
1.
|------------------------|
1-1'-2-2'-3-3'-4-4'-5-5'-6-6'-7-7'
|-------------------|
2. In this pass, isn't this easy to find out where 1 is pointing to and point 1' to 7'? In this pass itself, break the extra links and get the new linklist.
It can be done in 3 passes I think. Let's call the input list 'list1', and let's use the following structure:
struct Node {
Node *pNext;
Node *pRand;
T value;
Pass 1: Walk list 1 and clone each node creating list 2. If the list1 node is N1 and list2 node is N2, set N2->pRand = N1->pRand, and N2->pNext = N1->pRand (effectively caching it here)
Pass 2: Walk list 2 and set each N2->pRand = N2->pRand->pRand
Pass 3: Walk list 1 and list 2 simultaneously and set temp=N2->pNext, N2->pNext = N1->pNext->pRand, and then N2->pRand = temp;
Make use the pointers in old list
Node * deepcopy(Node *head){
if(head == null){
return null;
}
Node * newlist = _deepcopy(head);
Node * p = newlist;
while(p!=null){
p->rand = p->rand->rand->next;
}
}
Node * _deepcopy(Node* old){
Assert(old!=null);
Node* oldnext = old->next;
Node * new = (Node*)malloc(sizeof(Node));
new->val = old->val;
old->next = new;
new->rand = old;
if(oldnext == null){
new->next=null;
}else{
new->next=_deepcopy(old->next);
}
}
Since many have the doubt on the question, here it goes
using the above structure, we construct the linked list where the nxt points to the next node and rand pointer points to some random node in the same linked-list. It can point to itself (same node), or even be NULL.
- NEO September 09, 2010So the problems is to achieve a deep copy with no referenct to the previous list.
Hope this clarifies.
This can be solved in O(n) i.e. with 3 passes of the linked - list and zero extra space.
using extra space you can store the mappings of addresses node1 of list1 and node1 of list2 which is what I guess the first person has suggested. But that's not the most optimal solution.