None of the code was executed. The interviewers just checked the logic..
Half of every session was behavioral a.k.a LP. Agh! Yak!
Q1:
Amazon trucks send their locations every x seconds. We need to record it in a way such that people can query how many times the trucks were at a certain location between arbitrary start and end times.
Impl. send and query meth.
Follow up: Change app to be able to query by truck id in addition to location & times. If not given the truck id for the query, output all the trucks and their number of visits at that loc-n.
My Impl
Stored every truck ping in a list @ map[loc]. For query meth, use BS for start and end times.
Return the index diff.
F_up: Add id to the map key: loc,id. Without truck id supplied, obtain the possible truck id's
that could visit the specific location. Use those in a for-loop: BS for every id.Q2:
Build a tree from the given graph edges. Find the tree root and the tree height.
Clarified: can assume the given tree is valid.
My Impl
Build the tree with parent node connection. Record the leaves during the build.
Go backwards from a leaf to find the root. Find the max height from the root.Q3:
Implement Thread sleep and resume methods. Turns out I had to reason and ask questions about the implementation: what is the data structure for storing thread id's? How often resume is getting called?
My Impl
I chose to store/insert threads in BST by (curr_time+t, id) in sleep(id,t) method.
Once the thread id is in BST, I proposed that it was going to be put to sleep by OS.
The interviewer asked to implement BST insert.
For resume() method, I implemented BST delete of all nodes with curr_time+t <= curr. time.
Follow up: what should delete output? -> List of id's woken up.
Need to run serialization on the deleted subtree.
Follow up 2: how would you output the sorted list? -> in-order traversal.
Did not have the time to impl. serialization.Q4:
System Design: design a product catalog with search as the main functionality.
My Impl
Distributed product indexing. This is similar to Twitter Search, imo.Result: Yuk