Frontend School

Twitter Timeline Operations Processor

DSA
medium

Twitter Timeline Operations Processor

Medium
Stack
String Parsing

Overview

Twitter's timeline is a dynamic feed of content, constantly updated by users' actions. To ensure a consistent and reliable user experience, especially with features like 'undo' or 'revert,' it's crucial to accurately track and process a sequence of user-generated operations. This problem simulates a core mechanism for maintaining the state of a user's visible timeline, reflecting how actions and their reversals impact the displayed content.

What you need to do / Task

Implement the function processTimelineOperations that takes a list of string operations and returns the final state of the user's timeline. Each operation modifies the timeline, which can be thought of as a sequence of tweet IDs. You will need to parse each operation string and apply the corresponding action.

Input & output

Input:

  • operations: An array of strings, where each string represents a single operation. Each operation will be one of the following formats:
    • "TWEET <id>": Adds a new tweet with the given <id> to the end of the timeline.
    • "RETWEET <id>": Adds a retweet of an existing tweet with the given <id> to the end of the timeline.
    • "UNDO": Reverts the last TWEET or RETWEET operation. If the timeline is empty, this operation does nothing.
    • "REVERT_ALL": Clears the entire timeline, removing all tweets.

Output:

  • A string[] representing the final state of the timeline. The elements should be tweet IDs, ordered from the oldest (first added) to the newest (last added).

Clarifications

  • Tweet IDs (<id>) are non-empty strings consisting of alphanumeric characters. You should treat them as opaque strings.
  • UNDO operations only affect the most recent TWEET or RETWEET operation. If the timeline is empty, UNDO has no effect.
  • The output array should reflect the contents of the timeline from its base to its top, representing the chronological order of tweets visible to the user.

Examples

1

Example 1

Input:

operations = ["TWEET 101", "TWEET 102", "UNDO", "RETWEET 201", "TWEET 103"]

Output:

["101","201","103"]

Note:

  1. TWEET 101: timeline = ["101"]
  2. TWEET 102: timeline = ["101", "102"]
  3. UNDO: timeline = ["101"]
  4. RETWEET 201: timeline = ["101", "201"]
  5. TWEET 103: timeline = ["101", "201", "103"]
2

Example 2

Input:

operations = ["TWEET 500", "REVERT_ALL", "UNDO", "TWEET 501", "RETWEET 600"]

Output:

["501","600"]

Note:

  1. TWEET 500: timeline = ["500"]
  2. REVERT_ALL: timeline = []
  3. UNDO: timeline = [] (no effect on empty timeline)
  4. TWEET 501: timeline = ["501"]
  5. RETWEET 600: timeline = ["501", "600"]
3

Example 3

Input:

operations = ["UNDO", "TWEET A1", "RETWEET B2", "TWEET C3", "UNDO", "UNDO", "TWEET D4", "REVERT_ALL", "TWEET E5", "RETWEET F6"]

Output:

["E5","F6"]

Note:

  1. UNDO: timeline = [] (no effect)
  2. TWEET A1: timeline = ["A1"]
  3. RETWEET B2: timeline = ["A1", "B2"]
  4. TWEET C3: timeline = ["A1", "B2", "C3"]
  5. UNDO: timeline = ["A1", "B2"]
  6. UNDO: timeline = ["A1"]
  7. TWEET D4: timeline = ["A1", "D4"]
  8. REVERT_ALL: timeline = []
  9. TWEET E5: timeline = ["E5"]
  10. RETWEET F6: timeline = ["E5", "F6"]

Constraints

Constraints & assumptions

  • 1 <= operations.length <= 10^5
  • Each tweet ID (<id>) is a non-empty string, up to 10 characters long, containing only alphanumeric characters (a-z, A-Z, 0-9).
  • All operation strings will strictly adhere to one of the four specified formats ("TWEET <id>", "RETWEET <id>", "UNDO", "REVERT_ALL"). No malformed strings will be provided.
  • The UNDO and REVERT_ALL operations do not take an <id> parameter.

Out of scope

  • Error handling for invalid operation formats or malformed tweet IDs.
  • Performance optimization beyond a linear time complexity relative to the number of operations.

What interviewers evaluate

  • Correctness in parsing various operation types and extracting relevant data.
  • Effective use of an appropriate data structure (e.g., a stack) to manage the dynamic timeline state.
  • Accurate implementation of all operation logic, including edge cases for UNDO and REVERT_ALL.
  • Code clarity, readability, and adherence to best practices.

Loading editor...