FastPrepTree Selection and Visibility
Problems/Tree Selection and Visibility

Tree Selection and Visibility

Jane Street logoJane Street● MediumFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: This is the first of two linked tree questions from one Jane Street interview round, in a phone screen. You turn nodes on and off and then list the nodes that can be seen. Picking a node lights up that node, the other children of its parent, and the whole path up to the root. Several picks can be active together, and turning one off must not hide a node that another active pick still lights. Speed of the listing call was the interviewer's main concern.

The report does not say how the tree is given, what display returns, or what happens when a node is selected twice. Here, the tree is a parent array with node 0 as the root, and every parent has a smaller number than its child. Display returns the visible nodes from smallest to largest number. Selecting a selected node or deselecting an unselected one changes nothing. You get the calls as a list of operations instead of a class, and the tests check the answers, not the speed of display.

Our version is about 85% the same as the reported question.

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 node x. If node x is already selected, nothing changes.
  • ["deselect", x]: deselect node x. If node x is 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, where n is the length of parent
  • parent[0] == -1, and 0 <= parent[i] < i for every 1 <= i < n
  • 1 <= operations.length <= 1000
  • Each operation is ["select", x], ["deselect", x], or ["display"].
  • Each x is a node number from 0 to n - 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

Jane Street interview experiences

  • Jane Street Quant Trading Intern Interviews: 1 Experience
All Jane Street interview questionsSee Jane Street hiring insights
Saved
class Solution {
    public List<List<Integer>> treeVisibility(int[] parent, String[][] operations) {
        // Write your code here.
    }
}
Checking account…