FastPrepVersioned Document Store

Versioned Document Store

Notion logoNotion● MediumFULLTIMEINTERNPHONE SCREEN
Learn

Problem statement

Maintain versions of named text documents. Process these operations in order:

  • ["CREATE", timestamp, name, text] creates the first version of name or overwrites it with a new version at that timestamp.
  • ["GET", name] returns the newest text for that document, or NULL when it has never been created.
  • ["GET_AT", name, timestamp] returns the text from the newest version whose creation timestamp is at most the query timestamp, or NULL when no such version exists.

Return the values produced by GET and GET_AT operations in order.

Function

runVersionedDocumentStore(operations: String[][]) → String[]

Examples

Example 1

operations = [["CREATE","0","doc","ABC"],["CREATE","3","doc","BCD"],["CREATE","6","doc","CDE"],["GET_AT","doc","1"],["GET_AT","doc","4"],["GET_AT","doc","7"],["GET","doc"]]return = ["ABC","BCD","CDE","CDE"]

Each historical lookup selects the latest creation at or before its timestamp. GET returns the newest version.

Constraints

  • 1 <= operations.length <= 200000.
  • Timestamps are decimal integers in [0, 10^18].
  • CREATE timestamps are strictly increasing for each document name.
  • Names are non-empty ASCII strings containing no whitespace.
  • Text is a printable ASCII string containing neither | nor a newline.
  • The total length of returned text is at most 1000000.

More Notion problems

See Notion hiring insights
public String[] runVersionedDocumentStore(String[][] operations) {
    // Write your code here.
}
operations[["CREATE","0","doc","ABC"],["CREATE","3","doc","BCD"],["CREATE","6","doc","CDE"],["GET_AT","doc","1"],["GET_AT","doc","4"],["GET_AT","doc","7"],["GET","doc"]]
expected["ABC", "BCD", "CDE", "CDE"]
Checking account…