Stage 1 of 2: Height after deletions
Background. A tree whose nodes can have any number of children is given as a list of parents. Deleting a node takes it out of the tree but keeps its children: they move up to its parent.
Implement remaining_height(parent, deleted) in nary_tree.py. Return the height of the tree once every node in deleted is gone.
parenthas n entries, 1 ≤ n ≤ 100,000. The root is node 0, withparent[0] == -1; any other entryparent[i]names the node directly above nodei, and together the entries form one tree under node 0. The numbers follow no order: a node can have a smaller number than its parent.deletedlists distinct nodes from 1 to n - 1, in any order, possibly none. The root is never deleted.- A deleted node leaves the tree and its children move up to its parent. If that parent is deleted too, they keep going up: every remaining node ends up under its closest ancestor that is not deleted. The order of
deleteddoes not change the result. - The height counts nodes: the most nodes on a path from the root down. A tree of one node has height 1, which is also the answer when every other node is deleted.
- A tree can be one path of 100,000 nodes. A call on 100,000 nodes must return within 4 seconds (
test_long_pathandtest_broom_with_its_line_deletedeach time one), and the code may not change Python's recursion limit: the tests refusesys.setrecursionlimit.
Example
parent = [-1, 0, 0, 1, 1, 2, 3]
deleted = [1, 5]
0 0
/ \ / | \
1 2 -> 3 4 2
/ \ \ |
3 4 5 6
|
6
remaining_height([-1, 0, 0, 1, 1, 2, 3], [1, 5]) returns 3: nodes 3 and 4 move up to the root, node 6 stays under node 3, and node 2 has no child left.
On the starter, 12 of the 13 tests in tests/test_part1.py fail; the recursion-limit test passes.
Done when Submit goes green.
Constraints
- Python 3.12 standard library only
- Editable:
nary_tree.py - Read-only:
test_helpers.pyand alltests/test_*.pyfiles - Do not change the recursion limit
What comes after stage 1
The next stage opens once the tests for the one before it pass. Each raises the bar, the way an interviewer does in the room.
- Stage 2: Fewest deletions for a height limit. Now choose the deletions: as few nodes as possible so a tree of up to 100,000 nodes fits under a height limit.
The files you get
- Yours to edit: nary_tree.py.
- Read-only: test_helpers.py.
- Tests you can read and run: tests/test_part1.py. Hidden tests run on Submit.
The round: no AI, an assistant that only answers
Snowflake runs this round without AI. Here the closest format is answer-only: the assistant answers your questions and reviews your code when you ask, the way an interviewer would, and never writes a line of it. The interviewer asks about your decisions as you go, and the report states the format. You can switch to the agent format when you press Begin.
Frequently asked, briefly answered
Is N-ary Tree Deletions free?
It is a Pro problem. Free plan includes one complete problem, plus the first stage of several more, so you can see how a round works before you pay.
Which company asks something like this?
Snowflake. It is modelled on Snowflake's coding round, which runs without AI. Based on candidates' reports of Snowflake interviews. Nyrion wrote this version, so the question you get may differ.
Do I bring my own AI tool?
No. The real round has no AI, so this one opens answer-only: an assistant that answers your questions and can't write code. You can switch to an agent that proposes changes when you press Begin.
What does the interviewer ask?
4 questions along the way about your own code, and one at the end about the whole session. A weak answer gets one follow up. The answers go into the report, which ends with a hire or no hire verdict.
Start the problem
Sign in and the problem opens where you left it. New here? An account takes a minute to create, and the Pro plan starts at the first stage of this problem.
More like it: every practice problem, Snowflake's interviews, the AI coding interview guide.