Skip to content
Data Structures & Algorithms

Greedy Algorithms interview questions and answers

41 questions, 17 with code. About 3 h 4 min to read them all.

By TestLab · Updated

Plan for an interview
41 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

What is a greedy algorithm in computer science?

A greedy algorithm makes the locally best choice at each step without reconsidering previous decisions. It produces an optimal solution only when that local choice can be proven safe for the global problem.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

A greedy algorithm repeatedly selects the option that appears best for the current state and then solves the remaining problem.

The greedy choice is safe when an exchange argument can show that some optimal solution includes that choice. The problem must also have the optimal substructure property: after making the choice, an optimal solution to the remaining subproblem can be combined with that choice to form an optimal solution for the original problem.

For example, activity selection chooses compatible activities in increasing order of finishing time. Choosing the earliest-finishing activity leaves as much time as possible for later activities.

Greedy Choice and Correctness

A typical greedy algorithm follows three stages:

  1. Select the best available option under the current greedy rule.

  2. Update the state to account for that selection.

  3. Repeat until no valid option remains.

Correctness requires more than simply choosing the “largest,” “smallest,” or “cheapest” item:

  • Greedy-choice property: The locally selected item can replace an item in an optimal solution without making the result worse.

  • Optimal substructure: An optimal solution can be composed from optimal solutions to the relevant subproblems.

  • Feasibility: Each choice must preserve the problem’s constraints.

Dynamic programming differs because it stores and compares results for multiple possible states. A greedy algorithm commits to one choice, so it is usually simpler and faster but not universally correct.

Complexity

There is no single Big-O complexity for greedy algorithms because it depends on the specific problem and greedy rule.

  • Time: Analyze the selection rule, number of steps, and any required sorting.

  • Space: Include auxiliary data structures and the recursion stack, if recursion is used.

  • Input counting: The complexities below exclude the input array itself unless explicitly stated.

  • Best, average, and worst case: These are identical for the deterministic activity-selection examples shown; other greedy algorithms may differ.

Approach Best, Average, and Worst Time Auxiliary Space When to Use
Brute-force activity selection O(n · 2^n) O(n) for the recursion stack and selected activities Small inputs or verifying a counterexample
Greedy activity selection O(n log n) O(n) for a sorted copy When earliest-finishing selection is provably safe

For brute force, there are O(2^n) subsets, and checking each subset can take O(n) time. For the greedy algorithm, sorting takes O(n log n) and the subsequent scan takes O(n), so sorting dominates. The sorted copy accounts for its O(n) auxiliary space.

Worked Example

For activity selection, consider these half-open intervals:

Activity Interval
A [1, 3)
B [2, 5)
C [3, 4)
D [4, 6)
  1. Sort by finishing time: A, C, D, B.

  2. Select A because it finishes first.

  3. Skip B because it overlaps A.

  4. Select C because it starts at or after A’s finish.

  5. Select D because it starts at or after C’s finish.

The result is A, C, D. The exchange argument is that replacing the first activity in any optimal schedule with the earliest-finishing compatible activity cannot reduce the number of activities that can be scheduled.

When Greedy Fails

Coin change is a useful counterexample. With denominations 1, 3, 4 and amount 6:

  • Greedy selection: 4 + 1 + 1, requiring 3 coins.

  • Optimal selection: 3 + 3, requiring only 2 coins.

The locally largest coin prevents a better global combination. For unrestricted coin change, dynamic programming is a standard correct alternative when the denomination system does not have special properties that make a greedy strategy optimal.

Common Pitfalls

  • Assuming greedy always works: Verify the greedy-choice property with an exchange argument.

  • Confusing local and global optimality: The best immediate choice may block better later choices.

  • Ignoring sorting costs: Account for O(n log n) sorting when the greedy rule depends on sorted input.

  • Mutating the input unnecessarily: Copy before sorting if callers need the original order.

  • Missing edge cases: Handle empty input, one element, duplicates, negative values, already sorted data, and impossible selections.

  • Choosing the wrong alternative: Some interval-scheduling variants maximize profit rather than the number of activities and may require dynamic programming.

Interviewers commonly ask for the greedy rule, its correctness proof, the time and space complexity, and a counterexample showing when the same strategy would fail.

2

What problems are solved with Greedy Algorithms?

A Greedy Algorithm is used for optimization problems where the optimal solution is constructed by making a sequence of locally optimal choices. It is applicable when the problem exhibits the greedy-choice property and optimal substructure, ensuring a global optimum without needing to backtrack.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • The greedy choice is to pick the best immediate option at each step.

  • This is safe if the problem has the greedy-choice property, meaning a locally optimal choice leads to a global optimum.

  • It also requires optimal substructure, where an optimal solution contains optimal solutions to subproblems.

  • Once a choice is made, it is never reconsidered, which eliminates the need for backtracking.

  • The algorithm builds the solution incrementally until the problem is solved.

Typical Problems

  • Activity Selection / Interval Scheduling: Selecting the maximum number of non-overlapping activities.

  • Merge Intervals: Combining overlapping intervals.

  • Fractional Knapsack: Maximizing value by taking fractions of items.

  • Huffman Coding: Constructing optimal prefix codes for data compression.

  • Dijkstra’s and Prim’s Algorithms: Finding shortest paths and minimum spanning trees.

  • Coin Change: Making change with the fewest coins (canonical systems only).

  • Jump Game: Determining if you can reach the last index.

  • Gas Station: Finding a starting station to complete a circuit.

  • Task Scheduler: Minimizing idle time between tasks.

  • Minimum Platforms: Finding minimum platforms needed for a station.

Complexity

  • Time: Typically O(n log n) because sorting is often the main cost, though some problems are O(n) if no sorting is required.

  • Space: Usually O(1) for in-place selection or O(n) to store the solution set.

  • Best/Average/Worst: Generally consistent across cases since the algorithm follows a fixed deterministic path.

When Greedy Fails

Problem Greedy Approach Why It Fails
Coin Change (1, 3, 4) 4 + 1 + 1 Optimal is 3 + 3
0/1 Knapsack Take highest value density Items cannot be divided
Traveling Salesperson Nearest neighbor Not guaranteed shortest path

Common Pitfalls

  • Assuming greedy works without proof.

  • Off-by-one errors in interval problems.

  • Not handling edge cases like empty input.

  • Confusing 0/1 knapsack with fractional knapsack.

3

What characteristics make a problem suitable for greedy algorithms?

Greedy algorithms solve optimization problems by repeatedly making the locally best choice that can still lead to an optimal solution. Problems suited to this approach usually have a provably safe local choice, an optimal substructure, and a simple way to construct a complete solution incrementally.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Characteristics

  • Greedy-choice property: At each step, at least one optimal solution begins with the greedy choice.

  • Optimal substructure: After making a choice, the remaining problem has the same form and can be solved optimally on its own.

  • Exchange argument: Often, the greedy choice can replace a different choice in an optimal solution without reducing the result.

  • No harmful interactions: Choosing one item usually does not create conflicts or unexpected costs involving later choices.

  • Incremental feasibility: The algorithm can test whether a candidate choice is valid and continue without extensive backtracking.

  • Repeatedly equivalent choices: Many instances can be handled by applying the same selection rule until no more choices remain.

  • Simple objective contribution: The value of each choice is commonly independent of the order in which choices are made.

A safe greedy choice is therefore not merely the option with the highest immediate value; it must preserve the possibility of an optimal final result.

Establishing Correctness

A common proof structure is:

  1. Identify the greedy choice.

  2. Assume an optimal solution exists.

  3. Show that the greedy choice can replace the first choice in that solution.

  4. Prove that the replacement does not reduce the objective or invalidate later choices.

  5. Apply the same reasoning recursively to the remaining problem.

This exchange argument is essential. Without it, an algorithm that looks greedy may produce a locally attractive but globally poor result.

Typical Problem Patterns

Space complexity below excludes the input and includes any recursion stack; the examples can be implemented iteratively with constant stack usage.

Problem Greedy choice Time Auxiliary space
Activity selection Select the compatible activity that finishes earliest O(n log n) O(n)
Jump Game Track the farthest reachable position O(n) O(1)
Gas station Start where the cumulative fuel balance never becomes negative O(n) O(1)
Fractional knapsack Select items by highest value-to-weight ratio O(n log n) O(n)
Huffman coding Repeatedly merge the two least frequent nodes O(n log n) O(n)

For activity selection, fractional knapsack, and Huffman coding, sorting or priority-queue operations dominate the runtime. If the activity intervals are already sorted by finish time, activity selection can run in O(n) time and O(1) auxiliary space.

Small Example: Activity Selection

Given activities (1, 3), (2, 5), (4, 7), and (6, 9):

  1. Sort by finishing time: (1, 3), (2, 5), (4, 7), (6, 9).

  2. Select (1, 3) because it finishes earliest.

  3. Skip (2, 5) because it overlaps the selected activity.

  4. Select (4, 7) because it starts after activity (1, 3) ends.

  5. Skip (6, 9) because it starts before (4, 7) ends.

The result is (1, 3) and (4, 7). Choosing the earliest-finishing activity is safe because it leaves at least as much time for future activities as any other first choice.

Where Greedy Choice Fails

With coin denominations 1, 3, and 4 and amount 6, choosing the largest coin first produces:

  • 4 + 1 + 1: 3 coins

  • 3 + 3: 2 coins

The greedy result is not optimal because the locally largest coin is not part of every optimal solution. Dynamic programming is more suitable because it considers all reachable remaining amounts.

Similarly, fractional knapsack is solved greedily by value-to-weight ratio, but 0/1 knapsack requires dynamic programming because taking one item prevents taking it again.

Common Pitfalls

  • Assuming local optimality is enough: Every greedy choice needs a greedy-choice or exchange proof.

  • Ignoring sorting costs: An O(n) selection scan may still produce O(n log n) total time because of sorting.

  • Applying greedy to 0/1 constraints: Items that cannot be reused often require dynamic programming or backtracking.

  • Overlooking negative or changing values: Greedy remains valid only if the choice remains safe for every allowed input.

  • Failing to handle ties: When choices have equal immediate value, verify that either choice preserves optimality.

  • Mutating input unnecessarily: Use copies when the original order is needed later.

  • Ignoring integer bounds: In fixed-width languages, check for overflow in accumulated costs or counts.

4

Difference between greedy and heuristic algorithms

Greedy algorithms make locally optimal choices at each step to find a global optimum, whereas heuristic algorithms use practical approximations to find good-enough solutions quickly, often without guarantees of optimality.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Concepts

  • Greedy Algorithm: An algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit. It never reconsiders previous choices.

  • Heuristic Algorithm: A technique designed to solve problems faster than classic algorithms, often by sacrificing completeness or optimality for speed. It is frequently used for NP-hard problems where finding the exact optimal solution is computationally infeasible.

Greedy algorithms rely on a “pick the best now” philosophy. They are deterministic and usually fast. Heuristics can be deterministic or stochastic (randomized) and are often used when the search space is too large for exact methods.

Key Differences

Feature Greedy Algorithm Heuristic Algorithm
Goal Find the exact global optimum Find a “good enough” solution
Optimality Guarantee Yes, if the problem has specific properties No, usually an approximation
Time Complexity Typically O(n log n) or O(n) Varies widely; often polynomial
Backtracking None May use randomization or restarts
Examples Dijkstra, Huffman Coding, Kruskal’s Simulated Annealing, Genetic Algorithms

Greedy Choice and Safety

For a greedy approach to yield an optimal solution, the problem must satisfy two properties: 1. Greedy-Choice Property: A global optimum can be reached by making a locally optimal choice at each step. 2. Optimal Substructure: An optimal solution to the problem contains optimal solutions to its subproblems.

If these properties hold, the greedy strategy is safe. If not, the algorithm may fail.

Counterexample: When Greedy Fails

Consider the Coin Change problem with denominations {1, 3, 4} and a target amount of 6. 1. Greedy Approach: Take the largest coin (4), then two 1s. Total: 4 + 1 + 1 = 3 coins. 2. Optimal Solution: Take two 3s. Total: 3 + 3 = 2 coins.

The greedy choice (4) leads to a suboptimal result because the problem lacks the greedy-choice property for this specific set of coins.

When to Use Which

  • Use Greedy when you can mathematically prove the greedy-choice property and optimal substructure (e.g., Minimum Spanning Tree, Interval Scheduling).

  • Use Heuristic when the problem is too complex for exact methods, or when a near-optimal solution is acceptable within a strict time limit (e.g., Traveling Salesperson Problem, large-scale scheduling).

Common Pitfalls

  • Assuming Greedy Works: Applying a greedy strategy without proving the greedy-choice property is the most common error.

  • Ignoring Complexity: Heuristics can sometimes be slower than expected if not tuned correctly.

  • Confusion: Remember that a greedy algorithm is a specific strategy, while a heuristic is a broader category of “rule of thumb” techniques.

5

How do Greedy, Divide & Conquer, and Dynamic Programming differ?

Greedy, divide and conquer, and dynamic programming are different algorithmic paradigms for finding optimal solutions. Greedy commits to locally best choices, divide and conquer splits a problem into independent subproblems, and dynamic programming solves overlapping subproblems while combining their results.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Differences

Paradigm Problem structure Main technique Typical time complexity Auxiliary space
Greedy Optimal solution can be built through locally optimal choices Make one irreversible, safe choice at each step Problem-dependent; often O(n log n) when sorting dominates Usually O(1) to O(n)
Divide and conquer Problem can be divided into smaller independent subproblems Recursively solve subproblems, then combine them Problem-dependent; merge sort is O(n log n) Often O(log n) recursion stack
Dynamic programming Problem has overlapping subproblems and optimal substructure Store and reuse solutions to states Often O(states × work per state) Often O(states)

Space complexities above exclude the original input unless otherwise stated. The exact complexity of any paradigm depends on the problem’s recurrence, number of states, and transition cost.

Greedy Algorithms

Greedy choice: Select the locally best feasible option at every step.

This is safe when the problem has the greedy-choice property: some optimal solution begins with that choice, and the remaining problem has the optimal substructure needed to complete it.

For example, interval scheduling selects the activity that finishes earliest. An exchange argument proves safety: the earliest-finishing activity leaves at least as much time for later activities as any other first activity, so replacing the first activity in an optimal schedule cannot reduce the number of selected activities.

  • Activity selection: O(n log n) time when sorting by finish time dominates; O(n) time if already sorted.

  • Minimum platforms: Sort arrivals and departures, then reuse a returned platform when possible; O(n log n) time.

  • Huffman coding: Repeatedly combine the two least frequent symbols; O(n log n) time with a min-heap.

  • Fractional knapsack: Select items by decreasing value-to-weight ratio; O(n log n) time after sorting.

Greedy is fastest and often uses little space, but it is applicable only when a local choice can be proved globally optimal.

Divide and Conquer

Divide and conquer divides a problem into smaller subproblems, solves each recursively, and combines their answers. Unlike dynamic programming, the subproblems are usually independent, so their solutions are not repeatedly reused.

For merge sort:

  • T(n) = 2T(n / 2) + O(n), producing O(n log n) time.

  • Auxiliary space is O(n) for temporary arrays, plus O(log n) recursion stack.

  • The original input is not counted in the auxiliary-space figure.

Other examples include binary search, quicksort, and FFT-based multiplication. Complexity varies: binary search takes O(log n) time and O(1) iterative space, while quicksort has O(n log n) average time, O(n²) worst-case time, and O(log n) expected auxiliary stack space.

Dynamic Programming

Dynamic programming is appropriate when a problem contains overlapping subproblems and can be decomposed into an optimal substructure. It stores each computed state and reuses it instead of recalculating it.

Two common forms are:

  • Memoization: Recursively calculate a state once and cache its result.

  • Tabulation: Build solutions iteratively in dependency order.

Examples include Fibonacci, all-pairs shortest paths (Floyd-Warshall), and 0/1 knapsack.

  • Fibonacci with memoization or tabulation: O(n) time and O(n) space, or O(1) space with careful tabulation.

  • 0/1 knapsack: O(nW) time and O(nW) space for a table, where W is capacity; optimized versions can reduce space to O(W).

The recurrence is expressed in words first. For example, the longest common subsequence computes the LCS of two strings by comparing characters and either matching them or skipping one character from either string.

Greedy Failure Example

Unlimited coin change with denominations 1, 3, and 4 demonstrates why greedy is not universally correct:

Approach Coins selected for amount 6 Number of coins
Greedy 4 + 1 + 1 3
Dynamic programming 3 + 3 2

The greedy choice of 4 is locally best because it is the largest usable coin, but it prevents the globally optimal combination. Dynamic programming explores the relevant subproblems and therefore returns 2.

Interview Tips

  • Identify the paradigm first: Look for independent subproblems for divide and conquer, repeated states for dynamic programming, and a provably safe local choice for greedy.

  • Prove greedy correctness: State the greedy choice and support it with an exchange argument or proof of the greedy-choice property.

  • Check complexity sources: Mention O(n log n) explicitly when sorting is the dominant cost.

  • Consider edge cases: Empty input, one element, duplicates, negative values, already sorted data, cycles, and disconnected graphs may affect validity.

  • Avoid assumptions: Greedy is not merely dynamic programming without a table; correctness depends on problem structure.

  • Common follow-up: Interviewers often ask for the recurrence, correctness proof, input mutation behavior, space including recursion stack, and an example where a tempting greedy choice fails.

6

Is Dijkstra’s algorithm greedy or dynamic programming?

Dijkstra’s algorithm is a greedy, label-setting shortest-path algorithm. It repeatedly selects the unsettled vertex with the smallest tentative distance, although its distance labels also resemble the subproblem values used in dynamic programming.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Classification and Greedy Choice

The greedy choice is: always settle the unsettled vertex with the smallest known distance from the source.

Dijkstra is normally classified as greedy because each iteration permanently finalizes the next vertex on a shortest path. It is dynamic-programming-like because it maintains and improves distance labels, but Bellman–Ford is the more conventional dynamic-programming shortest-path algorithm.

How It Works

For each vertex, the algorithm maintains:

  • Tentative distance: The shortest distance found so far from the source.

  • Finalized status: Whether the vertex’s distance is final and its outgoing edges can be relaxed.

  • Priority queue: Unsettled vertices ordered by tentative distance.

Consider directed edges A → B with weight 1, A → C with weight 4, and B → C with weight 2:

  1. Start at A with distance 0; all other distances are infinity.

  2. Settle A, improving B to 1 and C to 4.

  3. Settle B, the smallest unsettled distance, improving C to 1 + 2 = 3.

  4. Settle C; no distances improve.

  5. The final distances are A = 0, B = 1, and C = 3.

Why the Greedy Choice Is Safe

Dijkstra relies on two properties:

  • Greedy-choice property: When the smallest tentative distance is selected, no path through another unsettled vertex can produce a shorter distance, provided all edge weights are nonnegative.

  • Optimal substructure: Every prefix of a shortest path is itself a shortest path to its intermediate vertex.

A direct exchange argument proves the choice. Suppose the selected vertex v had a shorter path. Let y be the first unsettled vertex on that path and x its settled predecessor. When x was processed, relaxing x → y gave y a tentative distance no greater than the path’s prefix length. Nonnegative remaining weights imply that this label is smaller than the label of v, contradicting the fact that v had the smallest tentative distance.

Complexity and Alternatives

For a graph with V vertices and E edges:

  • Best time: O(V) for an edgeless graph because initialization dominates.

  • Average time: O((V + E) log V) under the standard simple-graph binary-heap model; the average and worst asymptotic bounds coincide in the usual analysis.

  • Worst time: O((V + E) log V) for simple graphs because heap operations cost O(log V). With a lazy heap and unrestricted parallel edges, the bound is O((V + E) log(E + 1)).

  • Auxiliary space: O(V) with a decrease-key heap or O(V + E) with a lazy heap, for distance labels and queued entries. There is no recursion stack.

  • Space including the input graph: O(V + E).

Approach Time Auxiliary space When to use
Exhaustive simple-path enumeration O(V! · V) O(V) Tiny graphs or verification
Bellman–Ford O(VE) O(V) Negative edge weights
Dijkstra with decrease-key heap O((V + E) log V) O(V) Nonnegative edge weights
Dijkstra with lazy heap O((V + E) log(E + 1)) O(V + E) Nonnegative weights and simpler heap handling

Dijkstra does not require sorting the graph; heap maintenance is the main source of its O(log V)-per-update cost.

Common Pitfalls and Interview Tips

  • Negative weights: Dijkstra’s correctness guarantee requires nonnegative edge weights. Use Bellman–Ford when a negative edge can affect the result.

  • Stale heap entries: A lazy implementation must skip queued entries whose distance differs from the vertex’s current label.

  • Unreachable vertices: Their distances remain infinity in a disconnected graph.

  • Edge cases: An empty graph has no valid source, so an implementation should define or reject that case explicitly; a one-vertex graph has source distance 0.

  • Parallel edges and cycles: Only strict improvements are relaxed, so parallel edges are handled safely and nonnegative cycles terminate.

  • Input order: Vertex or edge ordering does not change the result; no sorting is required.

  • Mutation and overflow: Do not modify the input unnecessarily, and use a sufficiently wide integer type in other languages for large path sums.

  • Greedy counterexample: For coin change with coins 1, 3, 4 and amount 6, largest-first greedy chooses 4 + 1 + 1, using three coins, while 3 + 3 is optimal with two. Coin change therefore lacks Dijkstra’s greedy-choice property.

7

How can you prove a greedy algorithm produces an optimal solution?

Yes. A greedy algorithm is provably optimal when it satisfies the greedy-choice property and its local choice preserves optimality for the remaining problem. The proof normally uses an exchange argument or induction.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Proof Framework

A complete proof usually establishes these points:

  1. Greedy choice: Define exactly which candidate the algorithm selects at each step.

  2. Greedy-choice property: Show that at least one optimal solution contains that choice.

  3. Exchange argument: Show that an optimal solution can be transformed to include the greedy choice without reducing its value.

  4. Optimal substructure: Show that solving the remaining subproblem optimally, together with the greedy choice, solves the original problem.

  5. Inductive conclusion: Apply the same reasoning repeatedly until no candidates remain.

These properties must be proved for the specific problem. There is no universal theorem stating that every greedy-looking algorithm is optimal.

Exchange-Argument Example

Consider interval scheduling, where the goal is to select the maximum number of non-overlapping activities.

Greedy choice: Select the compatible activity that finishes earliest.

To prove this is safe, let g be the earliest-finishing compatible activity and let o be the first activity in some optimal schedule. Because g finishes earliest:

end(g) <= end(o)

Replace o with g. Every activity following o starts at or after end(o), so it also starts at or after end(g). Therefore, replacing o with g preserves feasibility and does not reduce the number of selected activities.

Thus, some optimal schedule begins with g. The remaining activities form the same scheduling problem over the residual intervals, so induction proves that the entire greedy algorithm is optimal.

Approach Time Space When to use
Brute-force subset enumeration O(n · 2ⁿ) O(n) Small inputs or when proving correctness
Earliest-finish-time greedy O(n log n) O(n) Production interval scheduling

Complexity and Edge Cases

  • Best case: O(n) when activities are already sorted by finish time, because the scan is linear.

  • Average and worst case: O(n log n), because sorting dominates the O(n) scan.

  • Space: O(n), excluding the input, for the sorted copy and selected result.

  • Empty input: Returns an empty set of activities.

  • One activity: Selects it if its interval is valid.

  • Duplicates: Duplicate activities are handled independently.

  • Negative timestamps: Supported, including negative start and end values.

  • Already sorted input: Still correct.

  • Invalid intervals: A start greater than its end is invalid.

  • Graph-specific cases such as disconnected components and cycles do not apply to interval scheduling.

When Greedy Fails

Greedy fails when the locally best choice cannot belong to an optimal solution. For example, with coin denominations {1, 3, 4} and amount 6:

  • Largest-first greedy chooses 4 + 1 + 1, requiring 3 coins.

  • The optimal solution is 3 + 3, requiring 2 coins.

The largest-first algorithm lacks the greedy-choice property. This does not mean coin change always requires dynamic programming, but it does show that the greedy choice must be proved rather than assumed.

Common Pitfalls

  • Incorrect boundary handling: Decide whether activities touching at one endpoint are compatible.

  • Ignoring sorting cost: The scan is O(n), but sorting makes the overall complexity O(n log n).

  • Mutating input: Copy or explicitly document any in-place sorting.

  • Integer overflow: Fixed-width languages need sufficiently large integer types for timestamps and counts.

  • Assuming local optimality is sufficient: Feasibility alone does not prove global optimality.

  • Ignoring ties: Equal finish times may require a secondary ordering rule.

  • Using the wrong data structure: A visited set is relevant to graph traversal, not interval scheduling.

Interviewers commonly ask for the exchange argument, the induction step, the treatment of tied choices, and a counterexample showing where the same greedy strategy would fail.

8

What is the greedy-choice property in greedy algorithms?

The greedy-choice property means that an optimal solution can be made to begin with the choice selected by the greedy algorithm. Combined with optimal substructure, it allows an algorithm to make a locally best decision and then solve the remaining subproblem optimally.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Greedy-Choice Property

A problem has the greedy-choice property when at least one optimal solution contains the element, action, or value selected by the greedy rule.

For example, in activity selection, the greedy choice is to select the compatible activity with the earliest finishing time. There is always an optimal schedule that makes this choice, so selecting it cannot reduce the maximum number of activities that can be completed.

The property has two related parts:

  • Greedy choice: A locally optimal decision can be the first decision of some globally optimal solution.

  • Optimal substructure: After making that decision, the remaining problem has an optimal solution whose combination with the greedy choice produces an overall optimal solution.

Why the Choice Is Safe

Greedy algorithms often justify their choices with an exchange argument:

  1. Begin with an optimal solution.

  2. Show that the greedy choice can replace the solution’s corresponding choice.

  3. Explain that this replacement does not reduce the solution’s quality.

  4. Repeat the argument for the remaining subproblem.

For activity selection, suppose an optimal schedule starts with a later-finishing activity. Replacing it with the earliest-finishing compatible activity cannot prevent any subsequent activity from being scheduled, because the replacement finishes no later. Therefore, an optimal schedule exists that includes the greedy choice.

This reasoning differs from dynamic programming: greedy algorithms do not evaluate and compare multiple candidate subproblems.

Significance and Limitations

The greedy-choice property is significant because it makes a problem solvable through a sequence of irreversible local decisions, often avoiding the larger state space required by dynamic programming.

Approach Time Space, excluding input When to use
Brute-force scheduling O(2ⁿ) O(n) Very small inputs or simple reference implementations
Greedy activity selection O(n log n) O(n) Intervals with compatible, non-overlapping activities
Dynamic programming O(n²) or more O(n) or more Problems where local choices are not provably safe

For activity selection, sorting activities by finish time is the main cost: O(n log n) time and O(n) auxiliary space in the worst case for common sorting implementations. The scan afterward takes O(n) time and O(1) additional space. Total space is O(n) when the auxiliary sorting space is included; the original input is not counted.

Counterexample Where Greedy Fails

The greedy-choice property does not hold for every optimization problem. Consider coin change with denominations 1, 3, and 4 and amount 6:

  • Greedy: Choose 4, leaving 2, then choose 1 twice. Total: 4 + 1 + 1, or 3 coins.

  • Optimal: Choose 3 twice. Total: 3 + 3, or 2 coins.

The locally largest coin prevents the best global result. This problem requires dynamic programming or another strategy unless the denomination system has special properties.

Common Pitfalls

  • Assuming greedy always works: A locally attractive choice is not necessarily part of any optimal solution; the greedy-choice property must be proven.

  • Ignoring the remaining subproblem: A safe first choice is useful only when the remaining instance also has optimal substructure.

  • Forgetting preprocessing costs: Sorting may dominate the runtime, as it does in activity selection at O(n log n).

  • Failing to handle ties correctly: When multiple choices tie, each must preserve compatibility with an optimal solution.

  • Mutating input unexpectedly: In an interview, clarify whether sorting or modifying the original collection is permitted.

  • Common follow-up: Interviewers commonly ask for an exchange argument, a counterexample, or an analysis of preprocessing, scanning, and auxiliary-space costs.

9

How does greedy coin change minimize the number of coins?

For a canonical coin system, greedy coin change repeatedly selects the largest denomination that does not exceed the remaining amount. This produces the minimum number of coins for canonical systems such as standard U.S. denominations, but it is not optimal for arbitrary denomination sets.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Remove duplicate denominations and sort them from largest to smallest.

  2. For each denomination, use as many coins as possible without exceeding the remaining amount.

  3. Continue with the remainder until it reaches zero.

  4. If the amount cannot be represented exactly, report failure.

Using division rather than subtracting one coin at a time makes the denomination scan efficient. Producing the returned coin list still takes time proportional to the number of selected coins.

Greedy Choice and Correctness

The greedy choice is: always use the largest usable denomination first. In a canonical system, the greedy representation of every amount is itself a minimum representation, so selecting that denomination is safe. The remainder is a smaller instance over the same canonical denomination system, where the same property applies recursively; this is the optimal-substructure condition.

Canonicality is stronger than merely including denomination 1. For example, [1, 5, 10, 25] is canonical.

For arbitrary denominations, dynamic programming uses the recurrence:

best[x] = 1 + min(best[x - coin]) over denominations not exceeding x, with best[0] = 0 and unreachable states set to infinity.

Small Example

For denominations [1, 5, 10, 25] and amount 37:

  1. Take 25, leaving 12.

  2. Take 10, leaving 2.

  3. Take two 1 coins, leaving 0.

The result is [25, 10, 1, 1], using four coins.

Code Example

from collections.abc import Sequence


def _validated_denominations(
    coins: Sequence[int], amount: int
) -> list[int]:
    """Validate input and return distinct denominations in descending order."""
    if not isinstance(amount, int) or isinstance(amount, bool) or amount < 0:
        raise ValueError("amount must be a non-negative integer")

    if any(
        not isinstance(coin, int) or isinstance(coin, bool) or coin <= 0
        for coin in coins
    ):
        raise ValueError("coins must contain positive integer denominations")

    return sorted(set(coins), reverse=True)


def greedy_change(coins: Sequence[int], amount: int) -> list[int]:
    """Return greedy change; denominations must form a canonical system."""
    denominations = _validated_denominations(coins, amount)

    if amount == 0:
        return []
    if not denominations:
        raise ValueError("the amount cannot be represented exactly")

    change: list[int] = []
    remaining = amount

    for coin in denominations:
        coin_count = remaining // coin
        for _ in range(coin_count):
            change.append(coin)
        remaining %= coin

        if remaining == 0:
            break

    if remaining != 0:
        raise ValueError("the amount cannot be represented exactly")

    return change


def minimum_coins_exact(coins: Sequence[int], amount: int) -> list[int]:
    """Return a minimum-coin solution for arbitrary positive denominations."""
    denominations = _validated_denominations(coins, amount)

    if amount == 0:
        return []
    if not denominations:
        raise ValueError("the amount cannot be represented exactly")

    unreachable = amount + 1
    best_count = [unreachable] * (amount + 1)
    chosen_coin = [0] * (amount + 1)
    best_count[0] = 0

    for current in range(1, amount + 1):
        for coin in denominations:
            if coin <= current:
                candidate = best_count[current - coin] + 1
                if candidate < best_count[current]:
                    best_count[current] = candidate
                    chosen_coin[current] = coin

    if best_count[amount] == unreachable:
        raise ValueError("the amount cannot be represented exactly")

    result: list[int] = []
    current = amount
    while current > 0:
        coin = chosen_coin[current]
        result.append(coin)
        current -= coin

    result.reverse()
    return result


print(greedy_change([1, 5, 10, 25], 37))
# [25, 10, 1, 1]

print(minimum_coins_exact([1, 3, 4], 6))
# [3, 3]

Complexity and Alternatives

Let n be the number of input values, k the number of unique denominations, A the amount, and C the number of returned coins.

Approach Time Auxiliary space When to use
Greedy O(n + k log k + C) O(k) Canonical denominations
Dynamic programming O(n + k log k + A k) O(A + k) Arbitrary denominations
Brute force O(n + k log k + k^A) for k >= 2; O(n + k log k + A) for k = 1 O(A + k) Very small inputs or conceptual validation

Auxiliary space excludes the input and returned list but includes the denomination copy and, for dynamic programming, its arrays. No recursion is used. Set construction is O(n) on average; adversarial hash collisions can theoretically increase preprocessing to O(n^2).

When all n denominations are distinct, sorting is the main preprocessing cost at O(n log n). With duplicates, preprocessing is O(n + k log k). For greedy, the worst case has C = O(A).

Common Pitfalls

  • Greedy can fail for noncanonical systems: with [1, 3, 4] and amount 6, greedy returns 4 + 1 + 1, while 3 + 3 uses only two coins.

  • Do not use greedy_change unless the denomination system is known to be canonical; the implementation does not test canonicity.

  • Do not assume that including denomination 1 guarantees greedy optimality.

  • Amount 0 requires no coins. Empty denominations are valid only in that case.

  • With one denomination d, exact change exists only when the amount is divisible by d.

  • Duplicate denominations can be removed because they do not change the answer.

  • Reject negative amounts and non-positive denominations.

  • Already sorted input is accepted; sorting a separate copy avoids mutating the caller’s input.

  • Stop only when the remainder equals zero; a negative remainder indicates an off-by-one error.

  • Python integers do not overflow, but fixed-width languages need sufficiently large integer types for amount-based array indices.

  • A common follow-up asks how to detect whether a denomination system is canonical or how to replace greedy selection with dynamic programming.

10

Greedy algorithm for minimum resource event scheduling

A greedy interval-partitioning algorithm schedules events with the fewest resources by processing them in start-time order and reusing an available resource. Its minimum resource count equals the maximum number of events happening simultaneously.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

The Greedy Choice and Why It Is Safe

  • Greedy choice: When an event starts, reuse the resource with the earliest end time if it is free; otherwise, allocate a new resource.

  • Why it is safe: If no resource is free, every allocated resource overlaps the current event at its start time, so every valid schedule needs another resource.

  • Exchange argument: Once resources are free at the current start time, their identities are interchangeable; an optimal schedule’s future assignments can be exchanged without creating conflicts or increasing the resource count.

  • Optimal substructure: After assigning the current event, the remaining events form the same scheduling problem. Together with the overlap lower bound above, this proves the result is optimal.

Complexity

  • Best-case time: O(n), for example when events are already sorted and non-overlapping; Python’s sort detects the sorted run and the heap contains only one end time.

  • Average-case time: O(n log n).

  • Worst-case time: O(n log n). Sorting dominates; each event performs at most one heap removal and one insertion, each costing O(log k) for k allocated resources.

  • Auxiliary space: O(n) in the worst case. The heap uses O(k), and Python 3.12’s sort can use O(n) temporary space. The input itself is not counted, and there is no recursion stack.

Brute Force vs Greedy

Approach Time Space When to use
Exhaustive subset-overlap search O(n 2^n) O(n) Tiny inputs only
Greedy with a min-heap O(n log n) O(n) General event scheduling

Code Example

The example assumes each event requires one resource for its entire half-open interval [start, end).

  1. Sort by start: [[1, 4], [2, 3], [3, 5]].

  2. Event [1, 4]: no resource is available, so allocate one. Heap: [4].

  3. Event [2, 3]: the earliest end 4 is after 2, so allocate another. Heap: [3, 4].

  4. Event [3, 5]: the earliest end 3 is no later than 3, so reuse that resource. Heap: [4, 5].

  5. The result is 2 resources.

import heapq


def min_resources(events: list[list[int]]) -> int:
    """Return the minimum resources needed without mutating events.

    Each event is a [start, end] interval with start < end.
    A resource can handle only one event at a time.
    """
    if not events:
        return 0

    end_times: list[int] = []

    for start, end in sorted(events):
        if end <= start:
            raise ValueError("Each event must have end > start")

        # Reuse the resource that becomes free earliest.
        if end_times and end_times[0] <= start:
            heapq.heappop(end_times)

        heapq.heappush(end_times, end)

    return len(end_times)


# Example: min_resources([[1, 4], [2, 3], [3, 5]])  # Output: 2

Counterexample for Similar Problems

Greedy does not always work. For the coin change problem with denominations {1, 3, 4} and amount 6, the greedy choice 4 + 1 + 1 uses three coins, while the optimal solution 3 + 3 uses only two. This shows that a locally best choice need not produce a globally optimal result.

Common Pitfalls

  • Not sorting by start time: The algorithm depends on chronological processing.

  • Using a max-heap: A min-heap is needed to find the earliest-free resource.

  • Incorrect endpoint handling: A resource ending at start can be reused for an interval starting at start.

  • Invalid intervals: Require end > start; negative timestamps are valid when their ordering is meaningful.

  • Empty input, one event, and duplicates: These are handled naturally; duplicate intervals can overlap and require separate resources when concurrent.

  • Mutating input: sorted(events) leaves the caller’s list unchanged, whereas events.sort() modifies it.

  • Interview follow-up: Be ready to prove that the resource count equals maximum interval overlap and to discuss zero-length or overlapping boundary semantics.

11

How does greedy scheduling minimize total query waiting time?

The shortest-job-first (SJF) greedy strategy minimizes total waiting time by executing the query with the shortest processing time first. This assumes one server, all queries are available initially, and each query’s processing time is known.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Greedy Choice

Treat each query as a job with a processing time (p_i).

  • Sort the queries by increasing processing time.

  • Execute them in that order.

  • A query waits for the total processing time of all queries scheduled before it.

For sorted durations (p_0, p_1, ldots, p_{n-1}), the minimum total waiting time is:

[ sum_{i=0}^{n-1} p_i(n-i-1) ]

Each query’s processing time delays every query scheduled after it.

Why the Choice Is Safe

The greedy-choice property is that the shortest remaining query can always be selected next without worsening the optimal result.

Suppose two adjacent queries have processing times (a > b), but the longer query runs first. Their order contributes (a) waiting time to the second query. Reversing them reduces that waiting time to (b), while the completion time of the pair—and therefore the waiting time of every later query—remains unchanged.

Repeatedly removing these inversions produces the shortest-first order. This exchange argument establishes the greedy choice and the required optimal substructure.

A similar problem demonstrates where SJF fails. If each query has a weight and the objective is weighted waiting time:

Order Weighted waiting time
A first: duration 2, weight 1; B second: duration 3, weight 10 (1(0)+10(2)=20)
B first, then A (10(0)+1(3)=3)

For weighted objectives, sorting by (w_i/p_i) (weight per unit time) in descending order is appropriate instead of sorting only by duration.

Example Walkthrough

For durations [4, 1, 3]:

Step Sorted query Previous processing time Waiting time
1 1 0 0
2 3 1 1
3 4 4 4

The minimum total waiting time is (0+1+4=5).

Complexity

  • Best time: (O(n)) for already sorted input with Python 3.12’s adaptive sort.

  • Average time: (O(nlog n)), dominated by sorting.

  • Worst time: (O(nlog n)).

  • Space: (O(n)) auxiliary space for the sorted copy and sorting workspace; the original input is not counted.

Code Example

from collections.abc import Sequence


def minimize_total_waiting_time(
    query_durations: Sequence[int],
) -> tuple[list[int], int]:
    """Return the shortest-first schedule and minimum total waiting time."""
    ordered_durations = sorted(query_durations)

    if any(duration < 0 for duration in ordered_durations):
        raise ValueError("Query durations must be non-negative.")

    elapsed_time = 0
    total_waiting_time = 0

    for duration in ordered_durations:
        total_waiting_time += elapsed_time
        elapsed_time += duration

    return ordered_durations, total_waiting_time


schedule, total_wait = minimize_total_waiting_time([4, 1, 3])
print(schedule, total_wait)  # [1, 3, 4] 5

Common Pitfalls

  • Empty input: The function returns ([], 0).

  • One query: Its waiting time is zero because it has no predecessor.

  • Duplicate durations: Their relative order does not affect the result.

  • Negative durations: They are invalid and raise ValueError.

  • Already sorted input: The schedule remains unchanged, and Python’s adaptive sort performs best-case work.

  • Different arrival times: The simple static SJF solution no longer directly applies; shortest remaining processing time with preemption is the standard greedy strategy for minimizing total response or flow time.

  • Mutating input: The implementation uses sorted() and leaves the original collection unchanged.

  • Graph-specific cases: Disconnected graphs and cycles are not applicable to this single-server scheduling problem.

12

How can activity selection greedily maximize non-overlapping activities?

The activity selection problem is solved by repeatedly choosing the compatible activity that finishes earliest. This greedy choice leaves as much time as possible for subsequent activities and maximizes their total number.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Represent each activity as a (start, finish) pair. Two activities are compatible when the first one finishes no later than the second one starts, meaning finish <= start.

  1. Sort all activities by increasing finish time.

  2. Select the first activity.

  3. Scan the remaining activities.

  4. Select an activity whenever its start time is at least the finish time of the last selected activity.

  5. Return the selected activities.

The sorting step is the main cost. The scan itself is linear.

Greedy Choice and Correctness

The greedy choice is to select the compatible activity with the earliest finish time.

This choice is safe by an exchange argument: consider any optimal schedule whose first activity is not the greedy activity. Replacing that first activity with the greedy activity is still feasible because the greedy activity finishes no later. Therefore, all later activities in the original schedule remain compatible. Repeating this argument after each selection proves that the greedy schedule is optimal.

Code Example

from typing import TypeAlias

Activity: TypeAlias = tuple[int, int]


def select_max_activities(activities: list[Activity]) -> list[Activity]:
    """Return activities maximizing the number of non-overlapping selections."""
    ordered = sorted(
        activities,
        key=lambda activity: (activity[1], activity[0])
    )

    selected: list[Activity] = []
    last_finish: int | None = None

    for start, finish in ordered:
        if last_finish is None or start >= last_finish:
            selected.append((start, finish))
            last_finish = finish

    return selected


example = [(1, 3), (2, 5), (3, 6), (5, 7), (6, 9)]
print(select_max_activities(example))
# Output: [(1, 3), (3, 6), (6, 9)]

For the corrected example, the activities are considered in finish-time order:

Activity Decision Reason
(1, 3) Select First activity
(2, 5) Skip Starts before the previous activity finishes
(3, 6) Select Starts exactly when (1, 3) finishes
(5, 7) Skip Starts before (3, 6) finishes
(6, 9) Select Starts exactly when (3, 6) finishes

The result contains three activities.

Complexity

Approach Time Space When to use
Brute-force subset enumeration O(n · 2^n) O(n) Small inputs or problems without a greedy structure
Earliest-finish greedy O(n log n) O(n) Activity selection and interval scheduling

For the greedy algorithm:

  • Time: O(n log n) in the best, average, and worst cases. Sorting costs O(n log n), and the scan costs O(n).

  • Space: O(n) auxiliary space for the sorted copy and selected result, excluding the original input. The implementation is iterative, so it uses O(1) recursion-stack space.

Edge Cases and Counterexample

  • Empty input: Returns an empty list.

  • One activity: Selects that activity.

  • Already sorted input: Still works because the function explicitly sorts.

  • Duplicate activities: Selects only compatible activities according to the finish-time rule.

  • Negative or arbitrary numeric times: Works as long as start and finish times are ordered appropriately.

  • Equal boundary times: Activities are compatible when previous_finish <= next_start.

The earliest-finish strategy does not work for every optimization problem. For example, in 0/1 coin change with coins {1, 3, 4} and amount 6, choosing the largest coin first gives 4 + 1 + 1 using three coins, while 3 + 3 uses only two. Activity selection succeeds because replacing an activity with an earlier-finishing one cannot harm future choices.

Common Pitfalls

  • Sorting by start time instead of finish time.

  • Using start > previous_finish when the problem defines touching activities as compatible.

  • Mutating the caller’s input list.

  • Forgetting to update last_finish after selecting an activity.

  • Assuming the greedy algorithm applies to unrelated problems such as 0/1 knapsack.

13

How do you prove a greedy algorithm is correct?

Proving a greedy algorithm is correct requires showing that making the locally optimal choice at each step leads to a globally optimal solution. This rests on two pillars: the greedy-choice property (a globally optimal solution can start with the greedy choice) and optimal substructure (an optimal solution contains optimal solutions to subproblems). The most common proof techniques are an exchange argument, a greedy-stays-ahead argument, or a matroid-based proof when the problem fits that structure.

Read full answer

Applies tolanguage-independent

Core Properties

  • Greedy-choice property: There exists an optimal solution that begins with the greedy choice. To prove it, assume an optimal solution exists that does not start with the greedy choice, then show how to modify it to include the greedy choice without worsening the objective (exchange argument).

  • Optimal substructure: After making the greedy choice, the remaining problem is a smaller instance of the same problem, and an optimal solution to the original must contain an optimal solution to this subproblem. If the subproblem were solved suboptimally, swapping in its optimal solution would improve the overall result, contradicting optimality.

Proof Techniques

  • Exchange argument (standard for greedy-choice property):

  • Let G be the greedy solution and O an optimal solution.

  • Find the first index k where G and O differ.

  • Show the greedy choice at step k can replace the choice in O without increasing cost (or decreasing value).

  • The modified O' is still optimal and agrees with G for one more step.

  • By induction, G is optimal.

  • Greedy-stays-ahead (used for incremental construction like activity selection or Huffman coding): Prove by induction that after each step the greedy partial solution is at least as good as any other partial solution of the same size. If the algorithm finishes, its complete solution is optimal.

Counterexamples Where Greedy Fails

  • 0/1 knapsack: Items (value, weight) = (60,10), (100,20), (120,30), capacity 50. Greedy by value/weight picks first two (value 160), but optimal picks last two (value 220). Fractional knapsack works greedily because items are divisible.

  • Coin change with denominations {1, 3, 4} and amount 6: Greedy picks 4+1+1 (3 coins), optimal is 3+3 (2 coins).

Common Patterns and Complexity

Problem Type Typical Greedy Choice Proof Technique
Activity selection / interval scheduling Earliest finish time Exchange / greedy-stays-ahead
Huffman coding Merge two lowest-frequency nodes Exchange argument
Fractional knapsack Highest value/weight ratio Greedy-choice + optimal substructure
Minimum spanning tree (Kruskal/Prim) Lightest edge crossing a cut Cut property (exchange)
Dijkstra (shortest path) Closest unvisited vertex Greedy-stays-ahead

Sorting is often the dominant cost (e.g., sorting intervals by end time, edges by weight). Overall time complexity is typically O(n log n) from sorting plus linear/near-linear processing. Space complexity is usually O(n) for sorted arrays or priority queues, not counting the input.

Pitfalls and Interview Tips

  • Assuming greedy works without proof: Many problems look greedy but aren’t (0/1 knapsack, coin change with arbitrary denominations, longest path).

  • Confusing optimal substructure with greedy-choice property: Both are needed; optimal substructure alone only guarantees DP works.

  • Ignoring ties: The proof must hold for any tie-breaking rule, or specify a deterministic tie-break and prove it works.

  • Forgetting the base case: Inductive proofs need a valid base case (e.g., empty solution, first step).

  • Interview tips: State the greedy choice in one sentence, explain why it’s safe via exchange argument, mention optimal substructure explicitly, be ready with a counterexample, note when sorting is the bottleneck (O(n log n)), and anticipate follow-ups like “Can this be solved with DP?” or “What if input is already sorted?”.

14

Why do greedy algorithms often sort their input first?

Sorting is often preprocessing that exposes the priority needed by a greedy algorithm. It lets the algorithm select the locally best candidate in a predictable order, usually followed by a linear scan, instead of repeatedly searching or evaluating many alternatives.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why Sorting Matters

Many greedy problems define a choice in terms of an ordering:

  • Activity selection: choose the compatible activity that finishes earliest.

  • Interval merging: sort intervals by start time before merging overlaps.

  • Fractional knapsack: sort items by decreasing value-to-weight ratio.

  • Task scheduling: sort by deadlines, execution time, or priority, depending on the variant.

  • Huffman coding: repeatedly select the two lowest-frequency nodes using a min-heap.

After sorting, the greedy algorithm can usually process candidates once. Sorting is not inherently part of greedy reasoning; it is a way to make the required greedy choice efficient.

Why the Greedy Choice Is Safe

For activity selection, the greedy choice is to select the remaining compatible activity with the earliest finishing time. This is safe by an exchange argument: replacing the first activity in an optimal schedule with the earliest-finishing activity leaves at least as much time for subsequent activities. The remaining problem then has the same structure, demonstrating optimal substructure.

Sorting alone does not prove correctness. Each greedy problem needs its own greedy-choice property and optimal-substructure argument.

A similar greedy strategy can fail for 0/1 knapsack. With capacity 10 and items (weight, value) = (6, 12), (5, 9), (5, 9), sorting by value-to-weight ratio selects the first item for value 12. The optimal solution selects the other two items for value 18. Fractional knapsack permits the ratio-based greedy solution; 0/1 knapsack requires dynamic programming.

Complexity

For n activities, Python 3.12 uses Timsort for sorted():

Approach Time Auxiliary space When to use
Exhaustive subset search O(2^n) best/average/worst O(n) recursion stack Tiny validation sets
Sort by finish time, then greedy scan O(n log n) average/worst; O(n) best for sorted input O(n) Typical solution
Greedy scan on guaranteed presorted input O(n) O(1), excluding the result Presorted input only

The post-sort greedy scan is O(n) in all cases. Input storage is not counted in auxiliary space; the returned result adds O(k) space for k selected items. No recursion stack is used by the greedy scan. Sorting is often the dominant O(n log n) cost.

Example Walkthrough

For half-open intervals [start, end), activities that touch at an endpoint do not overlap:

  1. Given A(0, 3), B(1, 4), C(3, 6), and D(6, 9), sorting by finish time gives A, B, C, D.

  2. Select A, which ends at time 3.

  3. Skip B because it starts before time 3.

  4. Select C because it starts at time 3.

  5. Select D because it starts at time 6.

The selected schedule is A, C, D.

Common Pitfalls and Interview Tips

  • Wrong sort key: The ordering must match the greedy rule; sorting by start time alone is incorrect for activity selection.

  • Off-by-one or endpoint errors: Clearly define whether intervals touching at an endpoint conflict and compare start and end values consistently.

  • Integer overflow: Ratio comparisons using cross multiplication can overflow in fixed-width languages unless values are widened or compared carefully.

  • Mutating input: Use a non-mutating sort when the caller’s original order must be preserved.

  • Forgetting visited state: In greedy traversals over graphs, maintain a visited set to avoid cycles and repeated processing.

  • Assuming sorting proves correctness: A greedy-choice and optimal-substructure argument is still required.

  • Unnecessary full sorting: A heap may be better when only the next minimum or maximum is needed.

  • Common follow-up: Interviewers may ask why the chosen sort key is correct, how you would prove the greedy choice, and how the solution changes when the input is already sorted.

15

How can a greedy algorithm solve an optimization problem?

Greedy algorithms can solve optimization problems when a locally best choice can be proven safe for the global objective. They repeatedly select the best available option, but this works only when the problem has an appropriate greedy-choice property and optimal substructure.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Greedy Choice and Why It Is Safe

A greedy solution relies on two properties:

  • Greedy-choice property: At each step, some optimal solution contains the locally best choice.

  • Optimal substructure: An optimal solution contains an optimal solution for each relevant remaining subproblem.

The local choice must therefore be safe for the entire objective. Greedy algorithms are especially effective for activity selection, interval scheduling, task scheduling, and problems such as fractional knapsack where the objective and exchange argument clearly support the choice.

Example: Activity Selection

Suppose each activity has a start time and finish time, and the goal is to select the maximum number of non-overlapping activities.

The greedy choice is:

Select the compatible activity with the earliest finish time.

This is safe by an exchange argument: replace the first activity in an optimal schedule with the earliest-finishing activity. Because the replacement finishes no later, every later activity remains compatible. Repeating this argument proves that the greedy schedule is optimal.

Activities are treated as half-open intervals [start, finish), with start < finish. Therefore, an activity may start exactly when the previous one finishes.

For the activities below:

Activity Start Finish
A 1 3
B 2 5
C 3 7
D 4 8
E 6 9
  1. Select A, which finishes first at time 3.

  2. Reject B because it starts at 2.

  3. Select C because it starts at 3.

  4. Reject D because it starts at 4.

  5. Select E because it starts at 6.

The result is A, C, and E—a maximum of three activities.

Approach Best Time Average Time Worst Time Auxiliary Space When to Use
Exhaustive subset enumeration O(n · 2ⁿ) O(n · 2ⁿ) O(n · 2ⁿ) O(n) Tiny inputs or validation
Earliest-finish greedy algorithm O(n) O(n log n) O(n log n) O(n) General activity selection
  • Time: The scan is O(n). In Python 3.12, Timsort used by sorted takes O(n) when the input is already sorted by its key and O(n log n) on average and in the worst case. Sorting is the dominant cost; a generic comparison sort gives O(n log n) in all cases.

  • Space: O(n) auxiliary space for the sorted copy, including any internal stack; the result uses O(k) space for k selected activities. The recursive stack for the greedy scan is O(1). The input is excluded from auxiliary space; total storage is O(n).

  • Edge cases: Empty input returns an empty result; one activity is selected; duplicate positive-duration activities cannot all be selected; negative timestamps are valid; zero-duration and reversed intervals are rejected; already sorted input exercises the O(n) sorting best case. Disconnected graphs and cycles are not applicable to this interval problem.

When Greedy Fails

Greedy choices are not universally safe. For minimum-coin change with an unlimited supply of coins 1, 3, and 4 and amount 6:

  • Largest-coin-first selects 4 + 1 + 1, producing three coins.

  • The optimum is 3 + 3, producing two coins.

This is coin change with unlimited copies, not 0/1 knapsack; the optimal solution reuses denomination 3. The failure occurs because choosing the largest coin first prevents a better combination.

Code Example

def select_activities(
    intervals: list[tuple[int, int]],
) -> list[tuple[int, int]]:
    """Return a maximum set of compatible half-open activities."""
    for start, finish in intervals:
        if start >= finish:
            raise ValueError("Each activity must satisfy start < finish")

    # Sort by earliest finish time without mutating the caller's list.
    ordered = sorted(intervals, key=lambda interval: (interval[1], interval[0]))

    selected: list[tuple[int, int]] = []
    last_finish: int | None = None

    for start, finish in ordered:
        if last_finish is None or start >= last_finish:
            selected.append((start, finish))
            last_finish = finish

    return selected


activities = [(1, 3), (2, 5), (3, 7), (4, 8), (6, 9)]
print(select_activities(activities))
# [(1, 3), (3, 7), (6, 9)]

Common Pitfalls

  • Assuming every optimization problem supports a greedy solution without an exchange argument.

  • Ignoring the sorting cost or failing to distinguish the scan’s O(n) cost from the total complexity.

  • Using start > last_finish instead of start >= last_finish when endpoint-sharing activities are allowed.

  • Forgetting integer overflow in languages with fixed-width integers when computing finish times.

  • Mutating the input unnecessarily; sorting a copy preserves the caller’s data.

  • Forgetting a visited set in a graph-based reformulation, where cycles and disconnected components can occur.

  • Expecting interviewers to ask for the proof, edge cases, or how the algorithm changes when maximizing profit rather than activity count.

16

How do you solve fractional knapsack with a greedy method?

Fractional knapsack maximizes total value when items can be divided and each item may contribute any fraction between zero and one. The optimal approach sorts items by decreasing value-to-weight ratio and takes each item until the capacity is exhausted.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For each item, calculate its value density:

[ text{ratio}_i = frac{text{value}_i}{text{weight}_i} ]

Then:

  1. Sort items by decreasing ratio.

  2. Take the entire highest-ratio item if it fits.

  3. Otherwise, take the fraction that fills the remaining capacity.

  4. Stop when no capacity remains.

For example, with values [60, 100, 120], weights [10, 20, 30], and capacity 50:

  • Ratios are 6, 5, and 4.

  • Take all of item 0: value 60, weight 10.

  • Take all of item 1: value 100, weight 20.

  • Take 20/30 of item 2: value 80.

  • Total value is 60 + 100 + 80 = 220.

Greedy Choice and Correctness

Greedy choice: Always take the remaining item with the greatest value-to-weight ratio.

This is safe because fractional items can be exchanged freely. If an optimal solution uses capacity on a lower-ratio item while leaving capacity available for a higher-ratio item, replacing some of the lower-ratio portion with the higher-ratio item cannot decrease the total value. Repeating this exchange produces an optimal solution that agrees with every greedy choice.

This proof depends on items being divisible. The same greedy algorithm is not generally correct for 0/1 knapsack, where an item must be taken completely or not at all.

For example, with the values and weights above but a 0/1 constraint, ratio-based greedy selects items 0 and 1 for value 160, while the optimal selection is items 1 and 2 for value 220.

Algorithm Comparison

Approach Time Space When to use
Fractional greedy O(n log n) O(n) auxiliary Items may be split
Exhaustive subset enumeration for 0/1 O(n 2^n) O(n) Very small 0/1 instances
0/1 knapsack dynamic programming O(nW) O(W) Items cannot be split, where W is capacity

Complexity

  • Best time: O(n) when the items are already sorted by value-to-weight ratio, because Python’s adaptive sort detects sorted runs; otherwise O(n log n).

  • Average time: O(n log n), dominated by sorting the ratios.

  • Worst time: O(n log n), also dominated by sorting.

  • Space: O(n) auxiliary space for the sorted indices and selected fractions. The input arrays are not counted, and there is no recursion stack.

The sorting step is the main cost; scanning the sorted items takes O(n).

Code Example

from math import isfinite


def fractional_knapsack(
    values: list[float],
    weights: list[float],
    capacity: float,
) -> tuple[float, list[tuple[int, float]]]:
    """Return maximum value and selected (item index, fraction) pairs."""
    if len(values) != len(weights):
        raise ValueError("values and weights must have the same length")

    if not isfinite(capacity) or capacity < 0:
        raise ValueError("capacity must be finite and non-negative")

    if any(not isfinite(value) or value < 0 for value in values):
        raise ValueError("values must be finite and non-negative")

    if any(not isfinite(weight) or weight <= 0 for weight in weights):
        raise ValueError("weights must be finite and strictly positive")

    if not values or capacity == 0:
        return 0.0, []

    order = sorted(
        range(len(values)),
        key=lambda index: values[index] / weights[index],
        reverse=True,
    )

    selected: list[tuple[int, float]] = []
    remaining_capacity = capacity
    total_value = 0.0

    for index in order:
        if remaining_capacity <= 0:
            break

        taken_weight = min(weights[index], remaining_capacity)
        taken_fraction = taken_weight / weights[index]

        selected.append((index, taken_fraction))
        total_value += values[index] * taken_fraction
        remaining_capacity -= taken_weight

    return total_value, selected


values = [60.0, 100.0, 120.0]
weights = [10.0, 20.0, 30.0]
capacity = 50.0

result = fractional_knapsack(values, weights, capacity)
print(result)
# Expected: (220.0, [(0, 1.0), (1, 1.0), (2, 0.6666666666666666)])

Common Pitfalls

  • Zero or negative weights: Division by zero is invalid; the implementation requires strictly positive weights.

  • Negative values or capacity: These are rejected because they do not represent a standard fractional-knapsack instance.

  • Empty input or zero capacity: The function returns (0.0, []).

  • Duplicate items: Each item keeps its original index, so duplicates are handled independently.

  • Mutating the input: The implementation sorts indices rather than rearranging the caller’s arrays.

  • Floating-point precision: For monetary values, use Decimal or integer-scaled units instead of float.

  • Applying fractional greedy to 0/1 knapsack: The exchange argument depends on divisibility; use dynamic programming for 0/1 constraints.

Interviewers commonly follow up by asking why the greedy choice is optimal, how the algorithm changes for indivisible items, or how to avoid floating-point rounding errors.

17

How does greedy interval partitioning minimize the number of rooms?

The minimum-room interval partitioning problem is solved by sorting intervals by start time and reusing a room whenever its previous interval has finished. A new room is required only when every existing room is occupied.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Greedy Choice and Why It Works

Greedy choice: At each interval’s start time, reuse any room whose previous interval has ended; otherwise, allocate a new room.

This choice is safe because:

  • Intervals that are active at the same time require different rooms.

  • If a room is available, assigning the interval to it cannot harm future assignments—the room’s identity does not affect future availability.

  • If no room is available, the current overlap requires an additional room regardless of how previous intervals were assigned.

Thus, the algorithm uses exactly the maximum number of simultaneously active intervals, which is both a lower bound and an achievable room count. This demonstrates the greedy-choice property and optimal substructure.

Not every interval strategy works. For example, when selecting the maximum number of non-overlapping intervals, choosing the earliest-starting interval can fail. Given (0, 10), (1, 2), and (3, 4), choosing by start time selects only one interval, while choosing by earliest finish time selects two.

Walkthrough

For half-open intervals [start, end), consider:

[(1, 3), (2, 4), (3, 5), (6, 7)]

  1. At 1, no room is free, so create room 0.

  2. At 2, room 0 is occupied, so create room 1.

  3. At 3, room 0 is free because its interval ended at 3; reuse it.

  4. At 6, room 1 is free; reuse it.

The minimum is two rooms.

Complexity

Let n be the number of intervals.

  • Best case: O(n) when intervals are already sorted and do not overlap; Python 3.12’s sort is linear for sorted input, and the heap contains only one room.

  • Average case: O(n log n) because sorting dominates.

  • Worst case: O(n log n) because sorting and heap operations both require at most O(log n) per interval.

  • Auxiliary space: O(n) for the sorted copy and heap. The original input is not counted, the recursion stack is O(1), and the returned assignments also use O(n) space.

Approach Time Space When to use
Greedy start-time sweep with a min-heap O(n log n) O(n) Standard solution for production and interviews
Exhaustive maximum-overlap search over all subsets O(n · 2^n) O(n) Tiny inputs or cross-checking the greedy result

Sorting by start time is the main O(n log n) cost.

Code Example

from heapq import heappop, heappush


def assign_rooms(
    intervals: list[tuple[int, int]],
) -> tuple[int, list[list[tuple[int, int]]]]:
    """Assign half-open intervals [start, end) to the minimum number of rooms."""
    if any(start >= end for start, end in intervals):
        raise ValueError("Each interval must satisfy start < end")

    sorted_intervals = sorted(intervals, key=lambda interval: interval[0])

    # Each heap entry is (end_time, room_id).
    room_ends: list[tuple[int, int]] = []
    room_assignments: list[list[tuple[int, int]]] = []

    for start, end in sorted_intervals:
        if room_ends and room_ends[0][0] <= start:
            # Reuse the room that has been free the longest.
            _, room_id = heappop(room_ends)
        else:
            # Every existing room is still occupied.
            room_id = len(room_assignments)
            room_assignments.append([])

        room_assignments[room_id].append((start, end))
        heappush(room_ends, (end, room_id))

    return len(room_assignments), room_assignments


rooms = assign_rooms([(1, 3), (2, 4), (3, 5), (6, 7)])
print(rooms)
# Output: (2, [[(1, 3), (3, 5)], [(2, 4), (6, 7)]])

Common Pitfalls and Interview Tips

  • Endpoint convention: The code treats intervals as half-open [start, end), so an interval ending at 3 can share a room with one starting at 3. For closed intervals, change the reuse condition from <= to <.

  • Empty input: The function returns (0, []).

  • One interval: One valid interval requires exactly one room.

  • Duplicate intervals: Overlapping duplicates receive separate rooms.

  • Negative timestamps: They work normally because the algorithm depends only on ordering.

  • Already sorted input: It is copied rather than modified in place.

  • Zero-length intervals: They are rejected because [start, start) is empty. If an application treats an instantaneous event as resource-consuming, it should model that behavior explicitly.

  • Other languages: Python integers do not overflow, but timestamps in fixed-width languages must fit the selected integer type.

  • Typical follow-up: Explain why the result equals the maximum number of intervals overlapping at any point, and how the algorithm changes for closed intervals.

18

How can greedy algorithms minimize railway station platforms?

Minimum platform allocation is achieved by processing trains in arrival order and reusing a platform as soon as its previous train departs. The minimum number of platforms equals the maximum number of trains simultaneously present at the station.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Greedy Choice and Optimality

The greedy choice is: always reuse a platform whose train has departed before the current train arrives.

This choice is safe because platforms are interchangeable. An optimal allocation that leaves a free platform unused while assigning an arriving train to another platform can be adjusted without increasing the platform count. This is the greedy-choice property; after each arrival, only currently active trains affect the remaining requirement, giving optimal substructure.

Treat each train as a half-open interval [arrival, departure). Therefore, a train departing at time t frees its platform for another train arriving at time t.

Algorithm and Walkthrough

  1. Pair each arrival with its departure and sort the trains by arrival time.

  2. Maintain a min-heap containing the departure times of trains currently occupying platforms.

  3. Before processing an arrival, remove every departure less than or equal to that arrival.

  4. Add the new train to the heap.

  5. Track the maximum heap size, which is the minimum number of platforms required.

For arrivals [900, 940, 950, 1100, 1120, 1200] and departures [910, 1120, 1130, 1160, 1200, 1300]:

Arrival Departures removed Active trains Maximum so far
900 0 1 1
940 1 1 1
950 0 2 2
1100 0 3 3
1120 1 3 3
1200 3 1 3

Three platforms are necessary when the trains arriving at 1100 are all present.

Complexity

For n trains:

  • Best, average and worst-case time: O(n log n). Sorting takes O(n log n), and at most n heap insertions and removals add O(n log n) in total.

  • Auxiliary space: O(n) for the sorted train list and heap, excluding the input. Including the input, total space is O(n). No recursion stack is used.

Approach Time Extra space When to use
Compare every pair of trains O(n²) O(1) Small inputs or conceptual verification
Sorted sweep with a heap O(n log n) O(n) General railway platform allocation

Edge Cases

  • Empty input: Returns 0.

  • One train: Returns 1 when its departure is later than its arrival.

  • Duplicate arrivals or departures: Handled naturally by the heap.

  • Negative timestamps: Supported because the algorithm only compares times.

  • Already sorted input: Correct, although sorting still determines the overall complexity.

  • Invalid intervals: A departure equal to or earlier than its arrival is rejected.

  • Disconnected graphs or cycles: Not applicable because the problem models independent intervals.

Code Example

import heapq


def minimum_platforms(arrivals: list[int], departures: list[int]) -> int:
    """Return the minimum platforms required for the train intervals."""
    if len(arrivals) != len(departures):
        raise ValueError("Each arrival must have exactly one departure.")

    for arrival, departure in zip(arrivals, departures):
        if departure <= arrival:
            raise ValueError("Each departure must be later than its arrival.")

    trains = sorted(zip(arrivals, departures), key=lambda train: train[0])
    active_departures: list[int] = []
    maximum_platforms = 0

    for arrival, departure in trains:
        # A platform becomes reusable when its train departs.
        while active_departures and active_departures[0] <= arrival:
            heapq.heappop(active_departures)

        heapq.heappush(active_departures, departure)
        maximum_platforms = max(maximum_platforms, len(active_departures))

    return maximum_platforms


if __name__ == "__main__":
    result = minimum_platforms(
        [900, 940, 950, 1100, 1120, 1200],
        [910, 1120, 1130, 1160, 1200, 1300],
    )
    print(result)  # 3

Common Pitfalls

  • Tie handling: The code allows a platform to be reused when one train departs exactly when another arrives. Change <= to < if station policy requires a buffer.

  • Incorrect counting: Do not simply subtract all departures from all arrivals; each departure belongs to a specific train.

  • Mutating input: This implementation sorts a new list, preserving the caller’s data.

  • Similar greedy failure: For coin change with coins 1, 3, 4 and amount 6, choosing the largest coin gives 4 + 1 + 1 for three coins, while 3 + 3 needs only two. A greedy strategy is therefore valid only when the problem has the required optimality properties.

  • Typical follow-up: Interviewers may ask you to return the actual platform assignment, handle delayed trains, or adapt the algorithm when platform capacities differ.

19

When do greedy algorithms fail to produce optimal results?

A greedy algorithm fails when the greedy-choice property does not hold, meaning a locally optimal choice prevents the globally optimal solution. This typically occurs when the problem lacks optimal substructure or when making a choice restricts future possibilities in a way that blocks the best path. In these cases, dynamic programming or brute force is required.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why Greedy Fails

Greedy algorithms make the best local choice at each step with the hope of finding a global optimum. They work only if two conditions are met: - Greedy-choice property: A global optimum can be reached by making a local optimum. - Optimal substructure: An optimal solution to the problem contains optimal solutions to subproblems. When either condition is violated, the algorithm makes a short-sighted decision that leads to a suboptimal result. For example, in the 0/1 Knapsack problem, taking the item with the highest value-to-weight ratio might fill the knapsack inefficiently, leaving space that could have held a better combination of items.

Classic Counterexamples

Problem Greedy Strategy Why It Fails
Coin Change (1,3,4) Largest coin first Blocks optimal 3+3
0/1 Knapsack Highest value/weight Cannot fill space efficiently
Dijkstra Shortest edge first Negative weights break logic
  • Coin Change: With coins {1, 3, 4} and amount 6, the greedy choice is 4 + 1 + 1 (3 coins), but the optimal solution is 3 + 3 (2 coins).

  • 0/1 Knapsack: Greedy by value-to-weight ratio fails because you cannot take fractions of items. The fractional knapsack problem, however, allows fractions and is solved optimally by greedy.

  • Graph Algorithms: Dijkstra’s algorithm fails with negative edge weights because a shorter path might be discovered later.

How to Verify Greedy Correctness

Before using a greedy strategy, prove it using an exchange argument. Show that any optimal solution can be transformed into the greedy solution without increasing cost. If the exchange argument fails, the greedy choice is unsafe. This is the standard proof technique for greedy correctness.

Interview Tips

  • Always check if the problem allows optimal substructure before choosing greedy.

  • If the greedy choice blocks future options, use dynamic programming instead.

  • Be ready to provide a counterexample to disprove a greedy claim, such as the coin change case above.

  • Note that sorting is often the main cost in greedy solutions, taking O(n log n).

  • Distinguish between 0/1 and fractional versions of problems, as greedy only works for the latter.

  • Typical greedy problems include activity selection, Huffman coding, and fractional knapsack.

20

Greedy vs. brute-force efficiency for the traveling salesman problem

For the traveling salesman problem, a greedy nearest-neighbor heuristic constructs a tour in (O(n^2)) time but does not guarantee the minimum cost, while a brute-force permutation search finds the optimal tour in (O(n cdot n!)) time. Greedy is therefore much faster, whereas brute force is exact.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Efficiency Comparison

Let (n) be the number of cities.

Approach Time complexity Space complexity Guarantee
Greedy nearest neighbor (O(n^2)) best, average, and worst (O(n)) auxiliary; (O(n^2)) total if an input distance matrix is counted Produces a tour, but not necessarily an optimal one
Brute-force permutations (O(n cdot n!)) best, average, and worst (O(n)) auxiliary, including recursion; (O(n^2)) total with an input distance matrix Always finds the optimal tour
Held–Karp dynamic programming (O(n^2 2^n)) (O(n 2^n)) auxiliary Exact and faster than brute force for medium-sized inputs

The greedy algorithm visits cities by repeatedly selecting the closest unvisited city. At each step, it checks up to (n) candidates, and it performs roughly (n) such steps, giving (O(n^2)) time.

Brute force generates every possible ordering and evaluates the cost of each tour in (O(n)) time. Fixing one starting city and treating reversed tours as equivalent in an undirected graph reduces the constant factor by half, but it does not change the factorial complexity.

Greedy Choice and Correctness

The greedy choice is to select the cheapest edge from the current city to an unvisited city.

This choice is not safe for optimal TSP. The traveling salesman problem does not have the greedy-choice property required to prove that a locally cheapest edge can always appear in an optimal tour. Selecting an edge also affects which cities remain available and may force an expensive closing edge back to the start. Consequently, there is no general exchange argument proving nearest-neighbor optimality.

Brute force avoids this problem by considering every possible ordering, so it preserves all alternatives and is guaranteed to find the minimum-cost Hamiltonian cycle.

Counterexample

Consider this symmetric metric distance matrix, with A as the starting city:

City A B C D E
A 0 101 200 102 200
B 101 0 101 200 200
C 200 101 0 101 102
D 102 200 101 0 101
E 200 200 102 101 0

Nearest neighbor produces:

  1. A → B, cost 101

  2. B → C, cost 101

  3. C → D, cost 101

  4. D → E, cost 101

  5. E → A, cost 200

Its total cost is 604. However, the optimal tour is A → B → C → E → D → A, with cost:

101 + 101 + 102 + 101 + 102 = 507

Thus, greedy takes (O(n^2)) time but can return a tour (97) units more expensive than the optimum.

Common Pitfalls

  • Calling the greedy result optimal: Nearest neighbor is a heuristic, unlike brute force or Held–Karp.

  • Ignoring input storage: An (O(n^2)) distance matrix changes total space usage even when the algorithm needs only (O(n)) additional space.

  • Assuming every greedy TSP implementation works: If the graph is incomplete, nearest neighbor may become stuck and fail to produce a tour.

  • Using brute force too long: For moderate (n), Held–Karp is usually preferable because it remains exact while avoiding factorial enumeration.

  • Typical follow-up: Interviewers often ask for a counterexample, a proof that brute force is correct, or an exact algorithm such as Held–Karp that improves on permutation enumeration.

21

What is Huffman Coding, and why is it greedy?

Huffman coding builds an optimal binary prefix code for symbols based on their frequencies. It is a greedy algorithm because each step combines the two least frequent symbols or subtrees into a single subtree.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Greedy Choice and Why It Is Safe

The greedy choice is to repeatedly merge the two items with the smallest frequencies.

An exchange argument shows that an optimal prefix-code tree can place the two least frequent symbols at two deepest sibling leaves without increasing the weighted path length. Swapping a less frequent symbol into a deeper position cannot increase the cost when the more frequent symbol moves to the shallower position.

Contracting those siblings into one symbol whose frequency is their sum reduces the problem to a smaller instance of the same problem. The total cost of the contracted tree differs from the original by only the combined frequency of the two siblings. Thus, choosing the two smallest items is safe, and recursively solving the contracted problem yields an optimal code—an instance of optimal substructure.

How the Algorithm Works

  1. Count the frequency of each symbol.

  2. Insert the symbols into a min-heap ordered by frequency.

  3. Remove the two items with the smallest frequencies.

  4. Merge them into a parent node whose frequency is their sum.

  5. Insert the parent node into the heap and repeat until only the root remains.

  6. Assign 0 and 1 to the two edges of each internal node and read the codewords from the root to the leaves.

The resulting code is prefix-free: no symbol’s code is a prefix of another symbol’s code. A decoder follows one bit at a time from the root and stops when it reaches a leaf.

Worked Example

For aab:

Step Tree or heap state
Count symbols a = 2, b = 1
First merge Merge b and a into a node with frequency 3
Second merge The node becomes the root with frequency 3
Assign bits b = 0, a = 1
Encode aab 1 + 1 + 0 = 110

Complexity and Comparison

Let n be the number of distinct symbols, L the input length, M the number of encoded output bits, and K the sum of all generated codeword lengths.

  • Construction time: Given the frequencies, O(n log n) in the best, average, and worst cases. There are n - 1 merges, and each heap operation costs O(log n).

  • Frequency counting: O(L) on average with a hash table; a pathological hash-table worst case is O(Ln).

  • Encoding time: O(L + M), including looking up each codeword and writing its bits.

  • Working space: O(n) for the heap and tree, excluding the input and returned representations.

  • Output storage: An explicit codebook requires O(K) space, which can be O(n²) in the worst case, and the encoded output requires O(M) space.

The dominant construction cost is heap maintenance at O(n log n); the algorithm does not require a separate sort.

Approach Time Space When to use
Exhaustive full-tree search O(n · n! · 4^n) coarse upper bound O(n) per candidate Only for very small alphabets
Huffman coding O(n log n) construction O(n) working space General symbol-by-symbol binary prefix coding

Common Pitfalls and Interview Tips

  • Empty input: There are no symbols and therefore no codewords.

  • One distinct symbol: Assign it a one-bit code such as 0; an empty codeword would be ambiguous.

  • Duplicate symbols: Aggregate their frequencies rather than treating occurrences independently.

  • Invalid frequencies: Symbol frequencies must be nonnegative, and normally positive for symbols being coded.

  • Tie-breaking: Different valid choices can produce different codewords, but not a different optimal weighted length.

  • Greedy is problem-specific: Huffman’s rule does not apply to coin change. With coins 1, 3, 4 and amount 6, greedy selection uses 4 + 1 + 1, while the optimal solution uses 3 + 3.

  • Additional constraints: Huffman coding minimizes total symbol-by-symbol prefix-code length, but it may not minimize storage under restrictions such as maximum code length or fixed codeword-length limits.

22

How do routing protocols use greedy path selection?

Greedy algorithms help routing protocols select paths by repeatedly choosing the currently best-known route according to a cost metric. In link-state protocols, this commonly means using Dijkstra’s algorithm to compute shortest paths; distance-vector and policy-based protocols use different decision rules.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

A network is modeled as a weighted graph:

  • Vertices: routers or networks

  • Edges: links between routers

  • Weights: link costs, such as latency, bandwidth, or an OSPF-style metric

  • Routing table: the resulting paths installed by the protocol

The routing protocol first learns the topology, then computes paths and installs the best routes into its routing information database and forwarding table.

A typical workflow is:

  1. Discover neighboring routers and links.

  2. Exchange or advertise topology information.

  3. Build a weighted topology graph.

  4. Compute paths using the protocol’s path-selection algorithm.

  5. Install the selected routes.

  6. Recompute affected paths when links or metrics change.

How Protocols Apply Greedy Selection

Protocol or algorithm Path-selection method Greedy relationship
OSPF Uses Dijkstra’s shortest-path-first algorithm Directly uses greedy settling of the nearest vertex
IS-IS Uses a shortest-path-first calculation Uses a Dijkstra-style greedy process
RIP Uses Bellman-Ford Not greedy; it repeatedly relaxes all edges
EIGRP Uses DUAL, an advanced distance-vector method Not the standard greedy Dijkstra algorithm
BGP Selects paths using policy attributes and preferences Not based solely on the shortest mathematical path

The key distinction is that a protocol may be called a “routing protocol” while using different internal algorithms. OSPF’s use of Dijkstra is a clear example of a greedy algorithm inside a routing protocol.

Greedy Choice and Why It Is Safe

Greedy choice: repeatedly select the unsettled router with the smallest tentative distance from the source, then update its neighbors.

This is safe when all link weights are nonnegative. Once the router with the smallest tentative distance is selected, no later path can improve it: any alternative path would first pass through another unsettled router whose tentative distance would have to be smaller, contradicting the selection rule.

Dijkstra also relies on optimal substructure: a shortest path to a router consists of a shortest path to its predecessor plus the final link, provided weights are nonnegative.

Step-by-step trace on a small network (A→B: 1, A→C: 4, B→C: 2, C→D: 1):

  1. Start: distances = {A: 0, B: ∞, C: ∞, D: ∞}; all routers unsettled.

  2. Select A (distance 0, smallest). Mark A visited. Update B = 1, C = 4.

  3. Select B (distance 1, smallest). Mark B visited. Update C = min(4, 1+2) = 3.

  4. Select C (distance 3, smallest). Mark C visited. Update D = 3+1 = 4.

  5. Select D (distance 4). Mark D visited. No neighbors remain.

  6. Final distances: {A: 0, B: 1, C: 3, D: 4}.

However, a locally greedy choice can fail when each router independently chooses the cheapest next hop. For example:

  • A → X costs 1

  • X → Y costs 100

  • A → Y costs 3

Choosing the cheapest next hop from A selects X, producing a total cost of 101, while the direct path costs 3. Link-state protocols avoid this problem by computing paths from a shared topology rather than making purely local greedy decisions.

Complexity

For a graph with V routers and E links, a binary-heap implementation of Dijkstra has:

  • Time: O((V + E) log V) in the standard best, average, and worst cases. The heap can contain multiple entries, but a stale entry is discarded when popped.

  • Space: O(V + E) including the input graph, distance and predecessor maps, visited set, and heap. The algorithm is iterative, so no recursion stack is needed.

  • Auxiliary space excluding the input: O(V + E).

Protocol-specific message processing, storage, and recomputation costs are separate from the shortest-path calculation.

Common Pitfalls

  • Negative link weights: Dijkstra is not valid for negative weights; use Bellman-Ford instead.

  • Disconnected networks: The algorithm returns only routers reachable from the source.

  • Parallel links: Multiple links between the same routers are handled naturally.

  • Stale heap entries: Always check visited before processing a popped router.

  • Mutable input: The graph should not be modified during computation.

  • Greedy overgeneralization: A shortest path is not always the preferred path for BGP, where policy, AS policy, and attributes matter.

  • Recomputation behavior: In real protocols, topology changes can trigger partial recomputation rather than a full calculation.

23

How do greedy algorithms handle distributed load balancing and task scheduling?

Greedy algorithms balance distributed workloads by repeatedly making a locally best decision, such as assigning a task to the least-loaded worker or selecting the task with the earliest deadline. They are useful when fast decisions and low coordination overhead matter more than finding a globally optimal schedule.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Greedy Choice and Safety

  • Greedy choice: For identical workers, LPT orders known task durations from longest to shortest and assigns each task to the worker with the smallest current load. For deadline-driven scheduling, EDF selects the available task with the earliest deadline.

  • EDF exchange argument: On a single processor with preemptive scheduling of independent jobs, a feasible schedule can be rearranged to execute the available earliest-deadline job first without causing a deadline miss. This establishes EDF’s optimality under the standard single-processor assumptions.

  • Least-loaded limitation: Assigning the next task to the least-loaded worker minimizes the maximum load immediately after that assignment, but it does not guarantee the minimum final makespan because future tasks can change which assignment is best.

  • LPT guarantee: LPT produces a makespan at most 4/3 - 1/(3w) times optimal for w identical workers. It is therefore an approximation algorithm, not an exact optimizer.

  • Distributed EDF: EDF is generally a heuristic when extended to multiprocessors or distributed workers; global EDF variants require additional machinery and do not generally guarantee optimality.

Distributed Scheduling Patterns

Pattern Greedy decision Advantages Limitation
Central least-loaded dispatcher Send each task to the worker with the lowest estimated load Simple and based on centralized state The dispatcher can become a bottleneck
Join-shortest-queue Choose the worker with the shortest observed queue Decentralized and scalable Queue information may be stale or incomplete
Power-of-two choices Choose between two workers and select the less loaded one Very low coordination overhead Statistical rather than globally optimal
Weighted least work Compare estimated work divided by worker capacity Supports heterogeneous workers Requires reliable runtime and capacity estimates
Work stealing Idle workers take work from busy workers Adapts to dynamic load Requires safe ownership and synchronization
Earliest deadline first Run the available task with the nearest deadline Deadline-aware real-time scheduling Global variants are not generally optimal on distributed systems

Task dependencies require additional care. For tasks represented by a directed acyclic graph, the scheduler must honor precedence constraints; unrestricted greedy assignment is invalid.

Complexity

A typical LPT implementation sorts n task durations, initializes w workers, and maintains their loads in a binary min-heap:

  • Best case: O(w + n log(w + 1)) when the tasks are already ordered non-increasingly. Python 3.12’s adaptive sort processes that ordered input in linear time, while each heap update costs O(log(w + 1)).

  • Average and worst case: O(w + n log n + n log(w + 1)). Sorting is the main cost at O(n log n).

  • Auxiliary space: O(n + w), excluding the input, for the sorted task copy, heap, and worker loads. The call stack uses O(1) space.

  • Other patterns: A central scan takes O(w) time per assignment and maintains O(w) worker state. Checking d join-shortest-queue candidates takes O(d) time per assignment, or O(nd) for n assignments.

Walkthrough and Counterexample

For tasks [4, 4, 3, 3, 3, 1] and two workers, LPT produces:

  1. Assign 4 to worker 0: [4, 0].

  2. Assign 4 to worker 1: [4, 4].

  3. Assign 3 to worker 0: [7, 4].

  4. Assign 3 to worker 1: [7, 7].

  5. Assign 3 to worker 0: [10, 7].

  6. Assign 1 to worker 1: [10, 8].

The greedy makespan is 10, but scheduling [4, 4, 1] and [3, 3, 3] gives the optimal makespan of 9. Thus, locally balancing workers is not the same as finding a globally optimal assignment.

Common Pitfalls

  • Assuming optimality: Least-loaded assignment is generally a heuristic.

  • Ignoring dependencies: Independent-task LPT does not directly apply to workflows with precedence constraints.

  • Using stale load estimates: Predicted work may differ substantially from actual execution time.

  • Choosing poor task granularity: Tiny tasks increase coordination overhead, while very large tasks create stragglers.

  • Ignoring worker capacity: A faster worker may be overloaded even when its task count is lower.

  • Integer overflow: Python integers do not overflow, but equivalent Java or C++ implementations should use 64-bit or wider totals.

  • Typical follow-up questions: How would the scheduler handle worker failures, dynamic arrivals, heterogeneous hardware, network delays, or tasks that pause and resume?

24

How does greedy optimization apply to financial portfolio optimization?

A greedy algorithm can allocate a fixed investment budget by repeatedly funding the opportunity with the highest return per unit of cost. This is exact for a fractional portfolio allocation problem, where capital is divisible and investments have no minimum sizes, integer-share restrictions, or significant transaction costs.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Greedy Choice and Why It Is Safe

The greedy choice is: invest in the remaining opportunity with the highest expected return per dollar, then continue with the remaining budget.

This is safe because of the greedy-choice property:

  • If an allocation funds a lower-return opportunity while a higher-return opportunity has unused capacity, shifting capital toward the higher-return opportunity cannot reduce total return.

  • Repeating this exchange argument transforms an optimal allocation into the greedy allocation without worsening its result.

  • After each choice, the remaining budget forms the same kind of problem, demonstrating optimal substructure.

Therefore, sorting investments by return-to-cost ratio and funding them in that order produces an optimal fractional allocation under the stated assumptions. This argument applies when maximizing expected dollar return; it does not automatically optimize risk-adjusted portfolio performance.

Financial Model and Assumptions

A simplified model may contain:

  • Available budget: Total capital available for investment.

  • Investment cost: Amount required to fund an opportunity fully.

  • Expected return: Estimated profit if the opportunity is fully funded.

  • Risk-adjusted return: A linear estimate of return after accounting for risk.

The greedy approach is appropriate when:

  • Capital is freely divisible.

  • Partial funding produces a proportional share of expected return.

  • Returns are additive across investments.

  • There is one principal constraint, such as the total budget.

  • Minimum investments, integer-lot restrictions, leverage, and major transaction costs are absent or negligible.

It is usually a baseline rather than a complete real-world portfolio optimizer. Mean-variance optimization, quadratic optimization, or another constrained optimizer is more appropriate when risk, covariance, liquidity, taxes, turnover, and position limits matter.

Example Walkthrough

Consider a $100 budget:

Investment Cost Expected Return Return per Dollar
Index fund $60 $9.00 0.15
Startup fund $50 $6.00 0.12
Bond fund $40 $4.00 0.10
  1. Allocate $60 to the index fund, producing $9.00 in expected return.

  2. Invest the remaining $40 in the startup fund, funding 80% of it.

  3. The partial allocation produces $6.00 × 0.8 = $4.80.

  4. The total expected return is $9.00 + $4.80 = $13.80.

Complexity

For n investments:

  • Sorting: O(n) best case when the candidates are already ratio-sorted with an adaptive sort such as Python’s; O(n log n) average and worst case otherwise.

  • Allocation scan: O(n) best, average, and worst case because each candidate is considered once.

  • Overall time: O(n) best case for already ratio-sorted input and O(n log n) average and worst case, because sorting dominates.

  • Space: O(n) auxiliary space for the sorted candidates, excluding the input, plus O(n) for returned allocations. The recursion stack is O(1) because the algorithm is iterative.

Common Pitfalls

  • Greedy counterexample: With indivisible investments and a budget of 10, consider the following:

| Investment | Cost | Return | Return per Dollar | |—|—:|—:|—:| | A | 6 | 6.30 | 1.05 | | B | 5 | 5.00 | 1.00 | | C | 5 | 5.10 | 1.02 |

Greedy selection chooses A first, leaving $4, which cannot fund another investment; its return is $6.30. The optimal 0/1 choice is B and C, costing $10 and returning $10.10. Dynamic programming or integer optimization is required when investments cannot be divided.

  • Integer shares or minimum trade sizes: These invalidate the fractional greedy guarantee.

  • Ignoring portfolio interactions: Correlations and diversification make aggregate risk nonlinear.

  • Unrealistic estimates: Greedy allocation optimizes only the supplied forecasts; biased or unstable estimates can produce poor results.

  • Missing constraints: Taxes, transaction costs, liquidity, leverage, and turnover limits can change the optimum.

  • Edge cases: An empty portfolio or zero budget produces no allocations; one investment is straightforward; duplicate entries are separate investments; negative or zero-return candidates can be skipped; non-positive costs are invalid.

25

How do the cut property and greedy algorithms relate?

In greedy-algorithm terminology, the relevant concept is usually the cut property, rather than “primality of cuts.” A cut divides a graph into two parts, and the cut property identifies an edge that can be safely selected by a greedy minimum-spanning-tree algorithm.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

For a connected, undirected, weighted graph, a cut is a partition of its vertices into two nonempty sets, such as (S) and (V-S). An edge crosses the cut when one endpoint is in each set.

The cut property states that a minimum-weight edge crossing any cut is safe to include in some minimum spanning tree. “Safe” means the edge can be part of an optimal solution extending the edges already selected.

The greedy choice is: select a minimum-weight edge crossing the cut induced by the current tree component.

Why the Cut Choice Is Safe

Suppose an MST (T) does not contain the selected cut edge (e). Adding (e) to (T) creates a cycle. That cycle must contain another edge (f) crossing the same cut.

Because (e) is a minimum-weight crossing edge:

[ w(e) leq w(f) ]

Removing (f) from the cycle produces another spanning tree whose weight is no greater than (T). Therefore, an MST containing (e) exists. This exchange argument establishes both the greedy-choice property and the optimal substructure needed by the greedy algorithm.

Relation to Greedy Algorithms

The cut property is used directly by Kruskal’s algorithm:

  1. Sort all edges by increasing weight.

  2. Select the next edge if its endpoints belong to different components.

  3. Otherwise, reject it because it would create a cycle.

The cycle property is the complementary rule: the maximum-weight edge on a cycle can safely be excluded from an MST. For a maximum spanning tree, the weight directions are reversed.

If “primal” refers to primal-dual optimization, cuts can also represent dual constraints. For example, in maximum flow, a cut’s capacity is an upper bound on the maximum flow. A primal-dual algorithm adjusts both until the primal flow and dual cut provide matching certificates. This is different from the local edge-selection rule used by MST greedy algorithms.

Complexity

Approach Time Space When to use
Brute-force edge subsets (O(2^E(E+V))) (O(V+E)) including input Only tiny graphs
Kruskal with union-find (O(Elog E + Ealpha(V)) = O(Elog E)) (O(V)) auxiliary; (O(V+E)) including input Sparse graphs; handles disconnected graphs
Prim with a binary heap (O((V+E)log V)) (O(V)) auxiliary; (O(V+E)) including input Dense graphs or growing one tree

For Kruskal, sorting is the main (O(Elog n))-style cost, while union-find operations are amortized (O(alpha(V))). Scanning the edges of a specified cut costs (O(E)), although checking whether one edge crosses a known partition costs (O(1)). These iterative implementations do not require a recursion stack.

Small Trace

Consider edges AB:1, BC:2, CD:3, AC:4, and BD:5.

Step Current component Minimum crossing edge Action
1 {A} AB:1 Select
2 {A,B} BC:2 Select
3 {A,B,C} CD:3 Select

The resulting MST has total weight (1+2+3=6). Each selected edge is the minimum edge crossing the current component’s cut, so the exchange argument makes every choice safe.

A similar greedy strategy can fail when the problem lacks the required structure. For coin change with coins 1, 3, 4 and amount 6, choosing the largest coin first gives 4 + 1 + 1, or three coins, while 3 + 3 uses only two. Coin change is not a matroid problem, so the greedy-choice property does not hold.

Common Pitfalls

  • Do not confuse the cut property with the cycle property: cuts justify including safe edges; cycles justify excluding unnecessary edges.

  • Use the current component’s cut: selecting any globally minimum edge is not necessarily safe.

  • Handle equal weights carefully: multiple edges may be valid choices, but the implementation must still avoid cycles.

  • Do not generalize greedy correctness: the cut argument depends on the graphic matroid structure.

  • A common follow-up asks why Kruskal rejects an edge whose endpoints are already connected: that edge would create a cycle, and the cycle property allows the heavier edge to be excluded.

26

What is the local ratio technique in greedy algorithms?

The local ratio technique transforms a difficult weighted optimization problem into a sequence of simpler residual problems by reducing or charging part of each solution’s cost locally. It is commonly used to design approximation algorithms and often supplies the greedy choice used at each step.

Read full answer

Applies tolanguage-independent

How It Works

A local-ratio algorithm generally follows these steps:

  1. Compute nonnegative prices or reductions from the current instance.

  2. Use those reductions to produce a residual instance with modified costs.

  3. Solve the residual instance greedily or with another algorithm.

  4. Combine the local solution with the residual solution.

  5. Charge the original cost to the reductions and residual costs.

The relationship between the original and reduced costs determines the approximation factor. Repeating reductions can turn an intractable problem into several easy greedy decisions while preserving a provable guarantee.

Greedy Choice and Safety

For weighted set cover, the greedy choice is: for each element, select a containing set with the smallest residual cost.

This is safe because the residual cost is the maximum additional dual price that can be assigned to the element without making any set’s dual constraint invalid. Choosing the minimum therefore extracts the largest safe reduction. The selected set becomes tight, allowing its cost to be accounted for by the prices assigned to its elements.

Application to Weighted Set Cover

For universe (E), sets (S_i), and nonnegative set costs (w_i), the set-cover dual constraints are:

[ sum_{e in S_i} y_e leq w_i,qquad y_e geq 0 ]

The dual objective (sum_e y_e) is a lower bound on the optimal integral cover cost. The algorithm maintains:

[ r(S_i)=w_i-sum_{ein S_i}y_e ]

For an unpriced element (e), it increases (y_e) by:

[ Delta=min_{S_ini e} r(S_i) ]

and subtracts (Delta) from every residual cost of a set containing (e). This is the primal-dual form of the local-ratio technique. Selecting every set whose residual cost reaches zero gives an (f)-approximation, where (f) is the largest number of sets containing any one element; for weighted vertex cover, (f=2).

Complexity and Edge Cases

  • Time: (O(nm)) worst case, where (n) is the number of elements and (m) the number of sets; every element scans the sets and updates matching residuals.

  • Auxiliary space: (O(n+m)), excluding the input’s element-to-set incidence storage.

  • Sorting is not required, so there is no (O(nlog n)) sorting cost.

  • Empty universe returns an empty cover; one-element and duplicate-set instances work normally.

  • Negative costs and elements no set covers should be rejected rather than producing an invalid approximation.

  • Work on a copy of the costs so the caller’s input is not mutated.

Common Pitfalls

  • Local ratio provides an approximation, not an exact polynomial-time solution to NP-hard problems such as weighted set cover.

  • A greedy choice can fail on similar problems: for denominations (1,3,4) and amount (6), choosing the largest coin first needs three coins, while (3+3) needs only two.

  • Every dual price must preserve the residual-cost invariant; otherwise the approximation proof fails.

  • In languages with fixed-width integers, verify that cost reductions cannot overflow; Python integers are unbounded.

  • Interviewers often ask how the approximation factor is derived, how ties are handled, and why the algorithm remains feasible even when the residual solution differs from the original optimum.

27

How does the exchange argument prove that a greedy choice is optimal?

An exchange argument proves a greedy algorithm is optimal by showing that an optimal solution can be modified to include the greedy choice without becoming worse. It connects the locally selected option to a globally optimal solution.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

The exchange argument relies on the greedy-choice property: at each step, there exists at least one optimal solution that includes the option selected by the greedy algorithm.

The proof usually follows this structure:

  1. Assume an optimal solution exists for the current subproblem.

  2. Examine the first choice where that solution differs from the greedy solution.

  3. Replace the optimal solution’s choice with the greedy choice.

  4. Show that feasibility is preserved and the objective value does not decrease.

  5. Conclude that an optimal solution containing the greedy choice exists.

The exchange establishes the greedy-choice property. Combined with optimal substructure, meaning that fixing a choice leaves a residual subproblem whose contribution can be optimized separately, it supports an inductive proof of the complete greedy algorithm.

Activity Selection Example

Suppose each activity is represented by a start and finish time, and an activity may follow another when its start is at least the previous activity’s finish. The greedy choice is to select the compatible activity that finishes earliest because this leaves at least as much room for every later activity.

Consider these intervals:

Activity Start Finish
A 1 4
B 3 6
C 6 8
D 8 10

The greedy algorithm selects A, then C, then D.

Another optimal solution is B, C, D. Three activities is the maximum possible because A and B overlap, so at most one of them can be selected alongside C and D.

To exchange B for A:

  • A finishes at time 4, while B finishes at time 6.

  • Every activity that follows B starts at or after time 6.

  • Therefore, every activity that follows B can also follow A.

  • The number of selected activities remains unchanged.

Thus, replacing B with A transforms an optimal solution into another optimal solution containing the greedy choice.

Step Current optimal solution Exchange or greedy decision Result
1 B, C, D Replace B with earlier-finishing A A, C, D
2 A Choose earliest-finishing compatible activity C A, C
3 A, C Choose earliest-finishing compatible activity D A, C, D

What the Proof Must Establish

A valid exchange argument explicitly proves that:

  • Compatibility is preserved: the replacement does not conflict with any other selected item.

  • Objective value does not decrease: the replacement does not make the result worse.

  • At least one optimal solution remains: because the modified solution is still optimal.

  • The greedy decision is safe for the remaining subproblem: after the exchange, the same reasoning can be repeated.

Simply saying “choosing the earliest-finishing activity leaves the most room for future activities” is intuitive, but an interview answer is stronger when it explicitly connects that observation to an optimal solution.

When Greedy Choices Fail

Not every similar problem has the exchange property. For example, with unlimited coin denominations 1, 3, and 4 and amount 6:

  • Greedy choice: take 4, then 1, then 1, producing 3 coins.

  • Optimal choice: take 3 and 3, producing 2 coins.

The locally largest coin prevents the best global combination. An exchange from 3 + 3 to a solution containing 4 cannot preserve the number of coins.

Problem Greedy choice Result
Coin change with 1, 3, 4 and amount 6 Largest coin first Incorrect
Fractional knapsack Highest value-to-weight ratio first Correct because fractions are allowed
Activity selection Earliest-finishing activity Correct for maximum non-overlapping count

Complexity Implications

The exchange argument is a proof technique, so it has no runtime or space complexity of its own. For a typical activity-selection implementation:

  • Time: average and worst case O(n log n) because sorting by finish time dominates the O(n) scan; best case O(n) when activities are already sorted by finish time.

  • Space: O(n) auxiliary space because Python’s sorting can use O(n) temporary space. The selected result uses O(k) space for k activities. The original input and recursion stack are excluded; the algorithm is iterative.

If the input is already sorted, scanning takes O(n) time with O(1) working space, excluding the O(k) selected result.

Common Pitfalls

  • Proving only that the greedy choice “looks best” rather than showing that an optimal solution can contain it.

  • Omitting the feasibility argument: the exchanged solution must still satisfy all constraints.

  • Confusing earliest start, earliest finish, shortest duration, and lowest cost; these represent different greedy rules.

  • Applying an activity-selection proof to weighted interval scheduling, where selecting the earliest-finishing interval may reduce total value.

  • Claiming greedy algorithms are always optimal. The exchange argument must be specific to the problem’s objective and constraints.

  • Forgetting optimal substructure: proving the first greedy choice is safe is insufficient unless the remaining subproblem is handled correctly.

28

Where does a greedy algorithm fail to find the global optimum?

A largest-first greedy algorithm can fail to find the global optimum. For unlimited coins with denominations {1, 3, 4} and a target of 6, choosing the largest coin first produces 4 + 1 + 1, requiring three coins, while the optimal solution is 3 + 3, requiring only two.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Counterexample

For unlimited coin change, a tempting greedy choice is:

Always select the largest denomination that does not exceed the remaining amount.

Applying that rule to amount 6:

  1. Select 4; the remaining amount becomes 2.

  2. Select 1; the remaining amount becomes 1.

  3. Select 1; the remaining amount becomes 0.

  4. The greedy result uses three coins.

An optimal solution selects 3 and then 3, using only two coins.

Approach Result for amount 6 Correct?
Largest-first greedy 4 + 1 + 1 No
Dynamic programming 3 + 3 Yes
Exhaustive search 3 + 3 Yes

Why the Greedy Choice Fails

The greedy-choice property would require that some global optimum includes the largest available coin. Here, the global optimum 3 + 3 does not include 4, so that property does not hold.

An exchange argument also fails: replacing the selected 4 with smaller coins does not necessarily preserve the number of coins. In this case, replacing 4 + 1 + 1 with 3 + 3 improves the result.

The underlying coin-change problem does have optimal substructure. Its recurrence is:

OPT(amount) = min(OPT(amount - coin) + 1) over every usable denomination.

That recurrence leads to dynamic programming rather than an unproven greedy rule. Greedy algorithms are still valid for some coin systems, particularly canonical systems where largest-first selection is guaranteed to work.

Complexity Comparison

Let m be the number of distinct denominations, A the target amount, and k the number of coins selected by the greedy algorithm.

Approach Time Auxiliary space When to use
Largest-first greedy O(m log m + k) O(m) Only when the coin system is proven suitable
Dynamic programming O(A × m) O(A) General unlimited coin change
Exhaustive search O(m^A) upper bound O(A) recursion stack Tiny inputs or correctness checking
  • Greedy time: sorting costs O(m log m), while selecting the coins costs O(m + k). If denominations are already sorted, sorting can be removed.

  • Dynamic-programming time: each amount from 1 through A examines all m denominations.

  • Space counts auxiliary arrays and the recursion stack, but not the input itself.

Common Pitfalls

  • Unlimited versus 0/1 coins: This counterexample assumes unlimited copies. With one copy of each coin, 3 + 3 is not valid.

  • Unsupported claims: Greedy algorithms do not always fail; the proof must establish the greedy-choice property for the specific problem.

  • Input edge cases: The implementation rejects negative amounts and nonpositive denominations, handles empty denomination sets explicitly, and safely ignores duplicate denominations.

  • Sorting cost: If sorting dominates the implementation, include its O(m log m) cost rather than claiming the entire algorithm is linear.

  • Interview follow-up: Interviewers commonly ask whether the problem permits repeated coins and whether an exchange argument can prove that the greedy choice is safe.

29

Why does greedy fail coin change with non-standard denominations

A greedy algorithm for coin change always selects the largest denomination coin that fits into the remaining amount, which is optimal only for canonical coin systems. For non-standard denominations, this locally optimal choice can prevent reaching the globally optimal solution, meaning the total number of coins used is not minimal.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why the Greedy Choice Fails

The greedy choice is to always take the largest coin that does not exceed the remaining amount. This is safe only when the coin system satisfies the greedy-choice property and optimal substructure. Non-standard systems break the greedy-choice property because a large coin can leave a remainder that requires many small coins, while a slightly smaller coin could complete the amount with fewer total coins.

Counterexample

Consider coins of denominations {1, 3, 4} and a target amount of 6.

  1. Greedy picks 4, leaving 2.

  2. Greedy picks 1, leaving 1.

  3. Greedy picks 1, leaving 0.

The greedy solution uses 3 coins: 4 + 1 + 1. The optimal solution uses 2 coins: 3 + 3. This proves greedy is not optimal for this denomination set.

When Greedy Works

Greedy is optimal for canonical coin systems (where the greedy algorithm always yields the optimal solution). A sufficient condition is that each coin is a multiple of the previous one (e.g., 1, 2, 4, 8…), but many canonical systems like US coins (1, 5, 10, 25) do not satisfy this yet still work. A common test is whether the greedy solution for any amount equals the dynamic programming solution up to a certain bound.

Greedy vs Dynamic Programming

Approach Time Space When to use
Greedy O(m) per amount O(1) Canonical coin systems only
Dynamic programming O(n * m) O(n) Any coin system

Here, n is the target amount and m is the number of denominations. Sorting the denominations costs O(m log m), which is typically not the main cost.

Better Approach

Use dynamic programming for the general coin change problem. Define dp[i] as the minimum coins needed for amount i, and compute dp[i] = min(dp[i - coin] + 1) for each coin. This guarantees the optimal answer but runs in O(n * m) time where n is the amount and m is the number of denominations.

Interview Tips

Interviewers often ask you to prove greedy optimality or find a counterexample. Always test your greedy assumption against small amounts before committing. A follow-up question may ask you to determine whether a given coin system is canonical, which requires checking all amounts up to a bound.

30

What are the limitations of greedy graph coloring?

Greedy algorithms for Graph Coloring are efficient but suboptimal because they prioritize immediate local choices over global constraints. They cannot guarantee the minimum number of colors and are highly sensitive to vertex ordering.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Greedy Graph Coloring Works

The greedy choice is to assign the lowest available color index to the current vertex. This choice is not safe because it violates the greedy-choice property: a locally optimal decision can eliminate color options for later vertices, preventing a globally optimal coloring.

  1. Iterate through the vertices in a fixed order.

  2. For each vertex, check the colors of its adjacent neighbors.

  3. Assign the smallest color index not used by any neighbor.

  4. Repeat until all vertices are colored.

  5. Time Complexity: O(V + E) with adjacency lists, or O(V^2) with an adjacency matrix.

  6. Space Complexity: O(V) to store the color of each vertex.

Why Greedy Fails: The Limitations

  • Suboptimality: The algorithm does not guarantee the chromatic number χ(G). It can use significantly more colors than necessary.

  • Ordering Sensitivity: The number of colors used depends entirely on the order in which vertices are processed. A poor ordering can force the algorithm to use O(n) colors on a graph that is bipartite (2-colorable).

  • Degree Bound: While greedy coloring is bounded by Δ + 1 (where Δ is the maximum degree), the actual chromatic number can be much lower.

  • Counterexample: Consider a bipartite graph where a high-degree vertex is processed early. It consumes the first color, forcing its neighbors to use distinct colors, whereas a different order might allow those neighbors to share colors.

Comparison: Greedy vs Optimal

Approach Time Complexity Space Complexity Guarantee
Greedy O(V + E) O(V) Approximation (at most Δ + 1)
Optimal (Backtracking) O(V^χ) O(V) Exact minimum colors
Optimal (Integer Programming) Exponential O(V) Exact minimum colors

Note: Finding the exact chromatic number is NP-hard, so exact algorithms are only feasible for small graphs.

When to Use Greedy

  • Use greedy when the graph is very large and an exact solution is computationally infeasible.

  • Use it when a solution within a factor of the optimum is acceptable.

  • It is often used as a preprocessing step or a heuristic for exact algorithms.

  • Sorting vertices by degree (Welsh-Powell) adds O(V log V) cost but often improves the result.

Common Pitfalls

  • Assuming Optimality: Never assume the greedy result is the minimum number of colors.

  • Ignoring Order: Failing to test different vertex orderings can lead to poor results.

  • Confusing with Bipartite: Greedy coloring on a bipartite graph is not guaranteed to use only 2 colors unless the order is favorable.

  • Follow-up: Interviewers often ask how to improve greedy results, such as using the Welsh-Powell algorithm or backtracking with pruning.

31

How do you form the largest number by greedily ordering a list?

The largest number is formed by sorting the list with a greedy comparator: place a before b whenever a + b is greater than b + a, then concatenate the elements. In the standard version of this problem, every element is a non-negative integer and must be used exactly once.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Greedy Choice

For two elements a and b, compare the two possible concatenations:

  • If a + b > b + a, place a first.

  • Otherwise, place b first.

  • If they are equal, either order produces the same result.

This is safe because every arrangement has the same total number of digits, so lexicographic comparison is equivalent to numeric comparison. If an optimal arrangement contains an adjacent pair in the wrong order, swapping that pair cannot decrease the result. Repeating these swaps produces the comparator-sorted order, proving the greedy-choice property. Once an element is selected, the remaining elements form the same suffix problem, giving optimal substructure.

Algorithm

  1. Convert each number to its decimal string.

  2. Sort the strings using a + b versus b + a.

  3. Concatenate the sorted strings.

  4. Return "0" if every element is zero.

Sorting numerically is insufficient. For example, descending numeric order produces 91 before 9, but "91" + "9" = "919" is smaller than "9" + "91" = "991".

Step-by-Step Example

For [3, 30, 34, 5, 9]:

Comparison Winner Reason
9 + 5 vs 5 + 9 9 "95" > "59"
5 + 34 vs 34 + 5 5 "534" > "345"
34 + 3 vs 3 + 34 34 "343" > "334"
3 + 30 vs 30 + 3 3 "330" > "303"

The final order is [9, 5, 34, 3, 30], producing 9534330.

Complexity

Let n be the number of elements and k the maximum number of digits in an element.

Approach Time Space When to use
Check all permutations O(n! × nk) O(n + nk) Very small inputs or verification
Greedy comparator sorting O(nk log n) O(nk) General solution

For comparator sorting:

  • Best case: O(nk) when the input is already correctly ordered.

  • Average case: O(nk log n).

  • Worst case: O(nk log n).

  • Space: O(nk) including the output, temporary strings and sorting wrappers. The original input is not counted, and no recursion stack is used.

The sorting comparisons are the main cost, with each comparison taking up to O(k) time.

Code Example

from functools import cmp_to_key


def largest_number(numbers: list[int]) -> str:
    """Return the largest number formed by concatenating non-negative integers."""
    if not numbers:
        raise ValueError("numbers must not be empty")

    if any(number < 0 for number in numbers):
        raise ValueError("numbers must be non-negative")

    parts = [str(number) for number in numbers]

    def compare(left: str, right: str) -> int:
        left_first = left + right
        right_first = right + left

        if left_first > right_first:
            return -1
        if left_first < right_first:
            return 1
        return 0

    parts.sort(key=cmp_to_key(compare))

    if all(part == "0" for part in parts):
        return "0"

    return "".join(parts)


print(largest_number([3, 30, 34, 5, 9]))  # 9534330

Common Pitfalls

  • Edge cases: Empty input and negative integers raise ValueError. One-element lists work directly, duplicates are handled by the comparator, and [0, 0] returns "0".

  • Zero values: Positive numbers are placed before zeros because "10" > "01".

  • Input mutation: The function creates a new list of strings and does not modify the original list.

  • Different problem: This algorithm assumes all elements must be used. If elements may be skipped or combined using arithmetic, the objective and greedy rule are different.

  • Greedy can fail elsewhere: For coin change with coins {1, 3, 4} and amount 6, choosing the largest coin first gives 4 + 1 + 1, while the optimal answer is 3 + 3. Such problems require dynamic programming.

  • Interview follow-ups: Clarify whether negative values are allowed, whether the result should be a string or integer, and whether every input element must appear exactly once.

32

How can job sequencing with deadlines be solved greedily to maximize profit?

Use a greedy profit-ordering algorithm: process jobs from highest profit to lowest and assign each job the latest free time slot before its deadline. A disjoint-set union (DSU) structure finds available slots efficiently.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Greedy Choice and Why It Is Safe

The greedy choice is to consider the highest-profit remaining job and place it in the latest free slot at or before its deadline.

Unit-time jobs with deadlines form a scheduling matroid, so the greedy-choice property applies. Let S be the jobs already selected and let O be an optimal feasible set containing S. For the next job j, if adding j to S is infeasible, no feasible extension of S can contain it. Otherwise, if O omits j, the matroid exchange property permits adding j and removing one conflicting job from the remaining part of O. Because jobs are processed in nonincreasing profit order, the removed job has equal or lower profit, so total profit cannot decrease. Inductively, the accepted jobs remain part of an optimal solution.

Choosing the latest slot is also safe: it preserves earlier slots for jobs with tighter deadlines. If a completion places the selected job in an earlier free slot t, move it to the latest free slot L. If L contains another job, swap them; that job’s deadline is at least L and therefore at least t, so feasibility is preserved.

How It Works

  1. Sort jobs by decreasing profit.

  2. For each job, find the latest available slot at or before its deadline.

  3. Assign the job if that slot exists; otherwise skip it.

  4. Return the selected jobs and their total profit.

The DSU tracks each component’s latest free predecessor. After occupying slot s, its component is merged with the component containing s - 1.

Job Deadline Profit Result Total Profit
A 2 100 Slot 2 100
B 2 19 Slot 1 119
D 1 10 No free slot 119
C 1 2 No free slot 119

Complexity

For n jobs:

  • Best time: O(n) in the best case when jobs are already ordered by decreasing profit and DSU accesses stay constant-time; Timsort detects the ordered run in O(n).

  • Average and worst time: O(n log n), dominated by sorting. DSU operations add O(n α(n)) amortized time.

  • Auxiliary space: O(n), excluding the input. This includes the sorted copy, DSU arrays, slot table, and selected schedule. The iterative find operation uses no recursion stack.

Approach Time Space When to use
Exhaustive subset enumeration O(2^n n log n) O(n) Very small inputs or validation
Profit-ordering greedy O(n log n) O(n) General use

Edge Cases and Counterexample

  • Empty input: Returns (0, []).

  • One job: Schedules it if its deadline is valid and profit is positive.

  • Duplicate jobs: Treated as separate jobs, each requiring its own slot.

  • Negative or zero profit: Skipped because selecting them cannot improve total profit.

  • Already sorted input: Valid and can reduce sorting time.

  • Cycles or disconnected graphs: Not applicable to this scheduling problem.

  • Greedy can fail for similar problems: For coin change with denominations {1, 3, 4} and amount 6, largest-first chooses 4 + 1 + 1; the optimal solution is 3 + 3.

Code Example

from collections.abc import Sequence
from dataclasses import dataclass


@dataclass(frozen=True, slots=True)
class Job:
    name: str
    deadline: int
    profit: int


@dataclass(frozen=True, slots=True)
class ScheduledJob:
    job: Job
    slot: int


def maximize_profit(
    jobs: Sequence[Job],
) -> tuple[int, list[ScheduledJob]]:
    """Return maximum profit and selected jobs in time-slot order."""
    if any(job.deadline <= 0 for job in jobs):
        raise ValueError("Job deadlines must be positive integers.")

    n = len(jobs)
    if n == 0:
        return 0, []

    # At most n unit-time jobs can be scheduled, so slots 1..n suffice.
    parent = list(range(n + 1))
    rank = [0] * (n + 1)
    latest_free = list(range(n + 1))

    def find(slot: int) -> int:
        while parent[slot] != slot:
            parent[slot] = parent[parent[slot]]
            slot = parent[slot]
        return slot

    def union(left: int, right: int) -> None:
        left_root = find(left)
        right_root = find(right)

        if left_root == right_root:
            return

        if rank[left_root] < rank[right_root]:
            left_root, right_root = right_root, left_root

        parent[right_root] = left_root
        if rank[left_root] == rank[right_root]:
            rank[left_root] += 1

        latest_free[left_root] = min(
            latest_free[left_root], latest_free[right_root]
        )

    selected_by_slot: list[ScheduledJob | None] = [None] * (n + 1)

    for job in sorted(jobs, key=lambda item: -item.profit):
        if job.profit <= 0:
            continue

        deadline = min(job.deadline, n)
        slot = latest_free[find(deadline)]

        if slot == 0:
            continue

        union(slot, slot - 1)
        selected_by_slot[slot] = ScheduledJob(job=job, slot=slot)

    selected = [entry for entry in selected_by_slot if entry is not None]
    total_profit = sum(entry.job.profit for entry in selected)
    return total_profit, selected


jobs = [
    Job("A", 2, 100),
    Job("B", 2, 19),
    Job("C", 1, 2),
    Job("D", 1, 10),
]

profit, schedule = maximize_profit(jobs)
print(profit)  # 119
print(schedule)
# [ScheduledJob(job=Job(name='B', deadline=2, profit=19), slot=1),
#  ScheduledJob(job=Job(name='A', deadline=2, profit=100), slot=2)]

Common Pitfalls and Interview Tips

  • Deadlines are normally one-based, and each job takes one time unit.

  • Do not use list.pop(0) or list.insert(0, value) for queues; use collections.deque.

  • Avoid mutating the caller’s input; the implementation sorts a separate list.

  • In fixed-width languages, use a wide enough integer type for accumulated profit.

  • Interviewers often ask why the latest slot is chosen, how feasibility is checked, and how the algorithm differs for jobs with non-unit durations.

33

How does greedy solve minimum arrows to burst balloons?

The greedy algorithm solves the minimum arrows to burst balloons problem by sorting the balloons by their end coordinate and shooting an arrow at the end of the first balloon. This choice is safe because it maximizes the number of overlapping balloons burst by a single arrow, and the problem exhibits optimal substructure.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Greedy Choice and Why It Is Safe

  • Sort: sort all balloons by their end coordinate in ascending order.

  • Shoot: place the first arrow at the end of the first balloon.

  • Advance: for each subsequent balloon, if its start is greater than the current arrow position, shoot a new arrow at its end.

  • Why safe: an exchange argument shows that any optimal solution can be transformed into one that uses the earliest end point without increasing the arrow count.

  • Counterexample: greedy fails for 0/1 knapsack (items cannot be split), but works here because balloons can be burst by a single point.

Step-by-Step Example

Example: [[10,16],[2,8],[1,6],[7,12]]

  1. Sort by end: [[1,6],[2,8],[7,12],[10,16]].

  2. Shoot at 6. This bursts [1,6] and [2,8] because 2 <= 6.

  3. Next balloon [7,12] starts after 6, so shoot at 12. This bursts [7,12].

  4. Next balloon [10,16] starts before 12, so it is burst by the arrow at 12.

  5. Total arrows: 2.

Approach Comparison

Approach Time Space When to use
Brute force O(2^n) O(n) Tiny inputs only
Greedy O(n log n) O(1) All inputs

Complexity

  • Time: O(n log n) because sorting dominates; the linear scan is O(n).

  • Space: O(1) extra space, excluding the input array.

  • Edge cases: empty input returns 0, one balloon returns 1, duplicates and negative coordinates are handled, and already sorted input does not change correctness.

Code Example

def find_min_arrows(points: list[list[int]]) -> int:
    """Return the minimum number of arrows to burst all balloons.

    Args:
        points: A list of [start, end] coordinates for each balloon.

    Example:
        >>> find_min_arrows([[10,16],[2,8],[1,6],[7,12]])
        2
    """
    if not points:
        return 0
    # Sort by end coordinate
    points.sort(key=lambda x: x[1])
    arrows = 1
    current_end = points[0][1]
    for start, end in points[1:]:
        if start > current_end:
            arrows += 1
            current_end = end
    return arrows

# Example call:
# find_min_arrows([[10,16],[2,8],[1,6],[7,12]])  # Output: 2

Common Pitfalls

  • Sorting by start coordinate instead of end coordinate.

  • Off-by-one errors in the overlap condition.

  • Mutating the input list without copying if the caller needs it.

  • Forgetting to handle empty input.

34

How does greedy bandwidth allocation maximize network utility?

Greedy bandwidth allocation maximizes total utility by assigning available capacity to traffic flows with the highest utility per unit of bandwidth. This works when bandwidth is divisible, each flow has linear utility, and the objective is to maximize aggregate value without additional fairness or QoS constraints.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Greedy Model

Represent each flow with:

  • Demand: The maximum bandwidth it can use.

  • Utility per bandwidth: The value obtained from each unit of assigned bandwidth.

  • Capacity: The total bandwidth available across the modeled resource.

The greedy choice is: always allocate capacity to the remaining flow with the highest utility per unit of bandwidth.

This is the fractional knapsack model. For example, a live video flow might have greater utility per Mbps than a background backup, so it receives capacity first.

Why the Greedy Choice Is Safe

The algorithm has the greedy-choice property and optimal substructure:

  • Exchange argument: If an allocation gives bandwidth to a lower-utility flow while a higher-utility flow remains unsaturated, transferring some bandwidth to the higher-utility flow cannot reduce total utility.

  • Optimal substructure: After fixing the greedy allocation, the remaining task is another fractional allocation problem with less capacity and fewer or smaller demands.

Therefore, an optimal solution can always be rearranged to agree with each greedy decision.

Example Walkthrough

With capacity 10 Mbps:

Step Flow Utility/Mbps Capacity Before Allocated Remaining
1 beta 3.0 10 4 6
2 alpha 2.0 6 6 0
3 gamma 1.5 0 0 0

Total allocated bandwidth is 10 Mbps, and total utility is 4 × 3 + 6 × 2 = 24.

Complexity

For n flows:

  • Best-case time: O(n) when the input is already sorted by utility density, because Python’s Timsort detects sorted runs; the allocation scan is always O(n).

  • Average-case time: O(n log n), dominated by sorting.

  • Worst-case time: O(n log n).

  • Space: O(n) auxiliary space for the sorted list, sorting workspace, and result. The input is not counted, and the recursion stack is O(1) because the implementation is iterative.

Code Example

from collections.abc import Sequence
from dataclasses import dataclass
from math import isfinite


@dataclass(frozen=True)
class BandwidthFlow:
    name: str
    demand_mbps: float
    utility_per_mbps: float


@dataclass(frozen=True)
class BandwidthAllocation:
    flow_name: str
    allocated_mbps: float


def allocate_bandwidth(
    flows: Sequence[BandwidthFlow],
    capacity_mbps: float,
) -> list[BandwidthAllocation]:
    """Allocate divisible bandwidth by descending utility per Mbps."""
    if not isfinite(capacity_mbps) or capacity_mbps < 0:
        raise ValueError("capacity_mbps must be a finite non-negative number")

    for flow in flows:
        if not isfinite(flow.demand_mbps) or flow.demand_mbps < 0:
            raise ValueError("flow demand must be finite and non-negative")
        if not isfinite(flow.utility_per_mbps):
            raise ValueError("flow utility must be finite")

    ordered_flows = sorted(
        flows,
        key=lambda flow: flow.utility_per_mbps,
        reverse=True,
    )

    allocations: list[BandwidthAllocation] = []
    remaining = float(capacity_mbps)

    for flow in ordered_flows:
        allocated = 0.0

        if remaining > 0 and flow.utility_per_mbps > 0:
            allocated = float(min(flow.demand_mbps, remaining))
            remaining -= allocated

        allocations.append(
            BandwidthAllocation(flow.name, allocated)
        )

    return allocations


flows = [
    BandwidthFlow("alpha", 6, 2.0),
    BandwidthFlow("beta", 4, 3.0),
    BandwidthFlow("gamma", 5, 1.5),
]

result = allocate_bandwidth(flows, 10)

# Expected output:
# [BandwidthAllocation(flow_name='beta', allocated_mbps=4.0),
#  BandwidthAllocation(flow_name='alpha', allocated_mbps=6.0),
#  BandwidthAllocation(flow_name='gamma', allocated_mbps=0.0)]

Common Pitfalls

  • Assuming divisibility: The greedy algorithm can fail for indivisible flows. With capacity 20, a flow requiring 6 Mbps for utility 10 and two flows requiring 9 Mbps each for utility 11, greedy allocation obtains 21, while selecting the two 9 Mbps flows obtains 22. Use 0/1 knapsack DP, costing O(nC) time and O(n) space, for that case.

  • Ignoring network constraints: Real multi-link networks may require considering path bottlenecks, minimum guarantees, latency, and congestion rather than one aggregate capacity.

  • Maximizing only throughput: All flows may have equal utility, so throughput is identical across allocations. Additional fairness objectives may require proportional-fair allocation instead.

  • Rounding errors: Use consistent units and consider integer packet or bandwidth units when fractional allocation is unrealistic.

  • Mutating input: The example sorts a copy and leaves the original flow list unchanged.

  • Likely follow-up: Interviewers may ask how you would extend the solution to indivisible traffic, multiple links, or a nonlinear utility function such as log(x).

35

How do you implement greedy Huffman coding for variable-length compression?

Huffman coding is a greedy compression algorithm that assigns shorter binary codes to frequent symbols and longer codes to less frequent symbols. It produces an optimal prefix-free code for minimizing the total encoded length.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Greedy Choice and Correctness

Greedy choice: Repeatedly combine the two symbols with the smallest frequencies into a new parent whose frequency is their sum.

This choice is safe because an optimal prefix tree can always place the two least-frequent symbols at deepest sibling leaves. Moving them there through an exchange argument cannot increase the weighted path length. After combining them, the same problem remains on the smaller set of symbols, giving the required optimal substructure.

Huffman coding minimizes:

[ L = frac{sum_i f_i l_i}{n} ]

where f_i is a symbol’s frequency and l_i is its code length.

How It Works

  1. Count the frequency of every symbol.

  2. Insert all symbols into a min-heap.

  3. Remove the two least-frequent nodes and merge them.

  4. Insert the merged node back into the heap.

  5. Repeat until one root remains.

  6. Assign 0 to left branches and 1 to right branches.

  7. Replace each input symbol with its generated code.

For banana, the frequencies are a: 3, b: 1, and n: 2. One valid result is:

Symbol Code
a 0
b 10
n 11

Encoding banana produces 100110110.

Complexity

Let n be the input length, k the number of distinct symbols, m the encoded output length, and S the total length of all generated code strings.

  • Frequency counting: O(n) expected because Counter uses hash-table operations.

  • Heap construction and merging: O(k log k) because there are k - 1 merges and each heap operation costs O(log k).

  • Code generation: O(k + S) because each tree node and generated code character is processed.

  • Encoding: O(m) because the output contains m bits.

  • Overall time: O(n + k log k + S + m). Best, average, and worst cases have this structural bound; pathological hash collisions can increase counting to O(n²).

  • Auxiliary space: O(k) for the heap, tree, and traversal stack, excluding the input and returned outputs. Including outputs requires O(S + m) additional space. The input itself occupies O(n) if counted.

Code Example

from __future__ import annotations

from collections import Counter
from dataclasses import dataclass
import heapq


@dataclass(frozen=True, slots=True)
class _Node:
    frequency: int
    symbol: str | None = None
    left: _Node | None = None
    right: _Node | None = None


def huffman_encode(text: str) -> tuple[str, dict[str, str]]:
    """Return a Huffman-encoded bit string and its symbol-to-code mapping."""
    if not text:
        return "", {}

    frequencies = Counter(text)

    # A one-symbol alphabet still needs one non-empty code.
    if len(frequencies) == 1:
        symbol = next(iter(frequencies))
        codes = {symbol: "0"}
        return "".join(codes[character] for character in text), codes

    heap: list[tuple[int, int, _Node]] = []
    for tie_breaker, (symbol, frequency) in enumerate(frequencies.items()):
        node = _Node(frequency=frequency, symbol=symbol)
        heapq.heappush(heap, (frequency, tie_breaker, node))

    next_tie_breaker = len(heap)

    while len(heap) > 1:
        left_frequency, _, left = heapq.heappop(heap)
        right_frequency, _, right = heapq.heappop(heap)

        merged = _Node(
            frequency=left_frequency + right_frequency,
            left=left,
            right=right,
        )
        heapq.heappush(
            heap,
            (merged.frequency, next_tie_breaker, merged),
        )
        next_tie_breaker += 1

    root = heap[0][2]
    codes: dict[str, str] = {}

    # Iterative traversal avoids recursion-depth problems.
    stack: list[tuple[_Node, int | None, bool]] = [(root, None, False)]
    path: list[int] = []

    while stack:
        node, incoming_bit, exiting = stack.pop()

        if exiting:
            if incoming_bit is not None:
                path.pop()
            continue

        if incoming_bit is not None:
            path.append(incoming_bit)

        if node.symbol is not None:
            codes[node.symbol] = "".join(str(bit) for bit in path)
            if incoming_bit is not None:
                path.pop()
            continue

        if node.left is None or node.right is None:
            raise RuntimeError("Invalid Huffman tree")

        stack.append((node, incoming_bit, True))
        stack.append((node.right, 1, False))
        stack.append((node.left, 0, False))

    encoded = "".join(codes[character] for character in text)
    return encoded, codes


encoded, codes = huffman_encode("banana")
print(encoded)  # 100110110
print(codes)    # {'a': '0', 'b': '10', 'n': '11'}

Common Pitfalls

  • Empty input: Return an empty encoding and an empty mapping.

  • One distinct symbol: Use a non-empty code such as 0; otherwise decoding becomes ambiguous.

  • Metadata overhead: A real compressed format must store the code table or a reconstruction method.

  • Compression is not guaranteed: Very short or incompressible inputs may become larger because Huffman codes also need metadata and bit packing.

  • Greedy is problem-specific: Largest-first coin change fails for coins {1, 3, 4} and amount 6: it chooses three coins (4 + 1 + 1), while 3 + 3 uses two.

  • Tie handling: Different tie-breaking choices can produce different codes with the same optimal encoded length.

  • Interview follow-ups: Expect questions about prefix-free codes, weighted path length, decoding, bit packing, and why Huffman coding loses efficiency against arithmetic coding when symbol probabilities are not powers of 1/2.

36

How does Kruskal’s algorithm construct a minimum spanning tree?

Kruskal’s algorithm constructs a minimum spanning tree (MST) by repeatedly adding the cheapest edge that connects two different components. For a connected, weighted, undirected graph, the result is a spanning tree with the minimum possible total edge weight.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Greedy Choice and Correctness

The greedy choice is to select the lowest-weight edge whose endpoints are not already connected in the current forest.

This choice is safe by the cut property: because edges are processed in increasing weight order, a selected edge is a minimum-weight edge crossing the cut between one of its current components and the remaining vertices. It can therefore be included in some MST. Contracting that component leaves the same kind of MST problem, preserving optimal substructure.

A disjoint-set union (DSU) data structure efficiently detects whether an edge would create a cycle.

When a Similar Greedy Strategy Fails

For minimum-coin change with denominations 1, 3, and 4 and amount 6, choosing the largest coin first gives 4 + 1 + 1, using three coins, while 3 + 3 uses only two. Kruskal is protected by the cut property and its cycle-free feasibility constraint, so arbitrary greedy arguments do not transfer to problems such as 0/1 knapsack.

Algorithm

  1. Sort all edges by increasing weight.

  2. Initialize a DSU with one component per vertex.

  3. Process edges in sorted order:

  4. If their endpoints belong to different components, select the edge and merge the components.

  5. Otherwise, skip it because it would create a cycle.

  6. Stop after selecting V - 1 edges.

  7. If fewer than V - 1 edges can be selected, the graph is disconnected and has no MST.

For example:

Step Selected edge Weight Total weight
1 (1, 2) 1 1
2 (0, 1) 2 3
3 (2, 3) 2 5
4 (3, 4) 3 8

All five vertices are now connected with four edges, so the MST has weight 8.

Code Example

from collections.abc import Iterable

Edge = tuple[int, int, int]


class DisjointSet:
    def __init__(self, vertices: Iterable[int]) -> None:
        self.parent = {vertex: vertex for vertex in vertices}
        self.size = {vertex: 1 for vertex in self.parent}

    def find(self, vertex: int) -> int:
        # Iterative path compression avoids recursion-depth problems.
        while self.parent[vertex] != vertex:
            self.parent[vertex] = self.parent[self.parent[vertex]]
            vertex = self.parent[vertex]
        return vertex

    def union(self, first: int, second: int) -> bool:
        first_root = self.find(first)
        second_root = self.find(second)

        if first_root == second_root:
            return False

        # Attach the smaller component to the larger one.
        if self.size[first_root] < self.size[second_root]:
            first_root, second_root = second_root, first_root

        self.parent[second_root] = first_root
        self.size[first_root] += self.size[second_root]
        return True


def minimum_spanning_tree(
    vertices: Iterable[int],
    edges: Iterable[Edge],
) -> tuple[int, list[Edge]]:
    """Return an MST's total weight and edges, or raise if disconnected."""
    vertex_ids = set(vertices)
    edge_list = list(edges)

    for start, end, _ in edge_list:
        if start not in vertex_ids or end not in vertex_ids:
            raise ValueError("Every edge endpoint must be a known vertex")

    disjoint_set = DisjointSet(vertex_ids)
    sorted_edges = sorted(edge_list, key=lambda edge: edge[2])

    selected_edges: list[Edge] = []
    total_weight = 0

    for start, end, weight in sorted_edges:
        if disjoint_set.union(start, end):
            selected_edges.append((start, end, weight))
            total_weight += weight

            if len(selected_edges) == len(vertex_ids) - 1:
                break

    if len(selected_edges) != max(0, len(vertex_ids) - 1):
        raise ValueError("The graph is disconnected and has no spanning tree")

    return total_weight, selected_edges


example = minimum_spanning_tree(
    [0, 1, 2, 3, 4],
    [
        (0, 1, 2),
        (1, 2, 1),
        (1, 3, 4),
        (2, 3, 2),
        (0, 2, 3),
        (2, 4, 5),
        (3, 4, 3),
    ],
)

print(example)
# (8, [(1, 2, 1), (0, 1, 2), (2, 3, 2), (3, 4, 3)])

Complexity

Let V be the number of vertices and E the number of edges.

  • Best time: O(V + E α(V)) when edges are already sorted by weight, because Python 3.12’s Timsort processes an already sorted run in linear time and DSU operations take amortized O(α(V)) time.

  • Average and worst time: O(V + E log E). Sorting edges is the main cost; DSU operations take O(E α(V)) amortized time.

  • Space: O(V + E) for the DSU, copied edge list, and selected tree. The original input is not modified or counted.

Approach Time Space When to use
Kruskal with DSU O(V + E log E): sorting dominates; DSU is amortized O(E α(V)) O(V + E): copied edges, DSU, and selected tree Sparse or moderately sized undirected graphs
Prim with a binary heap O((V + E) log V): heap operations dominate O(V + E): graph representation and heap Dense graphs or when constructing the tree from one vertex

Common Pitfalls

  • Cycle handling: Skipping the DSU check can produce a cycle rather than a tree.

  • Stopping condition: An MST on V vertices contains exactly V - 1 edges; check this even when the graph is disconnected.

  • Disconnected graphs: Kruskal can produce a minimum spanning forest, but no single MST spans every vertex.

  • Empty and tiny graphs: Empty input returns weight 0; one vertex needs no edges. Self-loops are ignored, duplicate parallel edges are valid, and negative weights are supported.

  • Input mutation: The implementation sorts a copy, so the caller’s edge list is unchanged.

  • Other languages: Use a sufficiently wide integer type for total weights to avoid overflow.

  • Interview follow-ups: Be ready to explain the cut property, compare Kruskal with Prim, and discuss how DSU achieves amortized O(α(V)) operations.

37

What is a matroid and its relation to greedy algorithms?

A matroid is an abstract mathematical structure that generalizes linear independence and identifies a broad class of optimization problems for which a suitably ordered greedy algorithm produces an optimal solution. Its exchange property is the key reason that local, feasible choices can be combined into a global optimum.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Definition

A matroid is a pair (E, I), where E is a finite ground set and I is a family of subsets of E called independent sets. The family satisfies three axioms:

  • Empty-set axiom: The empty set belongs to I.

  • Hereditary axiom: If A belongs to I, every subset of A also belongs to I.

  • Exchange axiom: If A and B belong to I and |A| < |B|, some element x in B - A can be added to A while preserving independence.

A maximal independent set is called a basis. Every basis of a matroid has the same cardinality, called its rank.

Why Greedy Works

  • Greedy choice: For a maximum-weight basis, repeatedly select the highest-weight element that preserves independence; for a minimum-weight basis, process elements in ascending weight order instead.

  • Safety: If the greedy choice is absent from an optimal basis, the matroid exchange argument permits replacing an appropriate element without decreasing the total weight.

  • Optimal substructure: After adding an independent element, contracting the matroid by that element leaves another matroid, so the same reasoning applies recursively. Together with the hereditary axiom, this supports an inductive proof of optimality.

The theorem applies to objectives that select a maximum- or minimum-weight basis. It does not mean that every greedy-looking algorithm on a matroid is automatically correct; the ordering, feasibility test, and objective must match the theorem.

Common Examples

  • Graphic matroid: The ground set contains a graph’s edges, and an independent set is a set of edges containing no cycle. Kruskal’s MST algorithm is the direct matroid-greedy example. Prim’s algorithm also finds an MST using the related cut property, but it is not usually described as the direct greedy algorithm on the original edge-set matroid.

  • Linear matroid: The ground set contains vectors, and independent sets are linearly independent vector subsets.

  • Uniform matroid: Every subset of size at most k is independent. Any k elements form a basis.

  • Partition matroid: At most a specified number of elements may be selected from each of several groups.

Where Greedy Fails

Not every optimization problem has the required exchange property.

Problem Greedy result Better result Reason
Coin change with {1, 3, 4}, target 6 4 + 1 + 1 uses 3 coins 3 + 3 uses 2 coins Unlimited coin solutions are multisets with repetition, so the set-matroid exchange argument does not apply directly
0/1 knapsack Capacity 10; item A = (weight 6, value 12) is selected by value-to-weight ratio Items B = (5, 9) and C = (5, 9) give value 18 instead of 12 Feasible item sets do not generally satisfy exchange

For the knapsack example, {A} and {B, C} are feasible and |{A}| < |{B, C}|, but neither B nor C can be added to {A} without exceeding capacity 10. Thus the exchange axiom fails.

Complexity

Let n = |E|. With an O(1) independence test and comparison sorting, the greedy algorithm takes O(n log n) average and worst-case time because sorting dominates the at most n feasibility checks. Its best case is O(n) when the elements are already ordered and sorting can be skipped.

If each independence check costs O(r), the total is O(n log n + nr), which can become O(n²) for a naive check. Space is O(n) auxiliary, excluding the input, for the ordered candidates and selected set; there is no recursion stack. Counting the input itself, total space remains O(n).

Interview Tips

  • Identify the ground set, the proposed independent sets, and the weight function before invoking the matroid theorem.

  • Verify the exchange axiom rather than assuming that “choosing the best item” is sufficient.

  • State whether the objective is a minimum- or maximum-weight basis and explain the corresponding sort order.

  • Distinguish Kruskal’s direct graphic-matroid greedy algorithm from Prim’s cut-property algorithm.

  • Treat coin change, 0/1 knapsack, and shortest paths as common warning examples: local choices can fail when the exchange property or required optimality conditions are absent.

38

How do greedy algorithms make safe moves?

A safe move is a greedy choice that preserves the possibility of completing the problem with an optimal solution. Greedy algorithms are correct only when each local choice has the greedy-choice property and the remaining problem retains the required optimal substructure.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Greedy Choice and Safe Moves

A greedy algorithm repeatedly selects the candidate that appears best according to a simple rule. For example, interval scheduling selects the compatible activity with the earliest finishing time.

The greedy choice is safe when there exists an optimal solution containing that choice. Merely making a feasible move or improving the current state is not enough: the move must not eliminate all optimal completions.

A safe move therefore connects two ideas:

  • Greedy choice: which candidate to select now.

  • Safe move: proof that selecting it still permits an optimal result.

Why a Greedy Choice Can Be Safe

Two common proof techniques establish safety:

  1. Greedy-choice property

  2. Show that the locally preferred candidate can belong to an optimal solution.

  3. Then solve the smaller remaining problem using the same reasoning.

  4. Exchange argument

  5. Begin with an optimal solution that does not contain the greedy choice.

  6. Replace an appropriate candidate with the greedy choice.

  7. Show that feasibility is preserved and the objective does not become worse.

For example, in interval scheduling, let A be the activity that finishes earliest. In any optimal schedule, the first activity B cannot finish before A. Replacing B with A leaves at least as much time for later activities, so the schedule remains feasible and has the same number of activities. Thus, choosing A is safe.

A small example illustrates the selection:

Activities (start, finish) Greedy selection Result
A(1, 3), B(2, 5), C(3, 7), D(6, 8) A, then C (an activity may start when the previous one finishes) Selects 2 activities

When Greedy Fails

A locally attractive choice is not automatically safe. Consider coin change with denominations 1, 3, and 4 and amount 6:

Strategy Coins selected Number of coins
Always choose the largest coin 4 + 1 + 1 3
Optimal selection 3 + 3 2

Choosing 4 is feasible and improves the remaining amount, but it is not safe because it prevents the optimal completion. This demonstrates why a greedy algorithm needs a proof rather than an intuitive preference.

Complexity

Greedy algorithms have no single universal complexity because it depends on how candidates are generated, sorted, and processed. A typical interval-scheduling implementation has:

  • Time: O(n log n) worst and average because sorting is the main cost; O(n) best when the input is already sorted.

  • Space: O(n) auxiliary space for a sorted copy and sorting workspace; O(1) additional space for the selection scan. The input itself is not counted.

A greedy implementation that avoids sorting can be linear, but only when the required choice can be identified in one pass.

Common Pitfalls

  • Assuming every greedy choice is safe: A heuristic may work on many inputs but fail on edge cases.

  • Maximizing only the immediate benefit: The best current value can cause a worse final result.

  • Skipping the exchange argument: State clearly why an optimal solution can be modified to include the greedy choice.

  • Ignoring ties: Multiple equally good candidates may lead to different remaining subproblems.

  • Overlooking edge cases: Empty input, one candidate, duplicate values, and tied finishing times or costs should be considered.

  • Mutating the original input: Sorting a copy makes the original easier to reuse and reason about.

In interviews, expect a follow-up asking for the greedy-choice property, an exchange argument, or a counterexample showing when the same strategy fails.

39

How do greedy approximation algorithms find near-optimal solutions?

Approximation algorithms use fast, often greedy decisions to produce a solution whose cost or quality is provably close to the optimum when finding the exact optimum is computationally hard. The key distinction is that an approximation algorithm has a guaranteed approximation ratio, whereas an ad hoc greedy heuristic has no such guarantee.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

For a minimization problem, an approximation ratio of (c ge 1) means:

[ operatorname{ALG} le c cdot operatorname{OPT} ]

For a maximization problem, the guarantee is usually:

[ operatorname{ALG} ge frac{operatorname{OPT}}{c} ]

A greedy algorithm repeatedly makes the locally best choice. Its correctness does not come from that choice always being globally optimal. Instead, a proof must establish that each choice preserves a guarantee relative to the remaining problem.

Greedy Choice and Safety

Greedy choice: In set cover, repeatedly select the candidate set covering the largest number of currently uncovered elements.

Let (k) be the number of sets in an optimal solution and (U) the currently uncovered elements. The optimal solution’s (k) sets collectively cover (U), so at least one covers at least (|U|/k) uncovered elements. The greedy choice covers at least that many, leaving:

[ |U_{text{next}}| le left(1-frac{1}{k}right)|U| ]

Starting with (n) elements, after (t) selections:

[ |U_t| le nleft(1-frac{1}{k}right)^t ]

After (kH(n)) selections, this is less than one element, where (H(n)=1+frac12+cdots+frac1n). Therefore, greedy set cover is an (H(n))-approximation. The residual problem has the same form on a smaller universe, providing the required subproblem structure; it need not preserve an exact optimum.

Representative Strategies

Problem Greedy choice Result Dominant complexity
Set cover Cover most new elements (H(n))-approximation (O(mnmin(m,n))) for the shown implementation
Interval scheduling Select earliest-finishing activity Exact optimum (O(nlog n)), mainly sorting
Fractional knapsack Select highest value-to-weight ratio Exact optimum (O(nlog n)), mainly sorting
Vertex cover Select maximum-degree vertex (O(log Delta))-approximation (O((n+m)log n)) with a degree heap

For exact greedy algorithms such as interval scheduling, an exchange argument establishes optimality: replacing the first activity in an optimal schedule with the earliest-finishing compatible activity cannot reduce the time available for later activities.

Code Example

The following implementation returns the indices of the greedily selected sets:

def greedy_set_cover(
    universe: frozenset[str],
    candidate_sets: list[set[str]],
) -> tuple[list[int], int]:
    """Return selected set indices and their count using greedy set cover."""
    uncovered = set(universe)
    selected: list[int] = []

    while uncovered:
        best_index: int | None = None
        best_gain = 0

        for index, candidate in enumerate(candidate_sets):
            gain = len(candidate & uncovered)
            if gain > best_gain:
                best_gain = gain
                best_index = index

        if best_index is None:
            raise ValueError("Candidate sets do not cover the entire universe")

        selected.append(best_index)
        uncovered.difference_update(candidate_sets[best_index])

    return selected, len(selected)


universe = frozenset({"a", "b", "c", "d", "e", "f"})
candidate_sets = [
    {"a", "b", "c"},
    {"d", "e", "f"},
    {"b", "c", "d", "e"},
]

print(greedy_set_cover(universe, candidate_sets))  # ([2, 0, 1], 3)

The example selects three sets, while sets 0 and 1 cover the universe in two. Thus the result is near-optimal but not exact.

Complexity and Edge Cases

Approach Time Auxiliary space When to use
Greedy set cover above Best (Theta(n+m)) for nonempty input; average data-dependent; worst (O(mnmin(m,n))) (O(n)), input excluded; recursion stack (O(1)) Larger instances needing a guarantee
Exhaustive exact set cover (O(2^m mn)) (O(m+n)), input excluded Very small numbers of candidate sets

Here, (n) is the universe size and (m) is the number of candidate sets. The implementation handles an empty universe, one-element universes, duplicates, overlaps, and ties by selecting the lowest index. It raises ValueError when coverage is impossible. Numeric ordering, sorted input, disconnected graphs, and cycles are not applicable to set cover.

Common Pitfalls

  • Assuming greedy means optimal: A greedy result needs an approximation proof or exchange argument.

  • Ignoring sorting costs: For many greedy problems, sorting dominates at (O(nlog n)).

  • Using a failing greedy strategy: With denominations 1, 3, 4 and amount 6, choosing 4 first gives three coins, while 3 + 3 gives the optimum of two.

  • Mutating inputs unnecessarily: The implementation copies the uncovered elements and leaves the input sets unchanged.

  • Typical follow-up: Interviewers commonly ask for the approximation ratio, a counterexample, and the greedy-choice proof.

40

How does a greedy algorithm solve the Gas Station problem?

A greedy algorithm finds a valid starting station in one pass by tracking the total fuel surplus and the surplus from the current candidate start. If the current trip runs out of fuel, it moves the candidate start to the next station.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Greedy Choice and Why It Works

Greedy choice: Keep station start as the current candidate, and replace it with i + 1 whenever the accumulated fuel from start through station i becomes negative.

This choice is safe by an elimination argument. Before the failure at i, every prefix from the current candidate is nonnegative. Therefore, for any station j between start and i, the fuel surplus from j through i is also negative. None of those stations can be a valid start, so discarding them cannot eliminate a solution.

At the end, a valid start exists exactly when total gas is at least total cost. The remaining candidate can then complete the circular route.

Algorithm

For each station, calculate:

net = gas[i] - cost[i]

Maintain:

  • total_tank: net fuel across the entire route.

  • current_tank: net fuel from the current candidate start.

  • start: the candidate starting index.

If current_tank becomes negative, set start = i + 1 and reset current_tank to zero.

Example walkthrough

For gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2]:

Station i Net fuel Total fuel Current fuel Candidate start
0 -2 -2 -2 1
1 -2 -4 -2 2
2 -2 -6 -2 3
3 3 -3 3 3
4 3 0 6 3

The final answer is station 3.

Complexity

  • Time: O(n) best, average, and worst case, because every station must be examined to guarantee correctness.

  • Auxiliary space: O(1), excluding the O(n) input storage. No recursion or additional collections are used.

Code Example

from collections.abc import Sequence


def gas_station(gas: Sequence[int], cost: Sequence[int]) -> int:
    """Return a valid starting station, or -1 if no circular route exists."""
    if len(gas) != len(cost):
        raise ValueError("gas and cost must have the same length")
    if not gas:
        return -1

    total_tank = 0
    current_tank = 0
    start = 0

    for i in range(len(gas)):
        net_fuel = gas[i] - cost[i]
        total_tank += net_fuel
        current_tank += net_fuel

        if current_tank < 0:
            start = i + 1
            current_tank = 0

    return start if total_tank >= 0 else -1


print(gas_station([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))  # 3

Why the Same Heuristic Can Fail Elsewhere

For a related minimum refueling stops problem, choosing the first reachable station is not always optimal. Suppose the initial fuel range is 10 miles, a station at mile 2 adds 1 gallon, a station at mile 5 adds 10 gallons, and the target is mile 16. Refueling at mile 2 requires another stop, while refueling directly at mile 5 reaches the target in one stop. The correct general solution uses a max-heap to select the largest available refill retroactively.

Common Pitfalls

  • Off-by-one error: The next candidate is i + 1, not i.

  • Ignoring total fuel: A locally successful candidate is not enough; total_tank must also be nonnegative.

  • Length mismatch: Always verify that gas and cost contain paired station values.

  • Integer overflow: In fixed-width languages, store the accumulated fuel surplus in a sufficiently wide type, commonly a 64-bit integer.

  • Edge cases: Empty input returns -1; one station returns 0 when fuel is sufficient; negative net fuel values are valid; duplicate values need no special treatment.

  • No sorting needed: Station order is already circular and must be preserved.

  • Input mutation: The implementation only reads the input sequences and does not reorder or modify them.

41

How to solve Majority Element in one pass with constant space?

Use the Boyer–Moore majority vote algorithm to find the majority element in one pass with constant additional space. This solution assumes a majority is guaranteed to exist, meaning one element appears strictly more than n / 2 times.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Greedy choice: Keep one candidate and cancel it against every different value encountered.

  • Why it is safe: Conceptually, canceling two different elements preserves the identity of a strict majority. If one canceled element is the majority, the majority and total element counts both decrease by one; if neither is the majority, the majority only becomes stronger relative to the remaining elements.

  • Optimal substructure: Each cancellation leaves a smaller sequence with the same majority property, so the argument can be applied repeatedly until only the majority remains.

  • Counterexample where greedy fails: The coin change problem with coins [1, 3, 4] and amount 6: greedy chooses 4+1+1 (3 coins) but the optimal is 3+3 (2 coins), showing that greedy choice is not universally safe.

The algorithm maintains two variables:

  • candidate: The current possible majority element.

  • balance: The number of unmatched occurrences of candidate.

For each value:

  1. If balance is zero, select the current value as the new candidate.

  2. If the value equals the candidate, increment balance.

  3. Otherwise, decrement balance, effectively canceling two different elements.

Because a strict majority exists, the final candidate must be the majority element.

Complexity

For an input containing n elements:

  • Time: Best case O(n), average case O(n), and worst case O(n) because every element is examined once.

  • Auxiliary space: O(1). The input is not counted, and there is no recursion stack.

  • Total space including the input: O(n).

Approach Comparison

Approach Best Time Average Time Worst Time Space When to Use
Pairwise frequency checks O(n²) O(n²) O(n²) O(1) Only for small inputs
Dictionary frequency counts O(n) O(n) O(n²) with pathological hash collisions O(n) When the majority is not guaranteed
Boyer–Moore voting O(n) O(n) O(n) O(1) When a majority is guaranteed

Sorting is unnecessary because it would make the sorting step the main O(n log n) cost.

Example Walkthrough

Input: [2, 2, 1, 1, 1, 2, 2]

Value Action Candidate Balance
2 Start candidate 2 1
2 Match 2 2
1 Cancel 2 1
1 Cancel 2 0
1 Start candidate 1 1
2 Cancel 1 0
2 Start candidate 2 1

The final candidate is 2, which occurs 4 times among 7 elements.

Code Example

from collections.abc import Sequence


def majority_element(values: Sequence[int]) -> int:
    """Return the guaranteed strict majority using one pass and O(1) space."""
    if len(values) == 0:
        raise ValueError("Input must contain at least one element")

    candidate = values[0]
    balance = 0

    for value in values:
        if balance == 0:
            candidate = value
            balance = 1
        elif value == candidate:
            balance += 1
        else:
            balance -= 1

    return candidate


print(majority_element([2, 2, 1, 1, 1, 2, 2]))  # 2

Common Pitfalls

  • No guaranteed majority: For [1, 2, 3], the algorithm returns 3, although no element occurs more than n / 2 times. If existence is uncertain, a second pass is required to count the candidate, making it a two-pass algorithm.

  • Empty input: The implementation raises ValueError; the problem itself normally guarantees a nonempty input.

  • Single-element input: The only element is returned correctly.

  • Duplicates and negative numbers: Both work because the algorithm relies only on equality, not ordering or positivity.

  • Already sorted input: Sorting has no effect on correctness or complexity.

  • Mutating the input: This implementation does not modify the input.

  • Interview follow-up: Interviewers commonly ask why one pass is sufficient, how you would verify an uncertain candidate, and how the algorithm changes if two elements could each occur more than n / 3 times.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 41 Greedy Algorithms answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects