Amazon Interview Question for SDE1s

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
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 =*i).first->arbit)

Note:- (*i).first = original_List node
(*i).first->arbit = arbitrary node pointed by (*i).first 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!!!

- pulkit.mehra.001 March 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
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'

2) Copy random links
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;
            //copy random links
            //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;
                    //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;

- GK March 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
of 1 vote


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

Use that somehow, okay?

- ARE YOU STUPID March 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
of 4 votes

thanks for the clue, but the arrogance is not appreciated

- blackpool March 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
of 0 votes

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

- YOU ARE STUPID April 08, 2014 | Flag

Add a Comment

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


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


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