FastPrepJSON Block Tree Operations

JSON Block Tree Operations

Notion logoNotion● MediumFULLTIMEONSITE INTERVIEW
Learn

Problem statement

Maintain an ordered forest of document blocks. Process these operations:

  • ["ADD", id, parentId, text] adds a block. A parentId of - makes it the newest root; otherwise it becomes the newest child of that active parent.
  • ["DELETE", id] deletes that block and its entire descendant subtree.
  • ["RENDER"] emits every active block in preorder. Each line is depth|id|text; roots and siblings retain insertion order, and lines are joined by a newline.

Return the values produced by RENDER operations in order.

Function

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

Examples

Example 1

operations = [["ADD","a","-","Page"],["ADD","b","a","Heading"],["ADD","c","a","Paragraph"],["ADD","d","b","Text"],["RENDER"],["DELETE","b"],["RENDER"]]return = ["0|a|Page\n1|b|Heading\n2|d|Text\n1|c|Paragraph","0|a|Page\n1|c|Paragraph"]

The first render is preorder. Deleting b also removes its descendant d while preserving sibling c.

Constraints

  • 1 <= operations.length <= 20000.
  • Every added ID is globally unique and is never reused after deletion.
  • Every non-root parent is active when its child is added.
  • Every deleted ID is active.
  • IDs are non-empty ASCII strings containing neither | nor whitespace.
  • Text is non-empty and contains neither | nor a newline.
  • The total number of rendered block lines is at most 200000.

More Notion problems

See Notion hiring insights
public String[] runJsonBlockTree(String[][] operations) {
    // Write your code here.
}
operations[["ADD","a","-","Page"],["ADD","b","a","Heading"],["ADD","c","a","Paragraph"],["ADD","d","b","Text"],["RENDER"],["DELETE","b"],["RENDER"]]
expected["0|a|Page\n1|b|Heading\n2|d|Text\n1|c|Paragraph", "0|a|Page\n1|c|Paragraph"]
Checking account…