As the title says, this is not a story of how I solved 500 problems on Leetcode to land an offer with a big tech company. This is more about approaching programming interviews in ways it's hard to mess up, if you have a decent knowledge of algoithms.
Background
3 years with a major (Google-esque) tech company in India, right out of college.
Bachelors in Computer Science and Engineering.
Decent-ish Github profile, experience with open source: Google Summer of Code, etc.
The Story
Nobember 2019
I was perfectly happy writing code for my current company; last year however, a recruiter from Google contacted me with an offer I couldn't resist. An amazing team in an equally amazing country. And the game was afoot.
The recruiter asked me if I was ready for a phone screen. I was asked 20 basic CS questions, like the time complexity of standard algorithms and what STL functions in my favorite programming language did.
The recruiter then asked me if I was ready for a phone round, I said I wasn't and needed time to prepare.
Procrastinated and did some 30-40 problems on Leetcode before proceeding to the next stage.
January 2020: First round of phone interview
A simple array manipulation problem.
- Solved the problem in liear time.
- Then in-place.
Then the interviewer modified the problem, making it more complex. - Converted my previous solution to a function call and repeatedly called it in a loop.
- Did some level of memoization to reduce the function call of the new loop.
I got a call in a couple of days, informing me that I will be moving to onsite.
I said I needed some time, and this time I promised myself I won't procrastinate. But I did. Solved ~25 easy problems just to get that confidence up and running and get some practice with writing C++ code on a Google doc.
March 2020: Virtual Onsite
This was 5 rounds.
Onsite Round 1: Programming Round
I was asked to build something like a maze generator/solver in two dimensions. Apparenly, this is a standard segment tree problem and I hadn't heard of/worked with segment trees before. However, I did put down a data structure in place and wrote the API that would be required to solve this. I then proceeded to solve this with first principles (BFS).
Learning: Do not be scared if you don't know the actual algorithm. They'll nudge you (the interviewer asked me whether I knew what segment trees were and I replied in negative; he asked me to do it however else I could in that case), but they don't expect you to invent an algorithm right out of the box. They're basically testing out your algorithm design skills, something that might be useful in an internal tech discussion.
Onsite Round 2: Googly-ness
There were problems on how I would deal with certain situations, involving conflicts, disagreements, and how I would handle things like accessiblity. Be truthful, do the right thing and this round should be a breeze.
Onsite Round 3: Programming Round
I was asked a problem that involved dynamic programming. I started with a recursive approach, told him the time/space complexity, proceeded to affirm that I could make this faster, did some dynamic programming magic.
Now, the peculiar thing about this interviewer was that I received very little feedback. In general, interviewers try to nudge you or confirm whether or not you're heading down the right path. Not so here. Past me would've shat his pants and bombed the interview right there. But this time, I knew better. So, I proceeded to test my code. I wrote down 5 different test cases, ranging from empty arrays to large and small arrays, negative numbers, mixed numbers, etc. and ran the manually through my code. He seemed satisfied and modified the problem. I refactored my code to accomodate his latest change. Again, ran the test loop.
Learning: There are different kinds of interviewers. At times you may have to drive the interview. Remember. Algorithm derivation, coding, refactoring and testing.
Onsite Round 4: Programming Round
String manipulation problem. Involved a bunch of string parsing here and there (would recommend be good at this; chars, strings, wide strings, etc). I wrote the code. He asked me the complexity. I derived the same. He asked me whether I can optimise it. I did. There was a string matching subproblem somewhere. He asked me to implement that as a separate routine. I said I know a bunch of algorithms by name, but I am not sure of their implementation details. I implemented a not-so-good string matching algorithm and told him that this can be replaced by KMP or something of that sort - I am not familiar with those since I haven't really used them much since college. He said that was fine.
Learning: Be honest. Again, they're testing your algorithm design skills and not your memory.
Onsite Round 5: System Design
This was my favorite. I was asked to design the backend for an email service. Now, it's easy to throw around technical terms in a system design interview, but that's not the best way, in my opinion. The best way is to go first principles.
All through this round, I focused on what mattered, and that was
- The user experience
- Reducing the cost of keeping the service up (COGS)
I played a numbers game. Initially discussed what kind of systems, badwidth, hard drive sizes one would need assuming some x number of users.
Then designed an API for the client - this included pagination, rate limiting authentication, authorization, etc.
Then, proceeded to talk about the application service, the load balancers, databases, sharding, caching, all this while keeping in mind the end user experience.
Designed this thing in 25 minutes, he tried breaking the system here and there the next 10 minutes and I fixed these potential issues. This is more like a discussion and is super subjective. My 2 cents here would be to be very numbers driven, focus on one component at a time, start with a high level overview and eventually dig deeper into each component.
April 2020: Post Onsite
A month from that, my recruiter told me that I have had great reviews on my interview and will be proceeding to the team matching round. And then one thing led to the other, I will be joining Google soon.
Further Notes
I can't stress the importance of thinking out loud during the interviews. And being calm and confident. I had never given a Google interview before because of the horror stories I'd heard. Honestly, while it's hard, it's doable, and you can get through with enough practice and knowledge of first principles. Even while solving LeetCode problems, focus on solving each problems in multiple ways. Your first solution may not be the most elegant one, it may not be the fastest one, it may take you hours to come up with, but it would be yours and that's important.
I apologise for redacting most of the details about what exact problems were asked, but that wasn't the point of this post anyway.
If you want to know more about my experince, please feel free to ask any questions.