Recently I gave round 1 for SWE III ML at Google, this was a dsa coding round. I have 4 years experience as a data scientist in a mid-size company. The interview was 45 minutes and was in the first week of July. I was asked a question and an advanced follow up on the same.
Initial Question
Given a list of events, each with a message and a timestamp. Please extract the most frequent one and give me its timestamps for further analysis.
Example ->
Event: ['error_1: 123', 'error_1: 234', 'error_2: 456']
Return: error_1 [123, 234]
My Answer
Initially I created a dictionary of events with list of timestamps as the values. For the maximum I was using a max heap but soon realised the heap is not needed and proceeded with coding the optimal solution with a max_counter.
class Solution:
def returnMost_frequent_better(self, events):
# O(n)
event_dict = {}
max_counter = 0
max_key = None
for event in events:
key, value = event.split(':')
value = int(value.strip())
if key not in event_dict:
event_dict[key] = [value]
else:
event_dict[key].append(value)
if len(event_dict[key]>max_counter):
max_counter = len(event_dict[key])
max_key = key
return event_dict[max_key]Time complexity - O(n) for the dictionary creation
Advanced Question
For the follow up, imagine that it's going to become a realtime system, and I will maintain a queue of N such events. When the queue is full, I will remove the oldest event from the queue. Every time a new event comes in, I will update the structure and get the most frequent event among the N events.
Example ->
N=2 (queue size)
Event: ['error_1: 123', 'error_1: 345']
event_element = 'error_1: 234'
delete- 'error_1: 123'
New_list= ['error_1: 345', 'error_1: 234']
return: error_1
My Answer
I actually misunderstood the question a bit and wrote a solution considering we have all the list of events and are not being passed one by one. Still was able to come up with a fair solution as given below.
Here the major dilemma was how to update and maintain the max_counter when an element is deleted.
class Solution:
def returnMost_frequent_better(self, events, N):
# O(n)
# We are passed all event_list and we handle >N, <N cases
event_dict = {}
max_counter = 0
max_key = None
time_heap = []
for i, event in enumerate(events):
key, value = event.split(':')
value = int(value.strip())
heapq.heappush(time_heap, (value, key))
size+=1
if size<N:
if key not in event_dict:
event_dict[key] = [value]
else:
event_dict[key].append(value)
if len(event_dict[key]>max_counter):
max_counter = len(event_dict[key])
max_key = key
else:
val_d, key_d = heapq.heappop(time_heap)[1]
event_dict[key].remove(val_d)
size-=1
new_max_key = None
new_max = 0
for key, val in event_dict.items():
if len(val)>new_max:
new_max_key = key
new_max = len(val)
max_key = new_max_key
return max_keyI was later told that I misunderstood the question and was told to write down my assumption. Overall it went well, prepping for the further rounds now.
Other Interviews:
- First Round | SWE III ML | Bengaluru
- Googleyness Round | SWE III ML
- Hiring Manager Round | Gemini Applications Team
Other Tech Firms
- Amazon | Interview (1st Round) | Applied Data Scientist | Bengaluru
- Freshworks | OA (1st Round) | Data Scientist | Bengaluru
- Razorpay | OA (1st Round) | Senior MLE | Bengaluru
- Avaamo | Interview | Senior MLE | Bengaluru
- Visa | Coding Round | Senior Data Role | Bengaluru