Coding

Greedy based

Asked at

Oracle

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01State the optimization objective and identify the local choice being proposed
02Test the choice against counterexamples before coding
03Give an exchange argument or stays-ahead proof for why an optimal solution can make that choice
04Sort or use the stated priority structure, then maintain the feasibility invariant
05Contrast it with dynamic programming when optimal substructure alone does not justify greediness

Reference answer

“Greedy based” is underspecified, so first ask for the objective, constraints, and whether choices are reversible. A greedy solution is not “take the largest” by instinct; it needs a locally safe choice and a proof. Describe the candidate rule, then use an exchange argument: take an optimal solution that differs at the first choice and show replacing that choice with the greedy one does not hurt feasibility or objective value. After the rule is justified, sort or prioritize the input, maintain a clear invariant, and explain exactly when an item is accepted or discarded. If you cannot prove the rule, say so and consider dynamic programming, a heap, or a graph formulation instead. Test ties, empty input, infeasible items, and cases designed to defeat a tempting local rule. Typical sorting-based greedy solutions cost O(n log n), but the correct complexity depends on the confirmed problem.

Then expect these follow-ups

What constraint would change your chosen approach?
Tests: constraint adaptation
How would you test the edge cases before implementation?
Tests: implementation extension

Hiring now

Get the Oracle interview, not just the prep

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Or practice this question first

Next question