skip to content

A wiring plan lists the link count each machine must end with - which checks decide whether it is buildable?

level: seniorimportance: should knowfreq 33%

answer

  1. two cheap screens, then a real test
  2. no demand may exceed available peers
  3. even total, or nothing to build
  4. feed the hungriest machine first
  5. necessary conditions are not sufficient

basics

~20 s

Three screens rule plans out: every listed count must be between 0 and one less than the fleet size, and the counts must sum to an even number. Those are necessary only; a recursive reduction decides the rest.

solid answer

~40 s

Run the cheap screens first. Every listed degree must lie between `0` and `n - 1`, since a machine has only that many distinct peers, and the degrees must sum to an even number, because the sum equals twice the link count. Both are **necessary and neither is sufficient** - `3, 3, 3, 1` on four machines clears both and is still unbuildable, since three machines of degree 3 must each link to all the others, forcing the fourth to degree 3 rather than 1. The decisive test is a recursive reduction: repeatedly take the largest remaining demand `d`, delete it, and subtract one from the next `d` largest entries. The list is realisable exactly when this reaches all zeros without ever going negative or running short of partners.

code

pseudocode · 14 lines
pseudocode
function is_buildable(demands):
    # simple mesh: no self-links, no duplicate links
    loop:
        sort demands descending
        drop trailing zeros from demands
        if demands is empty:
            return true
        d = remove_first(demands)
        if d > length(demands):
            return false            # not enough partners left
        for i = 0 to d - 1:
            demands[i] = demands[i] - 1
            if demands[i] < 0:
                return false        # a machine asked to over-give

go deeper

for a junior

Know the two quick screens: no machine may be asked for more peers than the fleet minus one, and the demands must add to an even number. Either breach means the plan cannot be built.

for a middle

Explain why those screens are necessary but not sufficient, using a small list that clears both and still fails. Describe the reduction that repeatedly satisfies the hungriest machine.

for a senior

Read a failure as design feedback - which demands are incompatible with which - and know that realisability says nothing about connectivity, so a realisable plan can still produce isolated islands.

for a principal

Recognise when the plan's shape, not its arithmetic, is the problem: a few high-fan-out coordinators alongside deliberately quiet machines is a pattern that fails this test repeatedly at small fleet sizes.

## The question being asked A plan states, per machine, how many replication peers it should end up with. That list of numbers is a **degree sequence**, and the question is whether any simple mesh - no self-links, no duplicate links - actually has those degrees. A sequence with such a mesh is called **realisable**. This is a genuinely different question from 'how many links does the plan need'. The link count follows immediately from the sum; realisability does not follow from anything cheap. ## The two free screens 1. **Range.** Every listed degree must satisfy `0 <= d <= n - 1`. A machine has only `n - 1` distinct peers, and duplicates are not allowed, so a demand of `n` or more is unmeetable at once. 2. **Parity.** The degrees must sum to an even number, because that sum equals twice the link count. Halving the sum also tells you how many links the plan requires, which is usually worth knowing anyway. Both screens are necessary conditions. Failing either kills the plan outright. **Passing both proves nothing.** ## Why the screens are not enough Take four machines with demands `3, 3, 3, 1`. The range screen passes - the ceiling is 3. The parity screen passes - the sum is 10, so the plan wants 5 links. It is still unbuildable, and the reason is worth walking: - a machine demanding degree 3 among four machines must link to **all three** others; - there are three such machines, so the fourth machine receives a link from each of them; - its degree is therefore 3, not the 1 the plan demands. No rearrangement escapes this, because the argument never chose a layout. The plan is self-contradictory, and only a test that looks at the *structure* of the demands rather than their total can see it. ## The decisive reduction The standard decision procedure (the Havel-Hakimi reduction) works by satisfying the hungriest machine first and asking whether what remains is still realisable: 1. Sort the remaining demands in descending order and drop trailing zeros. 2. If the list is empty, the plan is realisable - stop. 3. Remove the largest demand `d`. If fewer than `d` entries remain, the plan fails: there are not enough partners left. 4. Subtract one from each of the next `d` largest entries. If any goes negative, the plan fails. 5. Repeat. The insight that makes this correct is that if *any* realisation exists, one exists in which the highest-demand machine links to the `d` next-hungriest machines. So committing to that choice never loses a solution, which is what lets a greedy procedure decide the question rather than merely guess at it. Tracing `3, 3, 3, 1`: remove the leading 3 and subtract from the next three, leaving `2, 2, 0`; drop the trailing zero to get `2, 2`; remove the leading 2 and find only one entry left, fewer than the two partners demanded - fail. That matches the hand argument above. Tracing `3, 3, 3, 3`: `3, 3, 3` becomes `2, 2, 2`, then `1, 1`, then `0`, then empty - realisable, and indeed four machines each linked to the other three is exactly a full mesh of 6 links. ## Reading a failure as a design answer | what fails | what it tells the plan's author | |---|---| | range screen | a machine is asked for more peers than the fleet contains | | parity screen | the total is odd; move the fleet size or one machine's fan-out | | reduction runs short of partners | the high-fan-out machines cannot be fed without over-linking the quiet ones | | reduction drives an entry negative | some machine is asked to accept fewer links than its busy peers must give it | The last row is the interesting one in practice. It usually means the plan wanted a few heavily connected coordinators alongside machines held deliberately quiet, and those two wishes are arithmetically incompatible at the stated fleet size. The repair is to raise the quiet machines' allowance or lower the coordinators'. ## Scope of the result This decides realisability for **simple undirected** meshes. Relaxing the model changes the answer: allow duplicate links and the range screen disappears, leaving parity as the only obstruction; allow self-links, which add two to a degree, and more sequences become realisable still. Realisability also says nothing about whether the resulting mesh is connected - a plan can be perfectly realisable and yield two separate islands, which for a replication mesh is usually a defect rather than a success.

  • Why does satisfying the highest-demand machine first not lose a valid solution?
    Because if any realisation exists, one exists where the hungriest machine links to the next `d` hungriest. Given a realisation that links it elsewhere, you can swap one link to a higher-demand machine without changing any degree. So the greedy choice is always available, which is what makes the reduction a decision procedure rather than a heuristic.
  • How does allowing duplicate links between the same pair change the answer?
    The range screen disappears, because a machine can carry many links to one peer, so a degree above `n - 1` becomes meetable. Parity remains the obstruction: the degree sum must still be even. Allowing self-links loosens it further, since each self-link contributes two to a single machine's degree.
  • Does a realisable plan guarantee the mesh ends up connected?
    No. Six machines each demanding degree 2 is realisable as one six-machine ring or as two separate triangles, and the degrees cannot tell them apart. Connectivity is a separate requirement that has to be stated and checked on its own; for a replication mesh, two islands is usually a defect.

saying these in an interview costs you the question

  • Treats an even degree sum as proof the plan is buildable.
  • Checks only the total and never the individual demands.
  • Allows a demand equal to the fleet size in a simple mesh.
  • Assumes a realisable degree list yields a connected mesh.
  • Reduces against the smallest demand instead of the largest.
  • Concludes unbuildable from one failed layout attempt rather than an argument.