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.

Loading coding console...

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