Conjuring technical interview

I offer the readers of "Habrakhabr" a translation of the (possibly better) article by Kyle Kingsbury, aka "Aphyr".

A long time ago, in Svalbard, when you were a young witch only forty-three years old, your mother took your not yet scarred hands in your palms and said:

Vidrun, conceived from the sea winds in the tops of the firs,
Vidrun, the green of my branches, the joy and burden of my days,
Vidrun, all inspired and cleverer, may the wisdom of our clan be yours:
Never read Hacker News

But Hacker News read about you, and rumors spread through their mysterious nests filled with indispensable giggles. That’s why a young man offering you gifts of a buffet from a micro-kitchen already looks a little doubtful. He quickly takes you to the glass box of the conference room. For some reason, it causes claustrophobia, despite full transparency. You mentally note to avoid this room in the future, but you are sure that there was nothing personal in inviting you here.

"So, my name is Tim, and I will be your first interviewer ..." - Tim tries his best to seem joyful. His ears protrude slightly, and because of a dark brown sweater and cream t-shirt, he, anxiously leaning over the table, somewhat resembles a marten. You like martens, and therefore like Tim.

"Before we begin, can I ... answer your questions about the company?"

You would like to ask where Tim would hide his nest of nuts and bird eggs from other martens - but in return you just giggle about yourself, lean against a tree-like camp against the wall and settle comfortably on the floor. Tim arches to see more clearly where you have gone. "Definitely," you think to yourself.

"So, uh ... Could you, say, say a little about yourself?"

He did not read your resume. No one can.

"In winter, above the ice-covered fjords," you begin, "there is a rock, like an ashen hat covered with ghosts of glaciers--"

"You know!". He interrupts you. This is a beautiful story, but it may be possible to tell it later. "How about programming a little together? Just a few basic exercises, so that I understand what you think ?!"

"Nice offer, Tim."

"Okay, great." Tim seems to be confident that he was back in the rut of the interview. "Let's open the editor. Um ... would you like to sit down?"

"Sit down!" - You slap on the floor next to him, "So much safer." Tim stares in disbelief at the brackets of spilled salt, shakes his head, but carefully sits down beside him.

Tim retells an ancient riddle, he does not know its origin, and therefore he confuses words. Several travelers get lost in the woods, on a winding mountain path, and are worried that they may be walking in circles. They need to know - does the path to freedom lead? Or make them wander through the forest forever?

As the tradition goes, the group has to split up: the fastest foot rushes forward, while the others go slowly. If the runner is catching up with them, then the path goes in a loop.

"Let's start with the linked list?" - you smile assuredly.

"Yes," Tim says, "but ... um ... just a normal linked list, please. I know that you are, well, doing functional programming, but we have a more pragmatic office here. We are creating a real software. We need something more practical ".

"Yes, of course," you agree, "Practical. Understood." One of your spiders - you don’t see which one - gently sneak over Tim’s sweater, and you put the spider in your palm before you start.

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

"We, uh, don't need an IO here. Just a list in memory."

Politely agree, but do not delete anything. 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) 

"This is ... a bit not what I expected," says Tim. "No, no, good! Straight and simple. I just, you know, on the Internet they say that you ...". He subsides, and looks apologetically at you.

You disarm and smile and shake free hands from your woolen sleeves. Then you clap your palms, firmly put them on top of the disk and open the portal to the Lower World.

 (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) 

“Excuse me,” says Tim from over his shoulder, “I'm not an expert at Clojure. Why is that?”

"Just a boilerplate. Don't worry." Tim looks even more concerned. "We do that 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 colors start to run away from Tim's face. Looks like winter has come and he decided to fade.

 (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 readily explain, "So when we push Java classes back and forth, some reflection usually happens."

"It seems that you ... wrote a classloader solely to return an array of single bytes for a particular class? Is it ... is this normal?"

"Yes," you insist, eyes flashing menacingly.

"Why not just write an algorithm on Clojure?"

"Productivity" - you quite honestly explain. "Since constant checks will be carried out in a close inner loop, we absolutely do not want to write them in such a high-level language."

"X-well" - Tim stutters "So you write a java loop test? Will you call it from Clojure?"

"Something like that".

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

"What is it?"

"Magic numbers". You're a witch, after all. "Every class starts with a girl in a cafe"
[original - babe in a cafe, cm 0x ca 0x fe 0x ba 0x be ]

"What?"

"You know, a handsome man - like those who go to the movies - relaxes in the afternoon after a walk. In his hands a cup of coffee, orange glasses sparkle in the sun, and beautiful girls jog past him. If one is lucky, his gaze may be will meet her eyes, and they will smile at each other, and together they will find a brick-lined alley. Her lips will meet his skin, and she will feel the heat of the sun under her ... "

"Sorry what?"

To be honest, you never understood the concept of Sun in this story, or why the Java Virtual Machine specification, usually so prosaic, is thrown into sensory rhapsody on many stanzas in section 4.1.

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

"We are using version 49 because it does not require stack maps, which simplifies the task. Now we need a number of constants"

Remember the future. This is a common trick for spellcasters, many of whom lived like Merlin, writing down the constants and the size of the buffers even before (after) how they wrote (did not write) the buffers themselves.

Remember that 22 is enough. Write it down.

  0x00 0x17 ; 22 constants 

“I apologize” - Tim blinks “But after all, 0x17 is 23, not 22 decimal?”

“Og én,” you chant after me - “Til javanissen!”

"I apologize?"

"Javanis. You probably heard about them! They are small magical people - like gnomes - who live in each JVM. If you don’t give them one extra constant, they’ll spoil them with segfolts. But please javanisk and your mutexes will work like a butter."

This is a story from childhood. You remember the mother mumbling offsets and stirring the brew in the cauldron. “By byter for bufferen anvise / og ekstra én til javanisse.” This is a joyful memory, and you forget a little about it until Tim reminds you of your cough.

"Oh yes. Constants. We need our superclass. Object, of course. I would usually use the existing class to reduce the size, but here we work only with interfaces, so there will be an Object. And I think we need a class for ourselves."

  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 take Iterable and call .iterator (), which means we will 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 for this iterator we will need hasNext and Next () ...". Now the bytes will go faster. This is much better than the Old Norse hexography, where even and odd numbers had 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 was numb.

"Now you can think," you mutter, "that usually the code is hidden in a class, and therefore we should assign it a separate byte label - but instead, we would be good at sticking the word" Code "into each class and using 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 Iterable and return a boolean value.

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

"Well". It is necessary to crunch knuckles and apply the ancient seal.

  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 of your clan had to learn these bytes. What pride you felt when you first made a class without javac training supports! So, the beginning of the method:

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

"Method names must begin in lower case," says Tim. But his voice sounds like it was a question.

"Only by agreement. Almost any string will do, and we already have one in the pool of constants."

  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, wait,” Tim grabs a sliver during a storm. "Just four slots for variables? For arguments plus local ones?"

“Og to til javanissen!” - you remind him. Tim gasps the air while you remember how many instructions she wrote.

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

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

  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) 

“Probably astore_2 is needed here?” Tim asks, trying to help. “The zero variable contains our first argument, right?”

"So it was," you agree, "But we don’t need it anymore."

"But ... they are not even of the same type. This is ... it is illegal."

"If it was illegal," you patiently remind him, "then Sun Microsystems would make it impossible."

The first will be a fast iterator. Her name will be Yorun, her legs will be strong from many years of skiing. She flies forward with powerful shocks.

  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 

Bjorn in the zero register will be fat and lazy. He slowly treads ahead like his namesake. [Bjørn - bear].

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

Yorunn, so that she was not caught up, makes another breakthrough. Her gait is hard.

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

Knowing their position on the path, you check to see if they will collide with each other; and if not, repeat the process again:

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

Your sixty bytes are over, you quite sigh and put sealing runes on your spell before you convert each number into a single clever 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 politely tries to get the interview back to normal. Bless him, but not too much, or else he will be dragging you on Twitter for years, begging spells against every computational malady that will hit him. A conspiracy against minor file system damage will do.

Now you shake off the frost from your fingers, enter the torus deeply into the virtual machine and unwind a strong serialization loop.

 (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))) 

"Baos rhymes with chaos" - you politely inform Tim. He confusedly asks about the unit tests. In the preparations you weave a story about a path in the forest, which closes in with itself.

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

Before you cast the spell, you turn to the sides of the world marked with scars on your wrist: H, J, K, L. Only J gives answers like you, but being polite never hurts.

 (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 and fifty-six bytes" - you declare, and with pleasure you have to stretch. "Javac would have made about five hundred and eighty. Of course, we saved by skipping stackmap and line mapping, but additionally we reduced the number of variables, and also threw out four unnecessary astore / aload operations. Of course, since the class is never instantiated, we don’t need to generate the <init> method, or call the superclass ".

Tim stares at you with silent interest. His jacket shines from fast-melting frost. Most likely you are hired.

You reach into the pocket of your mantle, and gently, with slow movements, so as not to frighten him back into the burrow, stretch your hand, unclench your fingers, and offer him a nut.