## Microsoft Interview Question Software Engineer / Developers

- 0of 0 votes
How long it would take to sort 1 billion numbers? make any assumptions you wanted.. assume the computer would have more than 4 GB of RAM, so the array would fit in memory in its entirety, and the machine would run at 4 GHz.

I thought the way you had thought... since billion = 10^9 (not 10^10) it becomes 2.25 sec. which is hard to believe (:

But we only think the cpu speed, data transfer from memory to cpu and other operational stuff, will decrease the performance. Also we assume that cpu is not doing anything but our sorting operation.

Can any one explain how all this is working here? I mean I'm confused with 4GHz, how do we count the fastness of a computer from its GHz? any layman's terms would be really appreciated :)

Hertz is a measure of electric cycles per second (as in, the electrical signal on an oscilloscope would complete one full cycle, from baseline, to peak, to baseline, to trough, to baseline). For processors, one calculation can be performed per cycle.

So...

1 HZ = 1 processor cycle (calculation) per second

Giga is the prefix that indicates billions, so

1 GHZ = 1 billion calculations per second

4 GHZ = 4 billion calculations per second

>>make any assumptions you wanted..

Khoa what if I assumed that numbers are already sorted, then i just need one pass thrugh 1 billion numbers to confirm that they are already sorted.

Anyways the above assumptions may not impress anybody so I believe if all the 1 billion numbers could fit in memory then i would go for any inplace O(nlogn) algorithm .. personal choice would be quick sort(randomized version) or even heap sort is also not a bad idea.

is this problem vague just to test the candidate as where he goes with assumptions ?

statistical info abt the data could really help in choosing abt the algorithm.

nlogn/4GHZ=10^10*log(10^10)/(4*10^9)=25sec

- Anonymous on September 11, 2008 Edit | Flag Reply