Live Coding Interview

// Example 1: Overlapping intervals
// Input: [[1,3],[2,6],[8,10],[15,18]]
// [1,3] and [2,6] overlap → merge to [1,6]
// [8,10] doesn't overlap with [1,6]
// [15,18] doesn't overlap with [8,10]
// Output: [[1,6],[8,10],[15,18]]

// Example 2: One interval contains another
// Input: [[1,4],[4,5]]
// [1,4] and [4,5] overlap at 4 → merge to [1,5]
// Output: [[1,5]]

// Example 3: Edge case — empty input
// Input: []
// Output: []

public int[][] Merge(int[][] intervals) {
    if (intervals.Length == 0) return new int[0][];

    // Sort by start time
    Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));

    var result = new List<int[]>();
    int[] current = intervals[0];

    for (int i = 1; i < intervals.Length; i++) {
        if (intervals[i][0] <= current[1]) {
            // Overlapping: merge
            current[1] = Math.Max(current[1], intervals[i][1]);
        } else {
            // No overlap: add current to result, start new
            result.Add(current);
            current = intervals[i];
        }
    }

    result.Add(current);  // Don't forget the last one
    return result.ToArray();
}

// Trace Example 1: [[1,3],[2,6],[8,10],[15,18]]
// After sort: [[1,3],[2,6],[8,10],[15,18]] (already sorted)
// current = [1,3]
// i=1: [2,6], 2 <= 3? yes, merge → current=[1,6]
// i=2: [8,10], 8 <= 6? no, add [1,6], current=[8,10]
// i=3: [15,18], 15 <= 10? no, add [8,10], current=[15,18]
// End: add [15,18]
// Result: [[1,6],[8,10],[15,18]] ✓

// Example 1: Valid BST
//     2
//    / \
//   1   3
// 1 < 2 < 3? Yes, valid BST

// Example 2: Invalid BST
//     5
//    / \
//   1   4
//      / \
//     3   6
// Right subtree of 5 is [1,4,3,6]
// Node 3 (left child of 4) is in right subtree of 5, so must be > 5
// But 3 < 5, so it's invalid

// Example 3: Edge case — single node
// Single node is always a valid BST

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
}

public bool IsValidBST(TreeNode root) {
    return IsValidBSTHelper(root, long.MinValue, long.MaxValue);
}

private bool IsValidBSTHelper(TreeNode node, long min, long max) {
    if (node == null) return true;

    // Check if current node is within bounds
    if (node.val <= min || node.val >= max) {
        return false;
    }

    // Recursively check left and right subtrees
    // Left subtree: max becomes node.val
    // Right subtree: min becomes node.val
    return IsValidBSTHelper(node.left, min, node.val) &&
           IsValidBSTHelper(node.right, node.val, max);
}

// Trace Example 1: [2,1,3]
// IsValidBSTHelper(2, -∞, +∞)
//   2 in (-∞, +∞)? yes
//   Left: IsValidBSTHelper(1, -∞, 2)
//         1 in (-∞, 2)? yes
//         Left: null → true
//         Right: null → true
//         return true
//   Right: IsValidBSTHelper(3, 2, +∞)
//          3 in (2, +∞)? yes
//          Left: null → true
//          Right: null → true
//          return true
//   return true && true = true ✓