CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Microsoft Interview Question for Software Engineer / Developers






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

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

- Anonymous September 11, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Mehmet November 09, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Dom September 05, 2013 | Flag
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 :)

- Anonymous April 17, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- isochronous October 30, 2009 | Flag
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.

- algooz April 23, 2008 | Flag Reply
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.

- vodangkhoa April 23, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can only roughly guess. 6.96 second?

- Anonymous July 02, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous October 14, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- DJ January 24, 2009 | Flag
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

- Anonymous November 25, 2008 | Flag Reply
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.

- safakm August 14, 2009 | Flag Reply
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.

- Johan Braanen June 28, 2021 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More