The title of the article sounds like epic fail, but in reality everything is not so simple. And in general, this story ended very positively, although not in Google. But that's a topic for another article. In the same article, I will talk about three things: how my preparation process went, how interviews at Google went, and why, in my opinion, everything is not as clear as it might seem.
History in brief
One cold Cypriot winter evening, the thought suddenly occurred to me that my knowledge of classical Computer Science is very far from even average, and something needs to be done about it. If, by the way, suddenly someone has not yet read why the evening is Cypriot and cold, then you can find out about it . After some thought, it was decided to start with an online course on algorithms and data structures. I heard about Robert Sedgewick's course on Coursera from one of my former colleagues. The course consists of two parts ( и ). If suddenly the links change, then you can always google by the name of the author. Each part 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 basic data structures, the main types of sorts and the complexity of algorithms. The second part is more advanced, starting with graphs and ending with things like Linear Programming and Intractability. After thinking about all of the above, I came to the conclusion that this is exactly what I need. Here, by the way, an inquisitive reader may ask, what does Google have to do with it. Indeed, up to this point, he had nothing to do with it at all. But I needed a goal, because doing 12 weeks in the evenings without a goal is somewhat difficult. And what could be the purpose of obtaining new knowledge? Of course, their application in practice. In everyday life, this is quite problematic, but at an interview in a large company, it’s easy. A quick google showed that Google (forgive 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 located in Zurich, Switzerland. So it's decided - we're learning and going to interview at Google.
Preparing for the first run
12 weeks passed quickly and I completed both courses. My impressions of the courses are more than positive, and I can recommend them to anyone interested. I liked the course for the following reasons:
- The lecturer speaks quite clear English
- The material is well structured
- Gorgeous presentations showing the insides of each algorithm
- Good selection of material
- Interesting exercises
- Exercises are automatically checked on the site, after which a report is generated
My work on courses usually went like this. For 1-2 days I listened to lectures. Then I took a quick test on knowledge of the material. The rest of the week I did the exercise in several iterations. After the first one, I received my 30-70%, the subsequent ones brought the result to 97-100%. The exercise usually consisted in the implementation of some algorithm, for example or .
After completing the courses, I realized that a lot of knowledge is a lot of sorrow. If before I just knew that I didn’t know anything, now I began to realize what exactly I didn’t know.
Since it was still only May, and I scheduled the interview for the fall, I decided to continue my education. After reviewing the requirements for the vacancy, it was decided to go in parallel in two directions: to continue studying algorithms and take a basic course in machine learning. For the first goal, I decided to switch from courses to a book and chose Steven Skiena's monumental work Algorithms. Development Guide” (The Algorithm Design Manual). Not as monumental as Knut's, but still. For the second goal, I went back to Coursera and signed up for a course by Andrew Ng (Andrew Ng) .
Another 3 months passed and I finished the course and the book.
Let's start with the book. Reading was quite interesting, although difficult. In principle, I would recommend the book, but not right away. Overall, 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 before, but I did not know what they were called. Also in the book there are a number of tales from the life of the author (War Story), which somewhat dilute the academic presentation. By the way, the second half of the book can be omitted, there is rather a description of the existing problems and methods for solving them. It is useful if it is regularly applied in practice, otherwise it will be forgotten immediately.
The course made me happy. The author clearly knows his stuff and makes it interesting. Plus, a fair part, namely linear algebra and the basics of neural networks, I remembered from the university, so I did not experience any special difficulties. The course structure is fairly standard. The course is divided into weeks. Every week at first there are lectures mixed with short tests. After the lectures, an assignment is given that needs to be done, sent, and it will be automatically checked. Briefly, the list taught in the course is as follows:
- cost function
- linear regression
- gradient descent
- feature scaling
- normal equation
- logistic regression
— multiclass classification (one vs all)
— neural networks
- backpropagation
- 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, the understanding of all these topics was present. After 2 years, almost everything was naturally forgotten. I recommend it to those who are not familiar with machine learning and want to get a good understanding of the basic things to move on.
First run
It was already September and it was time to think about the interview. Since submitting through the site is a rather disastrous business, I started looking for friends who work at Google. The choice fell on , since he was the only one I knew directly (albeit not personally). He agreed to hand over my resume, and soon I received an email from the recruiter offering to book a slot on his calendar for the first call. A couple of days later I got a call. We tried to communicate via Hangouts, but the quality was terrible, so we 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 “what is the complexity of inserting into a hash map”, “what balanced trees do you know”. Not difficult if you have a basic knowledge of these things. The screening went well and, based on the results, it was decided to organize the first interview in a week.
The interview was also via Hangouts. First, they talked about me for 5 minutes, then they moved on to the problem. The task was on graphs. I quickly figured out what to do, but chose the wrong algorithm. When I started writing code, I realized this and switched to another option, which I added. The interviewer asked several questions about the complexity of the algorithm, asked if it could be faster. Somehow I got stuck and couldn't. At this point, the time came and we said goodbye. Then, after about 10 minutes, it dawned on me that instead of Dijkstra's algorithm, which I used, in this particular problem, one could use breadth-first search, and it would be faster. After a while, the recruiter called and said that the interview as a whole went well and it would be necessary to arrange another one. Made an appointment for another week.
This time things got worse. If the first time the interviewer was friendly and sociable, then this time he was somewhat gloomy. I could not immediately figure out the problem, although those ideas that I gave out, in principle, could lead to its solution. In the end, after a few prompts from the interviewer, I came up with a solution. This time it turned out to be breadth-first search again, only from a few points. I wrote the solutions, kept within the time, but forgot about the boundary cases. After some time, the recruiter called and said that this time the interviewer was not satisfied, because in his opinion I needed too many tips (3 or 4 pieces) and I constantly changed the code while writing. Based on the results of two interviews, it was decided not to go further, but to postpone the next interview for a year, if I have such a desire. For the sim, they said goodbye.
And this story I made several conclusions:
- Theory is good, but you need to quickly navigate it
- Theory without practice will not help. It is necessary to solve problems and bring the writing of code to automatism.
- Much depends on the interviewer. And do nothing about it.
Preparing for the second run
After thinking about the situation, I decided to try again in a year. And slightly edited the goal. If earlier the main goal was to study, and the interview in Google was like a distant carrot, now passing the interview was the goal, and learning is the means.
So, a new plan was developed, which included the following points:
- Continue to study theory by reading books and articles.
- Solve algorithmic problems in the amount of 500-1000 pieces.
- Continue learning theory by watching videos.
- Continue to study theory through courses.
- Study other people's experiences with Google interviews.
The plan was completed by me in a year. Next, I will describe what exactly I did for each of the points.
Books and articles
I don’t even remember the number of articles I read, I read them both in Russian and in English. Probably the most useful site . 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 fall into the first place. This is theory. The rest is preparation for the interview. Sedgwick in the book tells about the same thing as in his courses. Just in writing. There is not much point in reading carefully if you have taken the course, but it is worth overlooking in any case. If you have not watched the course, then it makes sense to read it. Cormen seemed too boring to me. Mastered honestly with difficulty. Just took it out , and several rarely used data structures (Fibonacci heap, van Emde Boas tree, radix heap).
You should read at least one book to prepare for an interview. 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, solve problems and analyze solutions. Of these three, I would probably recommend Cracking the Coding Interview as the main one, and the rest are optional.
Algorithmic problems
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 have mainly used three: , и . On CodeChef, tasks are categorized by difficulty, but not by topic. On Hackerrank both in terms of difficulty and topics.
But as I immediately found out for myself, there is a more interesting way. And these are competitions (programming challenges or programming contests). All three sites provide them. True, there is a problem with LeetCode - an inconvenient time zone. Therefore, I did not participate in this site. Hackerrank and CodeChef provide a fairly large number of different competitions, lasting from 1 hour to 10 days. Different formats have different rules, well, you can talk about it for a long time. The main reason why competition is good is to introduce a competitive (and again a tautology) element into the learning process.
In total, I participated in 37 competitions on Hackerrank. Of these, 32 were rated and 5 were either sponsored (I even got $25 in one of them) or for fun. In the rankings, I was in the top 10% 4 times, in the top 11% 12 times, and in the top 5% 25 times. The best results were 27/1459 in the 3 hour and 22/9721 in the week.
I switched to CodeChef when competitions on Hackerrank became less frequent. In total, I managed to participate in 5 competitions. The best result was 426/5019 in the ten day competition.
In total, at competitions and just like that, I solved a little more than 1000 problems, which fit into the plan. Now, unfortunately, there is no free time to continue competitive activities, just as there is no goal for which non-free time can be written off. But it was fun. I recommend that those who are interested in this find like-minded people. Alone or in a group is much more interesting. I had fun with this with a friend, so maybe it went so well.
View video
After reading Skiena's book, I basically became interested in what he does. Like Sedgwick, he is a professor at the university. In this regard, on the network you can find videos of his courses. I decided to review the course . I can't say that I really liked it. First, the video quality is not very good. Secondly, I did not try to solve the problems discussed in the course. So the involvement was not very high.
Also in the process of solving problems, trying to find the right algorithm, I came across Tushar Roy's video. He worked at Amazon and now works at Apple. As I later found out for myself, he has , where he lays out an analysis of various algorithms. At the time of writing, the channel contains 103 videos. And I must say that the analysis in his performance is done very decently. I tried to watch other authors, but somehow it didn't work. So I can definitely recommend this channel for viewing.
Courses
I didn't really do anything here. I watched a video from Android Developer Nanodegree from Google and took a course from ITMO . Nanodegree is quite for itself, although I naturally did not learn anything new from there. The course from ITMO is a little crumpled in terms of theory, but the tasks were interesting. I would not recommend starting with it, but in principle, time was not spent on it in vain.
Learn from other people's experiences
Of course, a lot of people tried to get into Google. Some got in, some didn't. Some have written articles about it. Of the interesting things, I will probably note и . In the first case, a 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 Amazon, but it's not so important. The second manual was written by Google engineer Larisa Agarkova (). In addition to this document, you can also read .
It makes sense to read interview reviews on Glassdoor. They are all more or less similar, but you can get some useful information.
I will not provide links to other small articles, you yourself can perfectly find them on Google.
Second entry
And now a year has passed. He turned out to be very rich in terms of study. But I approached the new autumn with much deeper theoretical knowledge and well-developed practical skills. There were still a few weeks left until the end of the year allotted to me for preparation, when suddenly a letter fell into the mail from a recruiter from Google, in which he asked me if I still had a desire to work at Google and would you mind talking with him. Naturally, I didn't mind. We agreed to call in a week. I was also asked for an updated resume, to which I added a brief description of what I did during the year at work and in general.
After talking for a lifetime, we decided that in a week there would be a Hangouts interview, just like last year. A week passed, it was time for the interview, but the interviewer didn't show up. 10 minutes passed, I was already starting 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 a replacement was urgently found for him. The person 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 tricks are possible, how they can be bypassed. We discussed several different options for the problem, the complexity of the algorithm. Then we talked for another 5 minutes, the engineer told his impressions of working in Munich (in Zurich, they did not find an urgent replacement), and on that they parted.
On the same day, a recruiter contacted me and said that the interview went well and they were ready to invite me for an interview in the office. The next day, we phoned via Hangouts and discussed the details. Since I had to apply for a visa, we decided to schedule an interview in a month.
While preparing the documents, along the way I 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 specifics, I could not shake out of the recruiter. As far as I understand, this was introduced relatively recently and he himself was not very up to date. I was also signed up for two training sessions: how to pass an algorithmic interview and how to pass a System Design interview. The sessions were of medium usefulness. There, too, no one could tell me what they ask Android developers. So my preparation for this month boiled down to the following:
- Buying a whiteboard and writing 2-3 dozen of the most popular algorithms on it from memory. 3-5 pieces every day. In total, each was written several times.
- Refreshing the memory of various Android information that I do not use every day
- Watching a few videos about Big Scale and all that
As I said, in parallel I was doing the documents for the trip. To begin with, I was asked for data in order 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 deal with this. As it turned out, this is done by the Austrian consulate. Called and made an appointment. They asked for a bunch of documents, but nothing particularly interesting. Photo, passport, residence permit, a bunch of different certificates and, of course, an invitation letter. In the meantime, the letter did not arrive. As a result, I went with the usual printout and it worked quite well. The letter itself arrived another 3 days later, and the Cypriot FedEx could not find my address and I had to go for it myself. At the same time, I received everything in the same FedEx'e package, which they also could not deliver to me, because they did not find the address, and which had been there since June (5 months, Karl). Since I did not know about it, which is natural and did not assume that they have it. I received my visa on time, after which I was booked a hotel and offered flight options. I have adjusted the options to make it more convenient. There were no more direct flights, as a result, he 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. Arrived without incident. I traveled from the airport to the city by train - quickly and conveniently. After a bit of wandering around the city, I found a hotel and checked in. Since the hotel was booked without food, I dined next door and fell asleep, because the flight was in the morning and I already wanted to sleep. The next day I had breakfast at the hotel (for some money) and went to the Google office. In total, Google has several offices in Zurich. My interview was not in the central. And in general, the office looked quite ordinary, so I didn’t have a chance to look at all the goodies of the “normal” Google office. 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 supposed to take place. Actually, the plan included 3 interviews, lunch and 2 more interviews.
Interview number one
The first interview was just for Android. Moreover, it had nothing to do with algorithms at all. Surprise, however. Well, okay, so even more familiar. We were asked to make a certain UI component. First, we discussed what and how. He suggested making a decision in RxJava, described what exactly and why he would do it. They said that this is certainly good, but let's do it using the Android framework. And at the same time we will write the code on the board. And not just a component, but the entire Activity that uses this component. That's what I was not ready for. It’s one thing to write an algorithm for 30-50 lines on the board, and another thing is Android code noodles, even with abbreviations and comments like “well, I won’t write this, since it’s so obvious.” It turned out some kind of vinaigrette for 3 boards. Those. I solved the problem, but it looked dumb.
Interview number two
This time the interview was based on algorithms. And there were two interviewers. One is the actual interviewer, and the second is a young Padawan (shadow interviewer). It was necessary to come up with a data structure with certain properties. First, as usual, they discussed the problem. I asked different questions, the interviewer answered. After some time, they were asked to write several methods of the invented structure on the board. This time it was more or less successful, although with a few minor errors that I corrected at the prompt of the interviewer.
Interview number three
This time System Design, which suddenly also turned out to be Android. It was necessary to develop an application with a certain functionality. We discussed the requirements for the application, for the server, for the communication protocol. Next, I began to describe which components or libraries I would use when building an application. And then, at the mention of the Job Scheduler, there was some gagging. The bottom line is that I never used it in practice, because at the time of its release I just switched to supporting applications, where there were no tasks for using it. During the development of subsequent ones, it was the same. That is, in theory, I know what kind of thing it is, when and how it is applied, but there is no experience in using it. And the interviewer didn't seem to like it much. Then they asked me to write code. Yes, when developing an application, you immediately need to write code. Again Android code on the board. It turned out terrible again.
Dinner
Another person was supposed to come, but did not come. And Google has mistakes. As a result, I went to lunch with the previous interviewer, her colleague, and a little later the next interviewer joined. Lunch was pretty decent. Again, since this is not the main office in Zurich, the dining room looked fairly ordinary, though very pleasant.
Interview number four
Finally, algorithms in their purest form. I solved the first problem quite quickly and immediately effectively, though I missed with one boundary case, but at the prompt of the interviewer (he gave this very boundary case), I found the problem and fixed it. Of course, it was necessary to write the code on the board. Then a similar task was given, but more difficult. For her, I found a couple of suboptimal solutions and almost found the optimal one, 5-10 minutes were not enough to finish the thought. Well, I didn’t have time to write the code for it.
Interview number five
And again Android interview. I wonder why I studied algorithms all year long?
At first there were a few simple questions. Then the interviewer wrote the code on the board and asked them to look for problems in it. Found, explained, corrected. Discussed. And then some unexpected questions began in the spirit of “what does method Y do in class X”, “what does method Y do inside”, “what does class Z do”. Of course, I answered something, but then I said that I had not come across this in my work lately and naturally I don’t remember who, what and how is doing it in detail. After that, the interviewer asked what I was doing now. And the questions went on this topic. Here I already answered much better.
After the end of the last interview, they took away my pass, wished me luck and sent me on my way. I walked around the city a little, had dinner and went to the hotel, where I fell asleep, as the flight was again early in the morning. The next day I safely reached Cyprus. At the request of the recruiter, I wrote feedback on the interview and filled out a form in a special service for a refund of the money spent. Of all the expenses, Google only pays directly for tickets. Hotel, food and travel are paid by the candidate. Then we fill out the form, attach 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 results of the interview. After which I was informed that I was "a bit below the bar". That is to say, it did not hold out a little. To be more specific, 2 interviews went well, 2 did not go very well, and System Design did not go very well. Now, if at least 3 went well, then it would be possible to compete, but without a chance. They offered to come back in a year.
At first, of course, I was upset, because a lot of effort was spent on the preparation, and by the time of the interview, I already had the idea of leaving Cyprus. Getting Googled and moving to Switzerland seemed like a great option.
Conclusion
And here we come to the final part of the article. Yes, I failed the Google interview twice. It is sad. It would be interesting to work there. But, you can look at the matter from the other side.
- In a year and a half, I learned a huge amount of things related to software development.
- I had a lot of fun participating in programming competitions.
- I went to Zurich for a couple of days. When else will I go there?
- I had an interesting interview experience in one of the largest IT companies in the world.
Thus, everything that has happened in these one and a half years can simply be considered training, or training. And the results of this training made themselves felt. My idea to leave Cyprus matured (due to some family circumstances), I successfully passed several interviews in another well-known company and after 8 months I moved. But that's a completely different story. However, I think that I still have to thank Google for the year and a half that I worked on myself, and for 2 interesting days in Zurich.
What can I say in the end. If you work in IT, prepare yourself for an interview at Google (Amazon, Microsoft, Apple, etc.). Maybe someday you will go there. Even if you don’t want to, then believe me, you won’t get worse from such training. The moment you realize that you can (even if only with luck) get an interview at one of these companies, you will have many more roads open to you than before you started your preparation. And all you need along the way is a goal, perseverance and time. I wish you success 🙂
Source: habr.com