Amazon Interview Question for Software Engineer in Tests






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

Since many have the doubt on the question, here it goes

typedef struct node {
int val;
struct node *nxt;
struct node *rand;
}

using the above structure, we construct the linked list where the nxt points to the next node and rand pointer points to some random node in the same linked-list. It can point to itself (same node), or even be NULL.

So the problems is to achieve a deep copy with no referenct to the previous list.

Hope this clarifies.

This can be solved in O(n) i.e. with 3 passes of the linked - list and zero extra space.

using extra space you can store the mappings of addresses node1 of list1 and node1 of list2 which is what I guess the first person has suggested. But that's not the most optimal solution.

- NEO September 09, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how do you do that in 3 passes and O(1) memory?

- Erik September 09, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

See method 3

hxxp: //exclusiveminds.com/2010/03/05/copy-a-linked-list-with-next-and-arbit-pointer/

- Mahesh September 10, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

So is it assumed that the List is a Doubly Linked list? I was thinking it to be a corrupted singly linked list.

- cirus September 22, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Copy each node and make original node point to new node (so there are two linked lists)
2. Make a third linked list. For each node, it stores the following address. For each node of linked list 2, node->randomeptr->randomptr.
3. Copy each randomeptr in linked list 2 back to original linked list.
4. Copy each address in third linked list to linked list 2.

- Anonymous September 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

did not get the q

- oshin September 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you please explain the question taking an example

- DashDash September 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A separate copy of the link list is to be made allocating new nodes for new list. Copying is simple solvable in O(n).
But random pointer create the problem then problem can be solve in O(n2) using native method or using hash table in O(nlgn).

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

this is a very good question..even i was asked this..question

- T September 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution if i understood question correctly :)

package linkedlist;

public class Node implements Cloneable{ private String value;
	
	private Node next;

	public String getValue() {
		return value;
	}

	public void setValue(String value) {
		this.value = value;
	}

	public Node getNext() {
		return next;
	}

	public void setNext(Node next) {
		this.next = next;
	}
	
	public Object clone(){
		try {
			Node clonnedNode = (Node)super.clone();
			clonnedNode.next= (Node)next.clone();
			return clonnedNode;
		}
		catch(CloneNotSupportedException cnse){
			return null;
		}
	}
	

}

- Mritunjay Kumar September 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think it can be done in two passes.

public void clone()
{

    // At this point all nodes are cloned and rand points to old node.
    Node newNode = super.clone();
    newNode.rand = thisNode;     
    map.store(oldNode,newNode);
    Node next = clone.next();

    // Now update the rand    
    newNode.rand = map.get(newNode.rand);
}

- Anonymous September 09, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This would work. But the extra storage for the map structure would require O(n) extra space. An extra pass is preferred over using extra space.

- Neo September 14, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done in one pass. You will need two hashmaps, one to keep track of the clones of each node and the other to keep track of the random pointer.

- Anonymous September 14, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hashmap would require extra space. Using zero extra space would be preferred.

- Neo September 14, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this.
let the list be
|---------|
1-2-3-4-5-6-7
|-------|

i.e. 1 pointing to 5 and 2 pointing to 7
Copy can be done in two passes
|------------------------|
1. 1-1'-2-2'-3-3'-4-4'-5-5'-6-6'-7-7'
|-------------------|
2. In this pass, isn't this easy to find out where 1 is pointing to and point 1' to 7'? In this pass itself, break the extra links and get the new linklist.

- Anon September 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your logic is good

- genthu January 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry for last comment.
How about this.
let the list be

|---------|
1-2-3-4-5-6-7
|-------|

i.e. 1 pointing to 5 and 2 pointing to 7
Copy can be done in two passes

1.

|------------------------| 
         1-1'-2-2'-3-3'-4-4'-5-5'-6-6'-7-7'
         |-------------------|

2. In this pass, isn't this easy to find out where 1 is pointing to and point 1' to 7'? In this pass itself, break the extra links and get the new linklist.

- Anon September 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done in 3 passes I think. Let's call the input list 'list1', and let's use the following structure:

struct Node {
  Node *pNext;
  Node *pRand;
  T value;

Pass 1: Walk list 1 and clone each node creating list 2. If the list1 node is N1 and list2 node is N2, set N2->pRand = N1->pRand, and N2->pNext = N1->pRand (effectively caching it here)

Pass 2: Walk list 2 and set each N2->pRand = N2->pRand->pRand

Pass 3: Walk list 1 and list 2 simultaneously and set temp=N2->pNext, N2->pNext = N1->pNext->pRand, and then N2->pRand = temp;

- peanutballs September 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Make use the pointers in old list

Node * deepcopy(Node *head){
   if(head == null){
      return null;
   }
   Node * newlist = _deepcopy(head);
   Node * p = newlist;
   while(p!=null){
      p->rand = p->rand->rand->next;
   }
}

Node * _deepcopy(Node* old){
   Assert(old!=null);
   Node* oldnext = old->next;
   Node * new = (Node*)malloc(sizeof(Node));
   new->val = old->val;
   old->next = new;
   new->rand = old;
   if(oldnext == null){
      new->next=null;
   }else{
      new->next=_deepcopy(old->next);
   }
}

- BUAA March 09, 2011 | 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