Amazon Interview Question
Software Engineer / DevelopersHow about this..
we have 1-->2-->3-->4--> and the random pointers.
1. we will create 1'->2'->3'->4' with (1'--ran-->1.random), (2'--ran-->2.random) and so on. Also (1--ran--> 1') and so on.
(i have shown random pointer as --ran-->)
2. for all node in list,node' in new list',
temp=node'->random;
node'->random=node'->random->random;
node->random=temp;
it has a little flaw
when you replace original random ptr values in original list. you loose the binding between 2 lists. if later nodes have random pointer pointing towards earlier nodes it will not work
for example in given example in 4 th node random is 1.
now at this point your 1 sth node in both lists points on node in it's own list.
so when you do node'->random you are on node1 whic has random as node2 which again has random as node3. so you'll fill node4'->random as node3 instead of node1'.
this solution can work if we are allowed to destroy the original list.
Here goes another solution to preserve original list..(i m not sure if this is same as arang)
1. create 1->1'->2->2'->3->3'->4->4'-> , no need to change original randoms
2. starting from 1, say node points to 1,
we would do, node->next->random=node->random->next
node=node->next->next, until node!=null;
3. now seperate the two lists, point node1 to 1 and node2=null
do
node2=node1->next;
node1->next=node2->next;
node1=node2->next;
node2->next=node1->next;
Take care of null as terminating condition.
1. Create the clone line following the next pointer in original list.
2. change the next pointer of original list to point to corresponding node in clone list.
3. change the arbitrary point of copy list to point to corresponding node in original list.
4. now for each node in original list do
clonelistnode-->orbit==clonelistnode--->orbit--->orbit-->next.
originalistnode--->next=originallistnode-->next-->next-->orbit
4th step will copy the orbit pointer of orignal node and also restore the next pointer for original list.
First i had given a solution using Hash table to do pointer mapping..with O(n) complexity... then he asked me to give solution without any additional space with same complexity O(n).
- Arang May 26, 2010He also gave me a hint "Break the list...clone it.. and restore the list"
My solution was...
Step-1) Break the list and create a clone such that
1-->1'-->2-->2'-->3-->3'-->4-->4'-->NULL
(dont distrub any random pointers)
step-2) Assign random pointer
1->next->random = 1->random
2->next->random = 2->random
.
.
step-3) restore the original list
1->next = 1->next->next;.
.
.