Compute Differences Between Catalog Trees

Q: Compute Differences Between Catalog Trees

This is a Coding & Algorithms interview question from DoorDash for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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: (

nodes that exist only in the left tree or only in the right tree count toward the total; (
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; (
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.

Compute Differences Between Catalog Trees

Comments (0)