Conjuring a technical interview

I Suggest the readers of "Habrahabr" translation (probably the best) articles Kyle Kingsbury, a.k.a "Aphyr".

long Ago, in Svalbard, when you were a young witch just forty-three years, mom took my hands and your not-yet-scarred hands, and said:

Vidron conceived from offshore wind in the tops of the fir trees
Vidron, greens of my branches, the joy and burden of my days,
Widran, all inspiration and wiser, let it be the wisdom of our clan of your
Never read Hacker News

But Hacker News I read about you, and their mysterious nests filled with indispensable giggle, rumors. But because the young man offers you gifts buffet with micro kitchen already looks a little doubtful. He quickly draws you into the glass box meeting room. For some reason he very claustrophobic, despite the complete transparency. You mentally note to continue to avoid this room, but I'm sure that inviting you here was nothing personal.

"so, my name is Tim, and I will be your first interviewing for a large..." — trying hard to seem happy Tim. His ears stick out slightly, but because of the dark brown jacket and cream shirt, he anxiously leaning over the table a few resembles the marten. Do you like marten, but because like Tim.

"Before we start, could I... to answer your questions about the company?"

would You like to ask, where Tim tries to hide from other cats their stash of nuts and bird eggs, but instead you just giggle to myself, bent like a tree mill to the wall and conveniently arranged on the floor. Tim bends, to see more clearly where you go. "Definitely", I think you're talking about yourself.

"So, um... could you, say, to tell about myself a little bit?"

He didn't read your resume. Nobody can do that.

"in the Winter, over ice-clad fjords", you begin, "is a rock as ash cap is covered with ghosts of glaciers--"

"I Know!". He interrupts you. It's a great story, but they may be able to tell her later. "How about a little Oprogramowanie together? Just a few basic exercises that I can understand how you think?!"

"Nice of you to offer, Tim".

"Okay, fine." Tim pretty sure that was able back in a rut interview. "Let's open the editor. Um... won't you sit down?"

"Sit down!" — clap you on the floor next to him, "So much safer". Tim with disbelief staring at the brackets spillage of salt, shake her head, but gently sits down next to.

Tim retells an ancient mystery, he does not know its origin, and therefore confuses words. Several travelers got lost in the woods, on a winding mountain trail and worried about what they might be going in circles. They need to learn — is the path to freedom? Or will cause them forever to wander in the woods?

As is tradition, the group must split up: the swift rushes forward, and the others go slowly. If the runner catches up with them, then the path is looped.

"let's Start with the linked list?" smile you overawe.

"Yes," says Tim, "but... um... just an ordinary linked list, please. I know what you're doing functional programming, but we're more pragmatic office. Create a real software. We need something more practical".

"Yes, of course," you agree, "Practical. Understand." One of your spiders — you can not see who it was — carefully slips the sweater for Tim, and you put the spider in her palm before starting.

the

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

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

Politely agree, but don't delete anything. Never apologize for who you are.

the

; A simple mutable linked list
(deftype MutableLinkedList [value next]
clojure.lang.Seqable
(seq [_]
(lazy-seq (cons value (seq @next)))))

(defn node [value]


(defn link! [node next]
(reset! (.next node) next)
next)

"That's... a bit not what I expected," says Tim. "No, no, good! Straightforward and easy. I just, you know, on the Internet saying that you...". It subsides and izvinyaysya looks at you.

You obezzarajivatmi smile and shake of the freedom hands of his woolen sleeves. Then both hands clasped firmly put them on top of the disk and open a portal to the Lower world.

the

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

"Excuse me," said Tim over his shoulder, "I'm no expert in Clojure. Why?"

"Just boilerplate. Don't worry." Tim looks even more worried. "We do this all the time".

the

(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]
(is this the loadClass 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? (.this superResolveClass 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 the face of Tim. Looks like winter came and he decided to shed.

the

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

"Clojure is a dynamic language", willing to explain to you, "So when we go back and forth Java classes, usually there is some reflection".

"Like what you... have written a classloader solely in order to return an array of single bytes for a particular class? Is this normal?"

"Yes," you insist, threateningly, his eyes gleaming.

"why not just write an algorithm in Clojure?"

"Performance" — quite honestly explain to you. "As regular inspections will be conducted in close inner loop, we absolutely don't want to write them on such a high-level language".

the"X-well," stuttered Tim, "So us will write a check for cyclicity in Java? Going to call it from Clojure?"

"something like that."

the

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

"what's that?"

the"Magic number". You're a witch, in the end. "Each class starts with a girl in a cafe"
[ original — babe in a cafe, see 0xca, 0xfe, 0xba, 0xbe ]

"What?!"

"you Know, handsome man — like the ones you see in the movies — relax in the afternoons after a walk. In the hands of a Cup of coffee, orange glasses sparkle in the sun, and by him run a beautiful girl. If one is lucky, that his eyes might meet her eyes, and they smile at each other, and together you will find brick lane. Her lips meet his skin, and she will feel the heat of the sun under it."

"Sorry?"

to be honest, you never realized the idea of the Sun in this story, or why the specification of the Java Virtual Machine, usually so prosaic, falls into an emotional Rhapsody on a stanza in section 4.1

the

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

"We use version 49 because it does not require stack maps, which makes it easier. Now we need the number of constants"

Remember the future. This is a common trick for summoners protocols, many of whom lived as Merlin, recording constants and buffer sizes before (after) they wrote (did not write) buffers themselves.

Remember that 22 is enough. Record.

the

 0x00 0x17 ; 22 constants

"I'm Sorry" — blink Tim "But 0x17 is decimal 23 and not 22?"

“Og én,” — you recite melodiously “Til javanissen!”

"I Beg your pardon?"

This is a story from my childhood. You remember mom, boomy offsets, and stirring brew in a cauldron. “To byter for bufferen anvise / og ekstra én til javanisse.” It is a joyful memory, and you are forgotten until Tim recalls his cough.

"Oh. Constants. We need our superclass. The object, of course. Usually, I'd use an existing class, to reduce the size, but here we only work with interfaces, so will the Object. And I guess, you need a class for ourselves."

the

 0x00 0x01 0x10 ; 1: A UTF-8 string of 16 bytes
(.getBytes "java/lang/Object")
0x00 0x07 0x01 ; 2: The Object class

0x01 0x00 0x19 ; 3: UTF-8 string of 25 bytes
(.getBytes "cycle_detector/core/Racer")
0x00 0x03 0x07 ; 4: Our class

We will take the Iterable and call .iterator(), and hence we will need:

the

 0x01 0x00 0x12 ; 5: UTF-8 string of 18 bytes
(.getBytes "java/lang/Iterable")
0x00 0x07 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 0x06 0x00 0x00 0x09 ; 10: methodref Interface for Iterable.iterator()

"And for this we need an iterator hasNext and Next()...". Now the bytes will go faster. It is much better than old Norse exography, where odd and even numbers was composed of the same rune.

the

 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 0x03 0x00 ; 14: UTF-8 string of 3 bytes
(.getBytes "()Z")
0x0c 0x00 0x0d 0x00 0x0e ; 15: Name and type info for .hasNext()
0x00 0x00 0x0b 0x0c 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 went numb.

"Now you can think" — you mutter, "that's usually code hidden in the class, and therefore it would be necessary to assign individual byte label — but instead of us it would be good to put the word "Code" to each class and use it to identify our code attributes".

the

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

Finally, our signature. Take an Iterable and return a Boolean value.

the

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

"Well". Need to crunch the knuckles and apply ancient seals.

the

 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 memorize these bytes. What pride you felt when he first skaldowie class without academic javac props! So, the beginning of the method:

the

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

"the method Names should begin in lowercase," says Tim. But his voice sounds as if it were a question.

"Only by agreement. Will fit almost any string, but we already have one in the pool of constants".

the

 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 the sliver during the storm. "Only four slots for variables? For arguments plus local?"

“Og to til javanissen!” — you remind him. Tim catches her breath, while you think about how many instructions are written.

the

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

Your method begins with the creation of a pair of iterators from a single Iterable argument.

the

 0x2a ; aload_0 (take arg)

0xb9 ; by invokeinterface
0x00
0x0a ; .iterator()
0x01 ; 1 arg
0x00 ; unused

0x4d ; astore_1 (store, iterator)

0x2a ; aload_0 (take arg)

0xb9 ; by invokeinterface
0x00
0x0a ; .iterator()
0x01 ; 1 arg
0x00 ; unused

0x4e ; astore_0 (store, iterator)

“Probably there need astore_2?” asked Tim, trying to help. “Our zero-variable contains the first argument, right?”

"But... they're not even the same type. It's... it's illegal."

"If it was illegal" — are you patiently remind him, "that Sun Microsystems would have made it impossible."

the First will be a fast iterator. Her name is Jorunn, her legs are strong from years of skiing. She flies forward powerful aftershocks.

the

 0x2d ; aload_1 take fast iterator

0xb9 ; by invokeinterface
0x00
0x10 ; hasnext
0x01 ; 1 arg
0x00 ; unused

0x9a ; ifne
0x00
0x05 ; jump 3 ahead 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 ; by invokeinterface
0x00
0x14 ; .next()
0x01 ; 1 arg
0x00 ; unused

0x57 ; discard element

; Ensure fast iterator has next

0x2d ; aload_1 (take fast iterator)

0xb9 ; by 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 day forward like his namesake. [Bjørn — bear].

the

 0x2c ; aload_0 (take slow iterator)

0xb9 ; by invokeinterface
0x00
0x14 ; .next()
0x01
0x00

Jorunn, so it is not caught, makes another breakthrough. Her gait is solid.

the

 0x2d ; aload_1 (take fast iterator)

0xb9 ; by invokeinterface
0x00
0x14 ; .next()
0x01
0x00

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

the

 0xa6 ; if_acmpne
0xff
0xd7 ; 0xffff + 1 - 41 instructions

; Return true

0x04 ; iconst_1
0xac ; ireturn

Your sixty-bytes over, you're a pretty sigh and applied to the sealing runes on your spell before you convert each number in the only tricky bytes.

the

 ; 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 return the interview in the normal way. Bless him, but not too much, not that he will come after you on Twitter, begging for spells against each computational disease that it will impress. Conspiracy against minor damages the file system will do.

Now shake off the frost of fingers c, injected deeply tor in a virtual machine and promote a strong loop of serialization.

the

(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 ^x bytes))))

(defn class-bytes
[class data]
(let [baos (ByteArrayOutputStream.)]
(with-open [ds (DataOutputStream. baos)]
(write-class! ds class-data))
(.toByteArray baos)))

"Baos rhymes with chaos" — politely inform you Tim. He sheepishly asked about unit tests. The preparations you weave a story about a path in the forest, which merges with itself.

the

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

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

the

(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," say you, and happy to stretch out. "From Javac would be approximately five hundred eighty. We of course saved the order, missing stackmap and line mapping, but additionally, we reduced the number of variables, and threw four extra operations astore/aload. And of course, because the class never installerede, we do not need to generate method <init>, or call the superclass".

Tim is staring at you with silent interest. His jacket is shiny from the quickly melting frost. Most likely you're hired.

Reaching into the pocket of his robe, and gently, slow movements, so as not to startle him back to the burrow, extend my hand, unclench my fingers, and offer him a nut.

Article based on information from habrahabr.ru