Full Interview Question: "Coding - Homepage Billboard Rotation" asked at Netflix

Problem Statement

Build a service that selects one movie or show title to display on a user's homepage billboard. Each title has a score representing how relevant it is to the user. The service should generally favor displaying titles with higher scores. However, to ensure diversity and avoid biasing the user's experience towards a small set of highly relevant titles, the service should also occasionally display titles with lower scores.

Examples

1. Given a list of titles with their scores: [ {"title": "Title A", "score": 10}, {"title": "Title B", "score": 8}, {"title": "Title C", "score": 12}, {"title": "Title D", "score": 7} ] The service should likely select "Title C" since it has the highest score.

2. Given a list of titles with their scores: [ {"title": "Title A", "score": 10}, {"title": "Title B", "score": 8}, {"title": "Title C", "score": 10}, {"title": "Title D", "score": 7} ] The service could select either "Title A" or "Title C" since they have the highest scores.

Constraints

1. The input list can contain any number of titles, from 1 to several thousand.
2. Scores are non-negative integers.
3. The service should be efficient and scalable, as it will be used in a production environment with millions of users.

Hints

1. Consider using a probabilistic approach to balance between selecting high-scoring titles and ensuring diversity.
2. Think about how to handle ties in scores and how to distribute the probability of selection among titles with the same score.
3. Consider the trade-offs between complexity and performance, and optimize for the most critical factors.

Solution

One possible solution is to use a weighted random selection algorithm. Here's a high-level approach:

1. Calculate the total score of all titles.
2. For each title, calculate its probability of being selected based on its score relative to the total score.
3. Normalize the probabilities so that they sum up to 1.
4. Use a random number generator to select a title based on the normalized probabilities.

Here's a sample implementation in Python:

`python import random

def select_title(titles): total_score = sum(title['score'] for title in titles) probabilities = [title['score'] / total_score for title in titles]

selected_index = random.choices(range(len(titles)), weights=probabilities, k=1)[0]
return titles[selected_index]

Example usage

titles = [ {"title": "Title A", "score": 10}, {"title": "Title B", "score": 8}, {"title": "Title C", "score": 12}, {"title": "Title D", "score": 7} ]

selected_title = select_title(titles) print(selected_title) `

This solution balances between selecting high-scoring titles and ensuring diversity by giving each title a probability of being selected proportional to its score. The random.choices function is used to select a title based on the calculated probabilities.