Skip to content
Tech Interview Prep
Technical interview guide

Greedy Algorithms

Making the locally-best choice at each step and never revisiting it: correct only when the problem has the right structural guarantee.

Read
42 min
Practice MCQs
25
Interview Q&A
25
Edition
v7
Editorial status
Reviewed

Scope: Language-neutral, with sorting and priority-queue behaviour cited from CPython 3.14.

Curated: · Written: · Reviewed:

25 questions

MCQ-7A vending machine's change routine repeatedly takes the largest coin that fits from the denominations {1, 3, 4}. A customer is owed 6 units; the machine dispenses 4 + 1 + 1. Which statement about this run is correct?
MCQ-1A payments service makes change from coins of 1, 3 and 4 units. Its algorithm is greedy: repeatedly take the largest coin that does not exceed the remaining amount. An engineer proposes shipping it, claiming the rule is correct for this coin set. For a 6-unit payment, which statement is correct?
MCQ-20A team's greedy rule for minimum coin change always takes the largest denomination not exceeding the remaining amount. With denominations {1, 3, 4}, they exhaustively check every amount from 1 to 5 against a dynamic-programming optimum; all five match, so they ship the rule. Which statement about the rule is correct?
MCQ-24A change-making service pays out 6 units using coins of 1, 3 and 4 units. Its rule takes the largest coin that fits at each step, so it returns 4+1+1. Its test suite asserts only that the returned coins sum to 6 and that each is a legal denomination, and the suite passes. Which statement about this run is correct?
MCQ-19A maintenance window of exactly 6 slots must be filled with jobs of size 4, 3 or 1, using the fewest jobs possible. The greedy rule take the largest job that still fits produces 4 + 1 + 1. Which conclusion follows for this window?
MCQ-13A scheduler must admit the maximum number of non-overlapping jobs from a batch of n candidate intervals, and the implementation sorts once before a single linear scan. Which statement describes the sort key the standard greedy requires and the reason the alternatives do not produce a maximum-size set?
MCQ-4A single-machine batch runner picks a non-overlapping set from a nightly queue of (start, end) hour pairs. It scans in start-time order and takes each job whose start is at or after the previous job's end. Last night's queue was (0,10), (1,3), (2,5), (3,6), (6,8). How many jobs did the runner schedule, and how many could it have scheduled at most?
MCQ-3A team proves their earliest-finish-time scheduler is optimal. For jobs A=[0,3], B=[2,5], C=[4,6], D=[5,8] the greedy schedule is {A, C}, and they take OPT = {B, D}. Their proof swaps A in for D, giving {A, B}, and concludes that some optimum contains A. A reviewer rejects the proof. Which statement is correct?
MCQ-5A nightly batch runs on a pool of identical workers. Each job holds one worker for its whole interval, jobs cannot be moved or split, and the pool must be big enough that no job ever waits. Intervals are half-open, so a job ending at minute 3 frees its worker for one starting at minute 3. The five jobs, in minutes from the batch start, are [0,8), [1,3), [2,4), [3,5) and [4,6). What is the smallest pool that runs them all without queueing?
MCQ-11A weighted undirected graph has vertices A, B, C, D, E and edges A–B (2), B–D (3), A–C (4), C–D (5), D–E (6), B–C (7), C–E (8), A–E (9). Consider the cut that separates S = {A, B} from T = {C, D, E}. Which edge does the cut property guarantee belongs to every minimum spanning tree of this graph?
MCQ-10A codec must encode a five-symbol alphabet with probabilities 0.35, 0.17, 0.17, 0.16 and 0.15. The code must be prefix-free, and its expected codeword length must be the minimum achievable for these probabilities. Which construction meets both requirements?
MCQ-12A team's Dijkstra implementation runs from source s on a directed graph with no negative-weight cycle, where every edge is positive except (d, e) with weight -4. It uses a binary heap with lazy deletion and runs until the priority queue is empty. On one input it reports dist[e] = 5, but the true shortest path to e is s → a → d → e with weight 2. Which mechanism explains why the reported value is wrong?
MCQ-14A single machine must process four jobs. Processing times and weights: A p=2 w=10; B p=5 w=10; C p=1 w=1; D p=4 w=2. The objective is to minimize total weighted completion time. What is the minimum total weighted completion time?
MCQ-15A CPU scheduler must run six tasks: four copies of A, one B and one C. Two copies of the same task must be separated by at least two other slots. The scheduler keeps a max-heap of remaining copy counts and, at each slot, runs the task with the most copies left that is not cooling down; if none is eligible, it idles. How many slots does the schedule take?
MCQ-6A cargo bike can carry 12 kg. Three crates, none splittable: X is 4 kg worth $30, Y is 5 kg worth $33, Z is 7 kg worth $42. A dispatcher loads by value per kg, highest first, skipping any crate that no longer fits. What does the bike carry, and what is the best possible?
MCQ-2A candidate argues that because the zero-one knapsack has optimal substructure, the density-ordered greedy rule is optimal for it. Test the argument on three items (A(value 60, weight 10), B(value 100, weight 20), C(value 120, weight 30)) with capacity 50. What does the rule return, and what does the instance show about the argument?
MCQ-25A capacity-10 knapsack must be packed with whole items only: X weighs 6 and is worth 6, Y weighs 5 and is worth 4.9, Z weighs 5 and is worth 4.9. A teammate sorts by value density, takes the best item that fits, and calls the result optimal because the problem 'has the greedy shape'. Which statement about this instance is correct?
MCQ-21An order-batching service packs a 10-slot batch by solving 0/1 knapsack greedily: sort items by value/weight ratio descending, break ties by input order, take each item that still fits. The queue is A(weight 6, value 12), B(weight 5, value 10), C(weight 5, value 10), in that order, and the packer returns 12. Reordering the same three items to B, C, A makes it return 20. Which statement correctly explains the two results?
MCQ-8A Jump Game I checker scans indices left to right with a single integer `reach`, the furthest index known to be reachable, and must return the right answer on every input: for example nums = [1,0,0] (unreachable) and nums = [1,1,1,1] (fully traversable). Which loop body is correct?
MCQ-9In the jump game, a[i] is the maximum forward jump length from index i, and the goal is to reach the last index. For a = [2, 3, 1, 1, 2, 1, 3, 1, 1, 1] (indices 0 through 9), what is the minimum number of jumps from index 0 to index 9?
MCQ-16A delivery van must complete one loop of five stations. Station i supplies gas[i] litres and the leg from station i to the next costs cost[i] litres, with gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2]. The tank starts empty, refuelling happens only at stations, and the van must never run dry. Which starting station (1-indexed) completes the loop?
MCQ-17An EV must complete a circular route through four charging stations. Station i provides charge[i] kWh and the leg from station i to the next costs cost[i] kWh. The arrays are charge = [3, 1, 2, 2] and cost = [4, 2, 1, 3]. A greedy scan starts at station 0, and whenever the running battery goes negative it restarts at the next station; it ends with a candidate start index. What should the function return?
MCQ-22A job scheduler assigns each job, on arrival, to the machine with the smallest current load. On a 3-machine cluster, jobs arrive in the order 1, 1, 1, 1, 1, 1, 3 (minutes of work). The scheduler finishes in 5 minutes; an offline scheduler that sees all jobs in advance finishes in 3. The lead calls the 5-minute result a bug. Which assessment is correct?
MCQ-18A capacity plan must cover 1,000 distinct required capabilities, and each vendor bundle covers a subset of them. Greedy selection, repeatedly take the bundle covering the most still-uncovered capabilities, returns 21 bundles. An offline ILP solver run on the same instance proves the optimum is 3 bundles. What does this tell the team?
MCQ-23A team runs steepest-ascent hill climbing (best-improvement, single-bit flips) from state 000 on this objective over 3-bit strings: f(000)=0, f(001)=1, f(010)=4, f(011)=9, f(100)=5, f(101)=2, f(110)=6, f(111)=3. What does the run return?