# 谷歌近期高频面经题汇总

1 Like

This may not really be a short post, but i will cover everything from the start. So first of all, my motivation. I wanted to work at google. not amazon, not uber, not facebook, not microsoft. Just google. Not only do they have so much scale and so many users, but each product of theirs has had incredible impact on my life.

I had a few friends at google. They said that i should become good at data structures and algorithms, and do lots of practice. And then get a referral. In short, thats what i did. Now for the details.
I started leetcode in January.

PHONE INTERVIEW:

you are given a linked list, where each node has a digit from 0-9. this LL represents an N digit number, you have to add 1 to this number. https://leetcode.com/problems/plus-one-linked-list/
answer: either reverse it, then add one, and then reverse the answer, or use a stack to go to the end, and add 1, using the stack as a carry buffer. implemented both, then the interviewer gave me a hint to do it in a better way, and i did it. wont tell the better way, maybe someone can try it.

ONSITE:
overall amazing experience. down to earth googlers, amazing office, amazing perks. friendly people. chromebook didnt work, which was a bummer because i was promised that i will not have to code on whiteboard. but i managed.

ROUND 1 Coding:
You are given an execution log of entry time and exit time of several functions during an execution. can you make a file-system-like directory telling me the duration of each functions runtime?
https://leetcode.com/problems/exclusive-time-of-functions/ similar to this, but you are supposed to give the total time of each function, and your answer should capture the nesting.
answer: make an N-ary tree data structure, and deserialize the logs to make that tree. coded on whiteboard
follow up: how will you validate that the input in the log is logically consistent?
answer: firstly the timestamps should be sorted, and secondly, use something like this https://leetcode.com/problems/valid-parentheses/ coded it on whiteboard, follow up 2: how will u do it for multithreaded? answer: have a thread flag in the input and split the array into a hash table of arrays, which will break down into single threaded prblem.

ROUND 2 coding:
You play a game of Go, https://www.wikiwand.com/en/Go_(game), the interviewer actually brought the game with him. which i loved. you are given a board with some stones placed on it, and you are given a new stone to be placed on an empty spot. you have to return the number of enemy stones that this move will capture. He taught me the rules of the game. I gave him a dfs solution, it was a long one. Finished it. had one logical bug, he gave a hint, i found it and fixed it. again whiteboard problem.

ROUND 3 system design:
I was especially worried about this round, but the interviewer was very calm and helpful. He probably knew i dont have much expereince in SDE, so he himself drew the whole system for me, then he said now we have 50k ad clicks per second, and 1 million queries per second. what problems will u face, how will u prevent those problems. I talked about core fundamentals like reducing latency, increasing throughput, and planning for failover. Basically they want to see your fundamentals when it comes to using tech, (throwing money and gear) at a scaling problem in order to solve it. I think it went well, but i am not a good judge of this, so i dont know, we will see

ROUND 4 gOoGLiNesS interview:
This is like an HR leadership round. A lot of questions about team management related situations. I found it easy, because i have actually been a team lead for a tech project which was my startup, even though i didnt code in it.

ROUND 5 Coding interview:
The question was similar to https://leetcode.com/problems/campus-bikes-ii/ except for a few details: