An unfamiliar requirement is written in business language; how do you check whether it is a known hard problem in disguise?
answer
- the domain nouns are the disguise
- objects, relation, objective
- state the decision version, with k
- cover, pick, pair, or order
- a match is a hypothesis, not a proof
basics
~20 sStrip the domain nouns and restate the requirement as objects, a relation between them, and an objective. That skeleton — cover everything, pick a subset under a budget, order with no repeats — is what you match against the known catalogue.
solid answer
~50 sI rewrite the sentence with the business words removed. Promo codes, shifts and delivery windows all become **items**; customers, links and stops become **elements**; "must reach", "must not overlap" and "must follow" become a relation. Then I state the objective in its decision form — *is there a selection of at most k items satisfying the relation?* — because that is the form in which known results are written. At that point the skeleton usually looks like one of a handful of families: cover every element with as few chosen items as possible, choose a subset under a budget to maximise value, or arrange everything in an order with no repeats. Saying which one it looks like, out loud, is the move the interviewer is scoring. It is a hypothesis about the problem, not yet a proof about it.
go deeper
Be able to restate a requirement without its business nouns and say which shape it has: cover everything, choose a subset, pair things up, or order them. Naming the shape is the whole expectation here.
Explain how you reach the decision version with a threshold k, and why that form is the one known results are written in. Show that you can spot the easy family too, not only the frightening ones.
Show the habit under pressure: the rewrite happens in the spike, the candidate name goes in the plan document, and the assumption about input size is recorded as a guard rather than a memory.
Make the rewrite a team norm rather than a personal trick. The cost you are managing is a design committed before anyone asked what the problem was, which is expensive to reverse once a schedule depends on it.
## Why the rewrite comes first Requirements arrive in the language of the business: "pick the cheapest set of delivery windows so every order gets one", "assign each engineer to one on-call slot", "find the shortest tour of every depot". The domain nouns are the disguise. Two requirements that read nothing alike can be the same mathematical object, and two that read almost identically — one asking for pairs, one asking for triples — can sit on opposite sides of the tractability line. Until the nouns are gone you are comparing stories, not structures, and you cannot tell which case you are in. This is the first ten minutes of a planning spike, before any code exists. The output is not an algorithm. The output is a **name**, or an honest "it resembles nothing I know". ## The rewrite, step by step 1. **Neutralise the nouns.** Everything you are choosing becomes an *item*; everything that must be satisfied becomes an *element*; everything that connects them becomes an *edge* or a *constraint*. Keep a one-line glossary so you can translate back. 2. **Name the relation.** Does an item *cover* elements? *Conflict* with other items? *Follow* another item in a sequence? *Pair* with exactly one element? 3. **Name the objective.** Minimise a count, maximise a total value, or merely decide whether anything feasible exists at all. 4. **State the decision version.** Convert "find the cheapest" into "is there one of cost at most k?". Hardness results are stated for that yes/no form, and the two forms are linked — you can search over k — so matching either is enough for triage. ## Skeletons worth recognising | Skeleton | Wording you actually see | Known family | |---|---|---| | Cover every element with as few chosen items as possible | "every segment must receive at least one", "every link must be watched" | Set Cover, Vertex Cover | | Choose a subset under a budget, maximising value or hitting a total | "fit the most valuable jobs in the window", "reach exactly this amount" | Knapsack, Subset Sum | | Choose items that mutually conflict with none of the others | "no two selected bookings may overlap" | Independent Set | | Order everything, visiting each once, cheaply | "a route through every depot, back to the start" | Hamiltonian cycle, Travelling Salesman Problem | | Pair each of these with one of those | "each engineer gets one slot, each slot one engineer" | bipartite matching — the routinely easy one | The last row matters as much as the others. A requirement that *sounds* combinatorial because it mentions assignment is often plain pairing, which has polynomial algorithms. Recognising the easy family is half the value of the exercise. ## What the match establishes, and what it does not - It establishes a **working hypothesis** about the general case, strong enough to plan around and cheap enough to state in a spike. - It does **not** prove hardness. A proof embeds a known hard problem inside yours, and that is a separate obligation you take on only if someone disputes the plan. - It says nothing about *your* instances. Hardness is a statement about the worst case across all inputs; the inputs you will actually receive may be small, structured, or both. - It does not survive a changed requirement. Drop one clause and the skeleton can change family, so re-run the rewrite whenever the requirement moves. ## Where the triage goes wrong - **Coding first.** Once an approach is on the whiteboard, everyone argues about the approach instead of the problem, and the match never happens. - **Keeping the nouns.** "Delivery window" carries connotations that suppress the pattern; "item covering elements" does not. - **Treating resemblance as proof.** Two problems can share a shape and differ in the one clause that decides feasibility — a bound of two rather than three, an input that happens to be a tree. - **Assuming novelty.** Most business requirements are decades-old problems in new clothing; the prior should be "this is known", not "this is new". - **Calling anything with many combinations exponential.** Sorting explores an enormous space of permutations and is cheap; the size of the search space alone predicts nothing.
- The skeleton matches a hard problem, but the real inputs will always be tiny. Does the match still matter?Yes, and it changes what you write down. The match tells you the growth is the risk and that the small bound is load-bearing, so it stops being an incidental fact and becomes a recorded assumption with a guard that fails loudly when a caller exceeds it.
- How do you tell whether you have matched the optimisation version or the decision version of a problem?The decision version asks a yes/no question against a threshold — is there a solution of cost at most k — while the optimisation version asks for the best value. Published hardness results are almost always stated for the decision version, and the two are linked by searching over k, so matching either one is enough to triage.
- What do you do when the skeleton matches nothing you recognise?Say so plainly, then attack the parts. Split the objective from the constraints and match each separately; a requirement is often a routine structure with one hard clause bolted on, and isolating that clause is more useful than a verdict on the whole.
A mechanic hearing "it whines when I turn left" is matching a description to a known fault before touching a tool — the name decides which page of the manual applies, and it is still a hypothesis until a test confirms it.
saying these in an interview costs you the question
- Starts designing an algorithm before naming the problem
- Treats a resemblance to a known hard problem as a proof of hardness
- Assumes an unfamiliar business requirement must be a new problem
- Keeps the domain nouns, so the structure stays hidden
- Calls anything with many possible combinations exponential