Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Couple of code-review comments -
1, You can do away with the check
if(a == null && b == null)
since one of the other two checks implicitly does what you want there.
2, While appending the surplus elements in either of the remaining lists (outside the comparison while loop -
while(a != null)
or
while(b != null)
, you don't need to walk the entire remainder of the list, as it can just be done in one shot. i.e., by replacing the while-construct by if-construt.
while at least one of the lists has some elements, check if one of the lists is empty; is one list is empty add elements from the other list. Each time you add an element to the merged list remove it from the input list (by updating the head node to head.next). If both lists have elements check which element is smaller, and remove it from the head of the list by pointing the head of that list to the head.next element, and add it to the tail of the merged list (current.next. O(n) time complexity, space complexity I think it's O(1) as we don't need to create a new structure to hold the merged list, we just need to update the pointer to the next node in the input lists. Pros of this approach: O(1) space complexity as we don't have to create a new structure, cons: we are destroying the input lists; if we need to mantain the input lists as they are we should make a copy of them before start updating the links to the next nodes.
class ListNode {
int value;
ListNode next;
public ListNode(int value) {
this.value=value;
}
}
public class SortedListMerger {
public static ListNode merge(ListNode l1, ListNode l2) {
if(l1==null && l2==null) {
System.out.println("Null Lists");
return null;
}
else if(l1==null) {
return l2;
}
else if(l2==null) {
return l1;
}
ListNode head;
ListNode current;
if(l1.value<=l2.value) {
head = l1;
l1=l1.next;
}
else {
head = l2;
l2=l2.next;
}
current = head;
while(l1!=null || l2!=null) {
if(l1==null) {
current.next=l2;
l2=l2.next;
}
else if(l2==null) {
current.next=l1;
l1=l1.next;
}
else {
if(l1.value<=l2.value) {
current.next=l1;
l1=l1.next;
}
else {
current.next=l2;
l2=l2.next;
}
}
current=current.next;
}
return head;
}
public static void printList(ListNode l) {
ListNode nextNode=l;
while(nextNode!=null) {
System.out.print(nextNode.value);
if(nextNode.next!=null) System.out.print(" -> ");
nextNode=nextNode.next;
}
System.out.println();
}
public static void main(String[] args) {
ListNode l1 = new ListNode(2);
ListNode l2 = new ListNode(19);
ListNode l3 = new ListNode(33);
ListNode l4 = new ListNode(221);
l1.next=l2;
l2.next=l3;
l3.next=l4;
ListNode ll1 = new ListNode(1);
ListNode ll2 = new ListNode(7);
ListNode ll3 = new ListNode(33);
ListNode ll4 = new ListNode(61);
ListNode ll5 = new ListNode(66);
ll1.next=ll2;
ll2.next=ll3;
ll3.next=ll4;
ll4.next=ll5;
printList(l1);
printList(ll1);
printList(merge(l1,ll1));
}
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
static LinkedList<Integer> mergeSortedList(LinkedList<Integer> A,LinkedList<Integer> B)
{
if( A == null) return B;
if( B == null) return A;
//int length = (A.size() >= B.size()? A.size(): B.size());
int aListSize = A.size();
int i=0,j=0;
//2-3-5-7-8
//4->5->7->9 //6->10->11->15
while(true)
{
if(A.get(i) > B.get(j))
{
//System.out.println("----- "+B.get(j));
A.add(i,B.get(j));
j++;
//i++;
}
else
{
//A.add(j-1,B.get(i));
i++;
}
//System.out.println("----- i "+i + " size "+A.size());
if( (aListSize + B.size()) == A.size()) break;
}
//System.out.println("----- i "+i + " size "+A.size() + " j "+j);
while(true)
{
if(j == B.size()) break;
//System.out.println("----- j "+j + " i "+i);
A.add(i++,B.get(j));
j++;
}
return A;
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
LinkedList<Integer> A = new LinkedList<Integer>();
// A.add(7);
// A.add(9);
A.add(2);
A.add(19);
A.add(33);
A.add(221);
//A.add(19);
LinkedList<Integer> B = new LinkedList<Integer>();
B.add(1);
B.add(7);
B.add(33);
B.add(61);
B.add(66);
LinkedList<Integer> merged = mergeSortedList(A,B);
ListIterator<Integer> it = merged.listIterator(0);
while(it.hasNext())
{
System.out.println("----- "+it.next());
}
}
}
It can be done with recursion, but it introduces some overhead. To write mergesort on unsorted lists you will probably need to use recursion.
Solution in Scala - easily transferable to Java
case class Node(x: Int, var next: Node)
def merge(a: Node, b: Node): Node = {
if (a == null) b
else if (b == null) a
else {
if (a.x < b.x) {
a.next = merge(a.next, b)
a
}
else {
b.next = merge(a, b.next)
b
}
}
}
val a = Node(1, Node(3, Node(5, null) ))
val b = Node(2, Node(6, null) )
merge(a, b)
O(n+m) where n is length of list 1 and m is length of list 2.
static class Node{
Node next;
Int value;
}
public static Node mergeSort(Node list1, Node list2){
//add fake root to list
Node result = new Node();
while(list1 != null && list2 != null){
if(list1.value < list2.value){
result.next = list1;
list1 = list1.next;
}
else{
result.next = list2;
list2 = list2.next;
}
}
if(list1 != null){
result.next = list1;
}
else if(list2 != null){
result.next = list2;
}
//remove the fake root
result = result.next;
return result;
}
I think while dealing with linked lists the 'next' should be of pointer type. In this version, just have a temporary pointer and a dummy node and splice the data.
#include <stdio.h>
#include <stdlib.h>
typedef struct _node
{
int data;
struct _node *next;
}Node;
Node* newnode(int value)
{
Node *n = (Node*)malloc(sizeof(Node));
if(n == NULL)
return NULL;
n->data = value;
n->next = NULL;
return n;
}
void printSL(Node* node)
{
while(node != NULL)
{
printf("%d ", node->data);
node= node->next;
}
printf("\n");
}
Node* mergeSL(Node *f, Node *s)
{
Node dummy, *tail;
dummy.next = NULL;
tail= &dummy;
while(1)
{
if(f == NULL){
tail->next = s;
break;
}
if(s == NULL){
tail->next = f;
break;
}
if(f->data <= s->data)
{
tail->next = f;
f = f->next;
}
else
{
tail->next=s;
s = s->next;
}
tail=tail->next;
}
return dummy.next;
}
int main()
{
Node *first = newnode(0);
Node *temp = first;
for(int i=1; i<10; i++)
{
temp = temp->next = newnode(i*2);
}
Node *second = newnode(1);
temp = second;
for(int i=1; i<15; i++)
{
temp = temp->next = newnode(i*2 + 1);
}
printSL(first);
printSL(second);
printSL(mergeSL(first, second));
}
Hi
Could you please be clear on the problem. You have two sorted LL and you want a resultant LL in sorted fashion ? or both your linked list are not sorted and you want a single sorted LL as a result ??
O(n) time and O(1) space.
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int val;
struct node *next;
} node_t;
typedef struct linked_list {
node_t *head;
size_t size;
} ll_t;
ll_t * linked_list_new()
{
ll_t *ll = (ll_t *)(malloc(sizeof(ll_t)));
ll->head = NULL;
ll->size = 0;
return ll;
}
node_t * linked_list_insert(ll_t *ll, int val)
{
node_t *node;
if (!ll)
return NULL;
if (ll->head) {
node_t *end = ll->head;
while (end->next)
end = end->next;
node = (node_t *)(malloc(sizeof(node_t)));
node->val = val;
node->next = NULL;
end->next = node;
} else {
node = (node_t *)(malloc(sizeof(node_t)));
node->val = val;
node->next = NULL;
ll->head = node;
}
ll->size++;
return node;
}
#define _LINKED_LIST_MERGE_NODE(_ll, _prev, _n) \
do { \
if (_prev) \
_prev->next = _n; \
else \
_ll->head = _n; \
\
_ll->size++; \
_prev = _n; \
_n = _n->next; \
} while(0);
/* merge into first list */
void linked_list_merge(ll_t *ll1, ll_t *ll2)
{
node_t *prev = NULL;
node_t *n1, *n2;
n1 = ll1->head;
n2 = ll2->head;
while (n1 && n2) {
if (n1->val >= n2->val) {
_LINKED_LIST_MERGE_NODE(ll1, prev, n2);
} else {
if (prev)
prev->next = n1;
prev = n1;
n1 = n1->next;
}
};
while (n2) {
_LINKED_LIST_MERGE_NODE(ll1, prev, n2);
}
}
int main(int argc, char *argv[])
{
ll_t *l1, *l2;
l1 = linked_list_new();
l2 = linked_list_new();
linked_list_insert(l1, 0);
linked_list_insert(l1, 1);
linked_list_insert(l1, 3);
linked_list_insert(l1, 5);
linked_list_insert(l1, 7);
linked_list_insert(l1, 7);
linked_list_insert(l1, 9);
linked_list_insert(l1, 11);
linked_list_insert(l1, 13);
linked_list_insert(l1, 15);
linked_list_insert(l1, 17);
linked_list_insert(l2, 0);
linked_list_insert(l2, 2);
linked_list_insert(l2, 4);
linked_list_insert(l2, 6);
linked_list_insert(l2, 7);
linked_list_insert(l2, 8);
linked_list_insert(l2, 10);
linked_list_insert(l2, 12);
linked_list_insert(l2, 14);
linked_list_insert(l2, 16);
linked_list_merge(l1, l2);
node_t *node = l1->head;
printf("size: %u\n", l1->size);
while (node) {
printf("%d ", node->val);
node = node->next;
}
printf("\n");
return 0;
}
C++ implementation with O(n)
#include <stdio.h>
#include <vector>
using namespace std;
struct Node {
int value;
Node *next;
};
Node *MergeLinkedLists(Node *n1, Node *n2) {
Node *head = nullptr;
Node *prev = nullptr;
while (n1 || n2) {
Node *next = nullptr;
if (!n1 ||
(n1 && n2 && n2->value < n1->value)) {
next = n2;
n2 = n2->next;
} else {
next = n1;
n1 = n1->next;
}
if (!head)
head = next;
else
prev->next = next;
prev = next;
}
return head;
}
// Test Code
Node *MakeLinkedList(const vector<int> &v) {
Node *prev = nullptr;
Node *head = nullptr;
for (auto &e : v) {
Node *n = new Node{e, nullptr};
if (!head)
head = n;
else
prev->next = n;
prev = n;
}
return head;
}
void Print(Node *n) {
while (n) {
printf("%d\n", n->value);
n = n->next;
}
}
int main() {
Node *l1 = MakeLinkedList({1, 3, 4, 8});
Node *l2 = MakeLinkedList({2, 3, 9});
Node *l_merged = MergeLinkedLists(l1, l2);
Print(l_merged);
}
Here's what I could come with... what do you guys think?
- amostech December 20, 2014public class Node { public int data; public Node next; public Node(int data) { this.data = data; } /*getter & setter*/ } public Node merge(Node a, Node b) { if(a == null && b == null) return null; if(a == null && b != null) return b; if(a != null && b == null) return a; Node mergedHead = null; //N = size(a) + size(b) if(a.data < b.data) { mergedHead = a; a = a.next; } else { mergedHead = b; b = b.next; } Node cur = mergedHead; while(a != null && b != null) { if(a.data < b.data) { cur.next = a; a = a.next; } else { cur.next = b; b = b.next; } cur = cur.next; } while(a != null) { cur.next = a; cur = cur.next; a = a.next; } while(b != null) { cur.next = b; cur = cur.next; b = b.next; } return mergedHead; }