Recommend movies by shared ratings

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.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

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

Example 1

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']])
Output: ['Interstellar', 'Memento']

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

Example 2

Input: ('Alice', [])
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

Example 1

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

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

Example 2

Input: ('A', [['A', 'S', '5'], ['A', 'Seen', '2'], ['B', 'S', '5'], ['B', 'Seen', '5'], ['B', 'Z', '5'], ['C', 'S', '4'], ['C', 'ARec', '4']])
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

Example 1

Input: ([])
Output: []

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

Example 2

Input: ([['Alice', 'Matrix', '5'], ['Alice', 'Matrix', '5'], ['Bob', 'Matrix', '4']])
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

Example 1

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

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

Example 2

Input: ('A', [['A', 'S', '5'], ['B', 'S', '5'], ['B', 'M1', '5'], ['B', 'M2', '4']], ['M1', 'M1', 'M2'])
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.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

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.

Recommended Approach

Use the string constraints to choose between two pointers, a stack, frequency counts, prefix/suffix state, or dynamic programming. Maintain the invariant that processed characters have already been normalized, counted, or matched according to the operation.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

Most direct string scans are O(n) time. Space ranges from O(1) for two pointers to O(n) for stacks, maps, or DP tables.

Edge Cases and Tests

Empty string, length 1, repeated characters, invalid characters, case sensitivity, Unicode vs ASCII, and very long input.