Google | SWE | Mountain View [Offer]
Posting a friends experience, On-site, Mountain-view, SDE, Received job offer
I would appreciate if you could post how you would approach these questions, it would help all of us.
Thank you
Round 1:
There are X people at Google looking for a scooter to use. There are Y scooters stationed throughout Google. Design an algorithm to pair people to scooters.
https://leetcode.com/problems/campus-bikes
Details:
X <= Y
People and scooters placed at various points on a 2D grid
Input is list of locations of people and list of locations of scooters
Algorithm should greedily prioritize closest pair of person and scooter
Round 2:
You have a staircase with N steps. At each step, you may climb one step or two steps. How many ways are there to climb to the top of the staircase?
https://leetcode.com/problems/climbing-stairs
Follow-up Questions:
Write algorithm for variable number that can be climbed at each step (what if we could jump two stairs?)
Write algorithm that tells us number of ways to arrive on last step for each leg (number of ways that end with left leg vs. right)
Now consider a variable number of legs.
Round 3:
Check to see if a tree is balanced
https://leetcode.com/problems/balanced-binary-tree/
Round 4:
Given a string X and a dictionary of words Y, return a set of words in Y that are at most one character different from X.
Follow-up questions:
what is best data structure for our dict for this algorithm?
---trie?
---hashmap?
Round 5:
Consider the rules of blackjack. If the dealer is holding two cards summing to X, what is the probability that they will bust?
Similar question:
https://leetcode.com/problems/new-21-game
Details:
Rules of blackjack (for this problem):
Dealer busts if holding over 21
Dealer doesn’t hit (stays) if 17 <= X <= 21
Dealer must draw below 17
Ace = 1 (not 1 or 11)
Equal probability of drawing 1 to 10 from the stack (independent of what dealer has already drawn, imagine an infinite stack of cards) (probability of drawing 10 = 1/10, not 3/13)
Make your algorithm run in linear time
Follow-up questions:
What if instead of busting at 21, the dealer busted at 1,000,000? Or some variable?
What if dealer could draw from more than 1 to 10? Design algorithm for variable drawing range.
Design algorithm for variable window of when the dealer stays.
What is the minimum space complexity of this algorithm (with linear time)?