Хочу работать в Google: Советы по подготовки к интервью от Google
Этот документ рекрутеры Google рассылают кандидатам, обычно после телефонных интервью. Мне разрешили его опубликоватьв блоге тоже, он не секретный. Но крайне полезный для тех, кто готовится.
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:
- Coding
– You should know at least one programming language really well, and it should preferably be an object-oriented language, ideally C++ or Java (C# is OK since it’s similar to Java, and Python is also perfectly fine)
– When presented with a coding problem you’re always free to choose whatever language you like, however some questions will lend themselves better to one language over another
– You should know a fair amount of detail about your favourite language, including justifying why it’s your favourite
– Coding speed is one of the signals we look for, however don’t fall into the trap of starting to code before you have the solution clear in your mind. Take some time to brainstorm, use the whiteboard, and solve the problem in your mind before coding
– Practice coding without an IDE. You won’t have one in the interviews
– Don’t be too pedantic about syntax as it will slow you down, and don’t avoid solving the meat of the problem
– Sample topics: construct / traverse data structures, implement system routines, distill large data sets to single values, transform one data set to another.
- 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)
- System design
– Ask the right clarifying questions up front, so you’re clear on what you’re actually designing
– Be prepared to dive down into the details at some point, which involves providing concrete details i.e. non-abstract
– 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.
Book:
– Site Reliability Engineering: How Google Runs Production Systems
Numbers every computer scientist should know: http://highscalability.com/blog/2011/1/26/google-pro-tip-use-back-of-the-envelope-calculations-to-choo.html
Presentation: Building software systems at Google
Video:
– Building Software Systems at Google
– How to leverage Google’s global network infastructure
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?
Blog posts
Dean Jackson: The Google technical interview
Steve Yegge: Get that job at Google
Cate: Interviewing @ Google
Don Dodge: How to get a job at Google, interview questions, hiring process
Videos
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
Online courses
Google hires a lot of graduates from Stanford and MIT. But you don’t have to attend these colleges to benefit from their courses….you can find the MIT Computer Science courses online through free Open Course Ware. Here is just a selection:
6.006: Introduction to Algorithms
6.853J Distributed Algorithms
6.854J Advanced Algorithms
Classic problems
Towers of Hanoi
There’s a temple in the middle of Hanoi. In that temple, there are three very large diamond-encrusted posts, and on those posts are sixty-four disks, all of a different size. There are a set of priests in that temple, and their task is to move the entire stack of sixty-four disks from one post to a second post. The rules, though, are, they can only move one disk at a time, and they can never cover up a smaller disk with a larger disk. Write a recursive program to solve this problem. What is the complexity?
Searching and sorting algorithms
Write code to search a sorted list.
Write a binary search algorithm.
Write a selection sort algorithm.
Write code to create a hash table of size 256
Shortest path problem
Write an algorithm to plan a route by minimising distance or time (eg Google Maps)
Traveling salesman
Write an algorithm to determine the least cost round-trip, given multiple cities and varying costs of flights
Knapsack problem
Write an algorithm to optimize the value of items you can fit into a backpack based on weight and volume
Sorting algorithms – know how they work, average/worst case running times, stack space
- Insertion sort
- Quicksort
- Mergesort
- Heapsort
Searching algorithms
- Sequential search
- Binary search
- Hashing
- Binary search trees
- Key indexing
Other algorithms
- Priority queues
- Selection
Back of the envelope calculations
- Know your powers of 2 (binary)
- Be able to express mega/giga/etc in binary and/or scientific notation
- Know cycle times and disk seek times for CPUs
- Explain and justify your assumptions
- Don’t be afraid of dealing with huge numbers!
Sample questions from Programming Pearls
- Given a file containing at most ten million 7-digit integers with no duplicates. What is an efficient way to print these numbers in ascending order using just 1.5Mb RAM and reading the data just once? What are the consequences of only having 1Mb of RAM and no other storage? How would your answer change if duplicates were permitted?
- Given a sequential file that contains at most four billion 32-bit integers in random order, find a 32-bit integer that isn’t in the file (and there must be at least one missing…why?). How would you solve this with unlimited main memory? How would you solve it if you could use several external files but only a few bytes of main memory?
- Rotate a one-dimensional vector of n elements left by i positions. For instance, with n=8 and i=3, the vector abcdefg is rotated to defghabc. Simple code uses an n-element intermediate vector to do the job in n steps. Can you rotate the vector in time proportional to n using only a few dozen extra bytes of storage?
- Given a dictionary of English words, find sets of anagrams. For instance, “pots”, “stop”, and “tops” are all anagrams of one another because each can be found by permuting the letters of the others.
- Write functions for the following date problems: given two dates, compute the number of days between them; given a date, return it’s day of the week; given a month and year, produce a calendar of the month as an array of characters
- Given a very long sequence (say, billions or trillions) of bytes, how would you efficiently count the total number of one bits? (i.e. how many bits are turned on in the entire sequence)
- Although Quicksort uses only O(logn) stack space on the average, it can use linear space in the worst case. Explain why, then modify the program to use only logarithmic space in the worst case.
- Write a program for finding the kth-smallest element in the array x[0…n-1] in O(n) expected time. Your algorithm may permute the elements of x.
- Build the fastest possible complete function to generate a sorted array of random integers without duplicates. (You need feel constrained to use any prescribed interface for set representation)
- Implement heap-based priority queues to run as quickly as possible; at what values of n are they faster than sequential structures?
