Jane Street's 2-Part Tree Selection Question

Jane Street favors precise data-structure work with a twist that punishes sloppy modeling. This two-part tree question is a recurring on-site: first a selection that must behave like a multiset, then a scoring pass to find the best consecutive levels to display. Here is the full question, Java for both parts, and the rubric.

The question

Part 1 · A duplicate-aware selection

The word multiset is the whole trap. Back the selection with a node-to-count map so add increments and remove decrements, deleting only when the count hits zero.

import java.util.*;

class Node {
    final int id;
    Node parent;
    final List<Node> children = new ArrayList<>();
    Node(int id, Node parent) {
        this.id = id; this.parent = parent;
        if (parent != null) parent.children.add(this);
    }
}

class DisplayManager {
    private final Node root;
    private final Map<Node, Integer> selection = new HashMap<>();   // multiset: node -> count
    DisplayManager(Node root) { this.root = root; }

    void addNode(Node n) { selection.merge(n, 1, Integer::sum); }

    void removeNode(Node n) {
        Integer c = selection.get(n);
        if (c == null) return;
        if (c <= 1) selection.remove(n);
        else selection.put(n, c - 1);
    }

    void displaySelection() {
        for (Map.Entry<Node, Integer> e : selection.entrySet()) {
            Node n = e.getKey();
            List<Integer> sibs = new ArrayList<>();
            if (n.parent != null)
                for (Node s : n.parent.children) if (s != n) sibs.add(s.id);
            List<Integer> kids = new ArrayList<>();
            for (Node ch : n.children) kids.add(ch.id);
            System.out.println("Node " + n.id + " (x" + e.getValue() + ")"
                + " parent=" + (n.parent == null ? "none" : n.parent.id)
                + " siblings=" + sibs + " children=" + kids);
        }
    }
}

Part 2 · The most valuable levels

Assign each node a level with a BFS, classify every node by the highest scoring rule that applies, sum scores per level, then slide a window of size maxLevels for the best total. Precompute the parent and neighbor sets once so each node is scored in O(1).

static class Result { List<Integer> levels; long score; Result(List<Integer> l, long s){levels=l;score=s;} }

Result findBestLevels(int maxLevels) {
    // 1) level of each node, grouped
    List<List<Node>> byLevel = new ArrayList<>();
    Deque<Node> q = new ArrayDeque<>();
    Map<Node, Integer> level = new HashMap<>();
    q.add(root); level.put(root, 0);
    while (!q.isEmpty()) {
        Node n = q.poll(); int lv = level.get(n);
        while (byLevel.size() <= lv) byLevel.add(new ArrayList<>());
        byLevel.get(lv).add(n);
        for (Node ch : n.children) { level.put(ch, lv + 1); q.add(ch); }
    }
    // 2) classify nodes by the selection
    Set<Node> selected = selection.keySet();
    Set<Node> parents = new HashSet<>(), neighbors = new HashSet<>();
    for (Node s : selected) {
        if (s.parent != null) {
            parents.add(s.parent);
            for (Node sib : s.parent.children) if (sib != s) neighbors.add(sib);
        }
        neighbors.addAll(s.children);
    }
    // 3) per-level score, highest rule wins
    int L = byLevel.size();
    long[] score = new long[L];
    for (int lv = 0; lv < L; lv++)
        for (Node n : byLevel.get(lv))
            score[lv] += selected.contains(n) ? 3 : parents.contains(n) ? 2 : neighbors.contains(n) ? 1 : 0;
    // 4) best window of consecutive levels
    int w = Math.min(maxLevels, L);
    long run = 0; for (int i = 0; i < w; i++) run += score[i];
    long best = run; int bestStart = 0;
    for (int i = w; i < L; i++) {
        run += score[i] - score[i - w];
        if (run > best) { best = run; bestStart = i - w + 1; }
    }
    List<Integer> levels = new ArrayList<>();
    for (int i = bestStart; i < bestStart + w; i++) levels.add(i);
    return new Result(levels, best);
}

Two precision traps decide this round: removal must be count-aware, and a node that qualifies for several rules scores only the highest. Miss either and your totals drift.

How Jane Street scores it

Jane Street interview FAQ