Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

I like the solution
1) Create the copy of node 1 and insert it between node 1 & node 2 in original Linked List, create the copy of 2 and insert it between 2 & 3.. Continue in this fashion, add the copy of N afte the Nth node
2) Now copy the arbitrary link in this fashion

original->next->arbitrary = original->arbitrary->next; /*TRAVERSE
TWO NODES*/
This works because original->next is nothing but copy of original and Original->arbitrary->next is nothing but copy of arbitrary.
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;
4) Make sure that last element of original->next is NULL.

Time Complexity: O(n)
Auxiliary Space: O(1)

- santosh July 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The approach is Good

- subrata August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice approach.

An O(N) time and O(N) auxillary space solution, would be to::

1) Scan the original list and create the copy list, one node at a time, populating ONLY the "next" pointers in each node. Also, while scanning the original list create a map between the addresses of corresponding nodes in original and copied list.

2) Now, scan the original list once again and for each "arbitrary" pointer in each node of the original list, get the corresponding value from the map, and copy that value in "arbitrary" field of the node of the copied list.

- DeathEater August 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It seems that you are duplicating every node in the list, if it's so, how the space complexity is O(1), isn't it O(n)?

Could you please elaborate on the space complexity?

- prasad January 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Got the point, no need any explanation. thanks

- prasad January 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node* f(Node* h)
{
   if (h==null) return null;

   Hash<int, int> *ht = new Hash<int, int>();
   Node *hp = h;
   Node *nh = null;
   Node *nt = null;
   while (hp!=null)
   {
      Node *n = new Node(hp->value);
      if (nh == null)
      {
         nh = nt = n;
      }
      else
      {
         nt->next = n;  
         nt = nt->next;
      }
      ht.Add(hp, n);
      hp = hp->next;
   };

   hp = h;   
   while (hp != null)
   {
      if (hp->random == null)
      {
          ht[hp]->random = null;
      }
      else
      {
          ht[hp]->random = ht[hp->random];
      }
      hp = hp->next;
   }

   delete ht;
   return nh;
}

- jiangok2006 July 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you pls elaborate your alg bit? Thanks

- nsdxnsk July 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can u please elaborate what is the point of "randolmy pointing "?otherwise its a simple enough question

- ank July 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Initial value of source is head of original list
public Node copyList(Node source)
{
	// base case
	if(source == null)
		return null;
		
	// create new node for new list
	Node newNode = new Node();
	newNode.setData(source.getData());
		
	// set new node's next to copy of original's next
	newNode.setNext(copyList(source.getNext()));
		
	return newNode;

}

- athap July 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Return value is the new head of copied list

- athap July 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You are in effect copying a graph, which may be circular, say a node points to one of its predecessors in the list.
The one thing notable is that you have a path with covers every node in the graph for only once.So if the nodes aren't many, you can traverse the old linked list or the new "graph" to check what you have already copied(the latter presumably better for it has less nodes, yet the pointers may overlap each other and point to the same nodes multiple times,the overlapping being proportional to the number of pointers of each node, plus you need to deal with the possibility of circling) instead of using a full-blown hash table; I leave out the implementation.

- EthOmus July 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node* copy(root)
{
	Node* cur,*tail,*newroot=NULL;

	cur=root;
	while(cur)
	{
		temp=getNode(cur->data);

		if(!newroot)
			newroot=tail=temp;
		else
		{
			tail->random=temp;
			tail=tail->random
		}
		cur=cur->random;
	}
	return newroot;
}

- Aashish July 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i don't understand what is meaning of randomly pointing does it make a graph?or it follow the meaning of single link list where each node point to one node and that node not points it back or multiple nodes can point to one node m confused if it is graph then i think we have to use dfs which is of o(n2) any better and simple solution??

- ritika July 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm confused as well. OP, can you please restate the question more clearly?

- Anonymous July 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

node* copy_list( node* original )
{
node* original_h=original;
store( original_h );
vector<node*> v;
node* copy_h=new node;
node* prev;
copy_h->data=original_h->data;
copy_h->next=NULL;
copy_h->random=original_h;
v.push_back(originl_h);
node* t=copy_h;
prev=original_h;

original_h=original_h->next;
prev->next=copy_h;
while(original_h)
{
node* tmp=new node;
tmp->data=original_h->data;
tmp->next=NULL;
tmp->random=original_h;
t->next=tmp;
t=t->next;
v.push_back(original_h);
prev=original_h;
original_h=original_h->next;
prev->next=tmp;
}
t=copy_h;
while(t)
{
t->random=t->random->random->next;
t=t->next;
}
node* restore= original;
for(int i=1;i<v.size();i++)
{
restore->next=v[i];
restore=restore->next;
}
return copy_h;
}

- bsnabg July 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{{{{{{{{{{{{{{{{{{{ }}}}}}}}}}}}}}}}}}}}}}}}}}}} - visnu April 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdlib.h>
#include<stdio.h>

    typedef struct node_s{
    int data;
    struct node_s *next;
    struct node_s *arbit;
    } Node_s;
 
    void free_list(Node_s * head){
    if(!head) return;
    Node_s * temp = head;
    Node_s * next = head;
    while(temp){
        next = temp->next;
        free(temp);
        temp = next;
    }
    }
    void push_1(Node_s **head, int value){
    if(*head == NULL){
        (*head) = (Node_s *)malloc(sizeof(Node_s));
        (*head)->data = value;
        (*head)->next = NULL;
    }
    else{
        Node_s * temp = (Node_s *)malloc(sizeof(Node_s));
        if(temp){
            temp->data = value;
            temp->next = (*head);
            *head = temp;
        }
    }
    }
    void add_arbit(Node_s *L1, int a, int b){
     Node_s * first = L1;
     Node_s * second = L1;
 
     while(first){
         if(first->data == a)
             break;
         first = first->next;
     }
     while(second){
        if(second->data == b)
            break;
        second = second->next;
    }
    if(first)
        first->arbit = second;
    }
    Node_s * create_node(int val){
 
    Node_s * temp =  (Node_s *)malloc(sizeof(Node_s));
    if(temp){
        temp->data = val;
        temp->next = NULL;
    }
    return temp;
    }
 
    Node_s * clone(Node_s * node){
 
    if(!node) return NULL;
    Node_s * current = node;
 
    //First insert clone nodes in original linked list.     
    while(current){
        Node_s * current_next = current->next;
        current->next  =  create_node(current->data);
        current->next->next = current_next;
        current = current_next;
    }
    current = node;
    
    //Now copy arbit pointer of each node to cloned list
    Node_s * clone_head  = current->next;
    while(current){
        Node_s * clone = current->next;
        if(current->arbit){
            clone->arbit    = current->arbit->next;
        }
        current = clone->next;
    }
 
    current = node;
    
    //Segregate two linked list
    while(current){
        Node_s * clone  = current->next;
        current->next = clone->next;
        if(clone->next){
            clone->next = clone->next->next;
        }
        current = current->next;
    }
    //return head pointer to the calling function
    return clone_head;
    }

    int main(){
    Node_s * L1 = NULL;
    push_1(&L1,1);
    push_1(&L1,2);
    push_1(&L1,3);
    push_1(&L1,4);
    push_1(&L1,5);
    push_1(&L1,6);
 
    add_arbit(L1,1,6);
    add_arbit(L1,2,5);
    add_arbit(L1,3,1);
    add_arbit(L1,4,2);
    add_arbit(L1,5,4);
    add_arbit(L1,6,3);
 
    print_list_1(L1);
    
    Node_s *clone_head  = clone(L1);
    free_list(L1);
    print_list_1(clone_head);
 
    return 0;    
    }

- Jitendra Sangar August 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think it is doubly linked list, not single linked list. Each node has two pointers next and arbitrary. Where next points to the next node, and arbitrary points to random node.

- chetan August 01, 2012 | 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