## Flipkart Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: Phone Interview

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

Given k sorted lists, with the total of n elements.
keep a pointer to each of the list
construct a minheap (data and arraynumber) by taking the first element from all the arrays.
increment all the pointers by 1

extract the minelement and print
take the element from the array in which the min element in present, and insert to min heap.
increment that pointer.
Continue till all the pointers reach end and min heap becomes empty

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

but now how would the complexity be nlogk becoz u are accessing each element once
hence complexity becomes n.k

please correct me always hav a complexity issue

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

This is NlogK alright.

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

Time complexity is O(k+(N-k)logk) which is equivalent to O(Nlogk). Note that N is sum of the total number of elements in all k arrays.

However if you say n is the average number of elements per array, you could also express the time complexity as O(nklogk).

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

It is O(NlogK) because there are logK merge operation of the external merge sort. At each you scan N elements.

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

This comment has been deleted.

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

kirubakaran :

but now how would the complexity be nlogk becoz u are accessing each element once
hence complexity becomes n.k

please correct me always hav a complexity issue

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

Time complexity will be O(K*N logk) because, each time, a new element is inserted in the min-heap, the heap needs to be heapified so that at each time during extraction, we get the minimum element only.As heapify takes logk time & it is done K.N times, so O(k*N logk)

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

Basically u hav to pick the smallest element from all the arrays in the 1st position of the final array.
So for this reason the merge part of the merge-sort algorithm can be used.

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

O(NlogK) is correct .

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

Hey what is the complexity of getting next element from list of arrays? you need to search again which array contained the min element? anybody can answer?

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

Usually people use a binary heap to implement a priority queue that allows the discovery of the next least element in O(log K) time.

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

I think the question here is not about how the binary heap works itself. The question is how we find the proper element to "feed" the heap after we take away its root. How can we tell which sorted array does the just taken element come from? You are using a dynamically updated hash map? I do not think it a good idea.

Btw, I think the complexity for a heap insertion should be O(1). In fact, most bubble-up in heap would end within 2 steps. You can turn to wiki about heap for more details.

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

Who said anything about a dynamically updated hash map? You'd insert tuples of the form <value, number of array it comes from> into the heap, which is sorted only by value. Then when you retrieve the tuple with the smallest value, you'd know which array it came from.

The worst-case complexity for heap insertion is O(log K) where K is the size of the heap. It is not O(1). I sure hope I can't turn to the wiki for more details, because that would mean I need to go edit it for correctness!

EDIT: I suppose that there are types of heaps other than binary heaps, and that those may have O(1) insert. But my comment was on binary heaps specifically, so I assume we're talking about binary heaps.

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

``````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);

Node n2 = new Node(4);
n2.next = new Node(6);
n2.next.next = new Node(8);
n2.next.next.next = new Node(10);

Node n3 = new Node(9);
n3.next = new Node(11);
n3.next.next = new Node(12);
n3.next.next.next = new Node(13);

Node n4 = new Node(-4);
n4.next = new Node(-2);
n4.next.next = new Node(-1);
n4.next.next.next = new Node(14);

Node n5 = new Node(-3);

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) {
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 + ", ");
}
}
}``````

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

The simple merge of every 2 arrays should be easier:

``````import java.util.ArrayList;
import java.util.List;

/**
* @author Sabuj
*
*/
public class Merge {

public static void main(String[] args) {
List<Integer[]> arrays = new ArrayList<Integer[]>();
arrays.add(new Integer[]{5, 7, 11, 19, 22});

Integer[] p = mergeArrays(arrays);
for (int i = 0; i < p.length; i++) {
System.out.print(p[i] + ", ");
}
}

public static Integer[] mergeArrays(List<Integer[]> arrays){
if(arrays == null || arrays.size() == 0)
return null;
Integer[] p, q;
if(arrays.size() >= 2){
p = arrays.get(0);
for (int i = 1; i < arrays.size(); i++) {
p = merge(p, arrays.get(i));
}
} else {
return arrays.get(0);
}
return p;
}

public static Integer[] merge(Integer[] a, Integer[] b){
Integer[] c = new Integer[a.length+b.length];
int i=0, j=0, k=0;

while(i < a.length && j < b.length){
if(a[i] <= b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
}

while(i < a.length)
c[k++] = a[i++];

while(j < b.length)
c[k++] = b[j++];

return c;
}

}``````

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

merge k sorted lists: writeulearn.com/leetcode-merge-sorted-lists/

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.