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
- 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.
- A film the new user has already watched is never recommended, even if every kept user watched it too.
- Order by score first; names only break ties, and they compare as plain strings, so '10' comes before '9' and 'ab' before 'abc'.