A Different Kind of Interview Question

There’s a recurring fantasy in engineering circles: the idea of an interview that adapts to the candidate rather than the reverse. Most technical interviews are rigid affairs — the same whiteboard questions, the same expected solutions, regardless of who is sitting across the table. But what if the interviewer recognized not just what you know, but how you think?

That’s the scenario a recent fictional piece explores when Vidrun — an ancient, immortal engineer with a proclivity for conjuring logic programs — walks into a routine interview at a geological surveying firm and finds herself face-to-face with Aisha. On the surface, it’s a standard balancing act: Aisha asks Vidrun to write code that determines whether a binary tree is balanced. But Vidrun, true to form, refuses the easy path.

The Setup: A Trap for the Prepared

Vidrun’s first instinct is to offload the problem to Prolog. She cannot directly invoke the transformation rules for tree balancing, so she plans to define the invariants and let Prolog’s logic engine solve them. Aisha, however, knows her adversary well. She’s read Vidrun’s work — she knows her style. Before Vidrun can act, Aisha enacts a binding spell: a trap designed not to ensnare, but to evince.

Vidrun is bound to a new plane of computation. She can only see what is shown, speak without speaking, and — crucially — operate within a well-defined set of rules. Aisha locks the two of them into a custom, purpose-built interpreter. The language? A Lisp, defined from a deliberately minimal core. Vidrun mutters a prayer to McCarthy and gets to work.

A Bootstrapped Calculus

The challenge is simple on its face: balance a binary tree. But to get there, Vidrun must first construct the world she’ll operate in. Aisha grants a small vocabulary — Nils, empty lists, numbers, equality constraints, and addition for computing tree heights. From there, Vidrun builds the machinery she needs: she tests type predicates, she writes serial assignment, and she asks for — to Aisha’s exasperation — macros.

“Really?” Aisha asks.

“It’ll be fun,” Vidrun replies.

She also demands a product type — and gets pushback for it. “Do you really want to watch me reinvent a dynamic type system on top of bare lists?” Vidrun asks. Aisha gives in, but only just barely.

The Relational Twist

What Aisha doesn’t expect is Vidrun’s central gambit. Rather than write a conventional Lisp program that checks tree balance, Vidrun proceeds to build a miniKanren — a relational programming system — embedded within the Lisp she’s been given. She invokes the names of Kiselyov, Friedman, and Byrd as if calling on deities to walk in an unfamiliar form. Aisha watches, jaw dropped.

“You can’t remember how to balance a binary tree, but you memorized µKanren?” she asks.

The plan is pure Vidrun: an explicit deduction for when the interviewer doesn’t want you to use a logic solver.

The Concrete, Elegant Payoff

With the relational engine in place, the problem itself becomes almost trivial. Aisha conjures a demonstration: a tiny maple seed planted on the conference table grows into a miniature tree. Following her lead, Vidrun splits it into copies, each varying in exactly one way. The trees shimmer and reform — branches transplanted, heights measured, rearrangement done with delicate precision.

Aisha’s oversized hand fan, signed by Turing himself, commands the scene. When she closes it, the entire forest of possibilities collapses to a single tree — a balanced version of the original. It is a recognition of the fundamental duality of the problem: defining “balanced” and finding a balanced version are two sides of the same relational equation. In logic programming, one didn’t need to tell the computer how to rearrange the limbs; one only needed to declare the goal.

A single query asks for the tree’s balanced form. The system, exploring its derivation tree, finds the branches it must reshape.

What This Demonstrates

Beyond the fanciful framing, the story is grounded in real computer science history. It draws on Andraka and Németi’s 1978 proof that Horn predicate logic is Turing-complete — the basis for Prolog itself — and McCarthy’s 1955 Lisp paper, which famously deduced a Lisp evaluator from five primitive functions: car, cdr, cons, cond, and the rest.

The technique shown here is nothing new — writing a miniKanren inside a Lisp inside a Prolog is just a deeply recursive engineering exercise — but the educational value is significant. A candidate who can bootstrap their own type system and logic programming core under interview pressure demonstrates a profound understanding of computation.

Vidrun claims the benefits are simplicity. “Honestly, it’s shorter,” she says. One definition feeds another until the whole apparatus fits her needs — so that the original question becomes just a simple byproduct of a much larger system.

A Shared Answer

The most rewarding moment is the realization that Aisha and Vidrun have done this kind of dance before. Their back-and-forth references a long forays in a shared history: Antwerp’s gem mages, the Gardnos Stone, 1920s Europe. The point isn’t just technical. It’s the comfort of meeting someone who speaks the same language — where a half-joke about M’Zero, a nod to the Greek symbol for a list of N zeros, means something shared.

They measure the tree, find its balanced state, and complete the ritual at the same time.

The conference room settles back. The interview ends. Aisha slides a maple seed — a reward, a souvenir — across the table to Vidrun. She’s solved the problem from first principles in a brutal, elegant way a simpler candidate might have completed in a few minutes with a dictionary.