Amazon Interview Question Software Engineer / Developers
I don't think you can do it in O(n*log(K)). There are N sorted lists where each list has K elements. Just to traverse the list, you have to go through
(N * K) elements. (N*K) > (N * Log(K)). I think the best you can do is O (N*K log(K).
Here is the discussion.
https://www2.blogger.com/comment.g?blogID=6957414&postID=109840061746437225
Assuming that size of each array is 'n' & there are 'k' such sorted arrays.
We are using a Min-Heap here.
Solution:
We assume that the lists are sorted in ascending order.
Insert all k elements at position 1 from each list into a heap. Use EXTRACT-MIN to obtain the smallest element (say x) of the heap.
Say then x came from list i, then take the next element from list i and insert it
into the heap. Continuing in this fashion yields the merged list. Clearly the running time is O(n log k)
It's an exercise problem straight from Cormen et al's 'Introduction to Algorithms' at the end of the chapter of Heapsort.
* In 3rd edition, it's Exercise 6.5-9
* In 2nd edition, it's Exercise 6.5-8
The problem asks an O(n log k)-time algorithm to merge k sorted lists into one sorted list where n is the total number of elements in all the input lists.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Set;
public class MergeArrays {
private static final int N = 7;
private static HashMap<Integer, ArrayList<Integer>> arrayMap = new HashMap<Integer, ArrayList<Integer>>();
private static int TOTAL = 0;
public static void main(String[] args) {
createArrays();
System.out.println("Number of arrays: " + N);
printArrays();
ArrayList<Integer> mergedList = mergeArrays();
System.out.println("Final merged lists data: ");
printMergedList(mergedList);
System.out.println();
}
public static void printMergedList(ArrayList<Integer> mergedList) {
if (mergedList == null || mergedList.size() < 1) {
System.out.println("Merged List is EMPTY!");
}
Iterator<Integer> iter = mergedList.iterator();
while (iter.hasNext()) {
System.out.print(iter.next() + " ");
}
System.out.println();
}
public static ArrayList<Integer> mergeArrays() {
ArrayList<Integer> mergedList = new ArrayList<Integer>();
Set<Integer> keySet = arrayMap.keySet();
Comparator<Node> comparator = new NumericComparator();
PriorityQueue<Node> minHeap = new PriorityQueue<Node>(TOTAL, comparator);
Iterator<Integer> iter = keySet.iterator();
while (iter.hasNext()) {
int key = iter.next();
ArrayList<Integer> list = arrayMap.get(key);
if (list != null) {
Integer data = list.remove(0);
Node node = new Node(data, key);
minHeap.add(node);
}
}
while (minHeap.size() > 0) {
Node node = minHeap.remove();
//System.out.print(node.data + " ");
mergedList.add(node.data);
int id = node.id;
ArrayList<Integer> list = arrayMap.get(id);
if (list != null && list.size() > 0) {
Integer data = list.remove(0);
Node newNode = new Node(data, id);
minHeap.add(newNode);
}
}
return mergedList;
}
public static void createArrays() {
Random rand = new Random();
for (int i=0; i<N; i++) {
int size = rand.nextInt(5) + 5;
TOTAL += size;
ArrayList<Integer> numList = new ArrayList();
for (int j=0; j<size; j++) {
int value = rand.nextInt(1000) + 1;
numList.add(value);
}
Collections.sort(numList);
arrayMap.put(i+1, numList);
}
}
public static void printArrays() {
Iterator it = arrayMap.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Integer, ArrayList<Integer>> pair = (Map.Entry<Integer, ArrayList<Integer>>)it.next();
ArrayList<Integer> list = pair.getValue();
Iterator liter = list.iterator();
while (liter.hasNext()) {
System.out.print(liter.next() + " ");
}
System.out.println();
}
}
}
class Node {
int data;
int id;
Node(int data, int id) {
this.data = data;
this.id = id;
}
}
class NumericComparator implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
if (o1.data < o2.data) {
return -1;
} else if (o1.data > o2.data) {
return 1;
}
return 0;
}
}
I failed the interview but later realized that this was the question straight from Cormen's book. Basically the solution involves usage of heap. I found the solution on the internet though can't remember the site address currently.
It is possible to do this in O(n*logK). If you use the medians, you can decide whether an element is to the left or right of the median.
This is a linked list. You don't have random access memory. To find the median, you need to traverse the linked list which is N.
To claim that you can sort a N sorted lists where each list has K elements in Nlog(K) is similar to claiming that you can sort two linked lists in N Log(2).
Linked list 1: 1 5 9
Linked List 2: 3 4 8
I do not think it can be done with the above linked lists.
L1:456 L2:123 ... LN
1.
1<5? Yes
1<4? Yes
L1: 1456
L2:23
2.
2 between 4&5? No
2 < 4? Yes
L1:12456
L2: 3
3.
3<4? Yes
3 b/w 1&2? No
3<1? No
3>2? Yes
L1:123456.
L2:
4. There are N-1 lists remaining. Do L2 with L3, and so on up to N.
To merge k sort array in one sorted array.
Suppose we have k sorted arrays. We have to merge this k sorted arays.
int a[]={1,4,7};
int b[]={2,5,6};
int c[]={0,3,8};
int d[]={9,10,11};
First we will store this k sorted arrays into one big array temp.
int temp[];
Second; we will again sort this temp array just like we sort the individual array in k sorted array.
Hope this solution will work.
I guess it should be O(n*k*log(n))
at the first iteration, we combine every two lists into one, thus we need O(n*k) to reduce n lists to n/2 lists,
at the second iteration, we again need O(n*k) to reduce n/2 lists to n/4 lists.
There are total log(n) such interation, so we have O(n*k*log(n))
Merge every two sorted lists into one list. Each merge takes O(k).
repeat above operation.
It will take logn/log2 times to get a sigle sorted list. Therefore we get O(k*log(n))
Guys, do not waste your time figuring out how you can do O(nlogk). It is just impossible unless you use some linear-time sorting methods...let's make k=1...You will see why
You can merge starting from 2 lists and then continue. Since there are k lists logk merges are required each merge taking O(n) time. So run time complexity of algorithm is (Onlogk)
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if(lists.size() == 0) return null;
Queue<ListNode> q = new LinkedList<ListNode>();
for(ListNode n : lists){
q.add(n);
}
while(q.size() != 1){
ListNode l1 = q.remove();
ListNode l2 = q.remove();
q.add(merge(l1, l2));
}
return q.remove();
}
public ListNode merge(ListNode l1, ListNode l2) {
if (l1 == null)
return l2;
if (l2 == null)
return l1;
ListNode head = null;
if (l1.val < l2.val) {
head = l1;
l1 = l1.next;
} else {
head = l2;
l2 = l2.next;
}
head.next = merge(l1, l2);
return head;
}
}
import java.util.ArrayList;
import java.util.List;
public class MergeLists {
public static class Node implements Comparable<Node> {
int data;
Node next;
Node(int data){
this.data = data;
}
@Override
public int compareTo(Node o) {
if (this.data == o.data) {
return 0;
} else if (this.data < o.data) {
return -1;
}
return 1;
}
}
private Node resultList;
private MinHeap<Node> minHeap;
public MergeLists(List<Node> lists) {
this.minHeap = new MinHeap<Node>(lists.size(), lists);
this.minHeap.buildHeap();
}
public void merge() {
Node tail = null;
while (!minHeap.isEmpty()) {
Node node = minHeap.deleteMin();
if (resultList == null) {
resultList = node;
tail = node;
} else {
tail.next = node;
tail = node;
}
if (node.next != null) {
minHeap.insert(node.next);
}
node.next = null;
}
}
public static void main(String[] args) {
List<Node> list = new ArrayList<MergeLists.Node>();
Node n1 = new Node(1);
n1.next = new Node(2);
n1.next.next = new Node(3);
n1.next.next.next = new Node(5);
n1.next.next.next.next = new Node(7);
list.add(n1);
Node n2 = new Node(4);
n2.next = new Node(6);
n2.next.next = new Node(8);
n2.next.next.next = new Node(10);
list.add(n2);
Node n3 = new Node(9);
n3.next = new Node(11);
n3.next.next = new Node(12);
n3.next.next.next = new Node(13);
list.add(n3);
Node n4 = new Node(-4);
n4.next = new Node(-2);
n4.next.next = new Node(-1);
n4.next.next.next = new Node(14);
list.add(n4);
Node n5 = new Node(-3);
list.add(n5);
MergeLists ml = new MergeLists(list);
ml.merge();
ml.printList();
}
private void printList() {
Node temp = resultList;
while(temp != null) {
System.out.print(temp.data + ", ");
temp = temp.next;
}
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class MinHeap<E extends Comparable<E>> {
private List<E> elements;
private int k;
public MinHeap(int k, List<E> elements) {
this.k = k;
this.elements = elements;
}
public boolean isEmpty() {
return k <= 0;
}
public void buildHeap() {
for (int i = k / 2 - 1; i >= 0; i--) {
heapify(i);
}
}
public void heapify(int root) {
int left = leftChild(root);
int right = rightChild(root);
int min = root;
if (k > left && elements.get(root).compareTo(elements.get(left)) > 0) {
min = left;
}
if (k > right && elements.get(min).compareTo(elements.get(right)) > 0) {
min = right;
}
if (min != root) {
swap(min, root);
heapify(min);
}
}
public void insert(E e) {
elements.add(k++, e);
int parent = parent(k - 1);
int i = k - 1;
while (parent >= 0
&& elements.get(parent).compareTo(elements.get(i)) > 0) {
swap(parent, i);
i = parent;
parent = parent(i);
}
}
public E deleteMin() {
swap(0, k - 1);
k--;
heapify(0);
E e = elements.get(k);
elements.remove(k);
return e;
}
private void swap(int i, int j) {
E temp = elements.get(i);
elements.set(i, elements.get(j));
elements.set(j, temp);
}
private int parent(int i) {
return (i - 1) / 2;
}
private int leftChild(int i) {
return 2 * i + 1;
}
private int rightChild(int i) {
return 2 * i + 2;
}
public static void main(String[] args) {
Integer[] elements = { 3, 2, 1, 5, 4, 0, 1, -1, -9 };
ArrayList<Integer> elementList = new ArrayList<Integer>(
Arrays.asList(elements));
int k = elements.length;
MinHeap<Integer> heap = new MinHeap<Integer>(k, elementList);
heap.buildHeap();
for (int e : elementList) {
System.out.print(e + ", ");
}
System.out.println();
System.out.println(heap.deleteMin());
for (int e : elementList) {
System.out.print(e + ", ");
}
}
}
Solution:
We assume that the lists are sorted in ascending order.
Insert all k elements at position 1 from each list into a heap. Use EXTRACT-MIN to obtain the smallest element (say x) of the heap.
Say then x came from list i, then take the next element from list i and insert it
into the heap. Continuing in this fashion yields the merged list. Clearly the running time is O(n log k)
Take k sorted arrays of arbitrary sizes, returns a unified sorted Array
/**
* Class takes a n*k dimensional array and outputs a single sorted array of size n*k
*/
public class KArySorting {
public static void main(String[] args) {
// in an array- Multi dimensional
int arr[][] = new int[][] {
{1,2,3,4},
{15,16,17,18},
{3,3000},
{0,3,1191,9898},
{2, 6, 12, 34,50},
{1, 9, 20, 1000,1200},
{23, 34, 90,150,190},
};
//If all arrays are of same size as in merging k sorted Lists, this Step is not required
int N=0;
for (int row = 0; row < arr.length; row++)
{
N = N+arr[row].length;
}
KArySorting kSorting= new KArySorting();
KArySorting.Struct structNode = kSorting. new Struct();
int[] result = structNode.kWayMerge(arr,N);
System.out.println("Printing Final Array "+result.length);
for(int i=0;i<result.length;i++)
{
System.out.println(result[i]);
}
}
class Struct
{
int data;
int indexofArray;
int indexOfNextElement;
int size;
private int heapSize()
{
return size;
}
private int getLeftChild(int i)
{
return 2*i+1;
}
private int getRightChild(int i)
{
return 2*i+2;
}
public void swap( Struct[] arr, int index1, int index2) {
Struct temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
public void minHeapify( Struct arr[], int index)
{
int lIndex = getLeftChild(index);
int rIndex = getRightChild(index);
int smallest;
if(lIndex <= heapSize() && arr[lIndex].data<arr[index].data)
{
smallest = lIndex;
}
else
{
smallest = index;
}
if(rIndex <= heapSize() && arr[rIndex].data<arr[smallest].data)
{
smallest = rIndex;
}
if(smallest != index)
{
swap(arr, index,smallest);
minHeapify(arr, smallest);
}
}
public void buildMinHeap(Struct[] arr)
{
this.size = arr.length-1;
for(int i = (int)Math.floor(arr.length/2) ; i >= 0 ; i--)
{
minHeapify(arr, i);
}
}
// Returning Just the Data, i.e integer value.
public int[] kWayMerge( int [][] arr, int n)
{
int k = arr.length;
Struct[] dataArray = new Struct[k];
for (int i = 0; i < k; i++)
{
dataArray[i] = new Struct();
dataArray[i].data = arr[i][0]; // Store the first element
dataArray[i].indexofArray = i; // Stores the index of array from which the elem was picked to be stored in Heap
dataArray[i].indexOfNextElement = 1; // Index of next element to be stored from array, default to 1st element
}
buildMinHeap(dataArray);
int [] output = new int[n];// if n is size of single array, total = n*k
for (int count = 0; count < output.length; count++)
{
// Create a pointer Node Root from the top of Min Heap
Struct root = dataArray[0];
// Put it in final Array
output[count] = root.data;
// Check if the k array still has elements
if (root.indexOfNextElement < arr[root.indexofArray].length)
{
// get the new Root from the Array which has prevous root
root.data = arr[root.indexofArray][root.indexOfNextElement];
root.indexOfNextElement += 1;
}
// case when one of the array has reached its end
else
{
//Put the last data in the min heap on the Top as the array is extinguished
dataArray[0]= dataArray[size];
// Reduce HeapSize
size--;// reduce heap size
root= dataArray[0];
}
dataArray[0] = root;
minHeapify(dataArray, 0);
}
return output;
}
}
}
An idea: compare the last element of a list1(say a) with first element of other list2(say b). If a<b, just append the list2 to list1.
- sachinvirgo February 26, 2008We can further optimise it by comparing fisrt with first as well to proceed with correct order of merging