Morgan Stanley Interview Question
Developer Program EngineersCountry: India
Interview Type: In-Person
for simplicity : i am explaining for sorting 10 numbers with memory size 2
a) find the minimum element and its index in one full traverse from i to (total_numbers -1) [here it is 8]for (i+1)th iteration
for ex: {5,8,1,3,9,10,6,4,2,7} , store {2,1} where 2 is the index and 1 is the element for 1st iteration
b) swap(input[min_index],input[i]) where (i+1)th iteration
here,
swap (input[2],input[0]) for the 1st iteration
c) repeat a) and b) for 8 times .. as for 9th iteration no swaping will be there and elements are sorted..
Sort the numbers in groups of 20, starting from the first block of 20
so you will sort elements 0-19, 20- 39, 40- 59 ...
then you sort the entire thing by blocks of 20 again, but offset by 10
so you will sort 10 - 29, 30 - 49, 50 - 69 ...
repeat this cycle 5 times.
If you use Quicksort/mergesort you'll have a bigO of nlogn, with n being 20. first half of the cycle takes 5 sorts, 2nd half takes 4 sorts, so each cycle takes 9nlogn, with n being 20. We go a total of 5 cycles, making it 45*nlogn, or with n being 20. This will be a 45 * 20 * log (20)
hey aftr sorting 10-29(let's say put in b[20]) compare 1-10(original list of numbers) with top 10 elements of sorted(10-29)...go on recusively like this compare 10 of previous sorted list with 10 of next sorted list
I assume 100 numbers are stored such that it can't be sorted in-place. Otherwise quicksort can sort them without even needing additional 20 space. So with that assumption, take 20 from the source and move to the additional space, sort in n log n (n=20). Copy it back to the original place. Repeat 4 more times for each block of 20. Now we have 5 sorted blocks of 20 in the original space. Now merge first block with second using the additional space as the temp storage. After this step, block 1 and block 2 are merged and sorted. Then merge 3 block with the first+second block. Then 4th and then 5th.
The problem states that you can use only array of size 20, so partitioning is prohibited. Assuming the numbers are input from an array...
1) Use insertion sort(outperforms divide-and-conquer algorithms because it's iterative, and good for small datasets) on the first 20 elements, then 2nd 20 elements, and so on, to produce sorted subsets
2) For i=0 to len-1, merge all 5 subsets in O(n) time
External merge sort[edit]
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:
Read 100 MB of the data in main memory and sort by some conventional method, like quicksort.
Write the sorted data to disk.
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.
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.)
Perform a 9-way merge and store the result in the output buffer. Whenever the output buffer fills, write it to the final sorted file and empty it. Whenever any of the 9 input buffers empties, fill it with the next 10 MB of its associated 100 MB sorted chunk until no more data from the chunk is available. This is the key step that makes external merge sort work externally -- because the merge algorithm only makes one pass sequentially through each of the chunks, each chunk does not have to be loaded completely; rather, sequential parts of the chunk can be loaded as needed.
we can use external sorting.
- sumedh August 07, 2012