How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview 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 Interview Question

Q: Decode an Encrypted Paragraph Tree

This is a Coding & Algorithms interview question from Jane Street for Software Engineer roles. View the full question and solution on PracHub.

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:

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.
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.

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:

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.
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.

Examples

Example 1

Input:  key = "bcdefghijklmnopqrstuvwxyza"
        s   = "(ij(bc)(de))"
Output: ["hi", [["ab", []], ["cd", []]]]

Example 2

Input:  key = "qwertyuiopasdfghjklzxcvbnm"
        s   = "(ug gf(xh(rgvf))())"
Output: ["go on", [["up", [["down", []]]], ["", []]]]

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.

Decode an Encrypted Paragraph Tree

Decode an Encrypted Paragraph Tree

Decode an Encrypted Paragraph Tree

Examples

Constraints

Submit Your Answer to Earn 20XP

Decode an Encrypted Paragraph Tree

Decode an Encrypted Paragraph Tree

Decode an Encrypted Paragraph Tree

Examples

Constraints

Submit Your Answer to Earn 20XP