My Google Interview Experience [Questions, Process]
Tarandeep Singh
What gives you Joy? If you are a passionate programmer your answer would differ from the masses : Concatenating “J”+”o”+”y”. And that’s what Google is hunting for.
Within a decade of its existence, Google has become one of the most respected and Innovative company of the modern times. Today we use the word “Google it” synonymous to “search it” on the web and even call it “God of the Internet”, which is in fact true: God controls the life forms, teaches them to adapt, learn, evolve and expand. Google is doing exactly that for the Internet.
I don’t exactly recall since when, but as far as I remember, it was a dream workplace for me. I’m fascinated by every aspect of Technology, but Google stacks on the Top. Apart from the famous lavish food, facilities, there’s something unique about this company. They give their developers 20% of the time to innovate and expediate new ideas.
Google’s corporate culture is based on hiring really smart people, giving them responsibilities, letting them know what problems the company thinks it should focus on, then letting them figure out how to tackle it.
Having worked with Top 100 Fortune companies as a Java Developer for years, I’ve loved the independence but complained about the culture. Something was missing all these years along. We, the developers, are free to use our own recipe but the end product is always of the company’s taste, in other words, driven by business. And Google is the only brand (that I know of) that lets you experiment with tastes.
A month back, I received a call from a random consultant who found me suitable to appear for an Google Interview. We agreed upon a date to kickstart the process.
For years, I’ been applying through their job portal and everytime I used to get same polite reply: “Thanks for showing interest in bla bla, Unfortunately we couldn’t find an appropriate job profile bla bla.”
That made me wonder: No Positions for Java developers, are you serious?
Going by the facts, Google gets around 10 Million Job applications every year, shortlists several thousands and recruits 2-3% from shortlisted ones, on an average. On one random note: my consultant told me that they referred 300 candidates for interview in last 4 months, and there was only 1 who made through the complete process.
Note: This is my Google India Interview Experience. However, the recruitment process is almost identical in all respects, across the world. The purpose here is to help the Scientist in you sharpen up and step up to Google.
Also, If at any time you get bored, you can jump to the last section: “What you should Learn from this Experience”
The Screening
Hardly a day or two passed, and I had the first tele-conversation with Google. Unlike others, these guys were extraordinarily smart and manipulative. We kicked off discussion with my past, present projects followed by some typical Puzzles. They riddled me two geeky ones, which took me a while to get hold on to. The first one was to do with the Graphing depth and width analysis and second was more about judging the optimal solution for a real case Ordering (not sorting) scenario, I suggested a O(n^2) [Big Oh n square] solution wasn’t the best but, worked fairly well.
Then we moved on to core programming concepts. We touched base on OOPs: The questions revolved around maintainability, scalability and performance aspects of Object oriented vs. Scripting and Object-based languages. Without dedicating much time on it, we jumped into something Google loves to play-with: Data-Structures. They made me to code my own implementation of doubly LinkedLists, Binary Tree and speak out loud. Now, that was weird, I can’t dictate code, especially on a phone. But I can think why that makes sense in real life.
While I was almost mid-way there, trying to explain the BinaryTree implementation, they interrupted, “When are you available?”, and I replied instantaneously, “Whenever you want me to”. “Alright, walk down to Google campus on xx date & xx:xx time, we’ll be sending you an email with the details” and it was over. I couldn’t believe it, I had just cleared the first hurdle. Things were very easy so far.
The Google Approach
A Normal day-2-day development tasks doesn’t involve designing own data-structures, and sorting, searching algorithms, especially, when you work for a Big firm. On the inside, things are slower, more qualitative and process oriented where we try to restrict ourselves to APIs, 3rd party libraries.
Barely 5 days were left for the Face-2-Face round, and I knew I needed to recall everything I’ve mingled with in the past.
Unlike other interviews you would appear for, Google stresses on your programming logic, thought process but never encourages use of inbuilt Language APIs. Of course they do judge analytical, and problem solving skills, but algorithms are rated much higher. Generally speaking, their interview questions remain language-agnostic. They would start by giving you a fairly easy problem and then, perhaps, dig deeper and deeper till the time you start to suffocate. However, they don’t expect you to be “perfect”, that’s why they give occasional hints. Such situations incur when they believe you are headed in the right direction.
The single-most Important word I can ask you to Remember for a Google interview: Optimal — Almost every algorithm you would write down will have to be optimized more and more till you get something really efficeint — Efficient enough to handle Google-level transactions.
I prepared not so well coz I had some ETAs to meet (with my current company). I spent a day or two going through the algorithms, especially, all the popular sorting ones and all data-structures.
However, the mistake I made came back as a boomerang and hit me Hard: I didn’t not practice any of that on-paper. I thought I could comfortably execute their internal in my head and hence skip wasting time on writing and practicing them. But, I was so wrong.
The Encounter
Finally, the day arrived, and I was all set for the amuzements of Google Interview Process. The campus, as expected, had a different feel. The work area was a lot more cooler than the ones I had been working in. There were some fantastic relaxing couches placed all over the work area, on which, one could sleep or take mechanical massage while at work. Not to forget, there were pool tables, play areas, a lavish pantry, custom-decorated cubicles side-by-side. The working spirit definitely would be phenomenal.
After waiting in the lobby for about 10 minutes, I was moved to a conference room where the things were about to get started. The first round was conducted by two young programmers who were certainly of my age. They were kind, polite and keen observers. Throughout our conversation, they were taking heavy notes on their laptops, which of course made me bit nervous during the initial stages. It was as if they were recording my every move. But soon after it alls tarted, I could ignore it without a glitch.
The first problem they put me into directly involved a board and a marker. The scenario was laid down and I was asked to design/architect a solution for it. It wasn’t hard, it was just a 3-tier transactional system with a traditional RDBMS storage. I did some block diagrams, and class diagrams to explain how that system could work. Then they came down to the real thing : Optimizations. “What would you do if this system receives Millions of hits every second”. Earlier, I was singing songs around “let J2ee application clusters do the magic” but, when they said “Millions in a second”, I knew they wanted me to come out of it and provide an alternate efficient solution, something beyond traditional j2ee apps can scale.
Based on the scenario, I insisted (and designed) use of distributed object caches (memcache in particular) and highlighted key areas it would touch in the application (and talked about no single points of failures), followed by usage of Denormalized databases with large store of key-value pairs (talked about Google’s BigTable). After digging in for a while and throwing some more solutions, I stopped for a second to see affirmations: if I was heading in the right direction. Damn! they were numb. I thought they wanted me to optimize the VM usage, so I jumped into VM performance tuning. (This is a very vast topic, but I kind of kept it brief, yet, clearly explaining everything). But they were still the same: numb and the other person was still taking down notes.
It was much later in the interview that I realized that they always have “same kind of numbness” no matter how well you answer them back. Strange, but, that’s their trick for benchmarking your confidence. Don’t lose it over their numbness. (But this was not the case with next rounds, so I guess it was an individual strategy)
Next, it was showtime for some string searching, of course without using any of the inbuilt APIs. They give me a chunk of data and another random chunk that needs to be searched for. Can be called as a needle in a haystack but was tricky. I could only play with characters with loops, etc, with no usage of any kind of String/Regex API. I wrote down a snippet that would complete the task, but they wanted me to “Optimize” it. I thought and took 5-10 minutes, I proposed several solutions, but none of them were “optimal enough” (n Log n), they always wanted more. I was not able to give them the “optimal solution” they expected but it worked fairly well and the confirmed solution was fair enough.
Followed by that were some programming puzzles with chessboard where I had to just explain the algorithms for the problems I was put into.
The whole thing lasted for an hour and a half, and All the time I was on the white baord. woof!
Who needs Telepresence, when you got Google?
After completion, I was given a 5 minutes break in which I was free to take lunch/food, but I all I had was water as my throat had dried up. Then I moved back to the same conference room until the next interviewer appeared on the screen.
Yes, it was a video conference.
They don’t use Cisco’s telepresence but, the experience was very similar. The video was kind of 720p, pixelated and projected to a large screen, bigger than the life-size. From what I could see it was a Linux box running a full fledged video conferencing application decoding and encoding video in the realtime, could be something proprietary, I don’t know.
This time I was given few new problems: some were just algorithmic or just conceptual and for others I had to write some code snippet. Most questions were pretty good and I was able to give good-enough solutions.
The problem is, its hard to understand “how good” is considered “Good”, interviewer would rarely leave an indication. What I learned was if the question is conceptual, you are better off with providing an answer which showcases your in-depth knowledge of the topic. (Seriously, Google craves for it). And with programming/algorithmic questions if you mange to solve the problem and then able to optimize to a certain degree, you are good enough. They don’t expect you to write the perfect code that is the most optimal, but they do want to drill you to the point you give-up, this gives them the exact capability of the individual.
This videoconf was with relatively higher people in the Management: Project Mangers or essentially Software Development Managers. It wasn’t hard to guess that from those experienced faces sitting on the other side of the country.
For some of you it might sound a little odd, but its kind of culture I’m used to: Technical Managers. They are less people’s managers and are more of just another developer — They code, they deliver, they fix. They exist to help and motivate developers, provide ideas and moderate all the technical decisions. Even with my present company, when we hire a senior director, we make him code. Call it weird or whatever but, that’s the kind of culture you would see in Top Software firms.
Moving On
This one was bit different, I was allowed to sit on the chair (Thanks!) and it was time to answer conceptual problems. It was an amazing talk and it’s more than obvious that I loved it. Since I’m a good reader, I have explored a lot about the JVM internals from everything to do with Memory allocation, deallocation (Garbage collector algos) to the runtime JIT optimizations, etc. And recently studying Android’s Dalvik VM had been a great experience.
None of the questions were straight forward, All of them talked about real case scenarios e.g. Consider a scenario where lots of objects are created in runtime and soon after the execution starts, you have millions of objects consuming 90% of JVM memory. What would you do about it?” This was direct hit on talking about some good coding techniques and in worst case trying to increase heap and choosing the right garbage collection algorithm. I started talking about what could be the potential reasons: infant mortality of the large amount of objects that were created in early lifetime of the program inside the methods and then de-referenced within a matter of milliseconds of execution.Going further, I talked about potential ways to prevent this kind of coding with some better alternatives like memory sharing (of redundant data), distributing objects across clusters, compression of objects, Persisting least used data in some storage (persistance), sharing objects (pooling), etc. Then talked about cures: Essentially, how Java does Memory management (Stack and Heap storages) followed by choosing the right GC algo for the situation.
Generally speaking, there are certainly more advantages than disadvantages of giving a detailed answer — First, you would answer all related questions before they even ask them. Second, they build up more trust on you during very early stages. Third, you can showcase your depth. But, don’t mess it by going offtopic.
Moving on, we touched base with some advanced topics within MultiThreading, MultiProcessing and streams.
After spending around 1 hour on theory/concepts, they also wanted me to code. Back to the board, I was made to create my own Implementation of HashMap from scratch. Now that was huge for a small board even when you are implementing just basic methods: put() and get(). I briefly wrote hashing method with a good compression algorithm, took some inital bucket size and defined a dictionary node (key, value) with object array as the storage DS and LinkedList element (when a bucket had more than one element). Woof! I couldn’t fit the code on board, but I explained whatever part was left-out. They kept asking questions in between “What if I don’t want LinkedList, what if I want faster iteration through enclosed LinkedList, how would you get this element back efficiently…” and so on..
I wanted to rub this mess off the board, but they wanted me to continue the next step: Make it thread safe. No biggie, Collections.synchronizedMap(), but as expected, they wanted me to implement it. I synchronized get() and put() methods. Then they said “Non-blocking threads” — Game Over! I was like shouting inside, I can’t do that on this board, I need a computer with eclipse. I cleaned a part of it and tried to concentrate on CAS for one of the methods i.e. put().
For those who are not aware, Non-blocking Concurrency can get hard to implement. It’s a feature of Java (implemented in 1.5) available under util.concurrent package. This is still very new for most developers and and has been used rarely. What happens is, practically, you are allowing Multiple threads to execute simultaneously (without blocking) any part of the code. There’s no mutex here. What we do is maintain AtomicReferences to objects and these references are used while updating it. Developer has to take care of every update at every line of code, by verifying with previous values (and all cases of data-corruption), and with something as complex as HashMap ( it has lots of updates), I couldn’t do it on the spot. But one of those interviewers seemed to be convinced already. But I was not sure if that was positive.
I admit, it was long since I last used it, most projects still use poor-performing blocking Threads due to ease and maintainability of code.
Up next was a sorting problem in which I had to sort a given data according to its weight and relevance (relevance was provided). I would call that a PageRank lite. I fiddled around with weighted sort algo but, it can get hard to think & write code when you are exhausted. After 4 hours of discussion, I hardly had any energy left. I fell, yet, again.
Unfortunately, that was the last question of the day.
The Aftermaths
I had a mixed feeling when I walked out. I did well on 80% of the cases but, in the last I just screwed up (yes, fatigue overtook me).
The last impression matters, and trust me, it matters a lot. I was confused and tired, I wanted to grab a nap but I couldn’t coz I had to move to office. I slept in the evening, and when I woke up, I was still confused, depressed, and happy at the same time. Only 2 things haunted me all the time along: “Would I lose the chance, the one I had been waiting for all my life?”. “A rejection means that I won’t be able to work with Google, ever?” Same set of questions kept me disturbed for almost 2-3 weeks.
After 3 weeks of time, I was almost certain that it was over. My fate and untimely fatigue had betrayed me. And I had consoled myself to live with this failure. After all, Google hires Scientists and not regular programmers. That night, I read some encouraging Google Interview experiences (from around the globe) which made me believe that Google Interviews are all about the experience and not necessarily cracking them.
Randomness is Bliss
One random day, I got a call, the convincing voice invited me for the Final round. They explicitly mentioned the word “Final” which meant it was time to get serious. He sent me a Google calendar invite instead of a mail, for which you don’t get any notifications in Gmail and there’s almost no way to know unless you use Google Calendar. Luckily enough, I happen to use it with iPhone PUSH notifications.
It was time to fix the mistake I had made in the past, I practiced several algorithms by hand on-paper. Trust me, I never wrote a line of code on the paper (except for the long forgotten engineering exams), I’m so addicted to IDEs that writing elsewhere doesn’t give me the same confidence.
The Dooms Day
The day finally arrived, It started 10 in the morning and lasted, surprisingly, only for 35-40 minutes. They kick started with the phrase “today its all programming, no theory”, I knew this was coming. They gave me just two programs, Of course nothing related to what I had been practicing. One of the problems was to validate an XML, (again, without using Java API). I implemented it using Stack and validated every open/close tag by pushing and popping. The question goes further, ” How would you fix the broken xml”, that wasn’t hard either, I did it all in under 15minutes.
The second question was about optimal iterations and finding duplicate elements in a very large LinkedLists (Millions of Items). I was able to give a decent solution (two iterators: one moves double the speed of the other until they lap each other) and then few tini-mini discussion on alternative approaches. To my surprise, that was all they had for me. That could be a positive or negative indication. But I was positive about it. While concluding the session, they seemed keen on knowing my notice period and related stuff which is a kind of hint you get from recruiters when they are interested in hiring you.
They asked me to leave and I went back to office. While I waited for the final judgement, I was happy and thrilled. I looked a lot happier than one would find me on a typical friday. I was amazed all on my own, while I was waiting to hear from them. I didn’t have to wait for long, the same evening consultant became the bearer of the good news. That was the moment I almost jumped.
That day would always be the most important one for the years to come.
What you should Learn from this Experience
Disclaimer: These are my personal Experiences, I’m a human, I could be wrong.
I didn’t write this all just because I was excited about it. The purpose is to help every desperate geek attain salvation:
The only secrets that steal the Nirvana are – Hard Work, Passion, thorough on concepts, in-depth knowledge of the subject.
No one can teach you how you can be Passionate. If you are NOT passionate about Tech, programming, don’t run after it. Be yourself. If you feel Google would pay you a lot, Trust me, I had been offered a lot better by other companies and I can, of course, teach you better ways to earn money than running un-ethically behind Google.
To conclude this Huge blog post, I`ll highlight everything that Google wants you to possess:
– Passion: Like I said, no one can teach you how to get it, you develop it over years and it comes from the inside.
– Strong Analytical skills: Average would not do, they need something a lot better than that.
– Performance Optimizations & Scalability: Google has built the applications that are more scalable than anything else in this world. They would expect you to have this skillsets under all circumstances. If you are not good at thinking optimal solutions, Google may not want to hire you.
– Problem solving: Achieving a highly robust system and still maintaining its scalability is very hard to achieve in practice. You need to develop problem solving skills. You should be full of ideas all the time.
– Datastructures & algorithms: This is single most important thing that you must be good at. Java gives you good inbuilt datastructures but, unless you understand their internals very well, Google won’t bother about you. The reason is obvious, if you don’t know about them, probably you won’t be able to create your own, which is something common in Google. For instance they rewrote lots of Java libraries while writing Android OS. and even lots of them while Developing App Engine. Besides that, you wont be even able to choose among them. e.g. You should be aware of how costly it could get when you are using HashMap adding large no. of objects and varying the load factor which actually results in recalculation of hashcodes and eventually re-insertion vs. something as simple as ArrayList where subsequent adds don’t slow thing down as badly. ( that’s the easiest example I could think of)
Keep your knowledge of Mathematics on tips: Big-Oh notation, Theta notation, and Omega notation. They would ask them for each and every algorithm you would implement. I’ve seen people craming the values for common algorithms and hardly understand significance of the three. Doing so evil for you. Apart from that, its obvious that you should be good at logarithms, basic idea of graph shapes for different kinds of mathematical functions.
– Read, read and read. Code, code and code. Build concepts well, get in habit of writing code for every algorithm that comes to your mind. You cannot put every idea into code during the interview, you should be good at it from the very begining.
– Google hires scientists and not programmers: If you have given up your creative thinking and rely only on inbuilt APIs, don’t expect that Google would entertain you.
– Presentable, Expressive, Good communicator: This is something every recruiter demands. Google would always ask you to explain the code you’ve written. The idea is not just to understand your brain’s runtime execution environment but also your expression. It’s no good if you can write a code but can’t explain it to your peers. Communication is still very important even though everyone is an “Individual contributor”.
What Google doesn’t Expect from You: Few Myths Demystified
– Perfect Programmer: This is a myth, there’s nothing called as perfect programmer, no one is invincible. Everyone is a horrible programmer, only difference is some are more horrible than others. You are allowed to make mistakes, but expected to pick-off from hints, when privileged with one.
– Memorize Language APIs: Google will never ask you to implement something solely based on inbuilt APIs. And they don’t even expect you to memorize them as well. e.g. if you are writing a method say for XML parsing and you forgot the Factory method, they would allow you to write any name as long as your overall logic makes sense. I’ve seen people asking methods, signatures, etc. in interviews, Google would certainly not do that.
Verdict
I’ve been conducting as well as going through large number of interviews, but trust me, there’s nothing like a Google Interview. Getting short-listed itself is a fortune, and cracking them requires a genius.
In nutshell, If you want to chase your dreams, work harder, don’t be afraid, you live your life only once, let your passion speak and success will come to your doorstep. Stay Hungry, Stay Foolish, it’s upto you.
