Katkat
Back

Solve friend recommendations and time-versioned maps

Lead BankSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to model a time-versioned key-value store and leverage graph adjacency structures to perform multi-hop relationship recommendations.

Part 1: Time-Versioned Store

Design a data structure VersionedMap that stores key-value pairs where each value is associated with a timestamp. The system should support retrieving the value for a key at a specific time_t.

  • put(key, value, timestamp): Stores the value at the given timestamp.
  • get(key, timestamp): Returns the value valid at the specified time. If multiple values exist, return the one with the largest timestamp less than or equal to the requested time. If no such value exists, return null.

Part 2: Friend Recommendations

Given a graph of users where edges represent friendships, implement a function get_recommendations(user_id, friendships) to find potential friends. A 'potential friend' is defined as a user who is not currently a direct friend but has at least two mutual friends with the target user.

Constraints

  • timestamp is a non-negative integer.
  • friendships is a list of tuples (u1, u2).
  • The graph is undirected.
  • Focus on clean API design and efficiency for Part 1 (logarithmic retrieval).

Example

VersionedMap:

vm = VersionedMap()
vm.put('a', 'v1', 10)
vm.put('a', 'v2', 20)
vm.get('a', 15) # Returns 'v1'
vm.get('a', 25) # Returns 'v2'

get_recommendations: If A is friends with B and C, and B is friends with D, C is friends with D, and A is NOT friends with D: D is a candidate for A because they share mutual friends B and C.

Hints

Hint 1

For the versioned store, use a dictionary mapping keys to a sorted list or an array of (timestamp, value) pairs, then use binary search to find the latest valid entry.

Hint 2

To solve the recommendation problem, perform a two-hop traversal starting from the target user to identify nodes that are distance 2 away.

Hint 3

In the recommendation logic, use a frequency map to count how many mutual friends each candidate has, filtering out existing friends and the user themselves.

Follow-up questions

  • How would you handle the 'VersionedMap' if the number of updates per key is extremely large? Would you use a different data structure?
  • How does the complexity of the recommendation algorithm change if we search for friends within a 3-hop radius instead of 2-hop?
  • In a real-world scenario with millions of users, how would you distribute the graph data across multiple servers to compute recommendations?