地点是Sunnyvale
Phone
- 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
- Write a function boolean isPresent(Node root, int n) . return true if that number is in the tree.
- https://leetcode.com/problems/count-complete-tree-nodes/
Onsite:
Round 1: (45 min)
- Given 2x4 matrix it contains numbers in the range 1-8.
For eg :
[4,2,6,5
1,8,7,3]
You have 3 operations:-
Rotate : Middle 4 numbers rotate in clockwise manner.
[4,2,6,5
1,8,7,3]
becomes
[4, 8 , 2 ,5
1, 7 , 6 ,3] -
Swap : swaps the two arrays
[4,2,6,5
1,8,7,3]
becomes
[1,8,7,3
4,2,6,5] -
Shift (right) :
[4,2,6,5
1,8,7,3]
becomes
[5,4,2, 6 ,
3,1,8, 7 ]
-
Rotate : Middle 4 numbers rotate in clockwise manner.
- Your goal is to reach following state and tell how many operations would it take to reach that state.
[1,2,3,4
5,6,7,8] - Similar to these if you could solve these problems you are good:
https://leetcode.com/problems/sliding-puzzle/
https://leetcode.com/problems/open-the-lock/
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 this (but maxpath which could end anywhere with 0s that you cant visit) :
https://leetcode.com/problems/minimum-path-sum/
Round 3 : (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 interrogation
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 4: (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:
Design Ticketmaster:
Personally I think you need way more depth than whats is in that educative link.
This youtube video is useful too :