Status: New grad, MS CS Top 10 CS school
Position: SDE1 at Google
Location: Mountain View, CA
Date: March 19, 2019
Onsite (4 rounds):
Round 1:
The interviewer come and pick me up at the reception. We first grabbed some coffee from their lounge and went to a conference room. It’s a white board coding. The interviewer briefly went over my resume but does not ask any specific question about the work experience or projects listed on the resume.
First round question is about serialization and deserialization. The interviewer said one of the common data structure used in database is called B-tree. B-tree is a self balancing search tree. He asked me whether I am familiar with the properties of B-tree or not and asked me to write a serialization method and deserialization method.
Hints:
The key point is that we can use B-tree’s property so we don’t have use a delimiter.
- All leaves of B-tree is at the same level.
- The number of children of a node is equal to the number of keys in it +1.
For the follow up questions, the interviewer asked what if we have a lot of repeated long keys. Is there a way to optimize the storage space?
Round 2:
The second interviewer asked a question about designing a small building tool. Given a list of dependencies, for example:
Lib1 depends on Lib2 Lib3 Lib4
Lib2 depends on Lib5
Lib3 depends on Lib5
Lib4 does not depend on any other library
Lib5 does not depend on any other library
If the user wants to build Lib1: one build order should be Lib4 Lib5 Lib3 Lib2 Lib1
I solved the problem using topological sort. The follow up question is some libaries do not depends on on each other. What if you have multiple threads and want to speed up the building process? Given the max number of threads that you can use say N, optimize the building time.
Lunch time:
I had a lunch with a Google engineer. Their food was okay not the best in bay area though. The coffee bar is pretty nice. I chatted with him about average promotion time from L3 to L4. How hard it is to switch teams. How does google help him grow as an engineer. I would say I am not really impressed.
Round 3:
The third interviewers asked a question about flippy birds. Say in a 2d space. You are a flippy bird and you are facing some obstacles. How do you know if you can cross all the obstacles and reach the other end.
For example:
In this case, starting from left the bird can reach the right part because there’s no obstacle that blocks the whole y axis.
In this case, starting from left the bird can’t reach the right part because there’s one big obstacle formed by two obstacles that blocked the whole y axis.
I first approached the problem in a wrong way. Turns out the interviewer is looking for a union find solution. Follow ups is about how to optimize union find like path compression etc.
Round 4:
This round is about a voting algorithm. Say we have a sequence of operations that transformed one object into the other one:
- object1->op1->op2->op3->object2
- object1->op1->op2->op4->object2
- object1->op5->op2->op3->object2
- object1->op1->object2
- object1->op1->op2->op4->object2
We know some of the sequence may be spoofed and some of the sequence may be missing certain operations. For example, for the first operation, we have 4 votes for op1 and 1 votes for op5. Thus we discard record 3. Second one we all agree on op2. For the third one, since record 3 was discarded, we choose to trust op4. Output the most trusted transformation between two objects.
The interviewer does not give much comments on my approach to this problem. He does asked me how I am going to test my code. Hope this helps someone who is hunting for a job. Thanks!