Frontend School

Story Rewatch Queue

DSA
medium

Story Rewatch Queue

Medium
Queue
Design
LinkedList
HashMap

Overview

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.

What you need to do / Task

Implement a StoryRewatchQueue class that manages a fixed-capacity list of unique story IDs.

  1. The StoryRewatchQueue should store up to capacity unique story IDs.
  2. When a story is "viewed" (viewStory method):
    • If the storyId is already in the queue, its position should be updated to become the most recently viewed.
    • If it's a new unique storyId and the queue is full, the least recently viewed story should be evicted to make space.
    • If it's a new unique storyId and the queue is not full, it should be added as the most recently viewed story.
  3. The system should allow retrieving the current list of stories in reverse chronological order (most recent first) via getRewatchList.

Input & output

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.

Clarifications

  • If capacity is 0, viewStory should do nothing, and getRewatchList should return an empty array.
  • All storyIds will be positive integers.

Examples

1

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:

  1. StoryRewatchQueue(2): Initializes with capacity 2.
  2. viewStory(1): Queue: [1]
  3. viewStory(2): Queue: [1, 2]
  4. getRewatchList(): Returns [2, 1] (most recent first)
  5. viewStory(1): Story 1 is already in the queue, its position is updated to become most recent. Queue: [2, 1] becomes [1, 2] internally.
  6. getRewatchList(): Returns [1, 2]
2

Example 2

Input:

operations = ["StoryRewatchQueue","viewStory","viewStory","viewStory","getRewatchList"], params = [[2],[1],[2],[3],[]]

Output:

[null,null,null,null,[3,2]]

Note:

  1. StoryRewatchQueue(2): Initializes with capacity 2.
  2. viewStory(1): Queue: [1]
  3. viewStory(2): Queue: [1, 2]
  4. 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]
  5. getRewatchList(): Returns [3, 2]
3

Example 3

Input:

operations = ["StoryRewatchQueue","viewStory","viewStory","getRewatchList"], params = [[0],[1],[1],[]]

Output:

[null,null,null,[]]

Note:

  1. StoryRewatchQueue(0): Initializes with capacity 0.
  2. viewStory(1): Capacity is 0, no stories can be stored.
  3. viewStory(1): Capacity is 0, no stories can be stored.
  4. getRewatchList(): Returns []

Constraints

Constraints & assumptions

  • 0 <= capacity <= 1000
  • 1 <= storyId <= 10^9
  • The total number of viewStory and getRewatchList calls will not exceed 10^5.
  • Time complexity for viewStory should be O(1).
  • Time complexity for getRewatchList should be O(N) where N is the current number of stories in the queue.

Out of scope

  • Handling invalid capacity (e.g., negative, non-integer).
  • Persistent storage; this is an in-memory data structure.
  • Concurrency or multi-threading.

What interviewers evaluate

  • Correctness of the StoryRewatchQueue logic, especially handling capacity limits and recency updates for stories.
  • Efficient use of data structures (e.g., HashMap and DoublyLinkedList) to achieve optimal time complexities.
  • Clean, readable, and maintainable code structure.
  • Thorough testing and consideration of edge cases.

Loading editor...