Dictionary Records to an Editable XML Tree
Learn this problem
Snap Inc.FULLTIMEONSITE INTERVIEWProblem statement
Build one XML tree from dictionary-style records, then apply an ordered sequence of edits. Each row of records is [id, parentId, tag, text]. Exactly one row has an empty parentId and represents the root. Every other row names its parent by ID.
Each row of operations is [kind, id, parentId, tag, text]:
- For
add, create a new leaf with the supplied ID, parent ID, tag, and text. Append it after the parent’s existing children. - For
remove, remove the non-root element with the supplied ID together with its entire subtree. The remaining three fields are empty strings.
After every operation, serialize the current root and append that XML string to the result. Preserve child order. Always use an explicit opening and closing tag, including for an empty element. In text, escape &, <, and > as &, <, and >, respectively.
Function
editXml(records: String[][], operations: String[][]) → String[]Examples
Example 1
records = [["root","","catalog",""],["a","root","item","A&B"]]operations = [["add","b","root","item","<B>"],["remove","a","","",""]]return = ["<catalog><item>A&B</item><item><B></item></catalog>","<catalog><item><B></item></catalog>"]The first edit appends element b after a and escapes both text values. The second edit removes element a, leaving only b.
Example 2
records = [["r","","library",""],["book","r","book",""],["title","book","title","Algorithms"]]operations = [["add","note","book","note","fast & clear"],["remove","book","","",""]]return = ["<library><book><title>Algorithms</title><note>fast & clear</note></book></library>","<library></library>"]The new note is appended to the existing book subtree. Removing book also removes its title and note descendants.
Constraints
1 <= records.length <= 500.0 <= operations.length <= 500.- Each record has exactly four fields and each operation has exactly five fields.
- IDs are unique nonempty strings of at most
30printable ASCII characters. - Tags match
[A-Za-z][A-Za-z0-9_-]*and have length at most30. - Text has at most
100printable ASCII characters. - The initial records form one valid rooted tree, although a child may appear before its parent.
- Every operation is valid when it is applied: an added ID is new, its parent exists, and a removed ID exists and is not the root.
- The total serialized output contains at most
10^6characters.