How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Lead.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Lead during technical interviews.

Solve friend recommendations and time-versioned maps

Quick Overview

This question evaluates the candidate's ability to design and implement specialized data structures for graph-based friend recommendation logic and time-versioned key-value storage, testing competencies in algorithmic design, data modeling, and complexity analysis.

Company: Lead

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Solve the following two coding problems. ## Problem 1: Friend recommendation from weighted likes You are given a directed weighted graph of users. Each record has the form: ```text from_user, to_user, like_count ``` `like_count` is the number of times `from_user` liked `to_user`. Implement a data structure that supports: 1. `getLikeCount(userA, userB)`: return how many times `userA` liked `userB`. If there is no record, return `0`. 2. `recommendFriend(user)`: recommend one user according to the following rule: - First find the users that `user` likes the most. - For each such favorite user, look at the users that favorite user likes the most. - A recommended user must not be the original `user` and must not already be a friend of the original `user`. - Two users are considered friends if they have liked each other at least once. - Like counts may tie. If all candidates at the current highest like count fail, continue to the next lower like count until a valid recommendation is found. - If multiple valid users are tied, you may return any one of them, but your behavior should be deterministic if the interviewer asks for it. - If no valid recommendation exists, report an error or return a sentinel value such as `null`. Discuss the data structures you would use and implement the required methods. ## Problem 2: Time-versioned key-value map with snapshots Design and implement a key-value store with timestamped writes. It should support: ```text put(key, value, timestamp) ``` Stores `value` for `key` at `timestamp`. ```text get(key, timestamp) ``` Returns the value associated with `key` at the greatest timestamp less than or equal to `timestamp`. If the key did not exist at or before that timestamp, return `null`. Additionally implement: ```text snapshot(timestamp) ``` Returns a map containing the visible value of every key at the greatest timestamp less than or equal to `timestamp`. Keys that did not exist at or before that timestamp should be omitted. Discuss complexity and edge cases, including duplicate timestamps, missing keys, and large numbers of keys.

Quick Answer: This question evaluates the candidate's ability to design and implement specialized data structures for graph-based friend recommendation logic and time-versioned key-value storage, testing competencies in algorithmic design, data modeling, and complexity analysis.

Implement one function that processes operations for two independent data structures. Part 1 is a directed weighted like graph. Each initial record is `(from_user, to_user, like_count)`, meaning `from_user` liked `to_user` `like_count` times. Duplicate records for the same pair should be summed. Support `getLikeCount(userA, userB)`, which returns the total number of likes from `userA` to `userB`, or `0` if no such record exists. Support `recommendFriend(user)`. To recommend a user: 1. Consider the users that `user` likes, grouped by like count from highest to lowest. 2. For the current highest group of favorite users, look at users liked by those favorite users, again considering candidate like counts from highest to lowest. 3. A candidate is invalid if it is the original `user` or if it is already a friend of the original `user`. 4. Two users are friends if they have liked each other at least once. 5. If all candidates at a candidate like-count level are invalid, continue to the next lower candidate like-count level. If none work for the current favorite-user group, continue to the next lower favorite-user group. 6. If multiple valid candidates are tied, return the lexicographically smallest user ID for deterministic behavior. 7. If no valid recommendation exists, return `None`. Part 2 is a time-versioned key-value map. It supports timestamped writes with `put(key, value, timestamp)`, point-in-time reads with `get(key, timestamp)`, and full snapshots with `snapshot(timestamp)`. A `get` returns the value written at the greatest timestamp less than or equal to the query timestamp. If duplicate writes occur for the same key and timestamp, the latest write overrides earlier writes at that timestamp. Your function receives the initial like records and a list of operations. It should return a list containing the return values of query operations only. `put` operations produce no output.

Constraints

0 <= len(like_records) <= 10^5
0 <= len(operations) <= 10^5
User IDs and keys are non-empty strings
1 <= like_count <= 10^9
Timestamps are integers in the range [-10^9, 10^9]
Stored values are not None, because None is used as the missing-value sentinel
For deterministic recommendations, ties are broken by lexicographically smallest user ID

Examples

Input: ([('alice', 'bob', 5), ('bob', 'carol', 4), ('bob', 'dave', 4), ('alice', 'erin', 2)], [('getLikeCount', 'alice', 'bob'), ('getLikeCount', 'alice', 'carol'), ('recommendFriend', 'alice'), ('put', 'x', 'one', 10), ('put', 'y', 'why', 5), ('get', 'x', 9), ('get', 'x', 10), ('snapshot', 10)])

Expected Output: [5, 0, 'carol', None, 'one', {'x': 'one', 'y': 'why'}]

Explanation: Alice likes Bob most. Bob's top liked users are Carol and Dave with equal weight, so the deterministic recommendation is Carol. The versioned map returns None before key x exists, then returns the visible values at timestamp 10.

Input: ([('u', 'a', 10), ('u', 'b', 10), ('a', 'u', 7), ('a', 'd', 5), ('b', 'c', 6), ('b', 'e', 6)], [('recommendFriend', 'u'), ('getLikeCount', 'u', 'a'), ('getLikeCount', 'a', 'u'), ('put', 'k', 'old', 1), ('put', 'k', 'override', 1), ('get', 'k', 1), ('snapshot', 1)])

Expected Output: ['c', 10, 7, 'override', {'k': 'override'}]

Explanation: User u's top favorites are a and b. Candidate u from a is invalid because it is the original user, so the algorithm continues to the next candidate like count. Candidates c and e are tied through b, and c is lexicographically smaller. For the map, the second put at timestamp 1 overrides the first.

Input: ([('ann', 'bob', 3), ('bob', 'ann', 2), ('bob', 'cat', 5), ('ann', 'cat', 1), ('cat', 'ann', 1)], [('recommendFriend', 'ann'), ('put', 'a', 'first', -5), ('put', 'b', 'bee', 0), ('get', 'a', -6), ('get', 'a', -5), ('snapshot', -1), ('snapshot', 100)])

Expected Output: [None, None, 'first', {'a': 'first'}, {'a': 'first', 'b': 'bee'}]

Explanation: Ann's best intermediate is Bob. Bob likes Cat most, but Cat is already Ann's friend because Ann and Cat liked each other. Bob's other candidate is Ann, which is invalid, so there is no recommendation. The timestamp tests include negative timestamps and snapshots before and after key b exists.

Input: ([], [('recommendFriend', 'nobody'), ('getLikeCount', 'x', 'y'), ('get', 'missing', 100), ('snapshot', 100), ('put', 'z', 'zed', 50), ('get', 'z', 49), ('get', 'z', 50)])

Expected Output: [None, 0, None, {}, None, 'zed']

Explanation: With an empty like graph, recommendations are impossible and missing like counts are zero. The map starts empty, so missing reads and snapshots return None and an empty dictionary respectively.

Hints

For the like graph, store outgoing edges in nested hash maps and group each user's outgoing neighbors by like count.
For the time-versioned map, keep a sorted list of timestamps per key and use binary search to find the greatest timestamp not exceeding the query timestamp.

Quick Overview