FastPrepUndo/Redo Timeline State Engine
Problem · Stack

Undo/Redo Timeline State Engine

Learn this problem
● MediumKickdrum logoKickdrumINTERNFULLTIMEOA

Problem statement

A timeline begins at initialState. Process operations and return the active state after every operation.

  • "DO state" creates and activates a new state after the current one. It permanently discards every redoable future state.
  • "UNDO k" moves back by at most k states and stops at the initial state.
  • "REDO k" moves forward by at most k states and stops at the newest state on the current branch.
  • "CURRENT" only observes the active state.

Function

runTimeline(initialState: String, operations: String[]) → String[]

Examples

Example 1

initialState = "Origin"operations = ["DO A","DO B","UNDO 1","CURRENT","REDO 1"]return = ["A","B","A","A","B"]

Undo moves from B to A, CURRENT leaves A active, and REDO returns to B.

Example 2

initialState = "Basic"operations = ["DO Soup","DO Curry","UNDO 1","DO Salad","REDO 5"]return = ["Soup","Curry","Soup","Salad","Salad"]

Doing Salad from Soup discards the old Curry redo branch, so the final REDO stays at Salad.

Constraints

  • 1 <= operations.length <= 200000.
  • Every state is a unique token of 1 to 30 ASCII letters, digits, or underscores.
  • Every navigation count satisfies 0 <= k <= 10^9.
  • Every operation has exactly one of the documented forms.

More Kickdrum problems

drafts saved locally
public String[] runTimeline(String initialState, String[] operations) {
    // Write your code here.
}
initialState"Origin"
operations["DO A","DO B","UNDO 1","CURRENT","REDO 1"]
expected["A", "B", "A", "A", "B"]
checking account