Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Recommend movies by shared ratings states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Recommend movies by shared ratings

Company: Coinbase

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Write a function recommendations(user, ratings) that returns a list of movies to recommend to the given user based on shared preferences. Each rating is a triplet [User Name, Movie Name, Rating] where Rating ∈ {1,2,3,4,5} (strings). Define two users as having similar taste if they have both rated the same movie with a 4 or 5. Recommend a movie to the user if the user has not rated it and any similar-taste user rated it a 4 or 5. Ensure the output contains unique movie names and justify any ordering you choose.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Recommend movies by shared ratings states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Part 1: In-Memory Movie Recommendations by Shared High Ratings

Implement solution(user, ratings) to recommend movies for a target user. Two users have similar taste if they have both rated at least one same movie with rating 4 or 5. Recommend a movie if the target user has not rated it and at least one similar-taste user rated it 4 or 5. Assumption: records are valid triplets of strings, duplicate identical records may appear, and output is sorted lexicographically for deterministic ordering.

Constraints

  • 0 <= len(ratings) <= 100000
  • Each rating record has exactly three strings: user name, movie name, and rating.
  • rating is one of {'1', '2', '3', '4', '5'}.
  • Duplicate records are allowed and must not create duplicate recommendations.
  • A movie already rated by the target user, even with a low rating, must not be recommended.

Examples

Input: ('Alice', [['Alice', 'Matrix', '5'], ['Alice', 'Inception', '4'], ['Alice', 'Titanic', '2'], ['Bob', 'Matrix', '5'], ['Bob', 'Interstellar', '5'], ['Bob', 'Titanic', '5'], ['Carol', 'Inception', '4'], ['Carol', 'Memento', '4'], ['Dave', 'Matrix', '3'], ['Dave', 'Avatar', '5']])

Expected Output: ['Interstellar', 'Memento']

Explanation: Bob and Carol are similar to Alice through Matrix and Inception. Titanic is excluded because Alice already rated it.

Input: ('Alice', [])

Expected Output: []

Explanation: Edge case: no ratings means no similar users and no recommendations.

Hints

  1. Build sets of all movies rated by the target user and movies rated highly by each user.
  2. First find similar users through shared high-rated movies, then collect their high-rated unseen movies.

Part 2: Streaming-Compatible Movie Recommendations

Implement solution(user, ratings) for the same recommendation rule, but treat ratings as a replayable stream that may be too large for a full in-memory user-to-movie graph. The function may iterate over ratings multiple times. Use a streaming-friendly approach: collect only the target user's rated and high-rated movies, then find similar users, then collect recommendations. Return unique movie names sorted lexicographically.

Constraints

  • 0 <= len(ratings) <= 1000000
  • The ratings stream is replayable, so multiple linear passes are allowed.
  • Each rating record has exactly three strings.
  • rating is one of {'1', '2', '3', '4', '5'}.
  • Do not rely on ratings being sorted by user or movie.

Examples

Input: ('A', [['B', 'Early', '5'], ['A', 'Shared', '5'], ['B', 'Shared', '4']])

Expected Output: ['Early']

Explanation: B's recommendable movie appears before B is known to be similar, so a streaming solution needs another pass.

Input: ('A', [['A', 'S', '5'], ['A', 'Seen', '2'], ['B', 'S', '5'], ['B', 'Seen', '5'], ['B', 'Z', '5'], ['C', 'S', '4'], ['C', 'ARec', '4']])

Expected Output: ['ARec', 'Z']

Explanation: B and C are similar through S. Seen is excluded because A already rated it.

Hints

  1. A single pass is not enough if a similar user appears before the shared movie that proves similarity.
  2. Think in phases: target state, similar users, then recommendations.

Part 3: Validate Production Invariants for Ratings Data

Before computing recommendations, production code should assert invariants about the input data. Implement solution(ratings) that returns which invariants are violated. Check for malformed records, empty user names, empty movie names, invalid rating values, and conflicting ratings for the same exact user/movie pair. Return unique error codes in a fixed order.

Constraints

  • 0 <= len(ratings) <= 100000
  • A valid record has exactly three fields: user name, movie name, rating.
  • User and movie names must be non-empty after stripping whitespace.
  • rating must be one of {'1', '2', '3', '4', '5'}.
  • Exact duplicate records are allowed, but two different ratings for the same exact user/movie pair violate CONFLICTING_RATING.

Examples

Input: ([])

Expected Output: []

Explanation: Edge case: no records means no invariant violations.

Input: ([['Alice', 'Matrix', '5'], ['Alice', 'Matrix', '5'], ['Bob', 'Matrix', '4']])

Expected Output: []

Explanation: Exact duplicate ratings are allowed.

Hints

  1. Use a set for error codes so each violation type is reported once.
  2. Use a dictionary keyed by (user, movie) to detect conflicting ratings.

Part 4: Detect Off-by-One, Duplicate, and Tie-Breaking Bugs in Recommendation Output

You are given ratings and a candidate output produced by a recommendation implementation. Implement solution(user, ratings, candidate_output) that acts as a small oracle and reports which common bug categories are detectable. The correct recommendation output uses rating threshold 4 or 5, unique movie names, and lexicographic ordering.

Constraints

  • 0 <= len(ratings) <= 100000
  • ratings contains valid triplets with rating in {'1', '2', '3', '4', '5'}.
  • candidate_output is a list of strings.
  • DUPLICATE means candidate_output contains the same movie more than once.
  • TIE_BREAKING means, after removing duplicates while preserving first occurrence, the candidate has the correct set but is not lexicographically sorted.
  • OFF_BY_ONE means the candidate includes a movie that would only be eligible if rating 3 counted as high, or misses a correct movie that would disappear if only rating 5 counted as high.

Examples

Input: ('A', [], [])

Expected Output: []

Explanation: Edge case: empty ratings and empty candidate output have no detectable bug.

Input: ('A', [['A', 'S', '5'], ['B', 'S', '5'], ['B', 'M1', '5'], ['B', 'M2', '4']], ['M1', 'M1', 'M2'])

Expected Output: ['DUPLICATE']

Explanation: The set and order are otherwise correct, but M1 appears twice.

Hints

  1. Compute the correct recommendation set with threshold 4, then compare against threshold 3 and threshold 5 variants.
  2. Check duplicates and ordering independently from set correctness.

Loading coding console...