Microsoft Interview Question
Software Engineer / DevelopersI 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.
If there are many CPUs, it could be possible to split the table into multiple parts, sort them individually, and then merge sort the sub-tables into a resulting table. The total time would then be
1. Time to split and distribute the tables
2. Time to sort the smaller tables
3. Time to merge sort the tables into one table.
However, to calculate an accurate number, it is very dependent on how many operations you can do in 1Hz.
nlogn/4GHZ=10^10*log(10^10)/(4*10^9)=25sec
- Anonymous September 11, 2008