Hey everyone,

Thought I'd give back. Just finished an interview for Meta 2 weeks ago. Got the results 3-4 days after. 45 Minute phone technical with Tech Lead ML Engineer. NONE of these two questions were on FB tagged :(

1. Design a Data Structure that can do insert(), remove(), and getRandomAccess()
   Follow-up: How can we do this with O(1) time and O(n) space.

Example:

Input:    insert(0), insert(1), insert(2), remove(0), getRandomAccess()
Output:   None, None, None, None, 1 #(could've been 2, since it's random)

Easy part is to keep track of all unique inserts. But what happens when we remove? How do we utilize O(1) for all runtimes? So, we should utilize a dictionary to keep track of which element has been inserted and their positions. Then, we should also have a another array for their physical locations.

The trick is to NOT remove the actual integers. We should just swap it to a location that won't be utilized and then only get RandomAccess to valid indexes that aren't removed. We also need to be careful of what happens if we reinsert 0, then we should reverse swap it to a valid position. Was not a hard question, just a lot of small complexity and edge cases.

2. Given a friend class and given an API to get the neighbors of friends, return all 2nd-degree connections for a given user_id?
   Follow-up: Utilizing the API, find the kth most individuals with the most friends

The first part is easy. We first call the API to get our neighbors and then call the API to get our neighbors neighbors. HOWEVER, we must be careful here because we are essentially double counting each person. So, to get all second-degree connections, we must ignore (use a set) the original user_id AND all of the neighbors of that user_id.

Part two also wasn't too bad. We can simply just create a counter after we've called the API on every single node (make sure we keep track of user_ids that we've seen so we don't infinitely loop). Then, we can simply utilize a heap to find the kth-most (or if you're really crazy and have time, use the quickselect trick).

Overall, both of these questions weren't necessarily hard on their own. It's just doing them both in 35 minutes (5 minutes at the beginning was introducing/talking), 35 minutes to code, and then they left me 5 minutes at the end to ask questions.

Results: Rejected! However, they told me to re-interview in 3 months since I almost got through both questions.

Wishing everyone the best of luck! :)