## Amazon Interview Question for SDE1s

Country: United States
Interview Type: In-Person

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

Merging two Linked List without using recursion.

``````public void sortList(){
// if list2 data is smaller than list1 exchange the current and buffer pointers
if(list2.data<list1.data)
{current = list2;
buffer = list1;
}

while(true){
if(buffer == null)
break;
if(current.data < buffer.data) {
current = current.next;
}
else {
newNode.next = current.next;
current.next = newNode;
current = current.next;
buffer = buffer.next;
}
if(current.next==null) {
current.next = buffer;
break;
}
}
}``````

Changes are made in current pointer which references to list1.

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

Superb code. Thanks a lot.

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

Shouldnt the newNode be inserted before current since current is greater?

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

Here it is:

``````public class MergeSortedLists {
static List<Integer> merge(List<Integer> list1, List<Integer> list2){
int k1=0;
int k2=0;
while(k1<list1.size()&&k2<list2.size()){
if(list1.get(k1)<list2.get(k2)){
} else {
}
}

while(k1<list1.size()){
}

while(k2<list2.size()){
}

return list;
}

public static void main(String[] args){

System.out.println(merge(list1,list2));

}

}``````

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

The get(int index) method of List is not efficient. It starts from the head or the tail to get the next element every time it is called, making it O(N^2). It is better to use an iterator.

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

``````public Node mergeLists(Node head1, Node head2) {
}
}

Node result;
} else {
}
return result;
}``````

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

package com.shashi;

import java.util.List;

public class MergeSortedList {

public static void main(String []args)
{

mergeLists(list1,list2);
}
public static void mergeLists(List<Integer>l1,List<Integer>l2)
{
if(l1.size()==0 && l2.size()==0)
{
System.out.print("Emppty lists were given");
}
if(l1.size()==0)
{
System.out.print(l2);
return;
}
if(l2.size()==0)
{
System.out.print(l1);
return;
}
//now actual algorithm starts!!!!!!!
int index1=0,index2=0;

for(;index1<l1.size() && index2<l2.size();)
{

if(l1.get(index1)<l2.get(index2))
{
if(index1==l1.size())
{
while(index2<l2.size())
{
}

break;
}

}
else
{
if(index2==l2.size())
{
while(index1<l1.size())
{
}
break;
}

}
}

//print merged data
System.out.print(fill);

}

}

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

// Merged likedlist A & B into C

while A not empty or B not empty:
{
if A empty
remove first element from B and assign to variable
end if

else if B empty
remove first element from A and assign to variable
end else if

else if first element of A < first element of B:
remove first element from A and assign to variable
end else if

else
remove first element from B and assign to variable

insert element into C
}

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

node* merge1(node* root, node* root1)
{
node *start, *end,*i,*j,*prev1,*prev2;
i=root;
j=root1;

if(i->data > j->data)
{
while(j!=NULL && j->data < i->data)
{
prev2=j;
j=j->next;
}
prev2->next=i;
root=root1;
root1=j;

}

while(i!=NULL && j!=NULL)
{
if(i->data<j->data)
{
while( i!=NULL && j!=NULL && i->data < j->data)
{
prev1=i;
i=i->next;

}
while( i!=NULL && j!=NULL && i->data > j->data)
{
prev2=j;
j=j->next;
}
prev1->next=root1;
prev2->next=i;
root1=j;

}

}
return root;

}

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

Uses recursion and iterators, hence avoids calling get(int index) method which is inefficient.

``````public static List<Integer> merge(List<Integer> listA, List<Integer> listB)
{
if (listA == null) return listB;
if (listB == null) return listA;

final ListIterator<Integer> iterA = listA.listIterator(0);
final ListIterator<Integer> iterB = listB.listIterator(0);

final List<Integer> result = new LinkedList<Integer>();

merge(iterA, iterB, result);
return result;
}

private static void merge(ListIterator<Integer> iterA,
ListIterator<Integer> iterB,
List<Integer>  result)
{
if (!iterA.hasNext())
{
return;
}

if (!iterB.hasNext())
{
return;
}

Integer a = iterA.next();
Integer b = iterB.next();

if (a < b)
{
b = iterB.previous(); // rewind
}
else if (b < a)
{
a = iterA.previous(); // rewind
}
else
{
}

merge(iterA, iterB, result);
}``````

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

``````def mergeSortedListsIteratively(l1head, l2head):
# initializing walkers
# merging lists
# append other, and place rest of new in other
tmp = newListWalk.next
newListWalk = newListWalk.next
else:                   # no other list

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

``````def mergeSortedListsIterativelySimpler(l1head, l2head):

# initializing walkers

# merging lists
# append other, and place rest of new in other
tmp = newListWalk.next
newListWalk = newListWalk.next

# appending end of other if reached end of newList

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

``````// -----------------------------------------------------------------------------
// Declare a NODE structure
// -----------------------------------------------------------------------------
typedef struct Node {
Node* next;
int data;
} NODE;

// -----------------------------------------------------------------------------
// Add a new node at the end of the list
// NOTE: Remember the special cases (the list is empty or has only one node)
// -----------------------------------------------------------------------------
NODE* newNode = createNewNode(value);

// SPECIAL CASE: The list is empty.
}
// NORMAL CASE
else {
// In this normal case, we'll traverse till the end of the list
// and then add the new node there. The head pointer is still the same
// because we only change the tail of the list.
// Go until we reach the end of the list
while (currentNode->next != NULL) {
currentNode = currentNode->next;
}
// Add the new node to the end of the list
currentNode->next = newNode;
}
}

// -----------------------------------------------------------------------------
// Merge 2 shorted linked lists
// -----------------------------------------------------------------------------
// Iterate each item of the two lists
// until we reach to the end of at least 1 lists
// If the current value of list1 is smaller than the current value of list2
// --> add the value of list 1 to the new list
// move to the next node in list 1, list 2 stays still
}
// same logic here
// if the current value of list2 is smaller than the current value of list1
// --> add the value of list 2 to the new list
// move to the next node in list 2, list 1 stays still
}
}

// If we reach this part of code, at least one of the list is now empty,
// all we need to do is to add the rest of the list that is still not empty
// to the new list
}
}

}``````

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

Iterative solution:

``````class ListNode {
public:

ListNode(int _data) : data(_data), next(nullptr) { };
ListNode* next;
int data;
};

ListNode* merge_ll(ListNode* a, ListNode* b)
{
if (nullptr == a) return b;
if (nullptr == b) return a;
auto d = (a->data < b->data) ? a : b;
auto s = (a == d) ? b : a;
ListNode* pd = nullptr;
while (nullptr != s && nullptr != d)
{
if (d->data < s->data)
{
pd = d;
d = d->next;
}
else
{
pd->next = s;
s = s->next;
pd->next->next = d;
pd = pd->next;
}
}
if (nullptr == d)
{
pd->next = s;
}
return (a->data < b->data) ? a : b;
}``````

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

This is easily done through MergeSort algorithm

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

mergesort is O(n log n).
Ognian.Kabranov solution is O(n).

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

How do you merge-sort a linked list?

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.