Amazon Interview Question Software Engineer Interns
Country: United States
Interview Type: Phone Interview
Node mergeList(Node a, Node b) {
Node currA, currB, currC, cHead;
currA = a;
currB = b;
cHead = null;
//add first- address edge cases
if (a == null && b == null) {
return null;
}
if (a == null && b != null) {
return b;
}
if (a != null && b == null) {
return a;
}
if (currA.value <= currB.value) {
cHead = currC = currA;
currA = currA.next;
}
else {
cHead = currC = currB;
currB = currB.next;
}
while (true) {
if (currA == null) {
while (currB != null) {
currC.next = currB;
currB = currB.next;
currC = currC.next;
}
break;
}
if (currB == null) {
while (currA != null) {
currC.next = currA;
currA = currA.next;
currC = currC.next;
}
break;
}
if (currA.value <= currB.value) {
currC.next = currA;
currA = currA.next;
currC = currC.next;
}
else {
currC.next = currB;
currB = currB.next;
currC = currC.next;
}
}
return cHead;
}
public static Node<Integer> merge(Node<Integer> n1 , Node<Integer> n2) {
Node<Integer> head = new Node<Integer>();
Node<Integer> node = head;
if(n1==null && n2==null) return null;
if(n1==null && n2!=null) return n2;
if(n1!=null && n2==null) return n1;
while(n1!=null && n2!=null) {
if(n1.get() <=n2.get()) {
Node tmpNode = new Node(n1.get());
node.setNext(tmpNode);
node = tmpNode;
System.out.println(n1.get());
n1 = n1.getNext();
} else {
Node tmpNode = new Node(n2.get());
node.setNext(tmpNode);
node = tmpNode;
System.out.println(n2.get());
n2 = n2.getNext();
}
}
while(n1!=null) {
node.set(n1.get());
System.out.println(n1.get());
n1 = n1.getNext();
}
while(n2!=null) {
Node tmpNode = new Node(n2.get());
node.setNext(tmpNode);
node = tmpNode;
System.out.println(n2.get());
n2 = n2.getNext();
}
return head.getNext();
}
public static Node<Integer> merge(Node<Integer> n1 , Node<Integer> n2) {
Node<Integer> head = new Node<Integer>();
Node<Integer> node = head;
if(n1==null && n2==null) return null;
if(n1==null && n2!=null) return n2;
if(n1!=null && n2==null) return n1;
while(n1!=null && n2!=null) {
if(n1.get() <=n2.get()) {
Node tmpNode = new Node(n1.get());
node.setNext(tmpNode);
node = tmpNode;
System.out.println(n1.get());
n1 = n1.getNext();
} else {
Node tmpNode = new Node(n2.get());
node.setNext(tmpNode);
node = tmpNode;
System.out.println(n2.get());
n2 = n2.getNext();
}
}
while(n1!=null) {
node.set(n1.get());
System.out.println(n1.get());
n1 = n1.getNext();
}
while(n2!=null) {
Node tmpNode = new Node(n2.get());
node.setNext(tmpNode);
node = tmpNode;
System.out.println(n2.get());
n2 = n2.getNext();
}
return head.getNext();
}
public static Node<Integer> merge(Node<Integer> n1 , Node<Integer> n2) {
Node<Integer> head = new Node<Integer>();
Node<Integer> node = head;
if(n1==null && n2==null) return null;
if(n1==null && n2!=null) return n2;
if(n1!=null && n2==null) return n1;
while(n1!=null && n2!=null) {
if(n1.get() <=n2.get()) {
Node tmpNode = new Node(n1.get());
node.setNext(tmpNode);
node = tmpNode;
System.out.println(n1.get());
n1 = n1.getNext();
} else {
Node tmpNode = new Node(n2.get());
node.setNext(tmpNode);
node = tmpNode;
System.out.println(n2.get());
n2 = n2.getNext();
}
}
while(n1!=null) {
node.set(n1.get());
System.out.println(n1.get());
n1 = n1.getNext();
}
while(n2!=null) {
Node tmpNode = new Node(n2.get());
node.setNext(tmpNode);
node = tmpNode;
System.out.println(n2.get());
n2 = n2.getNext();
}
return head.getNext();
}
Seems simple enough I'm assuming #1 That the head is a dummy object #2 That I can modify the objects.
public static Node MergeSortedList(Node head1, Node head2)
{
Node current1 = head1;
Node current2 = head2;
if(current1 != null)
{
current1 = current1.Next;
}
if(current2 !=null)
{
current2 = current2.Next;
}
Node head = new Node();
Node current = head;
while(current != null)
{
if(current1 == null)
{
// This means we are done with list 1
current.Next = current2;
break;
}
else if(current2 == null)
{
// This means we are done with list 2
current.Next = current1;
break;
}
else if(current1.Data < current2.Next)
{
current.Next = current1;
current1 = current1.Next;
}
else
{
current.Next = current2;
current2 = current2.Next;
}
current = current.Next;
}
return head;
}
3┃ typedef struct __node {
4┃ int data;
5┃ struct __node *next;
6┃ } node_t;
7┃
8┃ node_t* merge(node_t *a, node_t *b) {
9┃
10┃ node_t *head, *cur, *prev, *other;
11┃
12┃ head = a->data < b->data ? a : b;
13┃ other = a->data >= b->data ? a : b;
14┃
15┃ cur = head->next;
16┃ prev = head;
17┃
18┃ while (cur != NULL) {
19┃ if (cur->data < other->data) {
20┃ goto forward;
21┃ }
22┃
23┃ /* Swap cur with other */
24┃ node_t *tmp = cur;
25┃ cur = other;
26┃ other = tmp;
27┃
28┃ prev->next = cur;
29┃
30┃ forward:
31┃ prev = cur;
32┃ cur = cur->next;
33┃
34┃ }
35┃
36┃ prev->next = other;
37┃
38┃ return head;
39┃ }
3┃ typedef struct __node {
4┃ int data;
5┃ struct __node *next;
6┃ } node_t;
7┃
8┃ node_t* merge(node_t *a, node_t *b) {
9┃
10┃ node_t *head, *cur, *prev, *other;
11┃
12┃ head = a->data < b->data ? a : b;
13┃ other = a->data >= b->data ? a : b;
14┃
15┃ cur = head->next;
16┃ prev = head;
17┃
18┃ while (cur != NULL) {
19┃ if (cur->data < other->data) {
20┃ goto forward;
21┃ }
22┃
23┃ /* Swap cur with other */
24┃ node_t *tmp = cur;
25┃ cur = other;
26┃ other = tmp;
27┃
28┃ prev->next = cur;
29┃
30┃ forward:
31┃ prev = cur;
32┃ cur = cur->next;
33┃
34┃ }
35┃
36┃ prev->next = other;
37┃
38┃ return head;
39┃ }
I think to reduce space and time complexity below might help...
I have taken normal approch but in a different way .......
public List merge(List<Integer> l, List<Integer> m){
int j = l.size()-1;
int secondSize = m.size()-1;
while(j>=0 && secondSize>=0){
if(l.get(j)>m.get(secondSize))
{
l.add(j, m.get(secondSize));
j--;
}
else
l.add(j+1,m.get(secondSize));
secondSize--;
}
return l;
}
I have taken normal approch but in a different way .......
public List merge(List<Integer> l, List<Integer> m){
int j = l.size()-1;
int secondSize = m.size()-1;
while(j>=0 && secondSize>=0){
if(l.get(j)>m.get(secondSize))
{
l.add(j, m.get(secondSize));
j--;
}
else
l.add(j+1,m.get(secondSize));
secondSize--;
}
return l;
}
public void Merge(StateLinkedList states)
{
if (states == null || !states.States.Any())
return;
if (States == null || !States.Any() && states.States != null && states.States.Any())
States = states.States;
for (var state = States.First; state != null; state = state.Next)
for (var st = states.States.First; st != null; )
{
if (state.Value.CompareTo(st.Value) > 0)
{
LinkedListNode<State> old = st;
st = st.Next;
states.States.Remove(old);
States.AddBefore(state, old);
} else
st = st.Next;
}
}
public class HelloWorld {
public static void main(String[] args) {
Integer[] a1= new Integer[] { 10, 20, 23 };
LinkedList<Integer> l1 = new LinkedList<Integer>( Arrays.asList(a1) );
Integer[] a2= new Integer[] { 8, 15, 24 };
LinkedList<Integer> l2 = new LinkedList<Integer>( Arrays.asList(a2) );
System.out.println("RES:" + merge(l1,l2).toString());
}
public static LinkedList<Integer> merge(LinkedList<Integer> l1, LinkedList<Integer> l2){
LinkedList<Integer> m = new LinkedList<Integer>();
while(l1.size()>0 && l2.size()>0)
if(l2.getFirst()>l1.getFirst()){
m.add(l1.getFirst());
l1.removeFirst();
}else{
m.add(l2.getFirst());
l2.removeFirst();
}
if(l1.size()>0)
m.addAll(l1);
if(l2.size()>0)
m.addAll(l2);
return m;
}
}
public class HelloWorld {
public static void main(String[] args) {
Integer[] a1= new Integer[] { 10, 20, 23 };
LinkedList<Integer> l1 = new LinkedList<Integer>( Arrays.asList(a1) );
Integer[] a2= new Integer[] { 8, 15, 24 };
LinkedList<Integer> l2 = new LinkedList<Integer>( Arrays.asList(a2) );
System.out.println("RES:" + merge(l1,l2).toString());
}
public static LinkedList<Integer> merge(LinkedList<Integer> l1, LinkedList<Integer> l2){
LinkedList<Integer> m = new LinkedList<Integer>();
while(l1.size()>0 && l2.size()>0)
if(l2.getFirst()>l1.getFirst()){
m.add(l1.getFirst());
l1.removeFirst();
}else{
m.add(l2.getFirst());
l2.removeFirst();
}
if(l1.size()>0)
m.addAll(l1);
if(l2.size()>0)
m.addAll(l2);
return m;
}
}
Following is a simple merge routine as in mergerSort
import java.util.*;
public class mergeArrayList{
public static void main(String[] args){
List<Integer> l1 = new ArrayList<Integer>();
List<Integer> l2 = new ArrayList<Integer>();
l1.add(3);
l1.add(5);
l1.add(9);
l1.add(11);
l2.add(1);
l2.add(2);
l2.add(6);
l2.add(8);
l2.add(12);
List<Integer> result = mergeList(l1,l2);
for(Integer x : result){
System.out.print(x+" ");
}
}
public static List<Integer> mergeList(List<Integer> l1, List<Integer> l2){
if(l1 == null || l2 == null || l1.size() == 0 || l2.size() == 0)
return null;
List<Integer> l3 = new ArrayList<Integer>();
int n = l1.size();
int m = l2.size();
int i = 0;
int j = 0;
while( i<n && j < m){
int t1 = l1.get(i);
int t2 = l2.get(j);
if(t1 < t2){
l3.add(t1);
i++;
}else{
l3.add(t2);
j++;
}
}
if(i == n){
for(; j < m; j++){
l3.add(l2.get(j));
}
}else{
for(; i< n; i++){
l3.add(l1.get(i));
}
}
return l3;
}
}
Just use same approach as mergesort merge phase:
- guilhebl March 28, 2015public class Solution { public static void main(String[] args) { List<Integer> list1 = new ArrayList<Integer>(); list1.add(3); list1.add(5); list1.add(9); list1.add(11); List<Integer> list2 = new ArrayList<Integer>(); list2.add(1); list2.add(2); list2.add(6); list2.add(8); list2.add(12); List<Integer> result = mergeList(list1, list2); for (Integer integer : result) { System.out.print(integer + " "); } } public static List<Integer> mergeList(List<Integer> list1, List<Integer> list2) { if (list1 == null || list2 == null || list1.size() == 0 || list2.size() == 0) { return null; } List<Integer> result = new ArrayList<Integer>(); int n = list1.size(); int m = list2.size(); int i = 0, j = 0, elem1 = 0, elem2 = 0; while (i < n && j < m) { elem1 = list1.get(i); elem2 = list2.get(j); if (elem1 < elem2) { result.add(elem1); i++; } else { result.add(elem2); j++; } } // add remaining of i while (i < n) { elem1 = list1.get(i); result.add(elem1); i++; } // add remaining of j while (j < m) { elem2 = list2.get(j); result.add(elem2); j++; } return result; } }