I did a google onsite for the SDE interview on March 8th 2022.
Position is L4 SDE, @ 3 YOE.
Round 1)
Given a String, get the run length encoding of the string.
Follow Up #1: Given the Run length encoding, get the character at a specific index.
Follow Up #2: Can you do Follow up 1 in Log N Time??
This is a trival problem. Think this round went well. I was able to answer all the follow ups with minimal guidence and hints. I communicated out loud. My expectation is probably a HIRE or Strong HIRE.
Round 2)
Googleyness Round
I felt like it was mostly a chat to get to know me. The interviewer said there are no wrong answers. I answered all his questions with my previous experience. I don't know how this section is graded, but I assume if you don't raise any red flags, it would be a HIRE rating?? My guess is a HIRE or LEANING HIRE rating.
Round 3)
Given a Temperature Manager class, with functions recordTemp(int temp); and getMaxTemp(); You need to record the temperature when a new temp comes in, and get the max within the last 24 hours. This is not a monotonic stack problem. Honestly I struggled with this trying to think of stack solutions, but the thing is you need to somehow be able to remove the temperatures that were recorded more than a day ago.
As a brute force, I just kept the {temp, time} in a queue. When I needed to get the max, I needed to filter out the the temps that happened more than a day ago. I also needed to compute the new max if it got popped of.
I struggled to optimize thinking it was a still a stack solution. I ended up doing the priority Queue solution. This way we can get the max easily. I did have it coded out, but I feel I did not get optimal solution. I felt like I could have optimized more. Interviewer was extremley quiet and offered minimal hints.
My guess is LEANING NO HIRE or outright NO HIRE. This was my worst round.
Round 4)
Given a string s with only characters A, B, C and D, find if a substring of length 10 is located twice in the string.
Idea 1) Compute all the substrings of length 10 and put in a hashset. If we encounter the string again, return true. Else return false at the end.
Interviewer said this solution is good, but he wants me to optimize on space.
The key here is to realize that we are given only characters [A,B,C,D]. We need 2 bits to represent each character, so we could use 20 bits total. Since 20Bits < 32 bits, we could put our string representation inside an Integer!
I also mentioned that we could have a tree like structure, and for every 1 bit we go left, and for 0, we go right. He said this was good but he wanted something different. He said I got brownie points for bring this up :)
We eventually settled on the BitSet data structure. He did not expect me to come up with this, and gave me the API definitions.
I coded out the optimal solution.
Overall this round went well, my guess is STRONG HIRE OR HIRE.
Round 5)
You are given an the following API definitions you must implement.
addProduct(long productId, long offerId, double price);
removeOffer(long offerId);
getClosestOffer(long productId, double price); -> return the offer that is the closest to the provided paramter price
I spent a long time brainstorming during this round.
But the idea is that you want an offerId -> productId map and a map from productId -> price -> List
You need a treemap so that getClosestOffer can be time efficient. If you do brute force it will be linear time.
I ended up coding the optimal solution, but there were some mistakes I made. I used a List instead of a Set. I also got one of time complexities messed up.
My guess is that this round is a LH, or H if the interviewer is forgiving. I did get the code working though.
So if we take the worst possible scores for each round I get [H, LH, NH, H, LH].
If we take the best possible scores for each round I get [SH, H, LNH, SH, H].
Personaly I think this will be a downlevel to L3 or a reject since I messed up on round 3.
Let me know what you guys think.