背景信息：
- LeetCode：850+
- yoe：4 年以上
- 学历：M.Tech（印度理工学院）
面试进度：
我已经完成了 3 轮 DSA 编程轮，但第 4 轮 Googliness 面一直被反复延期，目前是第 4 次被 reschedule。
自我评估：
除了第一轮 follow-up 的代码部分没有写完（但思路有讲清楚），其他题目包括 follow-up 都顺利完成并实现了。
第一轮
Given a piano where you can only use one hand to play. You will place your hand on the piano and can play the five keys. In order to play a key which is not in range you will have to raise your hand. Find the minimum number of hand raises to play all the keys in given order.
Follow up:
return the list of thumb positions you actually use—so you can see exactly where your thumb goes for each segment
Self & Interviewer Feedback -
Solved the initial problem with (2 approaches) optimal time & space complexity but could complete the follow-up coding. Although was in the right direction.
Interviewer was satisfied but told he wanted to get more out of me. Did communicated well with dry runs but unfortunately couldn't complete coding.
第二轮
On my disk, I have a file system. The file system contains files which have a known size and directories that either contain files or directories. And I want to know, given any point in this file system, what's the total space it's consuming as I got a bit confused due to time running out.
Ex -
/*
root (id=1)
dir (id=2)
file1 (id=4): 100B
file2 (id=5): 200B
file3 (id=3): 300B
*/
Map<Integer,Entity> fileSystem = initialiseFileSystem();
Follow-up 1 : what happens when we need to add files?
Follow-up 2 : service is timing out on boot.
Self & Interviewer Feedback -
Was able to code optimally for the initial question and the first follow-up 1. There was no time left for Follow-up 2 but explained the approach verbally. Interviewer seem satisfied. Followed OOD for coding. Communicated well with dry runs.
第三轮
Q1. write an algorithm to find the top K most frequent words in a document. And I have to assume that the document is already parsed. So, I can read the document as an array of strings. For example, there is a set of words in the document array. So, Google, Bike, Pencil, Google, Bike, Google. So, the top two frequent words are Google and Bike.
Follow-up 1: What would you do if your document, not the words document, was not an array of strings, but it was actually a stream?
Follow-up 2: what happens now if your integer k is 0?
Q2. write an algorithm to perform a prefix search. For example, given that we have the words Google, Good, Grape in our dictionary, and a search for Goo, it should return Google and Good, but not Grape.
Follow-up 1: what happens when your prefix is an empty string?
Self & Interviewer feedback:
Solved both coding with optimal approach and answered all follow-ups via code / verbally as directed by the interviewer. Interviewer seemed satisfied as I was able to complete everything before time. He asked or pointed about few special and edge case scenarios which I answered or modified in my code as per discussion.
