Snap Feature Peak Users
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.
Implement a data structure that supports two operations on an array of daily active user counts:
update(dayIndex, newDAU): Updates the DAU for a specific dayIndex to newDAU.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.
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.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.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
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
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
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
1 <= dailyUsers.length <= 10^50 <= dailyUsers[i] <= 10^90 <= dayIndex < dailyUsers.length0 <= newDAU <= 10^90 <= startDay <= endDay < dailyUsers.length10^5 calls to update and queryPeak combined.update and queryPeak should be O(log N), where N is the number of days.O(N).update and queryPeak operations according to specifications.O(log N) time complexity requirements for operations.Loading editor...