I took a Google interview recently. Just received feedback from HR. Things didn't go well and I got rejected. The sharing posts here helped me a lot, so I want to share my experience, too. I will not be too specific about the interview code problems but will be more about the general directions.
1st round
Tree common ancestor related problem. The interviewer said there would be two problems - 1 basic and 1 follow-up. I only solved the 1st one in the end, so I already know the result would not be good.
I tried clarifying problem input/output like many people suggested.
I know an approach at the very beginning, but somehow I stuck at the basic DFS path recording. Finally, I got through it, but wasted a lot of time.
I was still too fast to start coding. The interviewer pulled me back to explain my approach. So later, I tried to explain all the way during coding. The interviewer stuck at the white-grey-black flag I used in DFS path recording. Spent a lot of time to explain.
I was asked to add error checking. Added a few. Asked to doublecheck the solution. Found a few bugs. I analyzed time complexity. Then I was asked to analyze mem complexity. Analyzed as well. The interviewer agreed the solution is correct.
Feedback (weak point)
Candidate needs hints. Lack of corner case consideration.
Not familiar enough with DFS and backtracking.
Coding is not good enough.
=> This is kind of expected result.
2nd round
Segment tree problem with many follow-ups. I've done a few follow-ups, but time's up. Don't know how many ones remaining.
The interviewer seems following my code very well, so I did not spend too much time to explain.
I wasn't asked for complexity analysis probably because of the nature of the tree problem or just no time for that. The interviewer did not open for any question but just say "you probably have next round of interview so let's end here" and quickly said goodbye.
Feedback (weak point)
Code design is not so good.
Lack of error handling.
Index handling is not efficient enough.
=> This is kind of unexpected. I thought I was doing well this round.
3rd round
Query min value in multiple ranges of a big array. It is again a segment tree problem.
The interviewer's voice is cold and not showing face, so I cannot see his reaction.
I didn't come up with a solution at the beginning, so I proposed a naive solution. Then I got hint and transform the problem into segment tree problem.
I made very sure about the direction, and then start to code. Didn't want to make the same mistake like in 1st round. Then I implemented the tree. The interviewer hinted to debug. I didn't found the bug. And then I did a few follow-ups. The interviewer asked again to go back to find that bug and hinted a corner case that array size = 1. I finally found the bug - typical off-by-1 error.
In the end, the interviewer opened for question, but since he was cold, I didn't ask.
Feedback (weak point)
Candidate needs too many hints to solve the problem. And a few coding mistakes.
Code readibility is not perfect.
=> I admit that I took too many hints this round, but the code readibility part is too picky. Anyway, they wrote everything they've taken note, not necessary affecting the assessment. I thought I screw up in this round, but turns out I actually got the highest score(?) comparing to other rounds.
4th round
Design a resturant queuing system. The interviewer is friendly. I proposed a naive solution that the average case would be O(1) and worst case is O(N), and I tried to minimize the chance of worst case and the N in the worst case. We all know when N is small, O(N) is nothing. However, the interviewer actually did not agree. We went back and forth but still not got a good sign. The interviewer brought up a couple of corner cases. I tried hard to defense my solution. I was like, this can be solved and that can be solved, too.
We kept debating against my solution until the last 5 mins. The interviewer said "let's start to write some code. If you don't have code (written down in this doc), that would be an immediate failure." So, I wrote down my naive solution quickly.
The interviewer finally said that an O(1) solution in worst case was expected.
I shouldn't insist on my solution but just start over. The interviewer prompted a few times that my solution does not meet the requirement, but it's obscure and I just kept defensing. I just didn't listen.
After interview, I had a nice chat with the interviewer (30 mins) . I asked about hiring process and the standard, and what's my performence in this round. He said the performance cannot be told right now but explained a lot. Basically because everything will get calibrated. There is no really a "score" but you can view it that way. Failing one round does not mean overall failure (failing two rounds may be); coding bad in one round but good in other round is probably okay. Employee can apply for being an interviewer, and will get training. Interviewer can only ask predefined, approved questions but not arbitrary ones, etc. Other things like, candidate should be able to finish leetcode medium problem in 20 minutes. Leaked problem will be banned, but only if it is identical and marked as "asked in Google interview". Problem can be similar. Even if an identical problem, checkpoints can be different, so that problem would still not be banned.
Feedback (weak point)
Code does not solve the problem. Data structure is inefficient. And does not dequeuing people when served.
=> I learned a lot from the interviewer, but I also think the interviewer failed to guide me into the direction he wanted. He was not satisfied about complexity, but he kept asking corner case that is unrelated to complexity. So, I didn't know what is the real problem until the end. And he kept emphasizing that I should think this as a "real world problem", but then he did not accept that when worst case is rare and with a small N, the problem is called "resolved" in real world.
I got the lowest score(?) comparing to other rounds.
Conclusion (what I learned)
They are really picky with the code. You must not take too many hints. You must not make careless mistakes. You must check corner case. And your solution cannot involve any inefficiency.
Leetcode problems usually don't need customized data structure. You are just given an array or a tree, and you start to code. Google interview will require you to build your own data structure, for example, to build a segment tree.
Leetcode problems come with boundary conditions and no bad inputs. Google interview will require you to check boundary conditions in the code. So, try to implement the checkings against boundary condition when practicing.
Leetcode problems come with test cases, especially the corner cases. Google interview will require you to make up the test cases. So, try to make up cases before you press submit. Try to get a higher AC rate.
Don't jump into coding but code fast. You need additional time to explain and dry-run your code. So practice is important. Practice more with trees. Especially, practice until you don't make off-by-1 error. Like, back to when you wrote a for-loop for the first time, you probably took some time to figure out it is i < n or i <= n, but now you just type the whole for-loop header without thinking.
Don't debate with the interviewer. You are not showing how convincing you are. You just take the hint and start over.
That's what I have right now. Thanks for reading and good luck to everyone!