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 hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Meta during technical interviews.

Build a Friend Recommender | Meta Coding Question

Quick Overview

This question evaluates proficiency in graph algorithms, recommendation system logic, input validation, metric design, and test-driven software implementation within the coding & algorithms domain for a machine learning engineering role, focusing on practical application of graph-based recommendation strategies.

Build a Friend Recommender

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given a simple social-graph codebase where each user has only an `id` and a collection of current friends. Starting from existing functions and unit tests, complete the following tasks: 1. Fix `valid_recommend(user, candidates)` so it rejects invalid recommendations, including recommending the user themself or someone who is already a friend. 2. Implement `random_recommend(user, candidates)` to return a random valid recommendation. 3. Define a measurable recommendation-quality metric using only graph structure, since no profile features are available. 4. Implement a `mutual_friends_recommend` strategy that ranks non-friends by the number of mutual friends, and add tests for it. Return any deterministic tie-broken result when multiple candidates have the same score.

Quick Answer: This question evaluates proficiency in graph algorithms, recommendation system logic, input validation, metric design, and test-driven software implementation within the coding & algorithms domain for a machine learning engineering role, focusing on practical application of graph-based recommendation strategies.

Part 1: Filter Invalid Friend Recommendations

You are given a user ID, a list of current friends, and a raw candidate list. A candidate is invalid if it is the same as the user or is already in the friend list. Return all unique valid candidate IDs in the order they first appear.

Constraints

0 <= len(friends), len(candidates) <= 100000
User IDs are integers
The friends list may be empty
Candidates may contain duplicates

Examples

Input: (1, [2, 3], [1, 2, 4, 5])

Expected Output: [4, 5]

Explanation: 1 is the user themself and 2 is already a friend, so only 4 and 5 remain.

Input: (10, [20], [30, 30, 10, 20, 40])

Expected Output: [30, 40]

Explanation: 30 is valid but should appear once. 10 is self and 20 is already a friend.

Input: (7, [1, 2], [])

Expected Output: []

Explanation: Edge case: no candidates.

Input: (5, [], [5])

Expected Output: []

Explanation: Edge case: the only candidate is the user themself.

Hints

Checking whether a candidate is already a friend should be O(1), not O(n).
Use one structure to recognize current friends and another to avoid returning the same valid candidate twice.

Part 2: Seeded Random Valid Recommendation

Build a testable random recommender. First filter candidates exactly as in Part 1: remove the user themself, existing friends, and duplicates while preserving first appearance. If no valid candidate exists, return None. Otherwise, choose one valid candidate using the deterministic pseudo-random rule index = (seed * 31 + 7) % len(valid). Return valid[index].

Constraints

0 <= len(friends), len(candidates) <= 100000
User IDs and seed are integers
Candidates may contain duplicates
The deterministic formula must be used exactly as stated

Examples

Input: (1, [2, 3], [1, 4, 5, 6], 0)

Expected Output: 5

Explanation: Valid list is [4, 5, 6]. Index = (0 * 31 + 7) % 3 = 1, so return 5.

Input: (10, [20], [30, 40, 30, 10, 20], 2)

Expected Output: 40

Explanation: Valid list is [30, 40]. Index = (2 * 31 + 7) % 2 = 1, so return 40.

Input: (5, [1, 2], [5, 1, 2], 99)

Expected Output: None

Explanation: Edge case: every candidate is invalid.

Input: (7, [], [7, 8, 8], 123)

Expected Output: 8

Explanation: Edge case: only one unique valid candidate remains.

Hints

It is easier to pick a random item after you build the filtered valid list.
Make sure the no-valid-candidate case is handled before taking a modulo.

Part 3: Compute a Graph-Only Recommendation Quality Score

No profile features are available, so use only graph structure. Define the quality of a recommendation list as the total mutual-friend score: for each unique valid recommended user, add the number of mutual friends shared with the target user. Ignore invalid recommendations: the user themself, users who are already friends with the target user, duplicate recommendation IDs, and IDs that do not appear in the graph.

Constraints

1 <= number of users in graph <= 10000
0 <= total number of friendship links <= 200000
The graph is intended to be undirected
Recommendation IDs may contain duplicates or IDs missing from the graph

Examples

Input: ({1: [2, 3], 2: [1, 3, 4], 3: [1, 2, 4], 4: [2, 3], 5: []}, 1, [4, 5, 2, 4, 1])

Expected Output: 2

Explanation: Valid unique recommendations are 4 and 5. User 1 shares 2 mutual friends with 4 and 0 with 5, so total score is 2.

Input: ({1: [2], 2: [1], 3: []}, 1, [])

Expected Output: 0

Explanation: Edge case: empty recommendation list.

Input: ({1: [2], 2: [1], 3: []}, 1, [1, 2, 4])

Expected Output: 0

Explanation: 1 is self, 2 is already a friend, and 4 is missing from the graph.

Input: ({1: [2, 3, 4], 2: [1, 5], 3: [1, 5], 4: [1, 5], 5: [2, 3, 4]}, 1, [5, 2, 5, 4, 1])

Expected Output: 3

Explanation: Only 5 is a unique valid recommendation. It shares mutual friends 2, 3, and 4 with user 1.

Hints

The score of a single recommendation is based on the intersection size of two friend sets.
Precomputing friend lists as sets makes repeated mutual-friend checks much faster.

Part 4: Rank Recommendations by Mutual Friends

Given an undirected social graph and a target user, return every non-friend in ranked order. Rank candidates by the number of mutual friends they share with the target user, from highest to lowest. If two candidates have the same mutual-friend count, the smaller user ID must come first. Include candidates with zero mutual friends at the end. If there are no non-friends to recommend, return an empty list.

Constraints

1 <= number of users in graph <= 10000
0 <= total number of friendship links <= 200000
The graph is intended to be undirected
User IDs are integers

Examples

Input: ({1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3], 5: []}, 1)

Expected Output: [4, 5]

Explanation: User 4 has 2 mutual friends with user 1. User 5 has 0, so 4 comes first.

Input: ({1: [2], 2: [1, 3, 4], 3: [2], 4: [2], 5: []}, 1)

Expected Output: [3, 4, 5]

Explanation: Users 3 and 4 each have 1 mutual friend, so the smaller ID comes first. User 5 has 0.

Input: ({1: []}, 1)

Expected Output: []

Explanation: Edge case: a graph with a single user has no non-friends to recommend.

Input: ({1: [], 2: [], 3: [], 4: []}, 1)

Expected Output: [2, 3, 4]

Explanation: Edge case: all candidates have 0 mutual friends, so the order is by user ID.

Input: ({1: [2, 3], 2: [1, 3], 3: [1, 2]}, 1)

Expected Output: []

Explanation: Edge case: user 1 is already friends with everyone else.

Hints

A candidate is anyone in the graph who is not the target user and not already a friend.
Sort by a pair such as negative mutual count and then user ID to get the required order.

Quick Overview