Solve scheduling and tree path problems
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Quick Answer: This set evaluates interval scheduling and constrained optimization for weighted, at-most-K selection, tree structure manipulation and subtree effects on height, and tree pathfinding with parent/child navigation, testing competencies in dynamic programming-like optimization, data structures (trees/binary trees), traversal, and ancestor relationships. These problems are commonly asked in Coding & Algorithms interviews because they probe algorithmic efficiency and correctness under large constraints and require both conceptual understanding of algorithmic trade-offs and practical implementation skills.
Part 1: Max credits with at most K non-overlapping courses
Constraints
- 1 <= len(s) == len(e) == len(c) <= 2 * 10^5
- 1 <= K <= n, where n = len(s)
- 1 <= s[i] < e[i] <= 10^9
- 1 <= c[i] <= 10^9
- For this interview version, assume n * K <= 2 * 10^6 so an O(nK) dynamic programming solution is acceptable.
Examples
Input: ([1, 2, 4, 6], [3, 5, 6, 7], [50, 10, 40, 70], 2)
Expected Output: 120
Explanation: Take courses [1,3) worth 50 and [6,7) worth 70 for a total of 120.
Input: ([1, 3, 3], [3, 5, 4], [10, 20, 30], 2)
Expected Output: 40
Explanation: Because intervals are half-open, [1,3) and [3,4) do not overlap. Their total is 40.
Input: ([1, 2, 3], [4, 5, 6], [5, 100, 6], 1)
Expected Output: 100
Explanation: With only one allowed course, choose the course with 100 credits.
Input: ([5], [10], [7], 1)
Expected Output: 7
Explanation: Single-course edge case.
Hints
- Sort courses by end time. For each course, use binary search to find the last course that finishes no later than its start time.
- Let dp[k][i] mean the best answer using the first i sorted courses and taking at most k of them.
Part 2: Height of a rooted binary tree after deleting a node's subtree
Constraints
- 1 <= number of nodes <= 10^5
- 1 <= number of queries <= 10^5
- Each node appears exactly once in nodes
- 1 <= node value <= 10^9 and all node values are unique
- -1 denotes a missing child
- Each query value exists in the tree
Examples
Input: (1, [[1, 2, 3], [2, 4, 5], [3, -1, 6], [4, -1, -1], [5, -1, -1], [6, -1, -1]], [3, 2, 1])
Expected Output: [2, 2, -1]
Explanation: Removing subtree 3 leaves depth 2 through nodes 4 or 5. Removing subtree 2 leaves depth 2 through node 6. Removing the root leaves an empty tree.
Input: (1, [[1, 2, -1], [2, 3, -1], [3, -1, -1]], [2, 3])
Expected Output: [0, 1]
Explanation: This is a chain 1 -> 2 -> 3. Removing 2 leaves only the root. Removing 3 leaves a tree of height 1.
Input: (7, [[7, -1, -1]], [7])
Expected Output: [-1]
Explanation: Single-node edge case. Removing the root makes the tree empty.
Input: (10, [[10, 5, 15], [5, 2, 7], [15, 12, 20], [2, -1, -1], [7, 6, 8], [12, -1, -1], [20, -1, -1], [6, -1, -1], [8, -1, -1]], [5, 15, 7])
Expected Output: [2, 3, 2]
Explanation: Removing subtree 5 leaves the deepest node at depth 2. Removing subtree 15 leaves the path through 5 -> 7 -> 6 or 8, so height 3. Removing subtree 7 removes nodes 7, 6, and 8, leaving height 2.
Hints
- In a DFS preorder traversal, every subtree occupies one contiguous interval.
- After deleting a subtree, the answer is the maximum depth of any node outside that subtree's preorder interval.
Part 3: Directions between two nodes in a binary tree
Constraints
- 1 <= number of nodes <= 10^5
- 1 <= node value <= 10^9 and all node values are unique
- -1 denotes a missing child
- startValue and destValue both exist in the tree
Examples
Input: (5, [[5, 1, 2], [1, 3, -1], [2, 6, 4], [3, -1, -1], [6, -1, -1], [4, -1, -1]], 3, 6)
Expected Output: "UURL"
Explanation: 3 -> 1 -> 5 -> 2 -> 6, so the moves are U, U, R, L.
Input: (2, [[2, 1, -1], [1, -1, -1]], 2, 1)
Expected Output: "L"
Explanation: The destination is the left child of the start node.
Input: (2, [[2, 1, 3], [1, -1, -1], [3, -1, -1]], 1, 3)
Expected Output: "UR"
Explanation: Move up from 1 to 2, then right to 3.
Input: (7, [[7, -1, -1]], 7, 7)
Expected Output: ""
Explanation: Start and destination are the same node.
Input: (8, [[8, 3, 10], [3, 1, 6], [10, -1, 14], [1, -1, -1], [6, 4, 7], [14, 13, -1], [4, -1, -1], [7, -1, -1], [13, -1, -1]], 4, 3)
Expected Output: "UU"
Explanation: 4 goes up to 6, then up again to 3.
Hints
- Any shortest path in a tree goes up from the start node to the lowest common ancestor, then down to the destination.
- If you store each node's parent and whether it is a left or right child, you can reconstruct the answer without explicitly building an LCA structure.