Google L5 Dublin [Offer] | Facebook E5 London [Offer]

Anonymous User

9903

Status: 10 yoe
Position: SSE @ startup
Location: Oslo, Norway
Date: Google September 2020, Facebook October 2020

Technical phone screen (45 minutes):

Google - Telephonic for Google was having only one problem with some minor follow-ups.

You are a traveling salesperson who travels back and forth between two cities (A and B). 
You are given a pair of arrays (revA and revB) of length n.

You can only sell goods in one city per day.
At the end of each day you can choose to travel to another city but it will cost a constant amount of money (travelCost).

Ex::
revA[] = {3, 7,2,100};

revB[] = {1,1,1,10};

travelCost = 2;
Find maximum profit.

There was a follow-up question on what if one of the cities for a particular day has a very high revenue compared to other cities.
I was able to coin the recurrence relation for this right away, and the interviewer got impressed by that. The next 15 minutes were spent on writing the code and discussin around complexity of the solution. I got strong feedback from the recruiter after an hour itself and the onsites were setup post that.

Facebook - Facebook telephonic was a rapid fire interview with 4 questions, one of which was just a follow up on the last question.
- https://leetcode.com/problems/string-to-integer-atoi/
- https://leetcode.com/problems/remove-nth-node-from-end-of-list/
- A variation of https://leetcode.com/discuss/interview-question/894401/facebook-phone-find-a-local-minima-in-an-array to find local maxima.
- Follow up was on the last question, by changing the definition of local maxima. What if local maxima is the one which is strictly greater than its neighbors. So, there will be situations where there might be no local maxima (When all elements are same). This is something that I was able to highlight during the discussions.

First two questions were straightforward, and I believe I was done with the first two problems in the first 15 minutes. I had a very good discussion on the last problem, regarding optimizing the solution. I implemented the solution following this https://leetcode.com/problems/find-peak-element/discuss/927641/Exact-the-binary-search-template-to-solve-the-solution-(LC-34-35-704) using binary search.
Interviewer was impressed with the last problem discussions and I got a strong feedback for this round.

Virtual Onsite Interviews
* 1st Round was behavioral for both Google and Facebook. I would suggest bringing out personal examples in this round like some open source contributions, startups, etc. Just see if you can bring out something apart from your job to this round. Google, facebook both really value this aspect. Suggested videos for the same:

Coding Interviews : There were 3 coding rounds for Google and two for Facebook. I found Google ones a bit harder than the Facebook rounds.
- Google 1st - Design a word suggestion that gives top k words from a dictionary that can be formed by using the characters from an input by the user. Interviewer explained this question by citing an example of iphone keyboard on which you can slide your fingers across the keyboard and possible words get suggested.

Ex:: 
   
	Dictionary - ["ball", "tall", "doll", "taller", "body", "cat" ]
	User Input - "jybkalrldeollbaocady"
	Output- "ball","doll", "body"

I presented a Trie based solution where I will keep track of all possible candidates after considering each character of the user input string one by one and then return the top k candidates which are word. All the time in this round was spent on writing the code, discussing complexity, running through test cases and identifying edge cases. Interviewer asked to optimize the solution further but I was not able to add any useful optimizations other than being able to reduce the complexity by constant factors only. I was not confident about this round, and thought may be the interviewer had a follow up question as well, but I didn't had enough time for that.

Google 2nd - Design a solution like linux grep command that takes in a query predicate to search and a context (number) and returns all lines in the file which match the predicate. The output needed to include "context" number of lines before and after the matched line. Problem was not to implement the text matching but the context implementation. Interviewer advised that you will have a library funtion invoking which you will be able to identify if that string line contains the query predicate. We had to take care that for context, all lines are included in the output only once.
Interviewer discussed about the complexity of the solution and agreed that I had the optimal solution. He then had a followup question where in I had to implement the solution to the same problem, but this time the funtion implementation doesn't have access to the entire file and the file can be very huge as well, so can not be loaded at once in the memory.
He also asked to come up with some test cases and identify edge cases. I was able to point out the case when the value of context is very large say in thousands, then in that case the output will be bloated and harder to keep memory usage low. Interviewer seemed happy with the approach and the discussion was very good.
Google 3rd - In this round I met with the best interviewer I have come across. The guy was old possibly in the 50s, but was very polite and treated me like a student trying to solve a problem rather than an interview. He kept appreciating me for all right decisions I took during the solution and also warned twice by giving hints. Problem was that we are given a list of songs, and you have to implement a random shuffler of songs where each song played has a cooling period before it can be played next. I started with using an extra memory (Queue) of size k (where k is the cooling period) and was able to implement shuffle in O(1). He was happy that I was able to implement the solution for O(1), and then asked a follow up to optimize the memory usage. I was able to implement this by applying circular buffer to the input array of songs. He was overjoyed when I implemented this and blessed me in the end for my future.
Facebook 1st -
https://leetcode.com/problems/add-binary/
Variation of https://leetcode.com/problems/random-pick-with-weight/ with changing the data representations. First question was straightforward, and I implemented the second with O(log n) complexity. He had a follow up tomoptimize the time complexity to O(1). I was able to pesent him an idea of doing feature scaling on the input to put all ranges in memory for O(1) access to pickup random element. He was not entirely satisfied with this answer but agreed that this would work. He then shared the information that this is a research problem and that his team are working on this at the moment.
Facebook 2nd - This round had leetcode problems with no major follow ups nor any serious discussions. The interviewer was already late and wrapped up the interview within 30-35 minutes.
https://leetcode.com/problems/valid-palindrome-ii/
https://leetcode.com/problems/basic-calculator/

Design Interviews

Google - I was asked to design a solution that can be used to whitelist traffic to multiple highly available services. There is a service made by governments which decides whether to allow a specific IP or not and we have to call that service for all incoming requests. This was also a very good discussion and the interviewer already had a set of questions which he wanted me to answer from the design. The interview went great and ended before time.
Facebook - Design a system that can search the most recent status of every facebook user for a given word or words. Unlike Google, Facebook design interview was not based on questions asked by the interviewer, instead he didnot speak much during the entire round. The expectations were already set by the recruiter on how the design round will go, so I had worked on a flow of how I will go through the design interview. In the end the interviewer was satisfied with the discussion.
- Tips for Design Interview:
- Start with a very simple monolithic design.
- Always show some calculations like how much size of data you would want to store.
- Scale from this point around various performance mandates adding horizontal scaling and sharding around the data layers, etc.
- Google and facebook both love to see some maths in this round.

I got good feedbacks from both Google and Facebook, and went ahead with the Facebook offer.
For DS & algo, I think the aspirants must stick to leetcode. Practice in monthly challenges and prepare through mock interviews, contests, company wise tracks, etc. Always try to look through the submission details of your solution and refer the most optimal for the problems of your choice.
For Design, I will suggest reading the solution to same problem from multiple resources, that way you get different perspectives to approaching the problem. I liked the approach discussed here:
https://techtakshila.com/system-design-interview/chapter-5/
Also, read gainlo blog for problems like proximity servers, web crawlers, etc.
Some good to watch videos:

Let me know if anyone has any other question around the interview process for any of these companies. I also interviewed for Microsoft, Amazon and Spotify recently with offers from all three, so I can share some thoughts around those as well.

Another useful link containig full fledged program to prepare for interviews. Not sure who is the original creator of this, but while going through the material please wish well for the anonymous contributor, I guess he wants only that!!
https://docs.google.com/document/d/1wUCqhVHydWiDk6FJdFLSMpgigNrGcs4OFZg0Wa7JGEw/preview?pru=AAABcwIONo4*LvMfol8cjjqLwdNoXE6HTg

Comments (38)