At DoorDash, menus are updated daily even hourly to keep them up-to-date. Each menu can be regarded as a tree. A menu can have many categories; each category can have many menu_items; each menu_item can have many item_extras; An item_extra can have many item_extra_options…
class Node {
String key;
int value;
boolean active;
List<Node> children;
}We will compare the new menu sent from the merchant with our existing menu. Each item can be considered as a node in the tree. The definition of a node is defined above. Either value change or the active status change means the node has been changed. There are times when the new menu tree structure is different from existing trees, which means some nodes are set to null. In this case, we only do soft delete for any nodes in the menu. If that node or its sub-children are null, we will treat them ALL as inactive. There are no duplicate nodes with the same key.
Return the number of changed nodes in the tree.
Existing tree:
a(1, T)
/ \
b(2, T) c(3, T)
/ \ \
d(4, T) e(5, T) f(6, T)
New tree:
a(1, T)
\
c(3, F)
\
f(66, T)a(1, T) a is the key, 1 is the value, T is True for active status
For example, there are a total of 5 changed nodes. Node b, Node d, Node e are automatically set to inactive. The active status of Node c and the value of Node f changed as well.
Existing tree
a(1, T)
/ \
b(2, T) c(3, T)
/ \ \
d(4, T) e(5, T) g(7, T)
New tree
a(1, T)
/ \
b(2, T) c(3, T)
/ | \ \
d(4, T) e(5, T) f(6, T) g(7, F)
sol: 2 Assumptions:
- when keys don't match, the entire subtree will be considered as new one and old one is considered deleted
- Treat the active-inactive status as value change => and proceed with lower dfs calls
class Node:
def __init__(self, key: int, val: int, children: [Node], active: bool):
"""
Represents a tree node with the following attributes:
:param key: Unique identifier for the node
:param val: Value stored in the node
:param children: List of child nodes
:param active: Boolean indicating the active/inactive status of the node
"""
self.key = key
self.val = val
self.children = children
self.active = active
class Solution:
def countChangedNodes(oldRoot, newRoot) -> int:
"""
Count the number of nodes that have changed between two trees,
including structure (subtree additions/deletions) and value/active-status changes.
:param oldRoot: Root of the old tree
:param newRoot: Root of the new tree
:return: Total count of changed nodes
"""
res = 0
# If both roots are null, no changes
if not oldRoot and not newRoot:
return res
# If old tree doesn't exist, count all nodes in the new tree
if not oldRoot:
return Solution.countAllChildren(newRoot)
# If new tree doesn't exist, count all nodes in the old tree
if not newRoot:
return Solution.countAllChildren(oldRoot)
# If keys don't match, count the entire subtrees of both as changed
if oldRoot.key != newRoot.key:
return Solution.countAllChildren(oldRoot) + Solution.countAllChildren(newRoot)
# Create maps for child nodes keyed by their keys for both trees
oldMap = {child.key: child for child in oldRoot.children}
newMap = {child.key: child for child in newRoot.children}
# Extract keys for comparison
oldKeys, newKeys = set(oldMap.keys()), set(newMap.keys())
# Find intersection, additions, and deletions
intersection = oldKeys.intersection(newKeys)
deletions = oldKeys.difference(intersection)
additions = newKeys.difference(intersection)
# Count all deleted subtrees
for key in deletions:
node = oldMap[key]
res += Solution.countAllChildren(node)
# Count all added subtrees
for key in additions:
node = newMap[key]
res += Solution.countAllChildren(node)
# Process nodes in the intersection
for key in intersection:
oldNode = oldMap[key]
newNode = newMap[key]
# Check if value or active status has changed
if oldNode.val != newNode.val or oldNode.active != newNode.active:
res += 1 # Count the current node as changed
# Recursively count changes in the subtree
res += Solution.countChangedNodes(oldNode, newNode)
return res
@staticmethod
def countAllChildren(root):
"""
Count all nodes in the subtree rooted at the given node (including the root).
:param root: Root of the subtree
:return: Total number of nodes in the subtree
"""
if not root:
return 0
# Count the root itself
res = 1
# Recursively count all child nodes
for child in root.children:
res += Solution.countAllChildren(child)
return res
Disclaimer: This is not an interview experience. This post has been made only to provide my thoughts and solution to the above frequently circulating doordash question on leetcode discuss section. in reference to, link.