Coding Interview Problems

In this lesson, we will explore three complex coding interview problems that cover a variety of algorithms and problem-solving techniques. We’ll look at problems involving sorting, tree traversal, and greedy algorithms. These examples are designed to help you understand how to approach different types of problems in competitive programming and improve your problem-solving skills.

1. Problem: Merge Intervals

Problem Statement: Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

import java.util.Arrays;
import java.util.LinkedList;

public class Solution {

  public int[][] merge(int[][] intervals) {
    // Sort the intervals based on the start time
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

    LinkedList<int[]> merged = new LinkedList<>();

    for (int[] interval : intervals) {
      // If the list of merged intervals is empty or the current interval does not overlap with the last one, add it
      if (merged.isEmpty() || merged.getLast()[1] < interval[0]) {
        merged.add(interval);
      } else {
        // If there is an overlap, merge the current interval with the last one
        merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]);
      }
    }

    return merged.toArray(new int[merged.size()][]);
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    int[][] intervals = { { 1, 3 }, { 2, 6 }, { 8, 10 }, { 15, 18 } };

    int[][] mergedIntervals = solution.merge(intervals);

    // Print the merged intervals
    System.out.println("Merged Intervals:");
    for (int[] interval : mergedIntervals) {
      System.out.println(Arrays.toString(interval));
    }
  }
}

Time Complexity for Merge Intervals Algorithm

1. Sorting Step:

   • The first operation in the code is sorting the intervals array based on the start times.
   • Time Complexity of Sorting: The sorting step takes , where n is the number of intervals. This is due to the use of a comparison-based sorting algorithm such as Timsort.

2. Merging Step:

   • The for-loop iterates through each interval exactly once, performing operations for each iteration to check for overlaps and merge intervals if necessary.
   • Time Complexity of the Loop: The loop runs in because it processes each of the n intervals once.

Overall Time Complexity:

• The overall time complexity is dominated by the sorting step:

Space Complexity for Merge Intervals Algorithm

1. Space for Sorting:

   • The sorting has a space complexity of due to the use of in-place sorting for primitive types.

2. Auxiliary Space for Merging:

   • The merged list is used to store the merged intervals. In the worst case, if there are no overlapping intervals, the list will store all n intervals, resulting in space.

3. Output Array:

   • The toArray() method creates a new array to return the result, which also takes space.

Overall Space Complexity:

• The total space complexity is: The primary contributor to space usage is the List used for storing merged intervals and the output array.

2. Problem: Maximum Path Sum in a Binary Tree

Problem Statement: Given a non-empty binary tree, find the maximum path sum. The path may start and end at any node in the tree.

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

public class Solution {

  private int maxSum = Integer.MIN_VALUE;

  public int maxPathSum(TreeNode root) {
    findMaxPath(root);
    return maxSum;
  }

  private int findMaxPath(TreeNode node) {
    if (node == null) return 0;

    // Recursively find the maximum path sum of left and right subtrees, only taking positive sums
    int leftMax = Math.max(0, findMaxPath(node.left));
    int rightMax = Math.max(0, findMaxPath(node.right));

    // Update maxSum if the current path (including this node) is greater than the current maxSum
    maxSum = Math.max(maxSum, node.val + leftMax + rightMax);

    // Return the maximum path sum including this node and one of its subtrees
    return node.val + Math.max(leftMax, rightMax);
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Constructing example tree
    TreeNode root = new TreeNode(-10);
    root.left = new TreeNode(9);
    root.right = new TreeNode(20);
    root.right.left = new TreeNode(15);
    root.right.right = new TreeNode(7);

    int maxPathSum = solution.maxPathSum(root);
    System.out.println("Maximum Path Sum: " + maxPathSum);
  }
}

Time Complexity for Maximum Path Sum in a Binary Tree

1. Recursive Calls:

   • The function findMaxPath(TreeNode node) is called recursively for each node in the tree.
   • Number of Calls: Each node in the tree is visited exactly once during the traversal.
   • Overall Time Complexity: , where n is the number of nodes in the binary tree. Each node is processed once, making the traversal linear in relation to the number of nodes.

2. Operations per Node:

   • For each node, the following operations are performed:
     • Calculating leftMax and rightMax using recursive calls → for each operation.
     • Calculating maxSum by comparing and updating → .
     • Returning the result for the current node → .
   • The total work done at each node is constant, , so the time complexity remains as each node is visited once.

Space Complexity for Maximum Path Sum in a Binary Tree

1. Recursive Call Stack:

   • The space complexity due to recursion depends on the maximum depth of the tree (i.e., the height h).
   • Balanced Tree: For a balanced tree, the height is .
   • Unbalanced Tree (Skewed): In the worst case (e.g., a tree that behaves like a linked list), the height is .

2. Auxiliary Space:

   • No additional data structures are used that depend on the size of the input, aside from the recursion stack.

Overall Space Complexity:

• Best Case (Balanced Tree):
• Worst Case (Unbalanced Tree):

3. Problem: Fractional Knapsack (Greedy Algorithm)

Problem Statement: Given the weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. You can take fractions of items.

import java.util.Arrays;

class Item {

  int weight;
  int value;

  public Item(int weight, int value) {
    this.weight = weight;
    this.value = value;
  }
}

public class Solution {

  public double fractionalKnapsack(int W, Item[] items) {
    // Sort items by value-to-weight ratio in descending order
    Arrays.sort(items, (a, b) ->
      Double.compare((double) b.value / b.weight, (double) a.value / a.weight)
    );

    double totalValue = 0.0;

    for (Item item : items) {
      if (W >= item.weight) {
        // If the whole item can be added, add it and reduce the capacity
        totalValue += item.value;
        W -= item.weight;
      } else {
        // If only part of the item can be added, add that fraction
        totalValue += ((double) item.value / item.weight) * W;
        break; // Knapsack is full
      }
    }

    return totalValue;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example items (weight, value)
    Item[] items = { new Item(10, 60), new Item(20, 100), new Item(30, 120) };

    int knapsackCapacity = 50; // Knapsack capacity

    double maxValue = solution.fractionalKnapsack(knapsackCapacity, items);

    System.out.println("Maximum value in Knapsack: " + maxValue);
  }
}

Time Complexity for Fractional Knapsack Problem

1. Sorting Step:

   • The items array is sorted based on the value-to-weight ratio in descending order.
   • Time Complexity of Sorting: Sorting the array of n items takes due to the use of a comparison-based sorting algorithm (Timsort in Java's Arrays.sort()).

2. Iterating Through Items:

   • The loop iterates over each of the n items once to add them or fractions of them to the knapsack.
   • Time Complexity of Loop: .

Overall Time Complexity:

• The overall time complexity is:

The sorting step dominates the runtime.

Space Complexity for Fractional Knapsack Problem

1. Auxiliary Space:

   • The space used for sorting is due to the in-place sorting algorithm.
   • No additional data structures are used, apart from a few variables to store the total value and the capacity W.

2. Space for Input:

   • The input items array does not count toward auxiliary space complexity as it is provided as input and not created within the function.

Overall Space Complexity:

• The total space complexity is: for auxiliary space, as the algorithm does not require additional data structures that scale with input size beyond sorting space.

I just read a lesson on **Coding Interview Problems** (DSA) and want to truly understand it. Explain Coding Interview Problems from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Coding Interview Problems** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Coding Interview Problems** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Coding Interview Problems** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.