Flipkart Interview Question for Software Engineer / Developers






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

Build a heap out the first element from all k streams.. Remove the minimum and insert the next element into the heap from the stream to which minimum belongs. Keep repeating this till we run out of all streams.. Will this work?

- Radhika July 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

ya it will work..its the best solution..it will produce a infinite stream

- @BeautyWithBrains July 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How would you keep track of which element came from which stream, especially after you have processed them to make a heap?

- kislay.nsit March 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do you need a heap when the streams are sorted?

- Kay October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We don't need heap. But we can have 2 if condition in a while loop. These if condition will find which element to put in output stream and get new element to the stream from which the minimum element was processed. I think 2 if conditions will solve the prob.

- Akshay December 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Looks like there are k incoming streams which are sorted among themselves. So all we need to do here is form another stream i.e. the output stream from the k input streams.
The problem would arise when one or more of the streams have their values start after a huge number of values of other streams.
In this case lets say that all the k-1 streams are having numbers from range 1 and 1000000. So now its easy to merge the k-1 streams.

if the kth stream starts from 10000000000000 i.e. of order several times larger then the values would keep coming in, and you would need to store in a buffer and when that goes full, serialize that into a filestream.

This is the main crux of the problem. The problem would be more magnified if its the other way round, i.e. 1 stream starts from 1 and goes up in increments of 1 and the other k-1 streams start from 100000000000000 and above. So you will have (k-1)*100000000000000 values in store before the first value gets consumed. this would mean requiring the (k-1) file streams to serialize and then read from the files to throw the output into the output stream.

This question is not an algorithmic or time complexity question but more of a large data system design.

- NEO September 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

External merge sort

One example of external sorting is the external merge sort algorithm, which sorts chunks that each fit in RAM, then merges the sorted chunks together.[1][2] For example, for sorting 900 megabytes of data using only 100 megabytes of RAM:

1. Read 100 MB of the data in main memory and sort by some conventional method, like quicksort.
2. Write the sorted data to disk.
3. Repeat steps 1 and 2 until all of the data is in sorted 100 MB chunks (there are 900MB / 100MB = 9 chunks), which now need to be merged into one single output file.
4. Read the first 10 MB (= 100MB / (9 chunks + 1)) of each sorted chunk into input buffers in main memory and allocate the remaining 10 MB for an output buffer. (In practice, it might provide better performance to make the output buffer larger and the input buffers slightly smaller.)
5. Perform a 9-way merge and store the result in the output buffer. If the output buffer is full, write it to the final sorted file, and empty it. If any of the 9 input buffers gets empty, fill it with the next 10 MB of its associated 100 MB sorted chunk until no more data from the chunk is available.

- Anonymous September 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since the streams are infinite in nature, we have to use MinHeap concept along with insertion sort. Take an empty result array.
From all of the sorted streams, pick the smallest number (comparing index 0 of all streams) and put in result array.
Continue the same.
In the result array, we need to take care of inserting the new element at correct position.

- Akash June 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since the streams are already sorted, the problem domain is not sorting but merging. Take any two streams at one time and perform a simple merge routine. Further merge processing can be made efficient on consideration that the streams are already sorted and tail of one stream may be directly lesser than head of another. Thus the number of times a stream needs to be compared element-wise may be reduced.

- logmagic July 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Radhika you are right if there are k streams which are sorted and n elements in total this gives O(nlogk) algorithm.(refer to cormen)

- Learner July 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Since we are performing heap operation for every element in all the streams there are a total of n*k elements. Therefore the complexity is O(nklogk)

- Naveen July 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry my mistake you said total of n elements.

- Naveen July 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Could we perform a k-way merge?

- Anonymous July 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hey friends
what if we construct a binary search tree it would have a time complexity of log(no. of elements=k.N) + its inorder traversal O(k.N)
where N is no. of elements in a stream...
becoz if we use heap for such large data set our programme will give heep Exception..

- shreyans June 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

shreyans, We will not have heap exception. As the heap has at most k elements at any time.

- sabz September 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Found on the algo blog

Step1: Take first element of all k streams and build a min heap of them. => O(k)
Step2: Remove the min element (elem at top of heap) from the heap and put in the new stream. => O(log k)
Step3: Put new element in heap from the stream to which the prev elem belongs (which was at heap min). => O(log k)
Step4: continue above steps till we exhaust all the streams. If all streams in combination have n elements then order is O(n log(k))

- Samz December 12, 2019 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More