## Microsoft Interview Question for Software Engineer / Developers

• 0

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

nlog(n) is the complexity. Not the number of instructions! it could be 10^100000*nlog(n).

Comment hidden because of low score. Click to expand.
1
of 1 vote

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 :)

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

>>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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Long as in how many seconds/minutes/hours it would take. Not asking for big O notation here.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can only roughly guess. 6.96 second?

Comment hidden because of low score. Click to expand.
0
of 0 vote

4GB memory can not store 1billion numbers. So....

Comment hidden because of low score. Click to expand.
0

And why exactly not?

4 GB = 2^2 X 10 ^ 9

1 billion = 10 ^ 9

Assuming 1 integer is 4 bytes, 1 billion numbers take 4 GB memory. Also, the question says we have more than 4 GB available.

Comment hidden because of low score. Click to expand.
0
of 0 vote

for me it comes to 7.5 sec...
nlogn/4GHZ (n=1 billion = 2^30 or 10^9 as per US...also 1G=2^30)
= [1024^3 * log( 1024^3)] / [4 * 1024^3]
= [2^30 * log(2^30)] / [4 * 2^30]
= [2^30 * 30] / [4 * 2^30]
= 30/4 = 7.5 sec

Comment hidden because of low score. Click to expand.
0
of 0 vote

do you all really think that CPU has the same speed with memory and the cpu can access to memory immediately? and there is also RAM latency
it is just the cpu clock time. what about memory access, copy cache operations, they are the time consuming ones.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.