So I did my virtual onsite interview for Google this past month. I wont post the exact questions with input and output, but I will describe.

First round: behavioral. This was standard behavioral questions but a bit deeper than standard. For example, I got a question like "tell me about a time you went above and beyond?"

Second round: I was a given a dictionary/list of strings, and a String s. I had to return a word in the dictionary, that was inside the string. But the string could be very long, and the characters that would match the dictionary could be spaced apart very far. This was my worst round. I provided a brute force approach instantly, and in my head I wasn't completely confident that I could find an optimal solution in time. I told the interviewer to let me implement the brute force, before findin a way to optimize. As I started to implement, interviewer caught a bug in the double nested for loop and I spent 5 minutes on this trying to find it, but the pressure was getting to me. Eventually I found it after another hint from the interviewer, but I pretty much knew I bombed this round (which sucked) cos of the hints and the fact I couldn't get to an optimal solution. This was by far my worst round and I knew it.

Third round: I low key loved this question. I was given an an array with unsorted integers and a target value, I had to figure out a way to get the index of the target, AS IF it was actually sorted. So immedieately I provided a min heap solution. The interviewer asked me if I can figure out a way to do it even faster. This is where I just started to play with the problem, and came up with some novel algorithm on the fly where I find the min and max of the array, including all elements not equal to the target, and basically made an array 0's where I placed each number depending on their minimum absolute difference. The index with the last 0, would be where the target index was. So I provided that solution, and the interviewer definitely seemed a little surprised. He asked me to explain what I would call this, and I legit had no clue since I and ended up just calling it splitting the array. Then he hinted to me an even faster solution, one where I wouldn't need any space at all, but it was something not very obvious. A math trick, and eventually the code was only like 5 lines. I'd like to think this interview went ok, since I came up with 2 approaches, and eventually the optimal. I believe this was hire/strong hire. I loved how this question could be very easy or very hard depending on the constraints given. Definitely a question I would ask if I was ever gonna interview anyone.

4th round: I was given a question that basically involved setting up a data structure to store a value with a weight. And then get a get random function to get the object based on its weight. I immediately thought of an O(N * Weight) solution by basially simulating each object with how many objects there are based on the weight into an array. Interviewer asked me to explore a faster solution, and I was coming close to a solution that involved using ranges of the weight in order to figure out what object to get, but I ran out of time before getting to a clear solution. Ended up coding up the first solution I had thought of before. I got 0 hints for this problem, but interviewer said I was on the right track with the ranges if that counts for anything. No clue. If I had to say, this was a "lean hire" round.

5th round: Easily my best round which felt good. The question involved finding the count of matching sorted strings in a list, given a prefix string. I immediately thought of a Trie solution explaining how we can store a count in a TrieNode each time we insert the string. Interviewer liked the solution, but he said we can do better. He asked me to find a faster solution. I knew the list was sorted, so I mentioned I'm pretty sure we can use binary search here. If we find the index of the first and last occurerences of what matches the prefix, we can subtract the indexes to get the answer. He liked the approach and I coded it up. I did mention to him tho, that my previous solution with the Trie would probably be better assuming the list given wasnt sorted from the start. He agreed. I think this was a hire/strong hire.

Overall I felt that I started off bad, but I ended pretty good. Not sure how Google will perceive that. Recruiter said I would find out in 1-3 weeks. If I really had to judge myself, I think I did good on rounds 1, 5, 3. 4 was "ok". 2 was just bad. Overall though, I am happy with myself that I was able to at least give a solution for all rounds, even though 2 of them were most definitely not optimal. Also quite shocked I wasn't given a single DP or graph question.. both of which I studied my ass off for.