## Amazon Interview Question for SDE1s

Country: India
Interview Type: In-Person

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

The method I came across uses <map> container of C++ STL. A map is actually an associative array which has a key and a value associated with that key.

Steps: (The code syntax isn't coming properly in comments so check online)

1. Copy the original list to new list with next pointers intact, leave arbit pointers for now

2. While copying make a map

``map <node*, node*> map_hash``

In our case map will have the key as the original list node and value as copy list node

3 Map would be somewhat like this

Original --> Copy
Node1 --> Node1(copy)
Node2 --> Node2(copy)
Node3 --> Node3(copy)

4 Start from head of copy list, corresponding to this copy list node we have the original list node in map. We can access it using an iterator.

``````map<node*, node*>::iterator i
i = map_hash.begin()
copy_node->arbit = map_hash.at((*i).first->arbit)``````

Note:- (*i).first = original_List node
(*i).first->arbit = arbitrary node pointed by (*i).first
map_hash.at() gives the value stored at that key

What we are doing is for each copy_List node we take its corresponding original_List node then find its arbit node, next we use our map to find the node in our copy_List corresponding to this arbit node and assign it to the arbit pointer of the copy_List node

Hope this will help!!!

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

This problem was already discussed many times. I've chosen the most elegant idea and implemented it

If we want to copy such linked list we should do following steps:

1) Create copy for each node and insert it next to node.
Example: was A->B->C became A->A'->B->B'->C->C'

Example: if there were connection A->C let's make connection A'->C'

3) Remove link between original node and it's copy (separate copy and original)

Totally we need to traverse three times through linked list (O(3N)) and O(1) extra memory
Here is C# implementation.

``````//O(3N) operations
public static Node Copy(Node start)
{
Node copy,result, original = start;
//First traverse
//For each node insert copy of node next to it
while (original != null)
{
copy = new Node
{
Val = original.Val,
Next = original.Next
};
original.Next = copy;
original = copy.Next;
}

//Second traverse
original = start;
//Example was A->C , copy link to nodes' copies A'->C' (-> means "Random")
while (original != null)
{
copy = original.Next;
if (original.Random != null)
copy.Random = original.Random.Next;
else
{
//this "else" block can be safely removed , because by default Random is null
//I save this code only for your understanding
copy.Random = null;
}
original = copy.Next;
}

//Third traverse
original = start;

//save the result , because now the code will destroy links between
//original nodes and copies
result = start.Next;

//destroy links between original nodes and copies
while (original!=null)
{
copy = original.Next;
original.Next = copy.Next;
if (original.Next != null)
copy.Next = original.Next.Next;
original = original.Next;
}
return result;
}``````

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

DUHHH. USE A HASH TABLE DUHHH.

Create cloned nodes and hash (key=cloned from, valu=clone itself)

Use that somehow, okay?

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

thanks for the clue, but the arrogance is not appreciated

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

Mr. DUHHH. this is a portal for discussion. Please have the courtesy to explain your logic, otherwise, silence is well respected. thank you!

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.