MS Question

Question:
------------

Given an array having 16000 unique integers, each lying within the range 1<x<20000, how do u sort it. U can load only 1000 numbers at a time in memory.

Solution:

Have an array of 2500 bytes (memory equaivalent of 625 ints) - Each bit in the array will show the presence/absence of a num betw 1-20,000. Lets call this the "presence-bit-map".

Since you can store the presence of 8 nos in a byte, you need (20,000/8) = 2500 bytes.

Initialize all bytes in the presence-bit-map to 0, meaning 'absent'.

Iterate the large integer list(be it in file / mem) once. For every number encountered, set the corresponding bit to 1(indicating present) in the presence-bit-map.

Now, by scanning the presence-bit-map once, you can write the present numbers in sorted order.

complexity
===========
The soln has a complexity of 'order of n', where n is 20,000 in this particular case. O(n) is the best u can get for a sorting problem !

O(n) is possible here coz we have 2 facts that could be taken advantage of
1. Numbers are known to be unique
2. Nos. are known to be in a specific range.

In a generic sorting problem, O(n) is usually not achievable since we can't assume anything like this.

Powered by ScribeFire.