Adobe Interview Question MTSs
Country: India
Interview Type: In-Person
this is a very common Amazon question but they do not mention about original list being unmodifiable but it is implied that the original list remains intact once you are done with your copy (u can modify intermittently but establish all relationship of the original list). Without modifying the original list i think you need to have a two way list if you dont want to do the messy work of counting node's position from its random node link
I knew the solution but when I started He added original is constant can't be modified.
Given brute force approach O(n2) but I was asked to do in O(n).
first creat normal duplicate list with random pointer pointing to corresponding original list. now list look like this
|----------|
A->B->C->D->
| | | |
E->F->G->H
now make original list's next pointer points to correspodinging in new list. look like this
|----------|
A B C D
|| || || ||
E->F->G->H
now E's random goes to G via E->random = E-random->random->next.
|----------|
A B C D
| || || ||
E->F->G->H
|----------|
after this original list restored like this A->next = A->next->next->random
|----------|
A->B C D
E->F->G->H
|----------|
Algo of Santosh works, but you would need to store original list pointers separetly in an array
it works but it doesn't satisfy the constant criterion, only solution that i can think of currently in that case is maintain a dictionary with key the original list node pointers and the value being the corresponding node in the duplicate list. in the first traversal create the duplicates without the random nodes, adding the pair in the dictionary. in the second traversal of the original list, read the random pointer, read its corresponding value from the dictionary and assign that to the random of duplicate
This is how we can do it ,
We can create a copy of Original to make sure Original is not changes, then on cloned one we can do this
1) Add duplicate node infront of all node like if i say list is 1->2->3 with random pointers then after duplicate insertion the list would be like this 1->1->2->2->3->3
2) Now use this Original->next->artitrary = original->arbitrary->next;
3) Original = Original->next->next;
Point me out if it seems incorrect.
Thanks
Nishant Pandey
Why can't you use a map to store the nodes you have already copied?
- {} October 19, 2012