Google | L4 | Sunnyvale [Fail]
Phone screen:
Given following pattern write a function print(int n):
n=1 : 1
n=2 : 2 1 2
n=3 : 3 2 3 1 2 3
n=4 : 4 3 4 2 3 4 1 2 3 4
Given input stream 1,2,3,4,5,6...... we are generating a binary tree from left to right.
Creation of the tree :
1, 1 , 1 , 1 ,
/ / \ / \
2 2 3 2 3
/
4
Check if the given node exists in a complete tree
Follow-up:
https://leetcode.com/problems/count-complete-tree-nodes
Onsite:
Round 1: (45 min)
Min steps to reach the state
Round 2: (45 min)
Find the best path to collect maxixmum gold.
Given Matrix there is gold mentioned +ve int.
There are 0's that are blocked paths. You will start from 0,0.
Give me the path and number of maximum gold collected.
Path could end anywhere not necessariliy (n-1,n-1).
Similar to
https://leetcode.com/problems/minimum-path-sum which could end anywhere with 0s that you cant visit.
Round 3: (45 min)
I dont rember this one but it was coding interview.
Round 4: (45 min)
All behavioural round. These were easy questions and nothing like grilling of amazon LP question.
Personally I feel amazon LP question are BS and feels like interogation see the Amazon post here.
Tell me about your self.
How do you work with PM, QA & support? (this is my resume related)
Talk about your favourate project.
Why are you leaving your company?
What are you looking forward to if you are working for google.
A lot of talk about what I do and my past experiences.
Round 5: (45 min)
System Design - ticketmaster like fandango but for concert tickets.
System shows 10 avialable tickets to the user1 for 2 mins.
Those 10 tickets are not available to other users for those 2 mins. after 2 mins those 10 tickets becomes available to show again.
He was very intereseted in how I design the tables and API.
The problem he was interseted in to solve was:
how do you track what available seats you are showing to different users and once the timer is expired how you make those avialable.
The mistake I made I went with distributed cache.
This opened whole lot of can of worms.
Cache invalidation is a nightmare in a distrubuted cache. (try to avoid as much as you can and try to use local cache.)
Useful links for System Design:
Grokking the System Design Interview - Design Ticketmaster. Personally I think you need way more depth than whats is in that educative link.
InterviewCake - Design a ticket sales site
VIDEO