I received an email invitation to a session to help me prepare for a Google interview. That's how I learned I was shortlisted for an on-campus interview with Google.

After a couple of days, I received a call from HR describing the interview process. She also sent me some material to prepare for the interview. This material included links to sites like LeetCode.

Q1: A single processor system has some processes scheduled, each with a start time and duration. Given a new process, can we schedule it without removing any pre-scheduled process? I shared a BS-based approach. The interviewer asked me to implement it. I did, and then she asked me to use lower_bound instead of implementing BS manually. She asked me to find some bugs in the code. I found and fixed one. Then she pointed out another bug, which I also fixed. Finally, she asked me to write the time and space complexity.

Q2: After that, she asked a follow-up: now the computer has 4 processors. How would we check if a new process can be scheduled to any of the processors? I shared an approach involving coordinate compressing the start and end times, then creating an array initialized with 0. For each process, I would do arr[start]++ and arr[end+1]--, where start and end are the compressed representations of the original values. She then mentioned building a segment tree to find the range. Finally, I explained that I would find the smallest interval containing our process from the compressed coordinates using binary search, then find the range maximum in that range. If it's 4, we can't schedule the process; otherwise, we can. She didn't ask me to code this but asked for the time and space complexity of my solution.

Overall, the round went pretty well.

2nd: Coding

He told me a bit about himself and asked me to describe my thesis project. After that, he asked me to open the coding document and started asking questions.

Q1: The interviewer asked me to find the number of ways to make 'K' non-empty sets from 'N' unique objects. He gave some samples: (1, 1) -> 1; (3, 2) -> 1; (4, 2) -> 2. Seeing the samples, it was pretty clear that the objects were not unique. When I pointed this out and asked if the problem was equivalent to finding the number of ways to partition N identical balls into K identical bags such that each bag has at least one ball, he replied yes. He wasn't thorough with the problem himself. I asked about the range of N, to which he replied 1 < N <= 1e6, K <= N. I dropped the idea of any DP-based solution and started focusing on solving this using PnC. However, the interviewer asked me to come up with a recurrence relation. I was really drawing a blank at that point and told him that even if we find a relation in terms of N and K, we would have N x K states. I failed to find any correct recurrence relation, and the interviewer also told me to forget about it and moved on to the next question. After the round, I found the relation online.

Q2: There's a directed graph; find the shortest cycle from a source node. I proposed a DFS-based solution using the standard cycle-finding algorithm, storing the length of the cycle whenever we encountered one and returning the minimum value. He asked for the time and space complexity of my solution. He then asked me to improve the complexity, and I was drawing a blank. He suggested using BFS. I agreed and wrote the time complexity for that as well. Then he asked me to code the solution, but now I had to return the nodes of the shortest cycle starting from the source. I coded the BFS and kept a parent array to retrieve the nodes of the cycle when found.

After this, he asked if I had any questions, which I did. He answered them, and the interview ended.

Overall, this round could have gone better. I thought the first question was really hard. The HR called me and said I have a third round, and it's a deal-breaker.

3rd: Coding

The interviewer told me about himself and his work. After I introduced myself, we moved straight to the interview.

Q1: Given a 2D matrix, the cost to move to an adjacent cell (4 directions: up, left, down, right) is defined as the absolute difference between the values in the cells. A path's cost is defined as the maximum cost of any step taken to traverse that path. Given a cost, can we move from the top-left to the bottom-right with a cost less than or equal to that? I proposed and implemented a BFS-based solution. He asked for the time and space complexity.

Q2: This was a follow-up to the first question: find the least cost to go from top-left to bottom-right. I told him that if we plot a graph of cost versus is_possible from the last problem, it would resemble a step function's graph, and the inflection point would be our answer. We could find the inflection point using binary search. He agreed. I coded the solution using the function from the previous question as the check function. He asked for the time and space complexity analysis, which I provided. I solved these two questions pretty quickly, so he decided to ask another one.