Frontend School

Netflix Hot Content Streamer

DSA
hard

Netflix Hot Content Streamer

Hard
Heap
Priority Queue
Sliding Window
Map
Deque

Overview

Netflix relies on real-time insights into content popularity to make critical decisions, such as optimizing CDN caching, dynamic server allocation, and tailoring recommendation algorithms. Identifying "hot" content as it trends is crucial for maintaining a seamless and engaging user experience.

This problem simulates a core component of such a real-time analytics system. You will process a continuous stream of content requests, each containing a timestamp and a content ID, and dynamically report the top K most requested content IDs within a recent sliding time window.

What you need to do / Task

Implement the HotContentStreamer class with the following methods:

  1. constructor(k: number, windowSeconds: number): Initializes the system with the desired number of top content IDs to track (K) and the duration of the sliding window in seconds (W).
  2. getHotContent(timestamp: number, contentId: number): number[]: Processes a new content request. This method should:
    • Record the new request (timestamp, contentId).
    • Update the request frequencies for all relevant content IDs, ensuring only requests within the W-second window ending at timestamp are counted.
    • Return an array of K content IDs that have the highest request frequency within the current W-second window. If fewer than K unique content IDs are active, return all of them.

Input & output

constructor(k: number, windowSeconds: number)

  • k: number - The number of top hot content IDs to return. 1 <= k <= 100.
  • windowSeconds: number - The duration of the sliding window in seconds. 1 <= windowSeconds <= 10^5.
  • Returns: void

getHotContent(timestamp: number, contentId: number)

  • timestamp: number - The time (in seconds) when the content request occurred. Timestamps are strictly increasing across calls. 1 <= timestamp <= 10^9.
  • contentId: number - The unique identifier for the requested content. 1 <= contentId <= 10^5.
  • Returns: number[] - An array of K content IDs (or fewer if not enough active content) with the highest frequencies. The order of content IDs with tied frequencies does not matter, but typically highest frequency first.

Clarifications

  • timestamp values are strictly increasing across calls to getHotContent.
  • If multiple content IDs have the same frequency and are candidates for the top K, any valid combination is acceptable. The output order for tied frequencies does not need to be stable.
  • Content IDs that fall out of the W-second window should have their frequencies decremented or removed.
  • A content ID's frequency is 0 if it has no requests within the current W-second window.

Examples

1

Example 1

Input:

operations = ["HotContentStreamer","getHotContent","getHotContent","getHotContent","getHotContent","getHotContent","getHotContent","getHotContent","getHotContent","getHotContent","getHotContent"], params = [[2,5],[1,101],[2,102],[3,101],[4,103],[5,102],[6,104],[7,101],[8,105],[9,102],[10,101]]

Output:

[null,[101],[101,102],[101,102],[101,102],[101,102],[101,102],[101,102],[101,102],[101,102],[101,102]]

Note:

K=2, W=5

  1. (1, 101): Freq(101)=1. Current window [1,1]. Top 2: [101]
  2. (2, 102): Freq(102)=1. Current window [1,2]. Top 2: [101,102]
  3. (3, 101): Freq(101)=2. Current window [1,3]. Top 2: [101,102]
  4. (4, 103): Freq(103)=1. Current window [1,4]. Top 2: [101,102] (103 is not hot enough yet)
  5. (5, 102): Freq(102)=2. Current window [1,5]. Top 2: [101,102]
  6. (6, 104): Freq(104)=1. Current window [2,6]. 101 from t=1 falls out, Freq(101)=1. 102 from t=1 falls out, Freq(102)=1. Top 2: [101,102] (frequencies are 101:1, 102:1, 103:1, 104:1. Any 2 are fine)
  7. (7, 101): Freq(101)=2. Current window [3,7]. Top 2: [101,102] (101:2, 102:1, 103:1, 104:1)
  8. (8, 105): Freq(105)=1. Current window [4,8]. Top 2: [101,102] (101:2, 102:1, 103:1, 104:1, 105:1)
  9. (9, 102): Freq(102)=2. Current window [5,9]. Top 2: [101,102] (101:2, 102:2, 103:0, 104:1, 105:1). Note: 103 from t=4 falls out.
  10. (10, 101): Freq(101)=3. Current window [6,10]. Top 2: [101,102] (101:3, 102:2, 104:1, 105:1).
2

Example 2

Input:

operations = ["HotContentStreamer","getHotContent","getHotContent","getHotContent","getHotContent","getHotContent"], params = [[1,3],[10,1],[11,2],[12,1],[13,3],[14,1]]

Output:

[null,[1],[2],[1],[1],[1]]

Note:

K=1, W=3

  1. (10, 1): Freq(1)=1. Window [10,10]. Top 1: [1]
  2. (11, 2): Freq(2)=1. Window [10,11]. Top 1: [1] (1:1, 2:1. Any one is fine, 1 was already there)
  3. (12, 1): Freq(1)=2. Window [10,12]. Top 1: [1] (1:2, 2:1)
  4. (13, 3): Freq(3)=1. Window [11,13]. 1 from t=10 falls out. Freq(1)=1 (from t=12 only). Freq(2)=1. Top 1: [1] (1:1, 2:1, 3:1. Any one is fine)
  5. (14, 1): Freq(1)=2. Window [12,14]. 2 from t=11 falls out. Freq(2)=0. Top 1: [1] (1:2, 3:1).
3

Example 3

Input:

operations = ["HotContentStreamer","getHotContent","getHotContent","getHotContent","getHotContent"], params = [[3,10],[1,100],[2,200],[3,100],[4,300]]

Output:

[null,[100],[100,200],[100,200],[100,200,300]]

Note:

K=3, W=10. Building up to K items.

  1. (1, 100): Freq(100)=1. Top 3: [100]
  2. (2, 200): Freq(200)=1. Top 3: [100,200]
  3. (3, 100): Freq(100)=2. Top 3: [100,200]
  4. (4, 300): Freq(300)=1. Top 3: [100,200,300] (100:2, 200:1, 300:1. All are returned as K=3)

Constraints

Constraints & assumptions

  • 1 <= K <= 100
  • 1 <= W <= 10^5 (window duration in seconds)
  • 1 <= timestamp <= 10^9 (timestamps are large, but their differences are relevant for W)
  • 1 <= contentId <= 10^5 (number of unique content IDs)
  • The total number of calls to getHotContent will not exceed 10^5.
  • Each getHotContent call must be efficient, ideally logarithmic in K and amortized constant with respect to W for individual content updates.
  • You can assume a standard PriorityQueue (min-heap or max-heap) implementation is available.

Out of scope

  • Handling concurrent requests or distributed system complexities.
  • Persistence or recovery mechanisms for the content data.
  • Advanced anomaly detection or predictive analytics.

What interviewers evaluate

  • Correctness of Sliding Window Logic: Accurately tracks content frequencies within the dynamic time window for all relevant content IDs.
  • Efficient Top-K Maintenance: Effective use of a priority queue (heap) to identify and maintain the K hottest content IDs.
  • Handling Stale Data: Correctly manages and filters out outdated frequency information from the priority queue.
  • Time and Space Complexity: Demonstrates an understanding of the chosen data structures' performance characteristics and ensures optimal efficiency given the constraints.
  • Code Clarity and Robustness: Well-structured, readable code that handles edge cases like fewer than K active content IDs.

Loading editor...