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.
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?
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)?