Reversing the technical interview
If you want to get a job as a software witch, you’re going to have to pass a whiteboard interview. We all do them, as engineers–often as a part of our morning ritual, along with arranging a beautiful grid of xterms across the astral plane, and compulsively running ls in every nearby directory–just in case things have shifted during the night–the incorporeal equivalent of rummaging through that drawer in the back of the kitchen where we stash odd flanges, screwdrivers, and the strangely specific plastic bits: the accessories, those long-estranged black sheep of the families of our household appliances, their original purpose now forgotten, perhaps never known, but which we are bound to care for nonetheless. I’d like to walk you through a common interview question: reversing a linked list.
First, we need a linked list. Clear your workspace of unwanted xterms, sprinkle salt into the protective form of two parentheses, and recurse. Summon a list from the void.
(defn cons [h t] #(if % h t))
“That’s not a list,” the interviewer says. “That’s an if statement.”
“What else are lists,” you reply, your eyes flashing, “But alternatives?”
user=> (def x (cons 1 (cons 2 nil))) #'user/x user=> (x true) 1 user=> ((x false) true) 2
“What’s x exactly?” The interviewer makes every attempt to appear friendly. Answer at the REPL, but do not be deceived for an instant. They are not a friend. Your oath at the Front Desk forbade it.
user=> x #object[user$cons$cell__4431 0x3b89cc1c "user$cons$cell__4431@3b89cc1c"]
“To know a thing is to name it,” you advise. True names have power. The K language was invented by Ursula K. Le Guin, and is among the oldest and tersest forms of magic. To imbue a language with a letter of your own name is to give up an element of your self. Your own initials ache at the memory.
“Erm, OK, so how would you get an element out of this list?”
The expression in your mind is beautiful, unfurling like a red carpet underneath your bare feet. The Oscars were on last night, but you long for the kiss of different stars upon your naked skin, as when you dwelt in the mountains of Sørøya, and called the moon your lover. Except for the bounds check, you get it right the first time.
(defn nth [l n] (when l (if (= 0 n) (l true) (recur (l false) (dec n)))))
“Could you just show me, you know, a regular list? Like in Python?”
You grit your teeth, plant your feet against the floor, and dredge a pretty printer from the void. Your palms are calloused now, your eyelids limned with crystalline, soot-black snowflakes. Every action comes at cost–except, of course, for pure functions, which are side-effect free.
(defn prn-list [l] (print "(") (loop [l l] (if (nil? l) (print ")\n") (do (print (l true)) (when (l false) (print " ")) (recur (l false))))))
No time for descriptive variables, examples, or docstrings here. In the whiteboard interview, time is of the essence. Pretend you are a Haskell programmer, as your grandmother was, before her continuation passed.
user=> (prn-list (cons 1 (cons 2 (cons 3 nil)))) (1 2 3)
The interviewer smiles, reassured. We are on, or at least above, familiar ground. “So, to reverse it, you’d…”
You seize his hands in yours, his mind a frantic clockwork unwinding, skittering ticker-tapeworm unraveling, pitter-patter heart askance and out of place, and in the ancient tongue, recite an epigram.
(defn reverse [l] (loop [r nil, l l] (if l (recur (cons (l true) r) (l false)) r))) user=> (prn-list (reverse (cons 1 (cons 2 (cons 3 nil))))) (3 2 1)
As you release your hold, he stutters something polite, and zips his hoodie to protect against the frost. There will be other meetings, but you need not participate. Send an eagle in your place.
They will refuse, of course, and ever so ashamed, cite a lack of culture fit. Alight upon your cloud-pine, and exit through the window. This place could never contain you.