Frontend School

Snap Feature Peak Users

DSA
easy

Snap Feature Peak Users

Easy
Segment Tree
Arrays
Data Structures

Overview

Snapchat frequently launches new features and needs to monitor their adoption and engagement. Daily Active Users (DAU) are a key metric. As features evolve or new marketing campaigns launch, DAU numbers can change. We need an efficient system to track these numbers and quickly identify periods of peak engagement.

What you need to do / Task

Implement a data structure that supports two operations on an array of daily active user counts:

  1. update(dayIndex, newDAU): Updates the DAU for a specific dayIndex to newDAU.
  2. queryPeak(startDay, endDay): Returns the maximum DAU observed within the range of days [startDay, endDay] (inclusive).

Your solution should be optimized for both update and query operations on a potentially large number of days.

Input & output

You will implement a class, DailyUserTracker, which is initialized with an array of dailyUsers.

  • DailyUserTracker(dailyUsers: number[])
    • dailyUsers: An array of non-negative integers representing initial daily active user counts.
  • update(dayIndex: number, newDAU: number): void
    • dayIndex: The 0-indexed day whose DAU needs to be updated.
    • newDAU: The new daily active user count for dayIndex.
    • This method does not return anything.
  • queryPeak(startDay: number, endDay: number): number
    • startDay: The 0-indexed start day of the query range.
    • endDay: The 0-indexed end day of the query range.
    • This method returns an integer representing the maximum DAU in the specified range.

Clarifications

  • The dailyUsers array will only contain non-negative integers.
  • dayIndex, startDay, and endDay will always be valid indices within the bounds of the initial dailyUsers array.
  • startDay will always be less than or equal to endDay.

Examples

1

Example 1

Input:

operations = ["DailyUserTracker","queryPeak","update","queryPeak","queryPeak"], params = [[[10,20,5,30,15]],[0,4],[2,25],[1,3],[0,1]]

Output:

[null,30,null,30,20]

Note:

Initial dailyUsers = [10, 20, 5, 30, 15] queryPeak(0, 4) -> max([10, 20, 5, 30, 15]) = 30 update(2, 25) -> dailyUsers becomes [10, 20, 25, 30, 15] queryPeak(1, 3) -> max([20, 25, 30]) = 30 queryPeak(0, 1) -> max([10, 20]) = 20

2

Example 2

Input:

operations = ["DailyUserTracker","queryPeak","update","queryPeak"], params = [[[100]],[0,0],[0,50],[0,0]]

Output:

[null,100,null,50]

Note:

Initial dailyUsers = [100] queryPeak(0, 0) -> max([100]) = 100 update(0, 50) -> dailyUsers becomes [50] queryPeak(0, 0) -> max([50]) = 50

3

Example 3

Input:

operations = ["DailyUserTracker","queryPeak","update","queryPeak","queryPeak"], params = [[[1,2,3,4,5]],[0,2],[1,10],[0,2],[2,4]]

Output:

[null,3,null,10,5]

Note:

Initial dailyUsers = [1, 2, 3, 4, 5] queryPeak(0, 2) -> max([1, 2, 3]) = 3 update(1, 10) -> dailyUsers becomes [1, 10, 3, 4, 5] queryPeak(0, 2) -> max([1, 10, 3]) = 10 queryPeak(2, 4) -> max([3, 4, 5]) = 5

Constraints

Constraints & assumptions

  • 1 <= dailyUsers.length <= 10^5
  • 0 <= dailyUsers[i] <= 10^9
  • 0 <= dayIndex < dailyUsers.length
  • 0 <= newDAU <= 10^9
  • 0 <= startDay <= endDay < dailyUsers.length
  • At most 10^5 calls to update and queryPeak combined.
  • Time complexity for update and queryPeak should be O(log N), where N is the number of days.
  • Space complexity should be O(N).

What interviewers evaluate

  • Correctness: The solution must correctly implement both update and queryPeak operations according to specifications.
  • Efficiency: The chosen data structure and algorithms must meet the O(log N) time complexity requirements for operations.
  • Code Structure & Readability: The code should be well-organized, clean, and easy to understand, reflecting good software engineering practices.
  • Edge Cases: Handling of array boundaries, single-element arrays, and single-day ranges.

Loading editor...