Interview Questions

160. Given a stream of N integers which has the property that no integer .......

Microsoft Interview Questions and Answers


(Continued from previous question...)

160. Given a stream of N integers which has the property that no integer .......

Question:
Given a stream of N integers which has the property that no integer is more than 1000 positions away from its sorted location, how would you output the integers in sorted order while using constant storage?


maybe an answer:


sort a[1] to a[2k] elements(heap sort)... elements 1 to k are in their right place.. now sort a[k] to a[3k], then a[2k] to a[4k] and so on...
Space complexity: 2 * n/2k * 2k log 2k = 2*n*log k


maybe an answer2:


1. Read first 1500 elements, sort it
2. output first 500 elements
3. read another 500 elements, and sort new 500 elements separately
4. merge new 500 elements with old 1000 sorted elements
5. goto step #2

(Continued on next question...)

Other Interview Questions