Quick Overview

Recommend films to a new user by keeping only existing users whose viewing history contains every film the new user watched, then ranking their other films by how many kept users watched them. It tests subset checks, counting with hash maps, and deterministic sorting with a tie-breaking rule.

Recommend Films From Users Whose History Contains Everything the New User Watched

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Recommend films to a new user based on what existing users have watched. You are given every existing user's viewing history and the list of films the new user has watched. Keep only the existing users whose history contains every film the new user watched, and skip all other users. Then recommend the films that the kept users watched but the new user has not, ranked by how many kept users watched each film, most first. The report's example: user 1 watched `a, b, c, d, e`, user 2 watched `a, c, d`, user 3 watched nothing, and the new user watched `a, c`. Users 1 and 2 are kept; `d` was watched by two kept users and `b` and `e` by one each, so the answer is `[d, b, e]`. This version fixes the order among films with equal counts. ### Function Signature ```python def recommend_films(histories: list[list[str]], watched: list[str]) -> list[str]: ``` ### Rules - `histories[i]` lists the films existing user `i` has watched; `watched` lists the films the new user has watched. - A user is kept when every film in `watched` appears in that user's history. A history equal to `watched` counts. If `watched` is empty, every user is kept. - A film is a candidate when it appears in at least one kept user's history and does not appear in `watched`. - A candidate's score is the number of kept users whose history contains it. - Return the candidates sorted by score descending, and by film name ascending (plain string comparison) when scores are equal. Return an empty list when there are no candidates. ### Constraints - `0 <= len(histories) <= 10^4` - `0 <= len(histories[i]) <= 10^3`, and the total number of entries across all histories is at most `2 * 10^5` - `0 <= len(watched) <= 10^3` - Films within one history are distinct, and films within `watched` are distinct. - Film names are nonempty strings of at most 20 lowercase letters and digits. ### Examples **Example 1** ```text Input: histories = [["a", "b", "c", "d", "e"], ["a", "c", "d"], []], watched = ["a", "c"] Output: ["d", "b", "e"] ``` Users 0 and 1 have both `a` and `c`; user 2 does not. Scores: `d` 2, `b` 1, `e` 1, and the tie between `b` and `e` is broken by name. **Example 2** ```text Input: histories = [["x", "y"], ["y", "z"], ["y"]], watched = [] Output: ["y", "x", "z"] ``` With nothing watched, every user is kept. `y` appears in three histories, `x` and `z` in one each. **Example 3** ```text Input: histories = [["a", "c"], ["a", "b", "c"], ["b", "c"]], watched = ["a", "c"] Output: ["b"] ``` User 0's history equals `watched`, so it is kept but contributes no candidate. User 1 is kept and contributes `b`. User 2 lacks `a` and is skipped, so its `b` does not count, and the score of `b` is 1.

Overview: Recommend films to a new user by keeping only existing users whose viewing history contains every film the new user watched, then ranking their other films by how many kept users watched them. It tests subset checks, counting with hash maps, and deterministic sorting with a tie-breaking rule.

Read the full Bloomberg Software Engineer interview experience this question came from

You are building a simple film recommender. You are given `histories`, where `histories[i]` lists the films that existing user `i` has watched, and `watched`, the list of films a new user has watched. Implement `recommend_films(histories, watched)` to recommend films to the new user using these rules: 1. **Keep** an existing user only when every film in `watched` appears in that user's history. A history equal to `watched` counts as kept. If `watched` is empty, every user is kept. Every other user is skipped, and nothing in a skipped user's history is used. 2. A film is a **candidate** when it appears in at least one kept user's history and does not appear in `watched`. 3. A candidate's **score** is the number of kept users whose history contains it. Return the candidates sorted by score in descending order. When two candidates have the same score, order them by film name in ascending plain string comparison (character by character, so digits come before letters and a name comes before any longer name that starts with it; for example `"10"` comes before `"1a"`, `"1a"` before `"9"`, and `"ab"` before `"abc"`). Return an empty list when there are no candidates. Every score is at most `10^4`, so it fits in a 32-bit integer. ### Example 1 ```text Input: histories = [["a", "b", "c", "d", "e"], ["a", "c", "d"], []], watched = ["a", "c"] Output: ["d", "b", "e"] ``` Users 0 and 1 both have `a` and `c`, so they are kept; user 2 is skipped. `d` was watched by two kept users and `b` and `e` by one each; the tie between `b` and `e` is broken by name. ### Example 2 ```text Input: histories = [["a", "c"], ["a", "b", "c"], ["b", "c"]], watched = ["a", "c"] Output: ["b"] ``` User 0's history equals `watched`, so it is kept but contributes no candidate. User 1 is kept and contributes `b`. User 2 lacks `a` and is skipped, so its `b` does not count, and the score of `b` is 1. ### Constraints - `0 <= len(histories) <= 10^4` - `0 <= len(histories[i]) <= 10^3`, and the total number of entries across all histories is at most `2 * 10^5` - `0 <= len(watched) <= 10^3` - Films within one history are distinct, and films within `watched` are distinct. - Film names are nonempty strings of at most 20 lowercase letters and digits.

Constraints

  • 0 <= len(histories) <= 10^4
  • 0 <= len(histories[i]) <= 10^3, and the total number of entries across all histories is at most 2 * 10^5
  • 0 <= len(watched) <= 10^3
  • Films within one history are distinct, and films within watched are distinct.
  • Film names are nonempty strings of at most 20 lowercase letters and digits.

Examples

Input: ([['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd'], []], ['a', 'c'])

Expected Output: ['d', 'b', 'e']

Explanation: Source Example 1: users 0 and 1 are kept, the empty history is skipped; d scores 2, b and e tie at 1 and are ordered by name.

Input: ([['a', 'c'], ['a', 'b', 'c'], ['b', 'c']], ['a', 'c'])

Expected Output: ['b']

Explanation: Source Example 3: user 0 equals watched and is kept but adds nothing; user 2 lacks a, so its b does not count.

Hints

  1. Settle whether each existing user is kept before looking at the rest of their films: a skipped user's films never contribute to any score.
  2. A film the new user has already watched is never recommended, even if every kept user watched it too.
  3. Order by score first; names only break ties, and they compare as plain strings, so '10' comes before '9' and 'ab' before 'abc'.

Film Recommendations from Matching Viewing Histories

mediumBloombergSoftware Engineer

You are building a simple film recommender. You are given histories, where histories[i] lists the films that existing user i has watched, and watched, the list of films a new user has watched. Implement recommend_films(histories, watched) to recommend films to the new user using these rules:

  1. Keep an existing user only when every film in watched appears in that user's history. A history equal to watched counts as kept. If watched is empty, every user is kept. Every other user is skipped, and nothing in a skipped user's history is used.
  2. A film is a candidate when it appears in at least one kept user's history and does not appear in watched.
  3. A candidate's score is the number of kept users whose history contains it.

Return the candidates sorted by score in descending order. When two candidates have the same score, order them by film name in ascending plain string comparison (character by character, so digits come before letters and a name comes before any longer name that starts with it; for example "10" comes before "1a", "1a" before "9", and "ab" before "abc"). Return an empty list when there are no candidates.

Every score is at most 10^4, so it fits in a 32-bit integer.

Example 1

Input:  histories = [["a", "b", "c", "d", "e"], ["a", "c", "d"], []], watched = ["a", "c"]
Output: ["d", "b", "e"]

Users 0 and 1 both have a and c, so they are kept; user 2 is skipped. d was watched by two kept users and b and e by one each; the tie between b and e is broken by name.

Example 2

Input:  histories = [["a", "c"], ["a", "b", "c"], ["b", "c"]], watched = ["a", "c"]
Output: ["b"]

User 0's history equals watched, so it is kept but contributes no candidate. User 1 is kept and contributes b. User 2 lacks a and is skipped, so its b does not count, and the score of b is 1.

Constraints

  • 0 <= len(histories) <= 10^4
  • 0 <= len(histories[i]) <= 10^3, and the total number of entries across all histories is at most 2 * 10^5
  • 0 <= len(watched) <= 10^3
  • Films within one history are distinct, and films within watched are distinct.
  • Film names are nonempty strings of at most 20 lowercase letters and digits.

Examples

Example 1
Input
([['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd'], []], ['a', 'c'])
Output
['d', 'b', 'e']
Notes
Source Example 1: users 0 and 1 are kept, the empty history is skipped; d scores 2, b and e tie at 1 and are ordered by name.
Example 2
Input
([['a', 'c'], ['a', 'b', 'c'], ['b', 'c']], ['a', 'c'])
Output
['b']
Notes
Source Example 3: user 0 equals watched and is kept but adds nothing; user 2 lacks a, so its b does not count.

Constraints

  • •0 <= len(histories) <= 10^4
  • •0 <= len(histories[i]) <= 10^3, and the total number of entries across all histories is at most 2 * 10^5
  • •0 <= len(watched) <= 10^3
  • •Films within one history are distinct, and films within watched are distinct.
  • •Film names are nonempty strings of at most 20 lowercase letters and digits.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def recommend_films(histories: list[list[str]], watched: list[str]) -> list[str]:
Sample call
recommend_films([['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd'], []], ['a', 'c'])
Language
Case 1
Input
([['a', 'b', 'c', 'd', 'e'], ['a', 'c', 'd'], []], ['a', 'c'])
Expected
['d', 'b', 'e']
Case 2
Input
([['a', 'c'], ['a', 'b', 'c'], ['b', 'c']], ['a', 'c'])
Expected
['b']

Browse More Questions

Show the approach

Approach

Put the films of watched into a hash set need, then process each history once. First count how many of its films are in need. Films within one history are distinct and so are the films in watched, so the history contains every watched film exactly when that count equals the size of need; with an empty watched the count is 0 and every user is kept, as the rules require. A history that fails the test is skipped and none of its films are counted. For a kept history, add 1 to the counter of each of its films that is not in need. Invariant: after processing any prefix of histories, each counter equals the number of kept users in that prefix whose history contains the film, because a kept user lists each film at most once and skipped users never touch a counter. At the end the counted films are exactly the candidates (present in some kept history, not watched) and each counter is that candidate's score. Sorting by the key (-score, name) gives score descending with ties in ascending plain string order (digits before letters, a prefix before its extensions). Edge cases: no histories, no kept user, or kept histories that hold only watched films leave no counters, so the result is []; a history equal to watched is kept but adds nothing; watched films never reach the output even when every kept user has them. Scores are at most 10^4, so 32-bit counters suffice. With T the total number of history entries, W = len(watched) and C <= T the number of candidates, the scan costs O(T + W) hash operations on names of at most 20 characters and the sort costs O(C log C).

Time complexity:
O(T + W + C log C), where T is the total number of history entries, W = len(watched) and C <= T is the number of candidates
Space complexity:
O(W + C)