Citadel Interview Question
1st Question:- Leetcode Hard. Link:- https://leetcode.com/problems/binary-tree-maximum-path-sum/ .. 2nd Question Similar to:- Leetcode Medium. Link:- https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/ Questions are not similar but identical to the mentioned problems.
Interview Answer
Anonymous
1st Question Approach: Implement DFS to traverse tree, compute max sum considering each node's value, and recursively explore children while tracking maximum sum. Complexity: Time - O(n), visiting each node once; Space - O(n), due to recursive calls on the tree height. 2nd Question Approach: Calculate sums, find missing elements, balance sums by iteratively replacing zeros with minimal values, considering constraints. Complexity: O(n * m) in worst-case scenario, using nested iteration; O(1) space complexity.