After two phone interviews Google asked me to visit London and have a whole day of chatting about technology and solving intricate coding puzzles. Just to see how good I am on a scale of 1 to Google.

An animation of the quicksort algorithm sortin...

An animation of the quicksort algorithm sorting an array of randomized values. (Photo credit: Wikipedia)

They aldo sent me an email with advice. It can be summed up as “You should know everything. If it’s to do with computers, you should know it. Here are 5 books and 4 fancy algorithms you should read. You must also be intimately familiar with all these basic-ish algorithms. This is your two week notice. Good luck. Oh and take a look at these videos too!”

Technical interviews have always been fun for me, I just love talking shop with anyone who would listen and how often do you get the chance to talk shop with some of the [provenly] best engineers out there?

Somehow, instead of being super solid advice, the email did nothing but cement my idea that it’s impossible to study up on all this and I should just hope I’ve got what it takes anyway.

Here’s the email, copied verbatim.

Guide to getting an engineering job with Google

Software engineers work in small, rapid teams, each handling the full development cycle without need for hierarchy; product design, system architecture, coding, testing & product launching at global scale. They don’t tend to make prototypes; but rather work in realtime, with live feedback from real people across the globe. Engineers don’t always get it right first time, but iterate fast in an agile, unit test environment.

Google takes an academic approach to the interviewing process.  This means that we’re interested in your thought process, your approach to problem solving as well as your coding abilities.

Technical Interviews

You can expect questions that evaluate your skills in three primary areas:

1. Coding

  • Fluency in at least one programming language is prerequisite, preferably be an object-oriented language, ideally C++ or Java (C# is OK, although engineers don’t use it and Python can be useful).
  • You should be able to produce fully compilable code in your chosen language, to justify why it’s your preferred language and be fully up-to-date with its latest editions.
  • Sample topics: construct / traverse data structures, implement system routines, distill large data sets to single values, transform one data set to another.
  • Google engineers don’t tend to need pre-coded solutions or architectures (so would not utilise MFC, .NET or J2EE).
  • Engineers develop in a globally open, unit test environment, so you should be familiar with this methodology and able to write your own tests.
  • Coding styleguides can be found here.

2. Algorithms

  • You need to know Big-O complexity analysis really well → it’s OK to quickly come up with a brute force solution, but that’s never going to be the answer → always look for an O(n*logn) solution or ideally a linear one.
  • Searching and sorting algorithms (Quicksort, Mergesort, etc) → know more than one O(n*logn) sorting algorithm → know how they work and how to optimise for time and space.
  • Hash tables → be able to implement one using only arrays.
  • Trees → know tree construction, traversal, and manipulation algorithms. Familiarise yourself with binary trees, n-ary trees and trie-trees, and at least one type of balanced binary tree.
  • Know the classic computer science problems (Shortest Path, Traveling Salesman, Knapsack, etc).

3. System design

  • You need to know powers of 2, and be good at back-of-the-envelope calculations e.g. to estimate the required number of machines for a given design.
  • Know Google’s products, and think about how you would design the back-end (or front-end).
  • System design questions are a test of your problem solving skills. Ask qualifying questions → make sure you explain your thought process → explain and justify your assumptions → think of the bigger picture and don’t get bogged down in the detail.
  • Sample topics: features sets, interfaces, class hierarchies, designing a system under certain constraints, simplicity and robustness, tradeoffs.
  • Checkout this link for basic systems design as used at Google.

Interview Hints

  • Talk through your thought processes. Our engineers are evaluating not only your technical abilities but how you approach & solve problems.
  • Ask clarifying questions if you do not understand the problem or need more information. Many of the questions asked in Google interviews are deliberately underspecified because our engineers are looking to see how you engage the problem. In particular, they are looking to see which areas leap to your mind as the most important piece of the technological puzzle you’ve been presented.
  • Think about ways to improve the solution you’ll present. In many cases, the first answer that springs to mind isn’t the most elegant solution & may need some refining. It’s definitely worthwhile to talk about your initial thoughts to a question, but jumping immediately into presenting a brute force solution will be received less well than taking time to compose a more efficient solution.
  • Show an interest in Google products. What is your favourite product, and how would you improve it?

Videos
- Interviewing at GoogleAn inside look at Google
- Google Youtube Channel
- Underneath the covers at Google
Google i/O 2011

Recommended books

  • Programming Pearls, 2nd Edition – Jon Bentley
  • Introduction to Algorithms, 2nd Edition – Cormen, Leiserson, Rivest, Stein
  • Programming Interviews Exposed: Secrets to Landing your next job, 2nd Edition – Mongan, Suojanen, Giguere
  • Effective C++ – Scott Myers
  • How Google Tests Software – James Whittaker

Background knowledge:
Background knowledge: The Google infrastructure Google has the world’s most formidable large-scale computing and storage infrastructure. Clusters of Linux-based machines with custom job and storage management systems allows us to build applications that access petabytes of data or process millions of requests a day. We can build such systems because, amongst other things, we have full control over the software stack.  Four of the key elements include:

  • GFS - the Google File System
  • MapReduce - to crunch large data sets
  • BigTable - a distributed storage system
  • Chubby - a distributed lock service

I asked an experienced Google engineer how/why Google uses Big O notation and they gave me this information:
Google-scale problems fall into two categories: those that span across machines, across very large amounts of data, and those that supply a large number of users with very quick access to data, such as search.

When we design a solution for either sort of problem, we are deal with large numbers of items, for example a large number of web pages to search, or customer reports to aggregate up.  This means that any algorithm that is not at least as good as linear (O(n)) in time is likely to be too slow.  User-facing products such as search require even better: that means aiming for constant time operation (O(1)), no matter how large our index, we need to show results in a fixed amount of time.  Sometimes that means we scale the system up to cope with the number of Web pages we have to search.  Any example of where your understanding of performance profiling would be applicable is now that we have a constant-time solution, we need to minimise the overhead of just one user performing a search; it’s no good if one user’s query causes 100MB to be allocated on 1000 computers.

Another example would be when we index the Web.  This means taking billions of Web pages, computing metrics on each of them to extract the search terms that might trigger them, and then putting them in a searchable index.  Adding each page means we might need to compare it with every other page to find the best result for a query, but in fact we can perform the index in linear time with respect to the whole internet by performing the entire computation in parallel.  What engineers have done is distilled the problem to an ‘embarrassingly parallel’ one where as much computation as possible is done on each single page before the more expensive step of comparing it with other pages.  This reduces the overall time to index the Web to the extent where we can keep much of the internet searchable even if the page is only 15 minutes old.  Here, we have used algorithms and Big O analysis to both decrease latency and increase throughput; performance profiling plays a part but but only once a truly scalable solution has been found.

Enhanced by Zemanta
  • Asgrim

    And that’s why I could probably never work at Google. The maths behind everything bores me. I just love coding :)

  • http://twitter.com/zidarsk8 Miha Zidar

     Seriously though, that sounds like you like typing lines and lines of code and not actually coding. Knowing the math behind the problem is what makes a good programmer. That does not mean you have to know everything, but enough to grasp the concepts and enough to know that for example if you need to sort something, there may be a better suited algorithm for your dataset than quicksort (lame example but go with the flow here).

    Lately I see more and more programmers who just know a ton of libraries and such, and use that. That’s awesome for most problems, but a good programmer should be able to handle many weird cases too.

  • http://twitter.com/zidarsk8 Miha Zidar

    random: the scale should be from 1 to Googol … sounds simmilar but better

  • http://twitter.com/eosrules EOSy

    -aldo
    +also

  • Vin

    Great entry. Will you post a follow up as to report how the interview went?

  • http://otfusion.org/jose152 Jose Miguel Salcido Aguilar

    congratulations for this entry.

  • Asgrim

    I wouldn’t say I’m a programmer at all! I’m a web developer, I make websites, not do complicated things like maths :) In my 10 years of web experience (8 years of that in professional jobs), I’ve done relatively few complicated mathematical type things.

    Not to say this talent isn’t useful, of course it is, but I’m just saying I’ve not needed it yet, and I expect that’s because I’m a (good, maybe?) web developer rather than a good programmer :)

  • Mac

    I really don’t think that email is unreasonable.  It isn’t really a “here’s how to get a job at Google” email.  It’s a “here’s what you have to have to get a job at Google” email.

    These are things any good software engineer will know/be able to do.  If we’re giving people computer science degrees without them proving these abilities, that’s a shame.  Don’t get me wrong, there is room in the industry for coders without these qualifications (I’m presently one of them!), but these are basics of computer science.  Even if they weren’t, there’s no shame in them demanding high qualifications if they are able to find enough of those people to hire…   and they definitely don’t owe the rest of us anything in terms of guiding us on how to meet their qualifications (although when they do, that works out for everyone).

  • Ariel Arjona

    Those requirements seem more than reasonable to me, not even for google-scale but for any-given-software-company-scale.

  • mandeep janjua

    Just try to understand what Miha is saying. Why you are running in circles?

    You mean to say web developers are not programmers just because they are working on web applications. I hope you will not next saying “Oh wait! I just discovered I am neither a programmer nor a web developer….I am just a designer….who just copies images from some where and taint them with different colors and finish the job”

  • http://swizec.com Swizec

    You’re just describing the difference between a coder and a programmer. Not everyone needs to be a programmer to do their job. More importantly, not everyone needs to be a programmer to create massive amounts of value to clients.

    I certainly wouldn’t want the guy coding up my blog template knowing too much about the deep mathematics behind rendering CSS to a screen. That will just distract the person from what they’re being paid to do – get shit done.

  • http://swizec.com Swizec

    Most web developers I’ve seen are just coders. Most web development jobs wouldn’t even benefit from hardcore programmers.

    But when it comes to scaling, that’s where you need brawn. Not sure the guys scaling apps to millions of concurrent users still count as “web developers” though. They’re solving very algorithmic problems that just happen to occur on the web.

  • http://swizec.com Swizec

    Of course :)

  • http://swizec.com Swizec

    The email isn’t unreasonable at all. And I do know most of the stuff there, some could use a bit of dusting off :)

    But it’s daunting to see it all listed like that. 

  • http://swizec.com Swizec

    As I’ve said elsewhere – the requirements are very reasonable. I wasn’t trying to imply that they weren’t, just that there are a lot of them and seeing a list like that is daunting.
    Whether you know the stuff or not.

  • Asgrim

    I am by no means a designer – I work on a business analytics system and a CRM system in my day job, neither of which use complex algorithms, it’s just complicated logic and automating tedious tasks and reporting to help run the business successfully.

    All I meant in my reply was that I wouldn’t consider myself a “programmer” at all, I write code to make websites, and I’m happy with that. And in my original post, I just say that because of that fact, Google would never hire me! :)

    I don’t know how compression works, or encryption algorithms, or different sorting algorithms. I do, however, know that I can use (say for example in PHP) gzcompress, mcrypt_* and sort functions to carry out those jobs. I’ve never needed to know how they work, and it doesn’t interest me. I’ve got all the tools to do my job and earn a living, so I’m happy not knowing these things.

  • Pingback: Google interviews « Dwell Angle

  • Pingback: Technology And Software » A geek with a hat » Google sent me a “what to know in on-site interviews” email. Here it is.

  • Pingback: A geek with a hat » Inside a Google onsite interview

  • Pingback: Ablauf von Google-Bewerbungsgesprächen | Karl Lorey