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$foradclickvspepsi0.001$ 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