Tree Selection and Visibility
Updated
Problem statement
You are given a rooted tree with n nodes, numbered from 0 to n - 1. Node 0 is the root, and parent[0] is -1. For every other node i, parent[i] is the parent of node i.
A node can be selected. At the start, no node is selected. A selected node makes these nodes visible:
- the selected node itself,
- its siblings, which are the other nodes with the same parent, and
- all of its ancestors: its parent, its parent's parent, and so on up to the root.
A node is visible when at least one selected node makes it visible. Many nodes can be selected at the same time. When a node is deselected, a node that another selected node still makes visible stays visible.
Run the operations in operations in order. Each operation is one of these:
["select", x]: select nodex. If nodexis already selected, nothing changes.["deselect", x]: deselect nodex. If nodexis not selected, nothing changes.["display"]: report every visible node, from the smallest node number to the largest. If no node is visible, the report is an empty list.
In an operation, x is a node number written as a string, such as "3".
Return one list for each "display" operation, in the order those operations appear. If there is no "display" operation, return an empty list.
Follow-up: make display as fast as you can.
Function
treeVisibility(parent: int[], operations: String[][]) → List<List<Integer>>Examples
Example 1
parent = [-1,0,0,1,1,2]operations = [["select","3"],["display"],["select","5"],["display"],["deselect","3"],["display"]]return = [[0,1,3,4],[0,1,2,3,4,5],[0,2,5]]Node 0 has children 1 and 2. Node 1 has children 3 and 4. Node 2 has one child, 5.
Selecting 3 shows 3, its sibling 4, and its ancestors 1 and 0. The first report is [0,1,3,4].
Node 5 has no siblings. Selecting it adds 5 and its ancestors 2 and 0, so the second report is [0,1,2,3,4,5].
After 3 is deselected, only 5 is selected. Nodes 1, 3, and 4 were visible only because of 3, so the last report is [0,2,5].
Example 2
parent = [-1,0,0,1,1,2]operations = [["select","3"],["select","4"],["deselect","3"],["display"],["deselect","4"],["display"]]return = [[0,1,3,4],[]]This is the same tree as Example 1. Nodes 3 and 4 are selected, and then 3 is deselected.
Node 3 is still visible, because it is a sibling of the selected node 4. The first report is [0,1,3,4].
After 4 is deselected, no node is selected, so the second report is an empty list.
Example 3
parent = [-1,0,0,0]operations = [["display"],["select","0"],["display"],["select","2"],["select","2"],["display"],["deselect","2"],["display"]]return = [[],[0],[0,1,2,3],[0]]The root 0 has three children: 1, 2, and 3.
The first report comes before any selection, so it is empty. The root has no parent and no siblings, so selecting it shows only 0.
Selecting 2 twice still selects it once. It shows its siblings 1 and 3, so the third report is [0,1,2,3].
One deselect of 2 is enough to remove it. Only the root is still selected, so the last report is [0].
Constraints
1 <= n <= 1000, wherenis the length ofparentparent[0] == -1, and0 <= parent[i] < ifor every1 <= i < n1 <= operations.length <= 1000- Each operation is
["select", x],["deselect", x], or["display"]. - Each
xis a node number from0ton - 1, written in decimal with no leading zeros.
More Jane Street interview questions
- Maximum-Scoring Consecutive Tree LevelsPHONE SCREEN · Seen Nov 2026
- Load/Store Arithmetic InterpreterPHONE SCREEN · Seen Oct 2026
- Instrument Stack Language JumpsPHONE SCREEN · Seen Oct 2026
- Run a Stack Language InterpreterPHONE SCREEN · Seen Oct 2026
- Positive-Integer Expression EvaluationPHONE SCREEN · Seen Oct 2026
- Code Editor FoldingONSITE INTERVIEW · Seen Oct 2026
- Exact-Sixty Dice Game ValueONSITE INTERVIEW · Seen Oct 2026
- Expected Value of Modified DiceONSITE INTERVIEW · Seen Oct 2026
- Spaceship Equipment LoadoutONSITE INTERVIEW · Seen Oct 2026
- Two-Tower Strategy GameONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
- Worst-Performing Ads by CTR in a Campaign TreeUber · PHONE SCREENUber interview questions
- Search for an Element in a StreamAmazon · PHONE SCREEN
- Build a File Tree from Streamed RecordsNextdoor · PHONE SCREENNextdoor interview questions
- Hierarchical In-Memory File SystemClay · PHONE SCREEN
- Page Permission InheritanceNotion · PHONE SCREEN · ONSITE INTERVIEWNotion interview questions
- In-Memory File System With Directory SizesCapital One · PHONE SCREEN · ONSITE INTERVIEWCapital One interview questions
- ClayWorkspace Resource TreeGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
- Insert Delete GetRandom O(1)Charta Health · PHONE SCREENCharta Health interview questions