Constraints

• 1 <= len(adj) == len(rating) <= 100000
• 0 <= start < len(adj)
• 0 <= k <= len(adj)
• Each neighbor in adj[i] is a valid movie ID in the range [0, len(adj) - 1]
• The graph is undirected, but the input may still contain repeated edges; do not revisit nodes infinitely
• watched may or may not contain start, but start must never be recommended

Examples

Solution

def solution(adj, rating, start, watched, k):
    from collections import deque

    n = len(adj)
    if k <= 0 or start < 0 or start >= n:
        return []

    watched_set = set(watched)
    visited = [False] * n
    visited[start] = True
    q = deque([start])
    answer = []

    while q and len(answer) < k:
        level_size = len(q)
        level_candidates = []

        for _ in range(level_size):
            node = q.popleft()

            if node != start and node not in watched_set:
                level_candidates.append(node)

            for nei in adj[node]:
                if 0 <= nei < n and not visited[nei]:
                    visited[nei] = True
                    q.append(nei)

        level_candidates.sort(key=lambda movie: (-rating[movie], movie))
        answer.extend(level_candidates)

    return answer[:k]

Time complexity: O(M + E + M log M) in the worst case, where M is the number of movies and E is the number of edges. The BFS is O(M + E), and sorting the discovered layers is at worst O(M log M) total.. Space complexity: O(M) for the visited array, queue, and collected recommendations..

Hints

1. Use BFS because every edge has the same cost, so BFS gives the shortest hop distance.
2. Process one BFS layer at a time. All movies found in the same layer have the same distance, so you only need to sort that layer by rating and movie ID.

Constraints

• 0 <= len(requests) <= 200000
• 0 <= sum(len(v) for v in cache_entries.values()) <= 200000
• 1 <= hot_threshold <= 1000000000
• Movie IDs are non-negative integers
• cache_entries may contain keys with empty dependency lists

Examples

Solution

def solution(requests, cache_entries, updated_movies, hot_threshold):
    counts = {}
    for movie_id in requests:
        counts[movie_id] = counts.get(movie_id, 0) + 1

    updated_set = set(updated_movies)
    all_keys = set(cache_entries.keys()) | set(counts.keys())

    result = []
    for movie_id in sorted(all_keys):
        deps = cache_entries.get(movie_id, [])
        stale = any(dep in updated_set for dep in deps)
        hot = counts.get(movie_id, 0) >= hot_threshold

        if stale and hot:
            action = 'recompute_and_protect'
        elif stale:
            action = 'recompute'
        elif hot:
            action = 'protect_hot_key'
        else:
            action = 'ok'

        result.append(f'{movie_id}:{action}')

    return result

Time complexity: O(R + D + U log U), where R is the number of requests, D is the total number of dependency IDs across all cache entries, and U is the number of unique movie IDs that appear in requests or as cache keys.. Space complexity: O(Ru + Mu + U), where Ru is the number of unique requested keys, Mu is the number of updated movies, and U is the number of output keys..

Hints

1. First count how many times each movie ID appears in requests to find hot keys.
2. Convert updated_movies to a set so you can test whether a cache entry is stale by scanning its dependency list once.