Amazon Interview Question for SDE1s


Country: India
Interview Type: In-Person




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

List merge(List head1, List head2) {
	List result = null;
	if (head1.data < head2.data) {
		result = head1;
		result.next = merge(head1.next,head2);
	}
	else {
		result = head2;
		result.next = merge(head1,head2.next);
	}
	return result;
}

- arsragavan March 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

There should be a terminating condition in your code to end recursive calls.

- Anonymous March 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 votes

The modified code would be

List merge(List head1, List head2) {
        if(head1 == null && head2 != null)
          return head2;
   
        if(head1 != null && head2 == null)
         return head1;  
 
	List result = null;
	if (head1.data < head2.data) {
		result = head1;
		result.next = merge(head1.next,head2);
	}
	else {
		result = head2;
		result.next = merge(head1,head2.next);
	}
	return result;
}

- Anonymous March 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static LinkedList MergeLinkedLists(LinkedList p1, LinkedList p2)
        {
            LinkedList newHead = new LinkedList();
            
            if (p1 == null && p2 == null) return null;
            if (p1 != null && p2 == null) return p1;
            if (p1 == null && p2 != null) return p2;

            Node Head1 = p1.Head;
            Node Head2 = p2.Head;

            while (Head1 != null && Head2 != null)
            {
                if (Head1.Data < Head2.Data)
                {
                    newHead.Add(Head1);
                    Head1 = Head1.Next;
                }
                else if (Head1.Data == Head2.Data)
                {
                    newHead.Add(Head1);
                    Head1 = Head1.Next;
                    newHead.Add(Head2);
                    Head2 = Head2.Next;
                }
                else
                {
                    newHead.Add(Head2);
                    Head2 = Head2.Next;
                }
            }

            if (Head1 != null)
            {
                newHead.Current.Next = Head1;
            }

            if (Head2 != null)
            {
                newHead.Current.Next = Head2;
            }
            return newHead;
        }


        public static void TestMergeLinkedLists()
        {
            LinkedList p1 = new LinkedList();
            LinkedList p2 = new LinkedList();

            p1.Add(new Node(3));
            p1.Add(new Node(4));           

            p2.Add(new Node(1));
            p2.Add(new Node(1));
            p2.Add(new Node(1));
            p2.Add(new Node(7));

            Console.Write("List1 = ");
            p1.Print();

            Console.Write("List2 = ");
            p2.Print();

            Console.WriteLine("---------------------------");
            LinkedList lst = MergeLinkedLists(p1,p2);

            lst.Print();
        }      

       public class LinkedList
    {
        private Node _Head;
        private Node _Current;
        public Node Head
        {
            get
            {
                return _Head;
            }
            set
            {
                _Head = value;
            }
        }

        public Node Current
        {
            get
            {
                return _Current;
            }
            set
            {
                _Current = value;
            }
        }
        public LinkedList(Node pH)
        {
            _Head = pH;
            _Current = _Head;
        }
        public LinkedList()
        {
            _Head = null;
            _Current = null;
        }
        public void Add(Node pD)
        {
            if (pD == null) return;

            if (_Current != null)
            {
                _Current.Next = pD;
                _Current = _Current.Next;
            }
            else
            {
                _Head = pD;
                _Current = _Head;
            }
        }

        public void Print()
        {
            Node pH = _Head;
            while (pH != null)
            {
                if (pH.Next != null)
                    Console.Write(pH.Data.ToString() + "->");
                else
                    Console.Write(pH.Data.ToString());

                pH = pH.Next;
            }
            Console.WriteLine("");
        }
    }

Output:

List1 = 3->4
List2 = 1->1->1->7
---------------------------
1->1->1->3->4->7

- Jasonhuangx March 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

node* merge(node* & p1,node* & p2)
{
if(p1==NULL)
return p2;
if(p2==NULL)
return p1;
node* temp;
if(p1->val>p2->val)
{
temp=p1;
p1=p2;
p2=temp;
}
temp=NULL;
node* temp1 = p1;

while(p1!=NULL && p2!=NULL)
{
while(p1->val<=p2->val)
{
temp=p1; // store the previous node;
if(p1->next==NULL)
{
p1->next=p2;
return temp1;
}
p1=p1->next;
}
temp->next=p2;// insert the node in first list
while(p2->next!=NULL&&p2->next->val<p1->val)
p2=p2->next;
temp=p2->next;
p2->next=p1;
p2=temp;
}
return temp1;
}

- brinel March 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

node* merge(node* & p1,node* & p2)
{
	if(p1==NULL)
		return p2;
	if(p2==NULL)
		return p1;
	node* temp;
	if(p1->val>p2->val)
	{
		temp=p1;
		p1=p2;
		p2=temp;
	}
	temp=NULL;
	node* temp1 = p1;
	
	while(p1!=NULL && p2!=NULL)
	{
		while(p1->val<=p2->val)
		{
			temp=p1; // store the previous node;
			if(p1->next==NULL)
			{
				p1->next=p2;
				return temp1;
			}
			p1=p1->next;
		}
		temp->next=p2;// insert the node in first list
		while(p2->next!=NULL&&p2->next->val<p1->val)
			p2=p2->next;
		temp=p2->next;
		p2->next=p1;
		p2=temp;
	}
	return temp1;
}

- brinel March 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

node* merge(node* la, node* lb)
{

  // either one is empty return other
  if(!la) 
    return lb;
  else if (!lb)
    return la;
    
    
  node *head;
  if(la->d < lb->d) {
    head = la;
    la = la->next;
  } else {
    head = lb;
    lb = lb->next;
  } 
  
  node *p = head;

  while(la && lb) {
    if(la->d < lb->d) {
      p->next = la;
      p = la; 
      la = la->next;
    } else {
      p->next = lb;
      p = lb; 
      lb = lb->next;
    }
  } 
  
  if(la)
    p->next = la;
  else
    p->next = lb;
    
  return head;
}

- geekz01 March 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take a new pointer say merged_pointer and point it to the lesser of the two start pointer , next keep on comparing the two linked list and keep on connecting the lesser to the merged_pointer. Whichever pointer was less that pointer will be moved to the next position. Keep on doing this until the end of one of the linked list is reached and then point the merged_pointer to the rest of the other linked list. This is very similar to the merge algorithm.

- praveenkcs28 March 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can either take a new link list and keep the merged in that one or we can change the pointer while merging. I think interviewer is expecting the result using changing the pointers.

- Tapas April 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct list{
int value;
struct listt *next;
}*temp,*p1,*p2,*final,*first_final;

struct list * merge(struct list *a,struct list *b)
{
if(a==NULL && b==NULL)
return NULL;
else if(a==NULL)
return b;
else if(b==NULL)
return a;
first_final=NULL;
if(a->value>b->value)
{
first_final=b;
b=b->next;
first_final->next=NULL;
temp=first_final;
}
else
{
first_final=a;
a=a->next;
first_final->next=NULL;
temp=first_final;
}
while(a!=NULL && b!=NULL)
{
//printf("Compared\n");
if(a->value>b->value)
{
temp->next=b;
temp=temp->next;
b=b->next;
temp->next=NULL;
}
else
{
temp->next=a;
temp=temp->next;
a=a->next;
temp->next=NULL;
}
}
if(a==NULL)
{
temp->next=b;
}
else if(b==NULL)
{
temp->next=a;
}
return first_final;
}

- Brijesh Patel August 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct list{
int value;
struct listt *next;
}*temp,*p1,*p2,*final,*first_final;

struct list * merge(struct list *a,struct list *b)
{
if(a==NULL && b==NULL)
return NULL;
else if(a==NULL)
return b;
else if(b==NULL)
return a;
first_final=NULL;
if(a->value>b->value)
{
first_final=b;
b=b->next;
first_final->next=NULL;
temp=first_final;
}
else
{
first_final=a;
a=a->next;
first_final->next=NULL;
temp=first_final;
}
while(a!=NULL && b!=NULL)
{
//printf("Compared\n");
if(a->value>b->value)
{
temp->next=b;
temp=temp->next;
b=b->next;
temp->next=NULL;
}
else
{
temp->next=a;
temp=temp->next;
a=a->next;
temp->next=NULL;
}
}
if(a==NULL)
{
temp->next=b;
}
else if(b==NULL)
{
temp->next=a;
}
return first_final;
}

- Brijesh Patel August 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

void merge(struct node *head1,struct node *head2)
{
     struct node *result=NULL;
     while(head1!=NULL && head2!=NULL)
     {
          if(head1->val < head2->val)
          {
             result = addnode(result,head1->val);
             head1=head1->next;
          }
          else
          {
             result = addnode(result,head2->val);
             head2=head2->next;
          }
     }
     if(head1==NULL)
     {
        while(head2!=NULL)
        {
           result = addnode(result,head2->val);
           head2=head2->next;
        }
     }
     else
     {
         while(head1!=NULL)
        {
           result = addnode(result,head1->val);
           head1=head1->next;
        }
     }
     printlist(result);
     printf("\n");
}

- Nitin March 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is similar to merge function of mergesort where we copy data into a new array while traversing both arrays. It is mentioned in the question not to copy data but to only manipulate the pointers.

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

sorry my bad...following code changes the pointers without copying the data

void merge(struct node *head1,struct node *head2)
{
     struct node *start=head1;
     struct node *prev=(struct node *) malloc(sizeof(struct node));
     prev=NULL;
     struct node *temp=(struct node *) malloc(sizeof(struct node));
     while(head1!=NULL && head2!=NULL)
     {
         if(head1->val>head2->val)
         {
            if(prev==NULL)
            {
               temp=head1;
               head1=head2;
               start=head1;
               head2=head2->next;
               head1->next=temp;
            }
            else
            {
                prev->next=head2;
                temp=head2->next;
                head2->next=head1;
                head2=temp;
                prev=prev->next;
            }
         }
         else
         {
             prev=head1;
             head1=head1->next;
         }
     }
     if(head1==NULL)
        prev->next=head2;
     printlist(start);
     printf("\n");
}

- Nitin March 10, 2014 | Flag


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