Question: Google Interview Experience | 2023 Graduate Offcampus
13
Entering edit mode

Round 1 | 45 mins Technical + 15 mins (G&L)

Click here to Practice

Given Two time series

  • The time series denote the spike that we have to make in discrete manner at that time.
  • The value remains same for all time until the next updated spike.
  • let T1 = [ (0,1) , (3,5) , (7,2) ] and T2 = [ (2,2) , (3,3) , (6,1) ]
  • For T1 , value = 1 for [0,3) , value = 5 for [3,7) , value = 2 for [7,inf)
  • For T2 , value = 0 for [0,2) , value = 2 for [2,3) , value = 3 for [3,6) and value = 1 for [6,inf)
  • We have to return a new List which denotes T1 + T2
  • T1 + T2 = [ (0,1) , (2,3) , (3,8) , (6,6) , (7,3) ]

Some good clarifications i asked :

  • is time and value integer? ( No , can be double)
  • is List sorted based on time? (Yes)
  • Range of time and value? (Assume Infinite)
  • Can there be 2 spikes for same time? (No , time wont be repeated)

  • Inititally misunderstood the question , clarified the question again. (wasted 10mins)

  • Was able to explain and code up a O(N) solution using two pointers.

Follow up questions

  • Lets say we have M such time series , how should we approach?
  • Came up with divide and conquer strategy to split M->M/2->M/4 ....2 and merge them bottom up using code to merge T1+T2.
  • Time Complexity - O(Log(M)*N) , space = O(Log(M)) (recursion stack)

Round 2 , 45mins technical


Implement a Cache management class.

class Cache{
    Cache(int capacity){};

    int get(int key);

    int put(int key , int value);
}

Has fixed capacity and Remove the oldest inserted key if there is size overflow.

Some good clarifications i asked :

  • will key be integer ? (Yes)
  • do we need to handle cases for invalid requests? (example capacity <= 0) ? (Yes)
  • will value be integer? (Yes)

Follow Up questions

  • Implement LRU cache.

Pretty much finished this round in 25mins and had good amount of chat regarding the work i did during my summer internship.


Round 3 , 45mins technical + 15mins G&L


Initial Problem : Easy version

Click here to Practice

Follow Up : Hard Version

Click here to Practice

Under Progress

Question

Modifiy the input string with following substitutions.

S = "Alice saw a tiger"
subs = [(0,5,"Bob") , (13,18,"cat")]  {L,R,string}
result = "Bob saw a cat"

Some good clarifications i asked :

  • is subs List sorted? (No);
  • Are all characters english alphabets? (Yes);
  • Are the ranges disjoint? (Yes , for now :) )

Approach for initial problem

  • Came up with a binary search solution ,
  • sort the subs List based on L
  • scan through S from left to right and search for match in subs.
  • Replace if there is a match , else append current character and keep scanning.

Follow up

  • The ranges are not disjoint now. ( we should replace with the string of an overlapping range that comes first in subs)
  • subs = [ (4,6,"hi") , (1,2,"bye") , (2,5,"ohho") , (6,6,"hehe")];
  • The range 4,6 overlaps 2,5 which overlaps 1,2 , Hence 1,2 indirectly overlaps 4,6.
  • Now when we reach index 1 in S , we will replace it with "hi" and jump to R = 6.
  • since range (4,6) is the first range in subs that indirectly overlaps with (1,2).

Approach for follow up

  • Came up with a Disjoint set Union solution.
  • Merge those ranges that overlap with each other.
  • Do Union by Size and store the [min_index , minL , maxR] for each component.
  • Make a new merged_subs = [ (minL , maxR , subs[min_index])] for each DSU component.
  • Now the question is same as first question , modifying string with disjoint ranges.

G&L (some i remember)

  • What would you do if your team lacks innovation
  • What if your manager isnt being helpful
  • What if one of your team mates arent speaking up
  • What if your team is not able to figure out on how to implement something.
  • How to bring up innovations ```
Entering edit mode
5

Great job solving with good speed, well-asked Clarification questions! Best wishes!

Thanks for sharing the experience honestly with the community, it should be super helpful for all preparing for placements.

ADD REPLYlink 21 months ago
admin
1.4k
5
Entering edit mode

Question 1 : Solution

Adding 2 Time Series Data

  • First part of the problem is to figure out how to add 2 time series data.
  • Looking on few test cases will help you understand how the summation works and will help you come up with a two-pointer method.
  • The main idea is to append the value to the result whose time is lesser and the magnitude of this point will depend on the magnitude of previously added point.
  • There are few edge cases you might need to handle , but the below code will give you a good idea on the implementation.

Adding K Time Series Data

  • We know how to add two time series data , and adding the K time series in any order should produce the same result.
  • We can use a Divide and Conquer approach to add them.
  • Let Merge( i , j ) = result of adding all time series data from T[i ..... j]
  • Merge(0 , K) -> Merge(0,K/2) + Merge(K/2+1 , K)
  • Base Case = Merge( i , i ) = return T[i]

Complexity

  • O(N) to add two time series.
  • O(NLog(K)) to add K time series of average length N.

Code

ADD COMMENTlink 17 months ago Gigaliths 540
Entering edit mode
0

Should not the overall TC be: O(N*M*log(k)), 

ADD REPLYlink 7 weeks ago
Ashutosh Saini
• 10

Login before adding your answer.

Similar Posts
Loading Similar Posts