How to prepare for an interview in Google and not pass it. Twice
The title of the article sounds like an epic fail, but in reality everything is not so simple. And in general, this story ended very positively, though not in Google. But this is a topic for another article. In the same article I will talk about three things: how did my preparation process go, how did interviews go on Google, and why, in my opinion, things are not as straightforward as it may seem.
How it all began
One cold Cypriot winter evening I suddenly had the idea that my knowledge of classical Computer Science is very far from even medium, and something must be done with this. If, incidentally, someone else has not read why the evening is Cypriot and cold, you can find out about it here . After some reflection, it was decided to start an online course on algorithms and data structures. From one of my former colleagues I heard about the course Robert Sedgewick (Robert Sedgewick) on Coursera. The course consists of two parts ( part 1 and part 2). If suddenly the links change, you can always google by the name of the author. Each of the parts takes 6 weeks. At the beginning of the week, lectures are given, and during the week you still need to do exercises. The first part of the course covers the basic data structures, the main types of sorts and the complexity of the algorithms. The second part is more advanced, it starts with graphs and ends with such things as Linear Programming and Intractability. Having considered all the above, I came to the conclusion that this is exactly what I need. Here, by the way, an inquisitive reader may ask, but what’s the point with Google. And indeed, up to this point he had nothing to do with it. But I needed a goal, as it is somewhat difficult to practice for 12 weeks in the evenings without a goal. And what could be the goal in obtaining new knowledge? Of course, their application in practice. In everyday life, this is quite problematic, but during an interview with a large company easily. A quick googling revealed that Google (sorry for the tautology) is one of the largest companies in Europe (and I was considering Europe), in which such interviews are conducted. Namely, their office is in Zurich, Switzerland. So it is decided - we study and go to interview at Google.
Preparing for the first call
12 weeks passed unnoticed, and I finished both courses. My impressions of the courses are more than positive, and I can recommend them to anyone interested. I liked the courses for the following reasons:
- Lecturer speaks quite clear English.
- The material is well structured.
- Smart presentations showing the insides of each algorithm
- Competent selection of material
- Interesting exercises
- Exercises are automatically checked on the site, and then a report is generated.
My work on the courses usually took place as follows. For 1-2 days I listened to lectures. Then passed a quick test of knowledge of the material. The rest of the week did an exercise in several iterations. After the first one I received my 30-70%, the subsequent ones brought the result to 97-100%. Exercise usually consisted in implementation of any algorithm, for example Seam carving or bzip .
After completing the courses, I realized that a lot of knowledge means a lot of sadness. If earlier I simply knew that I did not know anything, now I began to realize that it was I who did not know.
Since it was still only May, and I had scheduled an interview for the autumn, I decided to continue my education. After reviewing the requirements for a job, it was decided to go in parallel in two directions: to continue the study of algorithms and complete a basic course on machine learning. For the first purpose, I decided to switch from courses to a book and chose the monumental work of Steven Skiena “Algorithms. Development Guide "(The Algorithm Design Manual). Not as monumental as Knut's, but still. For the second goal, I again went to Coursera and enrolled in the Andrew Ng Machine Learning course .
Another 3 months passed, and I finished the course and the book.
Let's start with the book. The reading turned out to be quite interesting, though not easy. In principle, I would recommend a book, but not like that right away. In general, the book gives a deeper analysis of what I learned in the courses. Plus, I discovered (from a formal point of view) such things as heuristics and dynamic programming. Naturally, I used to use them, but I did not know what they are called. Also in the book there is a number of tales from the life of the author (War Story), which somewhat dilute the academic character of the presentation. By the way, the second half of the book can be omitted; there goes rather a description of existing problems and methods for solving them. It is useful if regularly used in practice, otherwise it will be forgotten immediately.
The course more than pleased me. The author clearly knows his stuff and tells interesting. Plus, I remember the hefty part, namely linear algebra and the basics of neural networks, even from university, so I did not experience any particular difficulties. The course structure is fairly standard. The course is divided into weeks. Every week, first there are lectures mixed with short tests. After the lectures, an assignment is issued that needs to be done, sent, and it is automatically checked. In short, the course list is as follows:
- cost function
- linear regression
- gradient descent
- feature scaling
- normal equation
- logistic regression
- multiclass classification (one vs all)
- neural networks
- back propagation
- regularization
- bias / variance
- learning curves
- error metrics (precision, recall, F1)
- Support vector machines (large margin classification)
- K-means
- Principal Components Analysis
- anomaly detection
- collaborative filtering (recommeder system)
- stochastic, mini-batch , batch gradient descents
- online learning
- map reduce
- ceiling analysis
After completing the course, an understanding of all these topics was present. After 2 years, almost everything was naturally forgotten. I recommend those who are not familiar with machine learning and want to get a good understanding of basic things to move on.
First run
It was already September in the courtyard and it was time to start thinking about the interview. So how to get through the site business is quite deadly, I started looking for friends working in Google. The choice fell on datacompboy, because he was the only one I knew directly (though not personally). He agreed to send my resume, and soon I received a letter from the recruiter, offering to reserve a slot in his calendar for the first conversation. A phoned after a couple of days. Tried to communicate through Hangouts, but the quality was terrible, so they switched to the phone. First, we quickly discussed the standard how, why, and why, and then moved on to technical screening. It consisted of a dozen questions in the spirit of "how difficult it is to insert into a hash map," "what kind of balanced trees do you know." Not difficult if there is a basic knowledge of these things. The screening went well and decided to organize the first interview in a week.
The interview was also via Hangouts. At first, they talked about 5 minutes about me, then they moved on to the puzzle. The task was on the graphs. I quickly realized what had to be done, but I chose the wrong algorithm. When I started writing the code I realized this and switched to another option, which I added. The interviewer asked a few questions on the complexity of the algorithm, asked if it could be faster. I somehow blunted and could not. At that time came out and we said goodbye. Then, in about 10 minutes, it dawned on me that instead of the Dijkstra algorithm that I used, it would be possible to use search width in this particular task, and that would be faster. After a while, the recruiter called and said that the interview as a whole went well and we should organize another one. Agreed on in another week.
This time things got worse. If for the first time the interviewer was friendly and sociable, then this time some kind of gloomy. I could not immediately see the problem, although those ideas that I gave out in principle could lead to its solution. In the end, after several interviewer prompts, the decision reached me. This time it again turned out to be a search in width, only from a few points. I wrote the solutions, I did it in time, but I forgot about boundary cases. After some time, the recruiter called and said that this time the interviewer was not happy, because in his opinion I needed too many prompts (3 or 4 pieces) and I constantly changed the code while writing. According to the results of two interviews, it was decided not to go any further, but to postpone the next interview for a year, if I have such a desire. Behind this and said goodbye.
And I made several conclusions from this story:
- The theory is good, but it must quickly navigate
- The theory without practice will not help. It is necessary to solve the problem and bring the writing of the code to automatism.
- Much depends on the interviewer. And nothing can be done about it.
Preparing for the second call
After thinking about the situation, I decided to try again in a year. And slightly edited the target. If before the main goal was to study, and an interview at Google as a distant carrot, now the passage of the interview was the goal, and study as a means.
So, a new plan was developed, which included the following items:
- Continue to learn the theory by reading books and articles.
- Solve algorithmic problems in the amount of 500-1000 pieces.
- Continue to learn the theory by watching the video.
- Continue to learn theory through courses.
- Learn the experience of other people in passing interviews at Google.
The plan was completed by me for the year. Then I will describe what I did for each of the points.
Books and Articles
I don’t even remember the number of read articles, I read them both in Russian and in English. The most useful site was probably this one . Here is a description of a large number of interesting algorithms with code examples.
I read 5 books: Algorithms, 4th edition (Sedgewick, Wayne), Introduction to Algorithms 3rd Edition (Cormen, Leiserson, Rivest, Stein), Cracking the Coding Interview 4th edition (Gayle Laakmann), Programming Interviews Exposed 2nd edition (Mongan, Suojanen , Giguere), Elements of Programming Interviews (Aziz, Lee, Prakash). They can be divided into 2 categories. The books of Sedgwick and Cormen get into the first one. This is a theory. The rest is preparation for the interview. Sedgwick in the book tells about the same thing as in his courses. Just in writing. It makes little sense to read carefully if you have completed the course, but it’s worth a look anyway. If the course is not watched, then it makes sense to read. Kormen seemed to me too boring. I mastered to be honest with difficulty. Made out only master theorem, and a few rarely used data structures (Fibonacci heap, van Emde Boas tree, radix heap).
An interview preparation book is worth reading at least one. They are all built on the same principle. They describe the interview process in large technology companies, give basic things from Computer Science, tasks for these basic things, solving problems and analyzing solutions. Of these three, I would probably recommend Cracking the Coding Interview as the main one, and the rest at will.
Algorithmic tasks
This was probably the most interesting point of preparation. You can, of course, sit down and stupidly solve problems. There are many different sites for this. I basically used three: Hackerrank , CodeChef and LeetCode . At CodeChef, tasks are broken down by complexity, but not by topic. On Hackerrank and in complexity, and by topic.
But as I immediately found out for myself, there is a more interesting way. And this competition (programming challenges or programming contests). All three sites provide them. The truth with LeetCode is a problem - an inconvenient time zone. Therefore, I did not participate on this site. Hackerrank and CodeChef provide a fairly large number of different competitions, ranging from 1 hour to 10 days. Different formats have different rules, but you can talk about it for a long time. The main point why competition is good is the introduction of a competitive (and again tautology) element into the learning process.
In total, I participated in 37 competitions at Hackerrank. Of these, 32 were rated, and 5 or sponsored (I even received $ 25 in one of them) or fan. In rating I entered the top 4% 10 times, 11 times the top 12% and 5 times the top 25%. The best results were 27/1459 in the 3-hour and 22/9721 in the week.
I switched to CodeChef when competitions started to be less frequent at Hackerrank. In total, I managed to participate in 5 competitions. The best result was 426/5019 in a ten-day competition.
In total, at competitions and just like that, I solved a little more than 1000 tasks that fit into the plan. Now, unfortunately, there is no free time to continue competitive activities, just as there is no goal for which unfree time can be attributed. But it was fun. I recommend those who are interested in this, find like-minded people. Together or group is much more interesting. I enjoyed it with a friend, so it could have gone so well.
View video
After reading the book Skieny, I basically became interested in what he was doing. Like Sedgwick, he is a university professor. In this regard, in the network you can find videos of his courses. I decided to view the COMP300E - Programming Challenges - 2009 HKUST course . I can't say that I liked it a lot. First, the quality of the video is not very. Secondly, I did not try to solve the problems that I deal with in the course myself. So the involvement was not very high.
Also in the process of solving the problems, trying to find the right algorithm, I ran across the video Tushar Roy. He worked at Amazon, and now works at Apple. As I later found out for myself, he has a YouTube channelwhere he puts the analysis of various algorithms. At the time of this writing, the channel contains 103 videos. And I must say that the analysis in its execution is done very well. I tried to watch other authors, but somehow did not go. So this channel definitely can be recommended for viewing.
Passing courses
I didn’t really do anything here. I watched a video from Google's Android Developer Nanodegree and completed a course from ITMO How to Win Coding Competitions: Secrets of Champions . Nanodegree is quite self, although I naturally did not learn anything new from there. The course from ITMO in terms of theory is a bit crumpled, but the problems were interesting. I would not recommend starting with him, but in principle, time was not wasted on him.
Examine other people's experiences
By itself, many people tried to get into Google. Someone got someone not. Some have written articles about it. Of the interesting things I will probably note this one and this one . In the first case, the person has prepared for himself a list of what he needs to learn in order to become a Software Engineer and get into Google. He ended up in the Amazon, but this is not so important. The second manual was written by a Google engineer, Larisa ( Larrr ). In addition to this document, you can also read her blog .
It makes sense to read reviews on interviews on Glassdoor. They are all more or less similar, but you can get some useful information.
Links to other small articles I will not give, you yourself can perfectly find them on Google.
Second run
And a year has passed. He was very rich in terms of study. But I approached the new fall with much deeper theoretical knowledge and practical skills. There were still a few weeks left until the end of the
After talking for life, they decided that in a week there will be a Hangouts interview, just like last year. A week has passed, the time has come to interview, but the interviewer did not appear. It took 10 minutes, I already started to get nervous, when suddenly someone broke into the chat. As it turned out a little later, for some reason my interviewer could not appear and he was immediately found a replacement. The man was somewhat unprepared, both in terms of setting up a computer, and in terms of conducting an interview. But then everything went well. I solved the problem quickly, described where the dirty tricks are, how to get around them. We discussed several different variants of the problem, the complexity of the algorithm. Then we talked for another 5 minutes, the engineer told us about his impressions of working in Munich (they didn’t find an urgent replacement in Zurich), so they parted.
On the same day, the recruiter contacted me and said that the interview went well and they are ready to invite me to the office for an interview. The next day, phoned through the Hangouts and discussed the details. Since I needed to do a visa, we decided to schedule an interview a month later.
While I was preparing the documents, I simultaneously discussed the upcoming interview with the recruiter. A standard Google interview consists of 4 algorithmic and one System Design. But, since I was working as an Android developer, I was told that part of the interview would be with Android specifics. What exactly and what will be the specificity of the recruiter I could not shake out. As I understand it, it was introduced relatively recently and he himself was not very up to date. I was also recorded for two training sessions: how to pass an algorithmic interview and how to pass a System Design interview. Sessions were of moderate utility. There, too, no one could tell me what the Android developers are asking. Therefore, my training this month has been reduced to the following:
- Buying a marker board and writing 2-3 dozens of the most popular algorithms on it from memory. 3-5 pieces every day. Total each has been written several times.
- Refresh in the memory of different information on Android, which I do not use every day
- Watching a few Big Scale videos and all that.
As I said, in parallel, I did the documents for the trip. To begin with, I was asked for the data to make an invitation letter. Then I tried for a long time to find out who in Cyprus makes visas to Switzerland, since the Swiss Embassy does not do this. As it turned out, this is the consulate of Austria. I called and made an appointment. They requested a pack of documents, but nothing particularly interesting. Photo, passport, residence permit, a bunch of different certificates and of course an invitation letter. The letter, meanwhile, did not come. In the end, I went with the usual printout and it is quite a ride. The very same letter came another day after 3, and the Cypriot FedEx was unable to find my address and had to go after him. At the same time I received a package in the same FedEx, which they could not deliver to me either, because they did not find the address, and which has been lying there since June (5 months, Karl). Since I did not know about her, I naturally didn’t assume that they have it. I got a visa on time, after which I booked a hotel and offered flight options. I corrected the options to make it more convenient. There were no direct flights, as a result, flew there through Athens, and back through Vienna.
After all the formalities with the trip were settled, a few more days passed and I actually flew to Zurich. Got no adventures. From the airport to the city I rode the train - quickly and conveniently. A little strayed around the city found a hotel and settled. Since the hotel was booked without food, I dined in the neighborhood and fell asleep, because the flight was morning and I wanted to sleep. The next day I had breakfast at the hotel (for some money) and went to the Google office. Just in Zurich, Google has several offices. My interview was not central. And in general, the office looked fairly normal, so I didn’t have a chance to look at all the buns of the “normal” Google office. I registered with the administrator and sat down to wait. After some time, the recruiter came out and told me the plan for the day, after which he took me to the room where the interviews were to take place.
Interview number one
The first interview was on Android. And in general, there was no connection with the algorithms. Surprise, however. Well, okay, so even familiar. Asked to make a specific UI component. We first discussed what and how. He proposed to make a decision on RxJava, described what exactly and why would have done. They said that this is certainly good, but let's do it using the Android framework. And at the same time write the code on the board. And not just a component, but the whole Activity using this component. I was not ready for this. It's one thing to write an algorithm of 30-50 lines on the board, and another thing is Android code noodles, even with abbreviations and comments in the spirit of "well, I won't write this, as it is obvious." It turned out some kind of vinaigrette on 3 boards. Those. I solved the problem, but it looked dumb.
Interview number two
This time the interview was on algorithms. And there were two interviewers. One is the interviewer, and the second is the young Padawan (shadow interviewer). It was necessary to invent a data structure with certain properties. First, as usually discussed the problem. I asked different questions, the interviewer answered. After some time, they asked me to write several methods of the invented structure on the board. This time, more or less succeeded, though with a few minor errors, which I corrected from the interviewer's prompts.
Interview number three
This time System Design, which suddenly turned out to be Android. It was necessary to develop an application with a specific functionality. We discussed the requirements for the application, to the server, to the communication protocol. Then I began to describe which components or libraries I would use when building the application. And then at the mention of the Job Scheduler there was some gag. The bottom line is that I never used it in practice, because at the time of its release I just switched to application support, where there were no tasks to use it. In the development of the subsequent was the same. That is, in theory, I know what this thing is, when and how it is applied, but there is no experience in applying it. And the interviewer didn’t seem to like it much. Then they asked me to write the code. Yes, when developing an application, you need to write code right away. Again, the Android code on the board.
Dinner
Another person had to come, but did not come. And there are google bugs. As a result, I went to dinner with the previous interviewer, her colleague, and a little later the next interviewer joined. The dinner was quite decent. Again, since this is not the main office in Zurich, the dining room looked quite ordinary, although very nice.
Interview number four
Finally, pure algorithms. I solved the first problem fairly quickly and immediately efficiently, though I missed with one boundary case, but at the prompting of the interviewer (he gave this very boundary case) I found the problem and fixed it. Needless to have to write code on the board. Then a similar task was given, but more difficult. For her, I found a couple of non-optimal solutions and almost found the optimal one, it took 5-10 minutes to finish the thought. Well, I did not have time to write the code for it.
Interview number five
Android interview again. I wonder why I taught algorithms all year?
At first there were a few simple questions. Then the interviewer wrote a code on the board and asked him to find problems in it. Found, explained, corrected. Discussed. And then a few unexpected questions started in the spirit of “what does class Y do in class X”, “what’s inside method Y do”, and what class Z does. Of course, I answered something, but then I said that I haven’t come across this lately, and naturally I don’t remember who is doing what and how. After that, the interviewer asked what I was doing now. And the questions went on this topic. Here I have already answered much better.
After the last interview I was taken a pass, wished me luck and sent me back home. I walked around the city for a while, had dinner and went to the hotel, where I fell asleep, as the flight was again early in the morning. The next day, safely reached Cyprus. I wrote a request for an interviewer at the request of the recruiter and filled out a form for the return of the money spent in a special service. Of all the expenses, Google only pays for tickets directly. Hotel, food and travel are paid by the candidate. Then we fill in the form, attach the checks and send it to a special office. They process it and quickly transfer money to the account.
It took a week and a half to process the interview results. After that I was informed that I was "a bit below the bar". I mean, I did not reach it. More specifically, 2 interviews went well, 2 were not very good, and System Design was not very good. Now, if at least 3 went well, then it would be possible to fight, and so no chance. They offered to come in a year.
At first, I was upset, of course, since a lot of energy was spent on the preparation, and by the time of the interview I had the thought of leaving Cyprus. Applying to Google and moving to Switzerland seemed like a great option.
Conclusion
And here we come to the final part of the article. Yes, I haven’t twice been interviewed by Google. It is sad. It would probably be interesting to work there. But, you can look at the case from the other side.
- For a year and a half, I learned a huge amount of things related to software development.
- I got a lot of pleasure participating in programming competitions.
- I went for a couple of days to Zurich. When will I get out there?
- I got an interesting interview experience in one of the largest IT companies in the world.
Thus, everything that happened during these one and a half years can simply be considered as training, or training. And the results of this workout made themselves felt. My idea to leave Cyprus has matured (for some family circumstances), I successfully passed several interviews to another well-known company and after 8 months moved. But that's another story. Nevertheless, I think that I still need to thank Google for the one and a half years that I have been working on myself, and for 2 interesting days in Zurich.
What can I say at the end. If you work in IT, prepare yourself for an interview at Google (Amazon, Microsoft, Apple, etc.). Maybe someday you go there to get there. Even if you do not want, then believe me, you will not get any worse from such preparation. At the moment when you realize that you can (even if only under luck) pass an interview at one of these companies, you will have many more roads before you than before starting your preparation. And all you need on the way is goal, perseverance and time. I wish you success :)