Tintri Interview Question
Member Technical StaffsCountry: United States
Interview Type: In-Person
You can do this in O(n) time and O(1) space but involves modifying original list's rnd pointers though they will be reverted back at the end.
Idea is after we do a normal clone of the list with next pointers set, the empty rnd pointers of the clone can be used to temp store original's rnd and original's rnd can store clone as a way to map original and clone. I'll sketch out an algo when I get time...
You can do this in O(1) space and O(N) time.
After doing the normal clone with next pointers, the empty rnd pointers can be used to temporarily store corresponding original's rnd and original's rnd can store corresponding clone node as a way to keep a map between original -> clone without using extra space.
I'll sketch out something when I get time...
> Traverse the linked list and for each node , create a new node.
> Insert the new node in the original linked list right after the original node.
> Once the entire linked list is traversed , we would be having a linked list with each node followed by its duplicate node.
> Now Traversal again, this time only by iterating over the original nodes.
> For each originalNode , we set its duplicate's random pointer to its randomPointer's next.
> Then traverse the link list again & remove all the duplicate nodes from the link list and return the head pointer of the linked list.
Complexity: O(n)
- R@M3$H.N October 01, 2015