Stage IV: Easy Questions

Greedy Algorithm

Pattern: Conceptual Understanding

These questions test your direct comprehension of the greedy philosophy, its necessary conditions, and its potential pitfalls.

1. The Greedy Philosophy and Its Failure

Problem: Explain the core philosophy of a "Greedy Algorithm." Using the non-standard coin example from the text ({1, 7, 10} cents for a total of 15 cents), explain why a greedy approach can sometimes fail to produce a globally optimal solution.

Concept Tested: Understanding the "locally optimal" choice and recognizing that it's not always globally optimal.

View Analysis

Greedy Philosophy: The core philosophy is to build a solution step-by-step. At each step, it makes the choice that seems best at that immediate moment (the "locally optimal" choice), without considering future consequences. The hope is that this series of local bests will lead to the overall best (globally optimal) solution.

Failure Case: For making 15 cents with coins {1, 7, 10}, the greedy approach is:

Take the biggest coin possible: 10¢. Remaining: 5¢.
Take the biggest coin possible: 1¢. Remaining: 4¢.
...and so on, resulting in 10 + 1 + 1 + 1 + 1 (5 coins).

This fails because the first greedy choice (taking 10¢) prevented us from using a better combination. The true optimal solution is 7 + 7 + 1 (3 coins), which a greedy algorithm would never find because it would never choose a 7¢ coin over a 10¢ coin at the start.

2. Conditions for a Greedy Algorithm

Problem: What are the two properties a problem must have for a greedy algorithm to be guaranteed to work? Briefly explain each one.

Concept Tested: Identifying the formal properties that justify a greedy approach.

View Analysis

Greedy Choice Property: This means a globally optimal solution can be reached by making a locally optimal choice. At every step, the choice that seems best right now must be part of some globally optimal solution, so we never have to backtrack and reconsider our choices.

Optimal Substructure: This means that an optimal solution to the overall problem contains within it the optimal solutions to its subproblems. In the standard change-making problem, the optimal solution for 48 cents (a quarter + the optimal solution for 23 cents) relies on finding the optimal solution for the smaller problem of making 23 cents.

Pattern: Foundational Greedy Problems

These problems are direct applications of a greedy strategy, often requiring a simple sorting step first.

3. Assign Cookies

Concept Tested: A simple, intuitive greedy choice. To maximize content children, the smallest cookie that can satisfy the least greedy child should be used. This is best achieved by sorting both arrays.

Companies: Google, Amazon

4. Gas Station

Concept Tested: A clever greedy approach where you track a running total. If the total goes negative, you know the starting point must be after the current position.

Companies: Amazon, Microsoft, Bloomberg

5. Jump Game

Concept Tested: A greedy strategy working backwards. You keep track of the "goal" post and see if it can be reached from the previous position.

Companies: Amazon, Facebook, Microsoft

Backtracking

Pattern: Conceptual Understanding

These questions test your direct comprehension of the backtracking framework, its recursive nature, and its key optimization techniques.

1. The Backtracking Pattern

Problem: Explain the "Choose, Explore, Unchoose" pattern that is central to all backtracking algorithms. Why is recursion a natural and elegant way to implement this pattern?

Concept Tested: Understanding the fundamental recursive structure of backtracking.

2. Pruning the Search Space

Problem: What is "pruning" in the context of a backtracking algorithm, and why is it crucial for solving complex problems efficiently?

Concept Tested: Understanding the primary optimization strategy for backtracking algorithms.

Pattern: Foundational Combinatorial Problems

These problems are the building blocks of backtracking, focusing on generating all possible combinations or permutations of a set.

3. Subsets (Power Set)

Concept Tested: The most fundamental backtracking choice: for each element, you either include it in the current subset or you don't.

Companies: Amazon, Facebook (Meta), Google, Microsoft, Bloomberg

4. Combination Sum

Concept Tested: Backtracking with a target sum and the ability to reuse elements.

Companies: Amazon, Facebook (Meta), Microsoft, Apple

5. Permutations

Concept Tested: Backtracking by swapping elements to generate different orderings.

Companies: Amazon, Microsoft, Facebook (Meta), Google, LinkedIn

Dynamic Programming

Pattern: Conceptual Understanding

These questions test your understanding of the core DP principles before diving into code.

1. The Pillars of Dynamic Programming

Problem: A problem is only suitable for a Dynamic Programming solution if it exhibits two specific properties. What are these two properties, and why is the Fibonacci sequence a perfect example that demonstrates both?

Concept Tested: Understanding the required conditions for applying DP.

2. Memoization vs. Tabulation

Problem: Explain the difference between the two main DP approaches: Memoization (Top-Down) and Tabulation (Bottom-Up).

Concept Tested: Differentiating between the two implementation strategies for DP.

Pattern: Classic 1D & 2D DP

These problems are the essential building blocks for your DP toolkit.

3. Climbing Stairs

Concept Tested: The "other" Fibonacci. The number of ways to reach step n is the sum of ways to reach step n-1 and ways to reach step n-2.

Companies: Amazon, Apple, Adobe

4. Word Break

Concept Tested: String-based 1-D DP. The state `dp[i]` is True if the substring `s[:i]` can be segmented.

Companies: Amazon, Facebook (Meta), Google, Microsoft

5. House Robber

Concept Tested: A classic decision-making problem. At each house i, the robber must choose: either rob house i or not rob house i.

Companies: Amazon, Google, Microsoft, Facebook (Meta)

6. Unique Paths

Concept Tested: Finding the number of ways to reach a cell in a grid from the cells above and to the left.

Companies: Amazon, Google, Microsoft, Bloomberg

7. Minimum Path Sum

Concept Tested: Finding the optimal path in a grid by taking the minimum of the paths from the cells above and to the left.

Companies: Amazon, Google, Microsoft

Pattern: Knapsack Variants (0/1 & Unbounded)

These problems test your ability to solve optimization problems involving choices with constraints.

8. Partition Equal Subset Sum

Concept Tested: A classic transformation of the 0/1 knapsack problem, where the goal is to find a subset of numbers that sums to `total_sum / 2`.

Companies: Amazon, Facebook (Meta), Microsoft

9. Coin Change

Concept Tested: The canonical Unbounded Knapsack problem. Find the minimum number of coins to make a target amount, where each coin can be used multiple times.

Companies: Amazon, Google, Microsoft, Apple, Bloomberg

Pattern: Longest Common/Increasing Subsequence

This is a major family of DP problems based on comparing two sequences or finding properties within a single sequence.

10. Longest Common Subsequence (LCS)

Concept Tested: The foundational LCS problem. The state `dp[i][j]` represents the length of the LCS of `text1[:i]` and `text2[:j]`.

Companies: Amazon, Google, Microsoft

11. Longest Increasing Subsequence (LIS)

Concept Tested: The canonical LIS problem. The state `dp[i]` stores the length of the longest increasing subsequence that *ends* at index `i`.

Companies: Amazon, Microsoft, Google, Apple, Facebook (Meta)

Pattern: Palindromic Substrings/Subsequences

Problems that involve finding palindromes within a string.

12. Longest Palindromic Substring

Concept Tested: A DP state `dp[i][j]` can be used to represent if the substring `s[i:j]` is a palindrome. An O(n²) "Expand From Center" approach is often simpler and preferred.

Companies: Amazon, Microsoft, Google, Apple