## Amazon Interview Question for Software Engineer / Developers

Team: SDE
Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
of 5 vote

First pass
>> Copy the basic linked list structure from old list to new list
>> You'll have data and nextLink fields filled properly
>> Hash the data in each node and store the memory address of the node in the buckets
Second pass
>> Examine what data the randomLink points to in the original list.
>> Look up the hash table with data as key and you'd get memory location of the data in the new list.
>> Fill up the randomLink field in the new list accordingly

PS: I think the hint was too big a hint

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

1) Create the copy of every node in the list and insert it in original list between current and next node.
create the copy of A and insert it between A & B..
create the copy of B and insert it between B & C..
Continue in this fashion, add the copy of N to Nth node.
2) Now copy the arbitrary link in this fashion
original->next->random = original->random;
3) Now restore the original and copy linked lists in this fashion in a single loop.
original->next = original->next->next;
copy->next = copy->next->next;

While doing this, take care of end of list (NULL pointer) and NULL pointer dereference.

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

Step 2 should be original->next->random = original->random->next;

otherwise random would be pointing to nodes of original list rather than new list

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

I guess there can be no solution with the entire link list, all the data in each node of the link list are the same. it can be done. but not going to be O(n) if all the data in the list are the same

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

Step1: In first pass using next pointer create a new linked list and also make a map of original reference Vs new reference
Step 2 In second pass using random node if it not null than search in the map and set to random pointer

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

Step1: In first pass using next pointer create a new linked list and also make a map of original reference Vs new reference
Creating map means that data in the node might not be distinct, so use object reference
Step 2 In second pass using random node if it not null than search in the map and set to random pointer

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

``````// creating a clone of the nodes of the list
// the next pointers of the original list will
// be pointing to the corresponding node in the copy list
// the next pointers of the copy list will be
// pointing to the next node of the corresponding node
// in the original list
while (p != null) {
q = clone(p)
q.next = p.next
p.next = q
p = q.next
// random pointer of q points to nowhere at this point
}

// copying random pointers to the copy list
while (p != null) {
q = p.random.next
p.next.random = q
p = p.next.next
}

// fixing the next pointers in the two lists
while (p != null) {
q = p.next
p.next = q.next
q.next = p.next.next
p = p.next
}

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

Copying isn't quite right because a copied node should point to the *copied* next node.

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.