How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at DoorDash.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at DoorDash during technical interviews.

Count changed nodes between two menu trees

Quick Overview

This question evaluates algorithmic problem-solving with tree data structures, testing competencies in hierarchical diffing, node matching by sibling keys, subtree addition/removal counting, and handling value updates while respecting performance constraints.

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You maintain a merchant menu as a rooted tree. Each node represents a menu item/category and has: - `key` (string, unique among siblings) - `value` (integer) - `children` (0..k child nodes) When a merchant sends a new menu tree, you want to count how many nodes have **changed** compared to the existing menu. A node is considered **changed** if any of the following is true: 1. **Removed (deactivated):** A node exists in the old tree but does not exist in the new tree **at the same position** (i.e., under the same parent). Count every node in the removed subtree as changed. 2. **Added:** A node exists in the new tree but does not exist in the old tree **at the same position**. Count every node in the added subtree as changed. 3. **Updated value:** A node exists in both trees at the same position (same parent and same `key`), but its `value` differs. Important: If a node with the same `key` appears under a **different parent** in the new tree, treat this as **removal of the old node (and its subtree)** plus **addition of the new node (and its subtree)**. ### Task Given the roots of the old and new trees, return the number of changed nodes. ### Example 1 Old tree: - a(1) - b(2) - d(4) - e(5) - c(3) - f(6) New tree: - a(1) - c(3) - f(66) Output: `4` Explanation: `b`, `d`, `e` are removed (3 changes) and `f` value changes from 6 to 66 (1 change). ### Example 2 Old tree: - a(1) - b(2) - d(4) - e(5) - c(3) - g(7) New tree: - a(1) - b(2) - e(5) - d(4) - f(6) - h(8) - g(7) Output: `5` Explanation: `f` is added (1). Subtree rooted at `c` is removed (`c` and its child `g`: 2). Subtree rooted at `h` is added (`h` and its child `g`: 2). Total = 1 + 2 + 2 = 5. ### Constraints (you may assume) - Total number of nodes across both trees up to `2 * 10^5`. - Children order does not matter. - `key` is unique among siblings (so children can be matched by `key` under the same parent). Design an algorithm to compute the count efficiently.

Quick Answer: This question evaluates algorithmic problem-solving with tree data structures, testing competencies in hierarchical diffing, node matching by sibling keys, subtree addition/removal counting, and handling value updates while respecting performance constraints.

You are given two rooted menu trees: an old menu and a new menu. Each node is represented as `(key, value, children)`, where `key` is a string, `value` is an integer, and `children` is a list of child nodes. An empty tree is represented by `None`. Count how many nodes have changed between the two trees. A node is considered changed if: 1. It exists in the old tree but not in the new tree at the same position. In that case, every node in the removed subtree counts as changed. 2. It exists in the new tree but not in the old tree at the same position. In that case, every node in the added subtree counts as changed. 3. It exists in both trees at the same position (same parent and same `key`), but its `value` is different. Then only that node counts as changed for the value update. Important rules: - Children order does not matter. - Siblings have unique `key` values, so children under the same parent should be matched by `key`. - If the same `key` appears under a different parent in the new tree, treat it as a removal from the old location plus an addition at the new location. - At the root, nodes match only if their root `key` is the same. Return the total number of changed nodes efficiently.

Constraints

0 <= total number of nodes across both trees <= 2 * 10^5
Children order does not matter
`key` is unique among siblings
`value` is an integer
An empty tree is represented by `None`

Examples

Input: ((('a', 1, [('b', 2, [('d', 4, []), ('e', 5, [])]), ('c', 3, [('f', 6, [])])]), ('a', 1, [('c', 3, [('f', 66, [])])])))

Expected Output: 4

Explanation: `b`, `d`, and `e` are removed, which contributes 3. Node `f` stays in the same position but its value changes from 6 to 66, contributing 1 more.

Input: ((('a', 1, [('b', 2, [('d', 4, []), ('e', 5, [])]), ('c', 3, [('g', 7, [])])]), ('a', 1, [('b', 2, [('e', 5, []), ('d', 4, []), ('f', 6, [])]), ('h', 8, [('g', 7, [])])])))

Expected Output: 5

Explanation: Under `b`, child order changes but that does not matter; only `f` is added there (+1). Subtree `c -> g` is removed (+2). Subtree `h -> g` is added (+2). Total = 5.

Input: (None, None)

Expected Output: 0

Explanation: Both trees are empty, so nothing changed.

Input: (('a', 1, []), ('a', 2, []))

Expected Output: 1

Explanation: The root node stays in the same position and only its value changes.

Input: (('a', 1, [('b', 2, [('x', 9, [])]), ('c', 3, [])]), ('a', 1, [('b', 2, []), ('c', 3, [('x', 9, [])])]))

Expected Output: 2

Explanation: Node `x` moved from under `b` to under `c`. That is counted as removing `x` from its old position (+1) and adding `x` at its new position (+1).

Input: (('a', 1, [('b', 2, []), ('c', 3, [])]), ('z', 1, [('b', 2, [])]))

Expected Output: 5

Explanation: The root key changes from `a` to `z`, so the entire old tree is removed (3 nodes) and the entire new tree is added (2 nodes).

Hints

Do not compare children by index. Since sibling keys are unique and order does not matter, build a hash map from `key` to child for each node.
If one side is missing, or two nodes at the same position have different keys, stop comparing deeper there and count the full size of the affected subtree or subtrees.

Quick Overview