I want to work at Google! Telephone interview (part 1)

Hi Habr! I have not written for a long time. Yes, this is understandable. Thesis defense, PhD, and now also an active job search - all this takes a lot of precious time. But the conversation today is not about that. I would like to share with you, dear habraradi, resources and a description of the process of preparing for a telephone technical interview with Google, the first technical stage of which I have already passed, and now I am preparing for the second, which will be on Friday.

The post structure will be as follows:

1. Topics and sources of information that the recruiter advised to read
2. Technical tasks and their solutions in C / C ++ and Python
3. Transcript of my real interview (Google was asked not to publish these materials)

Topics and sources of information

I wondered for a long time whether to leave the English version of the text. But fearing to be zaklevanom in place - I decided to translate everything into Russian. So, these are topics that an engineer can talk to when talking to you:

• Google products (what you use)
• Programming skills, you will be asked to write a code using Google Doc (telephone interview) or on the blackboard (the last stages of the interview at the company's office). Update your syntax memory languages ​​and standard libraries
• Algorithm Design and Analysis
• System design
• Open discussion, do not forget to think out loud and clarify the details of the problem that you asked

')
Programming:

• create / pass data structures
• implement system calls (implement system routines)
• folding large amounts of data to a single number
• converting one data type to another

Algorithm Design / Analysis:

• big-O analysis (asymptotics, algorithm complexity)
• sorting and hashing, searching
• control with a huge amount of data
• and analysis of the complexity of those from the "Programming" above

System Design:

• feature set
• interfaces
• class hierarchy
• system design under certain conditions
• simplicity and reliability
• compromises

Open discussion

• describe the most difficult test you have encountered
• best / worst design you've ever seen
• performance analysis and optimization
• testing
• ideas for improving google products

References:
Interviewing at Google

Google products - http://www.google.com/intl/en/options/

Posts (all in English):

• The Official Google Blog: Gretta Cook (Google Engineer)
• How to Get Hired by Steve Yegge (Google Engineer)
• How to Get Hired by Dan Kegel (Google Engineer)
• Five Essential Phone Screenshot Questions by Steve Yegge (Google Engineer)
• Binary Search - Binary Search
• Tasks for practice programming - Project Euler
• Google asks: Top Coder Tutorials
• Industry News: search engine land

Books:
Book number 2 was recommended by several engineers and very representatively shows the questions that you will be asked.

1. Review of Basic Algorithms: Anany Levitin
2. Types of coding questions Google asks: Programming Interviews Exposed; Secrets to Landing Your Next Job (Programmer to Programmer) by Noah Suojanen, and Eric Giguere

(from myself: I read both books. Even if you do not plan to apply for a job at Google, but program at least sometimes, read these books just for yourself.)

One of the engineers gave a brief overview of the topics asked by the Software Engineer during the interview (some are duplicated with the previously mentioned ones)

1. The complexity of the algorithms. Need to know a lot about. If you have problems with basic analysis of algorithms - almost guaranteed you will not hire. More information about the algorithms
2. Coding. You should know at least one programming language very well, and better if it is C ++ or Java. C # will also fit, because it is similar to java. Expect that you will write code during the interview and you will need to know the particular syntax of the language.
3. A highly recommended book for reading: Programming Interviews Exposed; John Monagan and Noah Suojanen ( Wiley Computer Publishing )
4. • System design
   • Google file system
   • Google bigtable
   • Google MapReduce
5. Sorting. Know how to sort. Do not try to sort the bubbles. You need to know at least one n * log (n) sorting algorithm, and preferably two or more (suitable for quicksort and merge sort)
6. Hashing Not just considered one of the most important ways to store data structures. You need to know how the hash works. Know how to write it using the language of your choice within 5-20 minutes.
7. Trees Know what it is, basic constructions, passage and manipulations with them. Familiarize yourself with binary, n-ary and tertiary trees. Know at least one type of balanced binary tree: a red / ebony, a splay tree, or an AVL tree. Know how to create it and walk through it in depth (DFS) and width (BFS), know the difference between inorder, postorder and preorder pass.
8. Counts. Very important for Google. There are a total of 3 main ways to represent a graph in memory: objects and pointers, a matrix, and a series of links (adjacency list). Know the advantages and disadvantages of these ways of presenting graph data. Know the basic algorithms for the passage of the graph: in depth (DFS) and in width (BFS). Know the complexity of these algorithms, and how to write them in your programming language. Check out the Dijkstra and A * algorithms
9. Other data structures. Examine as many other data structures and algorithms as possible. You should be familiar with known NP-complete problems, such as traveling traveling salesman (TSP) and knapsack problem. Recognize these tasks in others or convert this task to known ones. Learn what the NP-complete (NP-complete) task means.
10. Maths. Some examiners ask puzzles from the basics of discrete mathematics. This is more common in Google than in other companies because we are surrounded by counting problems, calculating probabilities, and other mathematical puzzles. Update your knowledge and skills of combinatorial computing and finding probabilities, sampling, etc.
11. Operating Systems. Be aware of the processes, threads, and competition issues. Know about locks, mutexes, semaphores and monitors, and how they work. Know about deadlock and livelock situations, and how to avoid them. Know what resources the process needs, threads, how context switching works, how it is implemented based on the operating system and hardware. Know about schedules. And as the world moves toward multi-nuclear, learn about it as much as possible.
12. for information on system design

In the next part we will talk about specific tasks and their implementations in C, C ++ and Python.