Frontend School

Tweet Activity Spike Detector

DSA
medium

Tweet Activity Spike Detector

Medium
Segment Tree
Data Structures
Range Query
Point Update

Overview

Twitter's platform generates vast amounts of real-time data, and identifying trending topics or unusual activity spikes is crucial for maintaining platform health and user experience. One way to achieve this is by monitoring the number of tweets for specific keywords or features over discrete time intervals. This problem asks you to design a system that can efficiently track tweet activity and detect peak activity within any given time window.

What you need to do / Task

Your task is to implement the TweetActivityTracker class. This class will manage tweet activity counts across a series of discrete time intervals and provide methods to update activity and query for maximum activity within a specified range.

  1. constructor(numTimeIntervals: number): Initialize the data structure to track tweet activity for numTimeIntervals distinct time slots. Initially, all activity counts are 0.
  2. recordActivity(intervalIndex: number, tweetCount: number): void: Update the tweet activity for a specific intervalIndex with the new tweetCount. This operation should replace any previous count for that interval.
  3. getMaxActivity(startInterval: number, endInterval: number): number: Return the maximum tweet activity observed within the inclusive range of time intervals [startInterval, endInterval].

Input & output

TweetActivityTracker(numTimeIntervals: number)

  • numTimeIntervals: An integer representing the total number of discrete time intervals to track. These intervals are 0-indexed, from 0 to numTimeIntervals - 1.
  • Returns: void (constructor).

recordActivity(intervalIndex: number, tweetCount: number): void

  • intervalIndex: An integer representing the 0-based index of the time interval to update.
  • tweetCount: An integer representing the new activity count for the specified intervalIndex.
  • Returns: void.

getMaxActivity(startInterval: number, endInterval: number): number

  • startInterval: An integer representing the 0-based start index of the query range (inclusive).
  • endInterval: An integer representing the 0-based end index of the query range (inclusive).
  • Returns: An integer, the maximum tweetCount found within the range [startInterval, endInterval].

Clarifications

  • numTimeIntervals will always be at least 1.
  • All intervalIndex, startInterval, and endInterval parameters will be valid indices within [0, numTimeIntervals - 1].
  • For getMaxActivity, startInterval will always be less than or equal to endInterval.
  • Initial activity for all time intervals is considered 0.

Examples

1

Example 1

Input:

operations = ["TweetActivityTracker", "recordActivity", "recordActivity", "getMaxActivity", "recordActivity", "getMaxActivity", "getMaxActivity"], params = [[5], [0, 10], [2, 20], [0, 4], [0, 5], [0, 1], [1, 3]]

Output:

[null, null, null, 20, null, 5, 20]

Note:

Initialize with 5 intervals: [0,0,0,0,0] recordActivity(0, 10) -> [10,0,0,0,0] recordActivity(2, 20) -> [10,0,20,0,0] getMaxActivity(0, 4) -> max([10,0,20,0,0]) = 20 recordActivity(0, 5) -> [5,0,20,0,0] getMaxActivity(0, 1) -> max([5,0]) = 5 getMaxActivity(1, 3) -> max([0,20,0]) = 20

2

Example 2

Input:

operations = ["TweetActivityTracker", "recordActivity", "recordActivity", "getMaxActivity", "recordActivity", "getMaxActivity", "recordActivity", "getMaxActivity"], params = [[3], [1, 100], [0, 50], [0, 2], [2, 150], [1, 2], [1, 120], [0, 1]]

Output:

[null, null, null, 100, null, 150, null, 120]

Note:

Initialize with 3 intervals: [0,0,0] recordActivity(1, 100) -> [0,100,0] recordActivity(0, 50) -> [50,100,0] getMaxActivity(0, 2) -> max([50,100,0]) = 100 recordActivity(2, 150) -> [50,100,150] getMaxActivity(1, 2) -> max([100,150]) = 150 recordActivity(1, 120) -> [50,120,150] getMaxActivity(0, 1) -> max([50,120]) = 120

Constraints

Constraints & assumptions

  • 1 <= numTimeIntervals <= 10^5
  • 0 <= intervalIndex < numTimeIntervals
  • 0 <= tweetCount <= 10^9
  • 0 <= startInterval <= endInterval < numTimeIntervals
  • The total number of calls to recordActivity and getMaxActivity (excluding the constructor) will not exceed 10^5.
  • The expected time complexity for recordActivity and getMaxActivity should be O(log N), where N is numTimeIntervals.

Out of scope

  • Error handling for invalid input parameters (assume all inputs conform to constraints).
  • Concurrency management or distributed system considerations.

What interviewers evaluate

  • Correctness of the underlying data structure (Segment Tree) for point updates and range maximum queries.
  • Efficiency of recordActivity and getMaxActivity operations, meeting the O(log N) complexity requirement.
  • Clarity, structure, and maintainability of the code, including proper handling of base cases and array indexing.
  • Ability to articulate the choice of data structure and its time/space complexity.

Loading editor...