Solve scheduling and tree path problems
Quick Overview
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.
You are given three separate coding problems (asked across two rounds). For each, write a function that returns the required output.
Problem 1: Max credits with at most K non-overlapping courses
You are given n courses. Course i has:
-
start time
s[i] -
end time
e[i](assume a course occupies the half-open interval[s[i], e[i])so a course ending at timetdoes not conflict with another starting att) -
credit value
c[i]
You may take at most K courses, and you may not take overlapping courses.
Output: the maximum total credits you can earn.
Inputs: arrays s, e, c and integer K.
Constraints (assume typical interview ranges): 1 ≤ n ≤ 2e5, 1 ≤ K ≤ n, times up to 1e9, credits up to 1e9.
Problem 2: Height of a rooted tree after deleting a node (subtree removal)
You are given a rooted binary tree (or general rooted tree—state assumptions in your solution) and a node x.
Operation: remove node x and its entire subtree from the tree.
Output: the height of the remaining tree (define height as number of edges on the longest path from the root to any remaining node; height of an empty tree is -1 or 0—state your convention).
You may be asked to answer this for one query or for multiple queries.
Problem 3: Directions between two nodes in a binary tree
You are given a binary tree and two node values startValue and destValue.
You must output a string describing how to move from the startValue node to the destValue node using:
-
L: move to left child -
R: move to right child -
U: move to parent
Output: the direction string representing a valid shortest path from start to destination.