I just got done reading the latest Cringley which of course revolves around my favorite bunch, Google.
(For those who don’t know me and didn’t hear my quite amusing story, I interviewed at Google and after the phone screen, 2 Colorado interviews, and the Cali interview they told me I couldn’t code and passed on me – hehe)
Furthermore, Philip Ogren and I had lunch yesterday and he mentioned that he interviewed at Google. He recalled one question that gave him particular trouble, which he believed to be the question that lost him more interviews. It was something like, “from an infinite stream of numbers select the highest 10%.” I had many similar questions such as “How would you find the median of an array that can’t fit in memory?” and “How would you randomly select N elements from an array of unknown size so that an equal distribution was achieved for infinite selects?” These questions are of course statistics based and selection questions, but Philip and I both could not definitely answer these questions for the interviewers. However, I moved on and he did not. In fact, he might have answered the questions better and definitely has more credentials than I do (he’s working on his PhD and I’m obviously not). So, before I get back to Cringley, what’s up with that?
It’s simple. Error is deterministic, guaranteed and often fixed. His interviewer was probably someone different than mine and probably had a larger ego than mine and this introduced error. My phone interviewer was a very cool dude who actually had a PhD in particle physics, but gave up research, probably for more money. Okay, back to the topic at hand – error – Google’s almost unavoidably introducing more error because smart engineers tend to believe they are better than you and this is 100% correct based on the 10-15 folks I’ve met from Google, with the exception of my interviewer and a few friends I have there. This ego-centric view of other developers introduces a high level of error when left unchecked.
Okay, so what does interviewing have to do with Google and Cringley’s belief that Google’s high concentration of smart engineers will be its down-fall? Well, it reveals the fact that Google is an enormously easy target. People talk about Googles hiring mistakes (error), issues with process and policy, and just about anything which is 100% perfect – meaning everything. Microsoft is likewise an easy target. The difference between Google and Microsoft is that Google used to be the good kid and everyone loved them to death. Now it seems that more and more people are shifting that view and looking at all the flaws and issues Google has and looking for ways to theorize their eventual decline into just another software factory that produces new versions of the same products with mundane certainty. Google is becoming just another evil empire, and if you look objectively, you can see that they are already heading full steam into the inevitable abyss where all enormous companies eventually end up. Google is just another company that everyone will love to hate but continue using everything they produce for at least another 10 years. Google self-destruction theories will become more and more common and folks will begin swapping, “did you hear Google messed up X,” stories at parties and events. This will all happen because as a society we tend to be deterministic in our love and then eventual hatred of companies on top. This cycle is quite simple to plot and if we did that exercise, Google would probably be right at the top on the verge of a lengthy but steady fall.
Invert your Mind 
Some folks at Amazon are fond of that sort of question. Amazon, at least, from the conceptual level — I can’t remember if we’ve asked people to code a selection algorithm.
Its somewhat pertinent to the types of work both companies do, but at the same time you can learn 98% of what you need to know by reading http://en.wikipedia.org/wiki/Selection_algorithm.
So the question is boiling down to “Are you an intelligent person?” and “Have you been exposed to these concepts before?”. So in that sense, its the type of question that can create a lot of false negatives.
LikeLike
Yeah, I agree. One of the issues I had overall with interviewing is many folks lack of balance. I was asked 95% algorithm (mostly selection and the like) questions and was never asked anything on design, systems, APIs, languages, theory, etc. I feel that a well balanced candidate should be able to show knowledge in many areas rather than just one.
The humor was the flat out statement, “you can’t code,” when all I was asked to code were these algorithms, which I did, just not extremely well on every single one. AND they didn’t verify this claim via my many open source projects out there. In fact, the most humorous part as that one of the algorithm questions, was regarding hiring error in companies and how to reduce error overall. To add insult to injury, my interviewer stumbled for about 5 minutes trying to solve this enormously simple math equation with no luck. hehe
Okay, enough Google talk, back to coding software module dependency graph compatibility algorithms using a bi-direction graph with fast paths and pruning for Savant. (hehe)
LikeLike
After reading your post last night I thought of a really simple solution to the question they gave me on my technical screening interview. The question was the following:
You have an infinite stream of numbers for which you have no prior information about the distribution (except that the distribution does not change over time.) Your job is to keep approximately 10% of the numbers such that you keep the 10% with the highest numerical value and discard the rest. You can imagine that you have three methods – getNext(), keep(), and discard().
Here is my solution. Begin with an empty list/array. Every time you call getNext() insert the number into the list such that the list is sorted. If the index of the number in the list over the size of the list is greater than 90%, then keep the number otherwise discard it. Do this until the size of list reaches some threshold (say, 1 million) at which point you can feel confident that whatever number is at the index corresponding to the 90th percentile is a good threshold to determine all future decisions. Now simply keep and discard the infinite stream of numbers for all eternity.
It does seem awfully simple now that I’ve thought of it. Sigh!
Well, this post was really off topic as we’re supposed to be bashing Google here. I’m not too worried about Google and am still infatuated with them and would probably do it again if they called me up. And if I wasn’t distracted by other things going on right now, I would probably take for a little self pity that I didn’t get a chance to interview.
LikeLike
Hi, Can you guys Please give me some more Questions that google had asked…
LikeLike
Jonny – I have a few bits of advice:
1. Determine if you want to work for Google first. Look around at some of the information about the company out there and think about what you’ll be doing there. Also think about what you want to do in your career. Do you want to become an architect and still code a bunch? Work on difficult problems that challenge you? Manage people? You might find more enjoyment professionally elsewhere or you might enjoy Google. I have a feeling that in the long run I’m glad I stayed away from Google because I want to start my own company and Google’s probably not the best place to write code on your own time. My guess is they own your entire life and anything you even think about, let alone code, is theirs.
2. If you do want to interview, brush up on all those basics from data structures, algorithms, etc. Think about hashes, trees, graphs, LRU, non-recursive tree traversals, sets, etc. Review big-O stuff. I think it is definitely important to understand that most questions for the in person interview will be coding questions on a white board. Therefore they will be quickly solvable but often more difficult to implement with the proper big-O. You’ll need to consider hashing, sorting, searching, looping, recursion, and branching a lot.
3. Good luck!
LikeLike