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 Medium 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.

Compute Differences Between Catalog Trees

Quick Overview

This question evaluates proficiency in tree algorithms and hierarchical data comparison, including simultaneous traversal, subtree sizing, key-based node identity, and time/space complexity reasoning, and is commonly asked to assess algorithmic problem-solving and trade-off analysis when comparing structured datasets.

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given two rooted catalog trees. Each node has a unique string key among its siblings and an associated value. Compare the two trees and return the total number of differing nodes under these rules: ( 1) nodes that exist only in the left tree or only in the right tree count toward the total; ( 2) if two nodes share the same path of keys but their values differ, treat the entire subtree at that node as 'delete + recreate' and count all nodes in the left subtree as deletions plus all nodes in the right subtree as creations; ( 3) child order is irrelevant and keys define identity. Design an efficient algorithm that traverses both trees simultaneously (e.g., a primary DFS with an auxiliary subtree-size computation) to compute the count. Analyze time and space complexity, describe edge cases (empty trees, duplicate keys, extremely unbalanced trees), and provide pseudocode or code.

Quick Answer: This question evaluates proficiency in tree algorithms and hierarchical data comparison, including simultaneous traversal, subtree sizing, key-based node identity, and time/space complexity reasoning, and is commonly asked to assess algorithmic problem-solving and trade-off analysis when comparing structured datasets.

You are given two rooted catalog trees, `left` and `right`. Each node is represented as `[key, value, children]`, where `key` is a string that is unique among its siblings, `value` is the node's associated value, and `children` is a list of child nodes (in arbitrary order). A whole tree is either `None` (empty) or a single root node. Return the total number of differing nodes between the two trees under these rules: 1. A node that exists only in the left tree or only in the right tree counts toward the total (every such node in the relevant subtree is counted). 2. If two nodes share the same path of keys but their values differ, treat the entire subtree rooted at that node as **delete + recreate**: count every node in the left subtree as a deletion **plus** every node in the right subtree as a creation. 3. Child order is irrelevant; a node's identity is its key (matched among siblings sharing the same parent path). When two nodes share the same key-path and the same value, recurse into their children. The root nodes are matched against each other directly (their keys are assumed to align as the tree root). Design an efficient algorithm that walks both trees simultaneously with a primary DFS, falling back to an auxiliary subtree-size DFS whenever an entire subtree must be counted as additions or deletions.

Constraints

Each node's key is a string unique among its siblings.
A whole tree may be empty (None / null).
Child order is not significant; identity is by key.
Node count can be large, so the traversal must be linear in the total number of nodes.

Examples

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

Expected Output: 0

Explanation: Identical trees: roots match (value 1), children a and b match by key and value, so there are no differing nodes.

Input: (None, None)

Expected Output: 0

Explanation: Both trees empty: nothing to compare, 0 differences.

Input: (['root', 1, [['a', 1, []]]], None)

Expected Output: 2

Explanation: Right tree empty: every node in the left subtree (root + a) is a deletion -> 2.

Input: (None, ['root', 1, [['a', 1, []], ['b', 2, []]]])

Expected Output: 3

Explanation: Left tree empty: every node in the right subtree (root + a + b) is a creation -> 3.

Input: (['root', 1, [['a', 1, [['x', 1, []]]]]], ['root', 1, [['a', 9, [['y', 2, []]]]]])

Expected Output: 4

Explanation: Roots match (value 1). Child 'a' has value 1 on the left but 9 on the right, so the whole subtree at 'a' is delete+recreate: left subtree (a + x = 2) deletions plus right subtree (a + y = 2) creations = 4.

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

Expected Output: 2

Explanation: Roots match. Key 'a' exists only on the left (1 deletion) and key 'b' exists only on the right (1 creation) -> 2.

Input: (['root', 5, []], ['root', 7, []])

Expected Output: 2

Explanation: The roots are matched but their values differ (5 vs 7): the entire left subtree (1 node) is deleted and the entire right subtree (1 node) is recreated -> 2.

Input: (['root', 1, [['a', 1, [['c', 3, []]]], ['b', 2, []]]], ['root', 1, [['a', 1, [['c', 3, []], ['d', 4, []]]]]])

Expected Output: 2

Explanation: Roots match. Under 'a' (matching value 1): 'c' matches on both sides, 'd' exists only on the right (1 creation). 'b' exists only on the left (1 deletion). Total = 2.

Hints

Match children by key using a hash map per parent so child order does not matter; iterate over the union of left and right child keys.
When a node exists on only one side, you do not need to recurse pairwise — just add the full size of that subtree via an O(size) DFS.
A value mismatch at a node short-circuits the pairwise descent: count subtree_size(left) deletions + subtree_size(right) creations and stop recursing into that node's children.

Quick Overview