Micro-questions over the selection and scheduling module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. Hire K workers
1. State the problem.
Answer
Hire people. Each has a quality and a minimum wage. Everyone hired is paid the same rate per unit of quality, and nobody may be paid below their own minimum. Which cost least in total?
2. What is the instinctive answer, and why is it wrong?
Answer
“Take the cheapest advertised wages.” Wrong because one expensive-per-unit person raises the rate for everybody.
3. Work the example: A(10, 70), B(20, 140), C(5, 60), .
Answer
Ratios 7.00, 7.00, 12.00. A+B = . A+C = . B+C = . A+C wins, despite containing the worst rate.
4. Why does the cheap rate of A+B lose?
Answer
B’s high quality. You pay for quality you do not need.
5. State the whole difficulty in one sentence.
Answer
The cost of a group is not the sum of its members’ costs — it is a product of two things that pull in opposite directions.
6. Give the cost formula.
Answer
7. Say it in words.
Answer
The bill is the group’s worst rate multiplied by the group’s total quality. One person sets the price; everyone contributes to the volume.
8. Give the greedy in five steps.
Answer
- Sort everyone by ratio, ascending.
- The worker you are at has the largest ratio seen so far, so they set the rate.
- Given that rate, you want the smallest qualities among those seen.
- Maintain them with a max-heap of size — push, and pop the largest when it exceeds .
- Once the heap holds exactly , candidate cost =
rate × sum_of_heap. Keep the minimum.
9. Why is it correct?
Answer
Every group has some member with the maximum ratio. Fixing that member fixes the rate, leaving only the choice of which others — for which you obviously want the smallest qualities. Iterating over every possible rate-setter considers every group that could be optimal.
10. What is the cost?
Answer
to sort plus to sweep.
11. How often is “take the cheapest wages” wrong?
Answer
130 of 400 random instances — nearly a third. Not an exotic corner case.
B. Interval scheduling
12. State the problem.
Answer
Given meetings with start and end times, fit in as many non-overlapping meetings as possible.
13. Which sort key is correct?
Answer
Earliest END time.
14. Why does earliest START fail?
Answer
It takes the meeting running 0–10 and is then blocked for the whole day — one meeting instead of two.
15. Why does shortest DURATION fail?
Answer
On [(0,5),(4,6),(5,10)] the short middle meeting blocks both long ones — one instead of two.
16. What is the testing lesson here?
Answer
Shortest-duration ties with the correct answer on the first example and fails on the second. Each wrong key fails on some input and ties on others; only “earliest end” survives both.
17. Give the exchange argument.
Answer
Let be the earliest-finishing meeting. Take any optimal solution sorted by end time; ends no later than , so replacing with leaves every later meeting still compatible. The modified set is valid and the same size, so still optimal. Recurse.
18. State the intuition in one sentence.
Answer
Finishing earliest leaves the most room for everything else, and nothing is lost by preferring it.
C. Select the most vs cover them all
19. What is the opposite problem, over the same input?
Answer
How many rooms do you need to hold all of them? Section 2 discards conflicting meetings; this one pays for them.
20. What is the answer?
Answer
The peak number of simultaneous meetings.
21. Describe the sweep.
Answer
Build events: at every start, at every end. Sort so that precedes at the same instant. Accumulate and track the maximum.
22. Why must precede ?
Answer
A meeting ending at 10 and another starting at 10 need one room, not two.
D. Traps
23. What problem shape has the “worst member sets the price” structure?
Answer
Any problem where one member’s constraint applies to the whole group. The naive per-member sum is wrong there.
24. Why negate when using Python’s heapq here?
Answer
heapq is a min-heap, and in the hiring sweep you are discarding the largest qualities — so the heap must surrender its maximum. Negation inverts it.
25. What is the floating-point ratio trap, and the fix?
Answer
Two candidates with equal ratios can compare unequal after division. Compare against to stay in integers.
26. Hire-K is greedy. What similar-looking problem is not?
Answer
The assignment problem — one person per job, each pair with its own cost. Greedy is wrong for it; it needs the Hungarian algorithm or min-cost max-flow.
27. What should you do if you cannot write the exchange argument?
Answer
Use dynamic programming. A greedy that passes your tests without an argument is a guess — slower and correct beats fast and wrong.
28. Summarise the module in one sentence.
Answer
The sort key is the greedy algorithm — and choosing it correctly means proving an exchange argument, not testing one example.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Selection & Scheduling — the module
- When Greedy Works — Question Bank
- Overlapping Intervals — the pattern
Software engineering
Infrastructure & security
Computer science
Hardware & engineering