Status: 4 YoE
Position: IC2 at Oracle
Location: Santa Clara, CA
Date: October 26, 2019

Onsite

Round-1: You have to drive a car having V gallons of fuel tank, filled to the fullest in the beginning, having M mpg mileage, in a straight line from start to the end. In between, there are k gas-stations. The per-gallon prices of the gas at each gas station is given in prices[]. The distances of the gas-stations from the first point is given in dist[]. Find the minimum cost spent in filling the gas to reach from start to the end.

( I initially started to think this in a greedy manner, I was able to get to the solution, but I found out the greedy approach will yield me sub-optimal solutions. Then with help of the interviewer, I derived a DP solution in form of an algorithm, considering capacity of gas tank, mileage, distance and cost to fill the gas in between. But I didn't get any time to code. I felt little better since I at least was come to DP approach with minute hints from interviewer. I personally found this problem too difficult for 45 mins interview. This round might be one of the reasons for the rejection. If anyone finds this problem with solution anywhere, please revert back to me.)

Round-2: (Behavioral Interview)
Questions about the challenging tasks and how you handled, situations when you didn't agree with the design of the feature and how you handled, etc.. I was able to answer it with my experience.

Round-3:
Given a linked list, that you're not allowed to modify, just "print" the reverse of the linked list with O(1) space. (I got confused here, since I wasn't allowed to use any extra space, and I wasn't allowed to alter the list-node links. It took me some time and after that when I was thinking out loud about recursion, the interviewer asked me to think more in that direction. After that I was able to come up with a solution. The interviewer asked me to convince that the time complexity is NOT exceeding O(N) in my approach, I convinced him. My point is, I didn't think of recursion since he said to do it in O(1) space. I didn't realize that he wouldn't mind recursion stack space. Because of this confusion, the time was wasted, and the interviewer didn't ask me second question. Please point me out if I am wrong.

Lunch: Had a lunch with a Google employee at their cafeteria. Discussed about general things at Google, their culture, their tech stack and VCS, and other things. Candidates don't get evaluated during lunch.

Round-4:
Design a single-threaded counter, which can be incremented by multiple processes, but only one process would be increasing it at a time. Also support two functions getIncrementsInLast60Seconds() and getIncrementsInLast60Minutes(). ( I gave a solution using binary heaps to keep track of the requests in last 60 seconds and last 60 minutes. The interviewer said, the requests could be in millions, so the space should be optimized. I came up with a "TreeMap" of seconds vs the increments happened in that very seconds. I mentioned the reason TreeMap is a best choice is that we can easily maintain last 60 seconds requests and 60 minute requests. The interviewer seem to be convinced.)

You have been given a stream of locations. Find K nearest businesses from the given location. (I gave them binary heap solution, but interviewer said, try not to scan every possible business in the stream. So, I suggested to pre-process the given businesses, based on some kind of grids. Based on what's the given location, I would grab only those grids which would have k nearest businesses, so that's how I wouldn't scan the entire stream. The interviewer said, "That's exactly how Google Maps works!" He showed me the actual grid from their inner console for the Google Maps. I felt nice about it, thinking the interviewer might have liked my approach.)

Round-5:
Find K most frequent occuring words from an infinite stream of words.
(Solved it with minHeap, and explained the time and space complexity. Wrote the code for the same. I misjudged the time complexity to O(n). The interviewer said the time complexity is wrong, I corrected my time complexity to O(n log k). I think this might be a red flag for my rejection. What do you guys think? The interviewer then asked me to think of other possible ways to solve this. I asked if I am allowed to use more space, he agreed. From here, it was all discussion, I laid out my thought process loud. But all the approaches were yielding back to O(n log k). The interviewer suggested to use stack to maintain the k largest frequencies, and try to find the k most occurring words accordingly. The interviewer said the theoritical time-complexity would still remain O(n log k). He also told me that his approach might fail for certain kind of use-cases, so my approach was more useful in-general for all use-cases. Honestly, I don't know if the solution of the interviewer would make any reduction in time, but I kept quiet.

After a week, the recruiter told me they wouldn't move forward with me. I want to introspect and understand my negatives here in this experience. Can you guys point me where I could have improved / what I lacked?