Story Rewatch Queue
Snapchat users often want to rewatch their favorite stories. To enhance this experience, we need a system that intelligently keeps track of a user's recently viewed stories. This ensures that the most relevant and recent content is always available for quick rewatching, even if it's been viewed multiple times.
Implement a StoryRewatchQueue class that manages a fixed-capacity list of unique story IDs.
StoryRewatchQueue should store up to capacity unique story IDs.viewStory method):
storyId is already in the queue, its position should be updated to become the most recently viewed.storyId and the queue is full, the least recently viewed story should be evicted to make space.storyId and the queue is not full, it should be added as the most recently viewed story.getRewatchList.class StoryRewatchQueue:
constructor(capacity: number): Initializes the queue with a maximum capacity for unique stories. capacity will be a non-negative integer.viewStory(storyId: number): void: Registers storyId as viewed. storyId will be a positive integer.getRewatchList(): number[]: Returns an array of story IDs, ordered from most recently viewed to least recently viewed.capacity is 0, viewStory should do nothing, and getRewatchList should return an empty array.storyIds will be positive integers.Examples
Example 1
Input:
operations = ["StoryRewatchQueue","viewStory","viewStory","getRewatchList","viewStory","getRewatchList"], params = [[2],[1],[2],[],[1],[]]
Output:
[null,null,null,[2,1],null,[1,2]]
Note:
StoryRewatchQueue(2): Initializes with capacity 2.viewStory(1): Queue: [1]viewStory(2): Queue: [1, 2]getRewatchList(): Returns [2, 1] (most recent first)viewStory(1): Story 1 is already in the queue, its position is updated to become most recent. Queue: [2, 1] becomes [1, 2] internally.getRewatchList(): Returns [1, 2]Example 2
Input:
operations = ["StoryRewatchQueue","viewStory","viewStory","viewStory","getRewatchList"], params = [[2],[1],[2],[3],[]]
Output:
[null,null,null,null,[3,2]]
Note:
StoryRewatchQueue(2): Initializes with capacity 2.viewStory(1): Queue: [1]viewStory(2): Queue: [1, 2]viewStory(3): Capacity is 2. Story 1 is the least recently viewed, so it's evicted. Story 3 is added as most recent. Queue: [2, 3]getRewatchList(): Returns [3, 2]Example 3
Input:
operations = ["StoryRewatchQueue","viewStory","viewStory","getRewatchList"], params = [[0],[1],[1],[]]
Output:
[null,null,null,[]]
Note:
StoryRewatchQueue(0): Initializes with capacity 0.viewStory(1): Capacity is 0, no stories can be stored.viewStory(1): Capacity is 0, no stories can be stored.getRewatchList(): Returns []Constraints
0 <= capacity <= 10001 <= storyId <= 10^9viewStory and getRewatchList calls will not exceed 10^5.viewStory should be O(1).getRewatchList should be O(N) where N is the current number of stories in the queue.capacity (e.g., negative, non-integer).StoryRewatchQueue logic, especially handling capacity limits and recency updates for stories.HashMap and DoublyLinkedList) to achieve optimal time complexities.Loading editor...