10 tough programming questions you will face in a Google interview

Not too difficult questions.. interesting that a position that high up requires that kind of info in an interview :s
 
Why Quicksort is the best sorting method?

Answer: Quicksort has the best big-O
Click to expand...

Questions like these usually stump me, this answer is basically saying it is the best because it is the best (fastest), my mind would wonder of into an attempted analysis of the underlying Why, possibly an attempted proof that a more effective algorithm cannot exist.
 
etienne_marais said:
Questions like these usually stump me, this answer is basically saying it is the best because it is the best (fastest), my mind would wonder of into an attempted analysis of the underlying Why, possibly an attempted proof that a more effective algorithm cannot exist.
Click to expand...

common problem with questions asked is that they do not specify the scope within which you must tackle them
 
There’s an array of 10,000 16-bit values, how do you count the bits most efficiently?

Answer: Use a lookup table and then sum the results
Click to expand...

overly technical, but

10 000 * 16 ? (plus pointer ?)
 
How is this even an article though? They take a blogpost, take the questions and expected answers out and post it?
 
etienne_marais said:
Questions like these usually stump me, this answer is basically saying it is the best because it is the best (fastest), my mind would wonder of into an attempted analysis of the underlying Why, possibly an attempted proof that a more effective algorithm cannot exist.
Click to expand...

I agree it's not a good answer at all. Firstly, generic Quicksort doesn't have the best big-O. It has an expected execution time of O(n.logn), but a worst case of O(n^2), while merge sort and heap sort have better big-O (O(n.logn) worst case). Quicksort can get worst case O(nlogn) by using median of 5 partitioning, but that affects the the run-time constant negatively.

The reason Quicksort is generally considered the best generic search is that unlike merge sort, it's in-place, and unlike heap-sort, it processes memory coherently and predictibly, making it far better for large data sets.

In practice, combining quick sort with a heap sort will give the best overall performance, by dropping to a heap sort when the data footprint is small enough to fit in the L1 cache (and random memory accesses become cheaper).

I find it somewhat hard to believe that the interviewer would not know the above and apparently get it wrong. I also find it strange that a recruiter is interviewing him (???).
 
Last edited:
etienne_marais said:
overly technical, but

10 000 * 16 ? (plus pointer ?)
Click to expand...

Both his answer and the recruiters are pretty bad. There is a hierarchical bit-counting method via bit manipulation and masking, but it is somewhat obsolete these days. Almost every CPU out there today has a hardware popcnt64 instruction. Intel does, and it has a throughput of 1 clock cycle, and latency of 3 clock cycles. This means that I would load in the data 64-bits at a time, and run popcnt64 on each 64-bit value. I would unroll the loop 3 times to account for the instruction latency. I would expect it to run in in 10000/4 = 2500 clock cycles, so just under a microsecond on a newish intel processor.

The explicit computation of the number would be way slower than 1 64-bit number per clock. This can be done in time sensitive to the number of on-bits, so if fewer bits set was somehow more likely, it would do better than the hierarchical bit counting method. Both of these would take much longer than using the popcnt instruction. A lookup table would in fact be much better than this, but because it would be larger than a typical L1 cache, it would still require 5x the number of reads (1x for the 64-bit read, and 4x lookups), and many of these reads would at best be in the L2 cache, so assuming the original data was in the L1 cache and the table was in the L1 and L2 cache, it would be at best ~20x slower.
 
krycor said:
Not too difficult questions.. interesting that a position that high up requires that kind of info in an interview :s
Click to expand...

Everything is so technical, that no manager's job there is just about people management - apart from the obvious benefit in terms of planning, scheduling, etc. (I.e., being able to put a reasonable timeframe and man count on things), I was surprised to see that the managers actually hash out most of the technical aspects of multi-team projects together - deciding on the features and scope of the project, etc. at the time. Even the senior VPs that I've met (thousands of indirect reports) have a fairly good idea of what's going on in the software and sometimes even in the silicon.
 
You must log in or register to reply here.
Back
Top
Sign up to the MyBroadband newsletter
X