Google | L4 | Sunnyvale | July 2019 [Fail]

Phone screen:

• 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

• Check if the given node exists in a complete tree
  • Follow-up: https://leetcode.com/problems/count-complete-tree-nodes

Onsite:

Round 1: (45 min)

• Min steps to reach the state

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 https://leetcode.com/problems/minimum-path-sum which could end anywhere with 0s that you cant visit.

Round 3: (45 min)

• I dont rember this one but it was coding interview.

Round 4: (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 interogation see the Amazon post here.
  • 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 5: (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:

  • Grokking the System Design Interview - Design Ticketmaster. Personally I think you need way more depth than whats is in that educative link.
  • InterviewCake - Design a ticket sales site