## Adobe Interview Question for MTSs

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

Why can't you use a map to store the nodes you have already copied?

Comment hidden because of low score. Click to expand.
0

yes, simply create a map of the original node and the corresponding copy node. arbit node can be copied using the map in second iteration.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Hey,
geeksforgeeks.org/archives/1155

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0

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
|----------|

Comment hidden because of low score. Click to expand.
0

Algo of Santosh works, but you would need to store original list pointers separetly in an array

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.