Hexing the technical interview

Previously: Reversing the technical interview.

Long ago, on Svalbard, when you were a young witch of forty-three, your mother took your unscarred wrists in her hands, and spoke:

Vidrun, born of the sea-wind through the spruce
Vidrun, green-tinged offshoot of my bough, joy and burden of my life
Vidrun, fierce and clever, may our clan’s wisdom be yours:

Never read Hacker News

But Hacker News has read of you, in their snicker-slithing sussurential warrens, and word has spread, which is why the young man offering you a smörgåsbord of microkitchen offerings looks mildly suspicious already. He whisks you into a glass shoebox of a conference room, which somehow manages to be claustrophobic despite the open sightlines. You make a mental note to avoid this conference room in the future, but reassure the room it’s nothing personal.

“So my name is Tim, and I’ll be your first interviewer today…” Tim is making every effort to be cheery. His ears stick out a bit, and in his dark-brown hoodie and cream shirt, perched expectantly at the table, he resembles something of a pine marten. You like pine martens, and therefore Tim as well.

“Before we get started, is there… anything I can tell you about the company?”

You would like to ask what kind of call Tim would make, were he guarding his cache of eggs and nuts against another marten–but instead, you just giggle to yourself, lean your sprig of cloud-pine against the corner, and settle comfortably to the floor. Tim leans in to get a clearer view of where you’ve gone. Definitely, you think to yourself.

“So, erm… Perhaps you could tell me a bit about your background?”

He hasn’t read your resume. No man can.

“In the winter,” you begin, “above the ice-locked fjørds, lies a creek, ash-white with the ghosts of glaciers–”

“You know what?” He interrupts. It was a beautiful story, but perhaps you can tell it later. “How about we do a little programming together? Just a basic exercise so I can get a sense of how you think.”

“That sounds nice, Tim.”

“OK, great.” Tim seems reassured to be back on track. “So let’s open up an editor. Would you… would you like to have a seat?”

“Come!” You pat the ground next to you. “It is safer this way.” Tim stares at the parentheses of salt with disbelief, shakes his head, and reluctantly sits by your side.

Tim retells an old riddle, though he does not know its origins, and has the words wrong. A group of travelers are lost in the woods, upon a winding mountain path, and worry that they have been traveling in circles. They must know: does their path lead to freedom? Or constrain them to wander forever in the wilderness?

Tradition sets down that the group must split: the fastest runner forges on ahead, while the rest continue slowly. If the runner ever catches them, the trail must loop back on itself.

“So we should start with a linked list?” You smile reassuringly.

“Yes,” Tim says, “but… um… just a regular linked list, please. I know you’re up on, well, functional programming, but we’re a more pragmatic shop here. Building real software. We want something practical.”

“Yes, of course,” you assent. “Practical. Got it.” One of your spiders–you can’t tell which–is picking its way carefully up Tim’s hoodie, and you scoop it up before typing.

(ns cycle-detector.core (:require [clojure.java.io :as io]) (:import (java.io DataOutputStream ByteArrayOutputStream)))

“We’re, uh, we’re not doing IO here. Just an in-memory list.”

Agree politely, but delete nothing. Never apologize for who you are.

; A simple mutable linked list (deftype MutableLinkedList [value next] clojure.lang.Seqable (seq [_] (lazy-seq (cons value (seq @next))))) (defn node [value] (MutableLinkedList. value (atom nil))) (defn link! [node next] (reset! (.next node) next) next)

“That’s… not what I was expecting.” Tim says. “No, no, it’s good! Straightforward and simple. I was just, you know, they said on the internet that you were…” He trails off, and looks to you apologetically.

Smile disarmingly and shake your wrists free of your wool shift. Then clap your hands, place them firmly upon the disk, and open a portal to the underworld.

(gen-class :name cycle_detector.core.ArbClassLoader :extends ClassLoader :state state :init class-loader-init :constructors {[ClassLoader String bytes] [ClassLoader]} :exposes-methods {defineClass superDefineClass resolveClass superResolveClass} :prefix "-" :main false)

“I’m sorry,” Tim comments over your shoulder. “I’m not really a Clojure expert. What’s this for?”

“Just boilerplate. Don’t worry about it.” Tim appears, if anything, more worried now. “We do this all the time.”

(defn -class-loader-init [^ClassLoader class-loader ^String class-name ^bytes bytecode] [[class-loader] {:class-name class-name :bytecode bytecode}]) (defn -loadClass ([this ^String class-name] (-loadClass this class-name true)) ([this ^String class-name resolve?] (if (= class-name (:class-name (.state this))) (let [bytecode (:bytecode (.state this)) c (.superDefineClass this class-name bytecode (int 0) (int (alength bytecode)))] (when resolve? (.superResolveClass this c)) c) (.loadClass (.getParent this) class-name)))) (defn class-loader [^String class-name ^bytes bytecode] (cycle_detector.core.ArbClassLoader. (.getClassLoader MutableLinkedList) class-name bytecode))

The color has begun to drain from Tim’s face. Perhaps winter has come, and his coat is changing.

(defn run-bytecode [bytecode class-name method-name signature & args] (-> class-name (class-loader bytecode) (.loadClass class-name) (.getMethod method-name (into-array Class signature)) (.invoke nil (object-array args))))

“Clojure is a dynamic language,” you explain helpfully. “So when we call back and forth with Java classes, there’s usually some reflection going on.”

“It looks like you’ve… built a classloader specifically to return a single byte array for a particular class? Is that… is that normal?”

“Yes,” you insist, eyes flashing dangerously.

“Why can’t you just write the algorithm in Clojure?”

“Performance.” You explain, wholly earnest. “Since cycle checking is going to be a tight inner loop, we don’t want to write it in such a high-level language.”

“O–Okay.” Tim stutters. “So you’re going to write the cycle detector in Java then? And call it from Clojure?”

“Something like that.”

(def racer (->> [0xca 0xfe 0xba 0xbe

“What are these?”

“Magic numbers.” You are, after all, a witch. “Every class begins with a babe, in a cafe.”

“What?”

“You know, a beautiful man–the kind like from the movies–relaxing in the afternoon by the promenade. He has his kaffe, and his orange glasses gleam in the sun, and perhaps some other nice men are jogging by. If they are lucky, perhaps he will lock eyes with one of the joggers, and they will smile, and find a brick-lined alleyway together. His lips press upon the other man’s skin, and he feels the heat of the sun infused there…”

“Excuse me?”

If you were to be honest, you’ve never understood Sun’s rationale for the story, or why the Java Virtual Machine specification, normally so prosaic, lapses into lustful rhapsody for so many stanzas in section 4.1.

0x00 0x00 ; Minor 0x00 0x31 ; Major

“We’re using version 49 because it doesn’t require stack maps, which keeps things simple. Now we need the number of constants.

Remember the future. This is a common trick for protocol wizards, many of whom live as Merlin did, writing constants and buffer sizes before (after) having written (unwritten) the buffers themselves. Recall that 22 sufficed then. Write that down.

0x00 0x17 ; 22 constants

"I’m sorry,” Tim blinks. “But isn’t 0x17 decimal 23, not 22?”

“Og én,” you recite, sing-song, “Til javanissen!”

“Beg pardon?”

“The javanisse. Surely you have heard of him! He is a small, magical man–something like a gnome–who inhabits every JVM. If you do not set out an extra constant for him, he can cause segfaults. But keep the javanisse happy, and your mutices will be fair.” It is a story from your childhood. You remember your mother, chanting offsets as she stirred the stew. “To byter for bufferen anvise / og ekstra én til javanisse.” It is a happy memory, and you lose yourself in it until Tim clears his throat.

“Ah yes. Constants. We’ll need our superclass, Object, of course. Ordinarily I’d use an existing class to save weight, but we’re only dealing with interfaces here so Object it is. And a class for ourself, I suppose.”

0x01 0x00 0x10 ; 1: A UTF-8 string of 16 bytes (.getBytes "java/lang/Object") 0x07 0x00 0x01 ; 2: The Object class 0x01 0x00 0x19 ; 3: UTF-8 string of 25 bytes (.getBytes "cycle_detector/core/Racer") 0x07 0x00 0x03 ; 4: Our class

We’ll take an Iterable, and call .iterator(), which means we need:

0x01 0x00 0x12 ; 5: UTF-8 string of 18 bytes (.getBytes "java/lang/Iterable") 0x07 0x00 0x05 ; 6: Iterable 0x01 0x00 0x08 ; 7: UTF-8 string of 8 bytes (.getBytes "iterator") 0x01 0x00 0x16 ; 8: UTF-8 string of 22 bytes (.getBytes "()Ljava/util/Iterator;") 0x0c 0x00 0x07 0x00 0x08 ; 9: Name and type info (7, 8) 0x0b 0x00 0x06 0x00 0x09 ; 10: Interface methodref for Iterable.iterator()

“And with that iterator, we’ll need hasNext and Next()…” The bytes are coming faster now. This is so much better than Old West Norse hexography, where both odd and even digits shared the same rune.

0x01 0x00 0x12 ; 11: UTF-8 string of 18 bytes (.getBytes "java/util/Iterator") 0x07 0x00 0x0b ; 12: Iterator 0x01 0x00 0x07 ; 13: UTF-8 string of 7 bytes (.getBytes "hasNext") 0x01 0x00 0x03 ; 14: UTF-8 string of 3 bytes (.getBytes "()Z") 0x0c 0x00 0x0d 0x00 0x0e ; 15: Name and type info for .hasNext() 0x0b 0x00 0x0c 0x00 0x0f ; 16: Interface methodref: Iterator.hasNext() 0x01 0x00 0x04 ; 17: UTF-8 string of 4 bytes (.getBytes "next") 0x01 0x00 0x14 ; 18: UTF-8 string of 20 bytes (.getBytes "()Ljava/lang/Object;") 0x0c 0x00 0x11 0x00 0x12 ; 19: Name and type info for .next() 0x0b 0x00 0x0c 0x00 0x13 ; 20: Iterator.next()

Tim has gone silent.

“Now you’d think,” you mutter, “that code would be a common thing to put in a class, and therefore it might have a dedicated byte tag–but instead, we have to put the word "Code” in every class and use it to identify our code attributes.

0x01 0x00 0x04 ; 21: UTF-8 string of 4 bytes (.getBytes "Code") ; String for code attributes

Finally, our signature. Take an Iterable, and return a boolean.

0x01 0x00 0x17 ; 22: UTF-8 string of 23 bytes (.getBytes "(Ljava/lang/Iterable;)Z") ; Our arg signature

“Now then.” Crack your knuckles, and inscribe the ancient sigils.

0x00 0x21 ; Flags: public & super 0x00 0x04 ; Our class 0x00 0x02 ; Our superclass (Object) 0x00 0x00 ; No interfaces 0x00 0x00 ; No fields 0x00 0x01 ; One method

Every young witch in your clan was required to memorize these bytes. Such pride, you felt, when you first incanted a class without the training wheels of javac. Our method begins:

0x00 0x09 ; Flags: public & static 0x00 0x15 ; Method name (21, "Code")

“Method names start with lowercase letters,” Tim asserts. His voice rises like a question.

“Only by convention. Almost any string will do, and we already have this one in the constant pool.”

0x00 0x16 ; Method signature (22) 0x00 0x01 ; One attribute ; Method attributes 0x00 0x15 ; Attribute name (21, "Code") 0x00 0x00 0x00 0x48 ; + 2 2 4 bytecode-length 2 0 2 attribute-len 0x00 0x02 ; Maximum stack 0x00 0x04 ; Number of local variables

“Wait, wait, hold on.” Tim has seized upon a piece of flotsam in the storm. “Only four variable slots? For arguments plus locals?”

“Og to til javanissen!” You remind him. He sputters while you try to remember how many instructions you’ll have written.

0x00 0x00 0x00 0x3c ; Size of bytecode

Your method begins by creating a pair of iterators from a single Iterable argument.

0x2a ; aload_0 (take arg) 0xb9 ; invokeinterface 0x00 0x0a ; .iterator() 0x01 ; 1 arg 0x00 ; unused 0x4d ; astore_1 (store iterator) 0x2a ; aload_0 (take arg) 0xb9 ; invokeinterface 0x00 0x0a ; .iterator() 0x01 ; 1 arg 0x00 ; unused 0x4e ; astore_0 (store iterator)

“Did you mean astore_2?” Tim asks, trying to be helpful. “Variable 0 holds our first argument, right?”

“It did.” You agree. “But we won’t be needing it again.”

“But… those aren’t even the same type. That’s… that’s illegal.”

“If it were meant to be illegal,” you remind him sagely, “Sun Microsystems would have made it unrepresentable.”

One will be the fast iterator. Her name is Jorunn, and her legs are strong from years of skiing. She flies forward with powerful strokes.

0x2d ; aload_1 take fast iterator 0xb9 ; invokeinterface 0x00 0x10 ; hasnext 0x01 ; 1 arg 0x00 ; unused 0x9a ; ifne 0x00 0x05 ; jump ahead 3 if we have a next element 0x03 ; iconst_0 0xac ; ireturn (return false) ; Move fast iterator forward by 1 0x2d ; aload_1 (take fast iterator) 0xb9 ; invokeinterface 0x00 0x14 ; .next() 0x01 ; 1 arg 0x00 ; unused 0x57 ; discard element ; Ensure fast iterator has next 0x2d ; aload_1 (take fast iterator) 0xb9 ; invokeinterface 0x00 0x10 ; hasNext() 0x01 0x00 0x9a ; ifne 0x00 0x05 ; jump forward by 3 if we have a next element 0x03 ; iconst_0 0xac ; ireturn

Bjørn, in register 0, is fat and lazy. He ambles along like his namesake.

0x2c ; aload_0 (take slow iterator) 0xb9 ; invokeinterface 0x00 0x14 ; .next() 0x01 0x00

Jorunn, not to be outdone, takes another stride. Her footing is sure.

0x2d ; aload_1 (take fast iterator) 0xb9 ; invokeinterface 0x00 0x14 ; .next() 0x01 0x00

With their positions on the path at hand, you check to see if they have run into one another, and if not, repeat the process once again.

0xa6 ; if_acmpne 0xff 0xd7 ; 0xffff + 1 - 41 instructions ; Return true 0x04 ; iconst_1 0xac ; ireturn

Your sixty bytes exhausted, you sigh contentedly, and inscribe the sealing runes upon your spell, before coercing each number to a single crooked byte.

; End of bytecode 0x00 0x00 ; No exceptions 0x00 0x00 ; No attributes ; End of method 0x00 0x00 ; No class attributes ] (map (fn [x] (if (instance? Long x) (unchecked-byte x) x)))))

Tim has been gently trying to steer the interview back on track. Bless him, but not too well, or he’ll follow you around on Twitter for years to come, asking for spells to soothe every computational malady that befalls him. Perhaps a ward against minor filesystem corruption would do.

Now shake the frost from your fingertips, drive your torus deep into the VM, and spin a tight-wound loop of serialization.

(defn write-class! [^DataOutputStream ds class-data] (doseq [x class-data] (condp = (class x) nil nil Long (.writeLong ds x) Integer (.writeInt ds x) Short (.writeShort ds x) Byte (.writeByte ds x) (.write ds ^bytes x)))) (defn class-bytes [class-data] (let [baos (ByteArrayOutputStream.)] (with-open [ds (DataOutputStream. baos)] (write-class! ds class-data)) (.toByteArray baos)))

“It rhymes with ‘chaos’,” you inform Tim helpfully. Nonplussed, he asks about unit tests. You weave a story of a path in the woods, which loops upon itself, in preparation.

(deftest cycle-test (let [nodes (mapv node (range 5)) list (first nodes)] (reduce link! nodes) (link! (nth nodes 3) (nth nodes 1))

Before casting the spell, you invoke the four cardinal directions, as scars around your wrist: H, J, K, L. Only the J wind answers to your kind, but it never hurts to be polite.

(deftest cycle-test (let [cycle? (partial run-bytecode (class-bytes racer) "cycle_detector.core.Racer" "Code" [Iterable])] (is (boolean (cycle? (seq list)))) (is (not (boolean (cycle? [])))) (is (not (boolean (cycle? [1 2 3])))))))) Ran 1 tests containing 3 assertions. 0 failures, 0 errors.

“Three hundred fifty-six bytes,” you declaim, and stretch in satisfaction. “Javac would have produced roughly five hundred eighty. We save a lot by omitting the stackmap and line mapping, of course, but we also cut the number of variables, and cut four superfluous astore/aload ops as well. And of course, since this class is never instantiated, we don’t need to generate an <init> method, or call super.”

Tim stares at you in mute concern. His hoodie gleams with quick-melting frost. Perhaps you have been hired.

Reach into your the pocket of your shift, and gently, with slow movements, so as not to startle him and send him scurrying back into his burrow, extend your hand, open your fingers, and offer him a walnut.

Next: Typing the technical interview.