How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Jane Street.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Jane Street during technical interviews.

Decode an Encrypted Paragraph Tree | Jane Street Coding Question

Quick Overview

This question evaluates skills in string parsing, tree serialization/deserialization, and bijective substitution cipher handling, assessing competency in parsing nested structures, character mapping, and traversal within the Coding & Algorithms domain.

Decode an Encrypted Paragraph Tree

Company: Jane Street

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

# Decode an Encrypted Paragraph Tree A document is stored as a tree of paragraphs. Each node holds a paragraph `text` — a string of lowercase English letters and spaces, possibly empty — and an ordered list of child nodes. The document was encoded in two steps: 1. **Substitution cipher.** Given a `key` that is a permutation of the 26 lowercase letters, every letter of every paragraph was substituted: the letter `'a' + i` was replaced by `key[i]`. Spaces were left unchanged. 2. **Pre-order serialization.** The tree was flattened into a single string: each node became ``` "(" + encodedText + serializedChild1 + serializedChild2 + ... + ")" ``` with children serialized in order. Because paragraph texts never contain parentheses, `(` and `)` unambiguously mark node boundaries. Given `key` and the serialized string `s`, which encodes exactly one root node, decode the document and return the tree as nested lists: each node is represented as `[text, [child1, child2, ...]]`, where `text` is the fully decoded paragraph and the second element is the (possibly empty) list of its children in order. ## Examples **Example 1** ``` Input: key = "bcdefghijklmnopqrstuvwxyza" s = "(ij(bc)(de))" Output: ["hi", [["ab", []], ["cd", []]]] ``` Here `key` maps each letter to the next one (`'a' -> 'b'`, ..., `'z' -> 'a'`), so decoding maps each letter back: `"ij" -> "hi"`, `"bc" -> "ab"`, `"de" -> "cd"`. The root `"hi"` has two leaf children. **Example 2** ``` Input: key = "qwertyuiopasdfghjklzxcvbnm" s = "(ug gf(xh(rgvf))())" Output: ["go on", [["up", [["down", []]]], ["", []]]] ``` Under this key, `'g' -> 'u'`, `'o' -> 'g'`, `'u' -> 'x'`, `'p' -> 'h'`, `'d' -> 'r'`, `'w' -> 'v'`, `'n' -> 'f'`; spaces are unchanged. The root decodes to `"go on"` and has two children: `"up"` (which has one child `"down"`) and a node with empty text. ## Constraints - `key` has length 26 and is a permutation of the lowercase English alphabet. - `1 <= s.length <= 10^5`, and `s` is a valid serialization of exactly one root node. - The tree has at most `10^4` nodes. - Every paragraph text consists only of lowercase English letters and spaces, and may be empty. - An `O(s.length)` solution is expected.

Quick Answer: This question evaluates skills in string parsing, tree serialization/deserialization, and bijective substitution cipher handling, assessing competency in parsing nested structures, character mapping, and traversal within the Coding & Algorithms domain.

Constraints

key has length 26 and is a permutation of the lowercase English alphabet.
1 <= s.length <= 10^5, and s is a valid serialization of exactly one root node.
The tree has at most 10^4 nodes.
Every paragraph text consists only of lowercase English letters and spaces, and may be empty.
An O(s.length) solution is expected.

Examples

Input: ("bcdefghijklmnopqrstuvwxyza", "(ij(bc)(de))")

Expected Output: ["hi", [["ab", []], ["cd", []]]]

Explanation: This key shifts every letter forward by one, so decoding shifts back: ij->hi, bc->ab, de->cd. The root "hi" has two leaf children.

Input: ("qwertyuiopasdfghjklzxcvbnm", "(ug gf(xh(rgvf))())")

Expected Output: ["go on", [["up", [["down", []]]], ["", []]]]

Explanation: Spaces are unchanged. Decoding: "ug gf"->"go on", "xh"->"up", "rgvf"->"down". The root has two children: "up" (with one child "down") and a node with empty text "()".

Hints

Build the inverse cipher first: since encoding maps letter 'a'+i to key[i], the decoding of character key[i] is 'a'+i. Spaces decode to themselves. A 128-entry lookup table gives O(1) per character.
Parse in a single left-to-right pass with an explicit stack (recursion can blow the stack at depth 10^4). On '(' create a new node; its text is the run of characters up to the next '(' or ')'. On ')' pop the current node.
Before pushing a newly opened node, attach it as the next child of the node currently on top of the stack. When the stack becomes empty after a ')', that popped node is the root.

Quick Overview