Phone screening 1 :
Given a chess board an a knight and a starting position return true if Knight can visit all cell
- a backtracking algorithm took 15-20 min to code
Followup 1 : How will you change the algorithm if a knight can only visit a cell once.
- changed the code to keep the visited 2D array .
Followup 2 : What if some cells are marked blocked. Return true if all remaining cells can be visited.
Followup 3 : Return the minimum path to visit all all cell just once.
- Backtracking but I did with BFS and returned the first solution.
Onsite
1 Coding : https://leetcode.com/problems/remove-invalid-parentheses/
- First asked to remove invalid brackets and return a solution with maximum length.
- Followup : can we generate all the possible longest valid parentheses string
2 Coding : very similar to https://leetcode.com/problems/logger-rate-limiter/
- Asked to design a class that will not print the log (an integer) if found in last x sec
- Interviewer was looking for a good data structure that can print and store it in buffer
- I did TreeMap but could have just used StringBuffer . I asked should we discard the most recent visited or already added in stream in x sec window - its up to me to decide.
3 : System Design - Ads click optimization . Design a system that can be trained and evaluated to optimize on revenue as objective function. Drilled down on how will you evaluate the model on frequent basis.
- Training objective function : Imaging coke pays 0.1 the optimization will be on total revenue and its possible model will prefer pepsi over coke as it drives heavy traffic.
Interviewer asked - Evaluation sets
- Data Handling
- Talk about Read Write and Update scenario
- Why choose one technology over other
- Testability
4 System Design : Google Event booking system
System will work as part of Google Search
- Able to list different cities in search
- Filter by city
- shows and event availability
- The user should be able to choose a show at a particular cinema and book their tickets.
- Users should be able to put a hold on the seats for x minutes
- The user should be able to wait if there is a chance that the seats might become available, e.g., when holds by other users expire.
- fair, first come . User can hold only upto 10 seats at a time
5 Googlenes / Behavior Round
- biggest technical challenge
- time when you failed
- had a conflict
- able to influence
- cross-team impact situation
