February 5, 2012 at 20:59

I want to work at Google! Telephone Interview (Part 1)

    Hi Habr! I haven’t written for a long time. Yes, this is understandable. Defense of the dissertation, obtaining a PhD, and now also an active job search - all this takes a lot of precious time. But the conversation today will not be about that. I would like to share with you, dear habra people, 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'm preparing for the second, which will be on Friday.

    The structure of the posts will be as follows:
    1. Topics and sources of information recommended by the recruiter
    2. Technical problems and their solutions in C / C ++ and Python
    3. Transcript of my real interview (From Google asked not to publish these materials)


    Topics and sources of information



    I wondered for a long time whether to leave a version of the text in English. But fearing to be pecked on the spot, he decided to translate everything into Russian. So, these are the topics that an engineer can touch upon when communicating with you:
    • Google Products (what you use)
    • Programming skills, you will be asked to write the code using Google Doc (telephone interview) or on the board (the last stages of the interview at the company office). Update your syntax memory for 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 were asked


    Programming:
    • creating / passing data structures
    • implement system routines
    • collapse large data sets to singular
    • conversion of one data type to another


    Algorithm Design / Analysis:
    • Big-O analysis (asymptotic behavior, algorithm complexity)
    • sorting and hashing, search
    • management with insanely huge amount of data
    • and complexity analysis topics from "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 seen
    • performance analysis and optimization
    • testing
    • ideas for improving google products


    Links:
    Interviewing at Google

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

    Posts (all in English):


    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: Introduction to the Design and Analysis of Algorithms by Anany Levitin
    2. Types of coding questions Google asks: Programming Interviews Exposed; Secrets to Landing Your Next Job (Programmer to Programmer) by John Mongan, Noah Suojanen, and Eric Giguere

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

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

    1. The complexity of the algorithms. Need to know the big-Oh. If you have problems with basic analysis of algorithms - you are almost guaranteed not to be hired. More information about algorithms
    2. Coding. You should know at least one programming language very well, and it is better if it is C ++ or Java. C # will also work, because It is similar to Java. Expect you to write code during the interview and will need to know the syntax of the language.
    3. A highly recommended reading book: Programming Interviews Exposed; Secrets to landing your next job by John Monagan and Noah Suojanen ( Wiley Computer Publishing )
    5. Sorting. Know how to sort. Do not try to do sorting with bubbles. You need to know at least one n * log (n) sorting algorithm, or better two or more (quicksort and merge sort will do)
    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. The trees. Know what it is, basic structures, passage and manipulations with them. Explore binary trees, n-ary and tertiary trees. Know at least one type of balanced binary tree: red / ebony, a splay tree, or AVL tree. Know how to create it and go through it in depth (DFS) and in width (BFS), know the difference between inorder, postorder and preorder pass.
    8. Counts. Very important for Google. In total there are 3 main ways to represent a graph in memory: objects and pointers, a matrix and a sequence of links (adjacency list). Know the advantages and disadvantages of these graph presentation methods. Know the basic graph passing algorithms: in depth (DFS) and wide (BFS). Know the complexity of these algorithms, and how to write them in your programming language. Check out Dijkstra and A * algorithms
    9. Other data structures. Explore as many other data structures and algorithms as possible. You should be familiar with well-known NP-complete problems, such as traveling salesman (TSP) and knapsack problem. Recognize these tasks in others or transform the given task to known. Find out what an NP-complete task means.
    10. Maths. Some examiners set tasks from the basics of discrete mathematics. This is more common on Google than other companies because we are surrounded by counting problems, calculating probabilities, and other math puzzles. Update your knowledge and skills of combinatorial computation and finding probabilities, sampling, etc.
    11. Operating Systems. Be aware of 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 a process needs, threads, how context switching works, how it is based on the operating system and hardware. Be aware of schedules. And as the world moves toward multi-nuclearity, learn about it as much as possible.
    12. for information about System Design


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

    Also popular now: