Amazon Interview Question for Software Engineer / Developers






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

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

- Arang May 26, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That looks like a good solution. You would need one more change in setting up the random pointers.

1->next->random = 1->random->next

since x' should point to y' and not y. Also, this should only be set when x->random != NULL

- Anurag June 07, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- XYZ May 26, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice one

- Anonymous May 26, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- vishal Sharma May 26, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks vishal...yeah this method would work only if we r allowed to destroy the original random...which is not the case here :(

- xyz May 27, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- xyz May 27, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

you fogrot to have Null check in step-2.
Amazone always looks for boundary conditions too.
what if node->random is null ???
node->random->next can not be done.
rt ???

- bansal.cool May 27, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous May 29, 2010 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More