Frontend School

Playlist Engagement Tracker

DSA
easy

Playlist Engagement Tracker

Easy
Segment Tree
Data Structures
Arrays

Overview

Spotify maintains vast user playlists, and each song within these playlists has an associated "engagement score" (e.g., derived from play counts, skips, or user interactions). To gain deeper insights into user behavior, personalize recommendations, and optimize content, it's crucial to have an efficient system for managing these scores. We need to quickly track individual song engagement and calculate the total engagement for any contiguous sub-segment of a playlist.

What you need to do / Task

Your task is to design and implement a PlaylistEngagementTracker class. This class should efficiently support the following operations:

  1. constructor(initialScores: number[]): Initializes the tracker with an array of initialScores. These scores represent the engagement level of songs in a playlist, where initialScores[i] corresponds to the song at index i.
  2. update(index: number, newScore: number): Updates the engagement score of the song at the given index to newScore. This operation modifies the underlying scores.
  3. query(left: number, right: number): Returns the sum of engagement scores for all songs in the playlist segment from left to right (inclusive). For example, query(0, 2) would sum scores at indices 0, 1, and 2.

Input & output

  • constructor(initialScores: number[]):
    • initialScores: An array of non-negative integers representing the initial engagement scores for songs.
    • Returns: void (constructor has no explicit return value).
  • update(index: number, newScore: number):
    • index: A 0-based integer representing the position of the song to update.
    • newScore: A non-negative integer representing the new engagement score for the song at index.
    • Returns: void.
  • query(left: number, right: number):
    • left: A 0-based integer representing the starting index of the query range (inclusive).
    • right: A 0-based integer representing the ending index of the query range (inclusive).
    • Returns: A number representing the sum of engagement scores within the specified range.

Clarifications

  • The length of the playlist (and thus the initialScores array) remains constant after the PlaylistEngagementTracker is initialized.
  • All engagement scores, both initial and updated, are non-negative integers.
  • The provided index, left, and right parameters for update and query methods will always be valid and within the bounds of the playlist length.

Examples

1

Example 1

Input:

operations = ["PlaylistEngagementTracker","query","update","query","query"], params = [[[1,3,5]],[0,2],[1,2],[0,2],[1,2]]

Output:

[null,9,null,8,7]

Note:

  1. Initialize with scores [1, 3, 5].
  2. Query sum from index 0 to 2: 1 + 3 + 5 = 9.
  3. Update score at index 1 to 2. Scores become [1, 2, 5].
  4. Query sum from index 0 to 2: 1 + 2 + 5 = 8.
  5. Query sum from index 1 to 2: 2 + 5 = 7.
2

Example 2

Input:

operations = ["PlaylistEngagementTracker","query","update","query"], params = [[[10]],[0,0],[0,5],[0,0]]

Output:

[null,10,null,5]

Note:

  1. Initialize with scores [10].
  2. Query sum from index 0 to 0: 10.
  3. Update score at index 0 to 5. Scores become [5].
  4. Query sum from index 0 to 0: 5.
3

Example 3

Input:

operations = ["PlaylistEngagementTracker","update","query","update","query"], params = [[[2,4,6,8]],[0,1],[0,1],[2,7],[0,3]]

Output:

[null,null,5,null,20]

Note:

  1. Initialize with scores [2, 4, 6, 8].
  2. Update score at index 0 to 1. Scores become [1, 4, 6, 8].
  3. Query sum from index 0 to 1: 1 + 4 = 5.
  4. Update score at index 2 to 7. Scores become [1, 4, 7, 8].
  5. Query sum from index 0 to 3: 1 + 4 + 7 + 8 = 20.

Constraints

Constraints & assumptions

  • 1 <= initialScores.length <= 10^4
  • 0 <= initialScores[i] <= 10^5
  • 0 <= newScore <= 10^5
  • 0 <= index < initialScores.length
  • 0 <= left <= right < initialScores.length
  • There will be at most 10^4 calls to update and query combined (after initialization).
  • The time complexity for update and query operations should be significantly better than O(N).
  • The total sum of scores can fit within a standard 32-bit integer type.

What interviewers evaluate

  • Correctness and Robustness: The Segment Tree implementation correctly handles range sum queries and point updates across all valid inputs and edge cases.
  • Efficiency: The update and query operations achieve logarithmic time complexity (O(log N)), and space complexity is appropriate (O(N)).
  • Code Quality: The code is clean, well-structured, readable, and adheres to good software engineering principles.
  • Problem Understanding: Demonstrates a clear understanding of the problem requirements and the underlying data structure's principles.

Loading editor...