Acing 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.

Azzie
Azzie, on

I’d laugh, but that had happened to me

Spelling Troll
Spelling Troll, on

s/sieze/seize :)

Bill Smith
Bill Smith, on

Nice writing, Aphyr. Were you reading William Gibson last night?

Cesar D
Cesar D, on

this was awesome.

Blaz
Blaz, on

This was seriously and awesome read. Worth a goof and a chuckle.

Eric Fode
Eric Fode, on

<3

Nathan
Nathan, on

Pure awesome. Thanks for writing Aphyr.

zpojqwfe1wfhiunz
zpojqwfe1wfhiunz, on

@Bill, The William Gibson version would begin thusly:

It was hot, the night I burned the Seeker. Moths batted themselves to death against the humming neon signs just outside the single window in the cramped room. There were ancient electronics piled to the ceiling in here, hot new chipsets from Taiwan still unwrapped distributed unevenly amongst them. The Seeker put his hands on his hips, brushing aside the corners of his Sukajan jacket bomber jacket replica. "I heard you and Bobby were hotshots, once. Real.. artístes", he said, the last word paired with a smug grin. "Heard you could do things." "Things like what?" It's been 20 seconds and you've already wasted too many cycles with this guy. "Things like making lists, just, fold up inside themselves. Come out the other way around. Crazy things." You grit your teeth. The dex has left your system and you're starting to feel a massive drug deficiency coming on. "Crazy things cost money", you manage. The lists already unfurling in your head, you start typing as quickly as you can to hide the microtremors.
Your Fan
Your Fan, on

Truly sublime.

Paul
Paul, on

Excellent. Reminds me of something by China Mieville.

Aaron
Aaron, on

Not Gibson. He’s obviously been reading The King Killer Chronicles by Patrick Rossfuss. “To know the name of a thing, is to have power over it”.

Nice incantations btw.

mario
mario, on

DAYYYAAAAAM

Marty
Marty, on

I don’t know, I sort of prefer

(defn cons [h t] #(if (or (= 0 %) %) h (if (number? %) (t (dec %)) t)))
Ahmed
Ahmed, on

Someone has been reading Rothfuss :)

anonymous
anonymous, on

Nope, I need a false?. Better:

(defn cons [h t] #(if (or (= 0 %) (false? %)) h (if (number? %) (t (dec %)) t)))
Nijiko Yonskai
Nijiko Yonskai, on

After the candidate took his leave the interviewer being bombarded with questions by the holders of steak stared out from inside the bustling warehouse wondering if he would ever truly understand what a list really is.

doktorpaine
doktorpaine, on

Kyle, you beautiful, mad man.

I need to try this in my next interview. Perhaps with raw lambda calculus for shits & giggles.

anonymous
anonymous, on

A transliteration in Python, because why let Clojure have all the fun?:

#!/usr/bin/python def cons(if_true, if_false): return lambda which: if_true if which else if_false def reverse_but_as_list(generated_cons, the_list = []): if generated_cons(False) is not None: return reverse_but_as_list(generated_cons(False), [generated_cons(True)] + the_list) else: return [generated_cons(True)] + the_list def reverse_but_as_cons(generated_cons, the_func = None): if generated_cons(False) is not None: return reverse_but_as_cons(generated_cons(False), cons(generated_cons(True), the_func)) else: return cons(generated_cons(True), the_func) l = cons(1, cons(2, cons(3, None))) # Reverse as Python list (normal order -> output is reversed from here) print(reverse_but_as_list(l)) # Reverse as Python list (the reversed cons -> output should be the same, but in a Python list instead) print(reverse_but_as_list(reverse_but_as_cons(l)))
Riking
Riking, on

In the spirit of the Python comment, I had a shot at writing this in golang. I hope you don’t mind.

I made sure to include tests, because we all know test-driven development is the wave of the present.

Forgive the generics, but this is a strictly typed language. Can’t have garbage of the wrong types polluting our beautiful lists.

package list import "io" import "fmt" // generics - swap out V1 for a new implementation type V1 int32 type I1 interface { Get() V1 Next() I1 } type T1 V1 type N1 func(bool) I1 func (t T1) Get() V1 { return V1(t) } func (t T1) Next() I1 { return nil } func (l N1) Get() V1 { return l(true).Get() } func (l N1) Next() I1 { return l(false) } var e I1 func Cons(h, t I1) N1 { return func(q bool) I1 { if q { return h } return t } } func Nth(l I1, n int) V1 { switch n { case 0: return l.Get() default: return Nth(l.Next(), n-1) } } func Print(l I1, w io.Writer) { fmt.Fprint(w, "(") for l != e { fmt.Fprint(w, l.Get()) l = l.Next() if l != e { fmt.Fprint(w, " ") } } fmt.Fprint(w, ")") } func Reverse(l I1) I1 { return reverse(e, l) } func reverse(r, l I1) I1 { if l == e { return r } return reverse(Cons(T1(l.Get()), r), l.Next()) }package list_test import "fmt" import ( "localhost.localdomain/list" "os" ) func ExampleCons() { l := list.Cons(list.T1(1), list.Cons(list.T1(2), nil)) fmt.Println(l.Get()) fmt.Println(l.Next().Get()) // Output: // 1 // 2 } func ExampleNth() { l := list.Cons(list.T1(1), list.Cons(list.T1(2), nil)) l = list.Cons(list.T1(3), l) fmt.Println(list.Nth(l, 1)) fmt.Println(list.Nth(l, 2)) // Output: // 1 // 2 } func ExamplePrint() { l := list.Cons(list.T1(1), list.Cons(list.T1(2), list.Cons(list.T1(3), nil))) list.Print(l, os.Stdout) // Output: // (1 2 3) } func ExampleReverse() { l := list.Cons(list.T1(1), list.Cons(list.T1(2), list.Cons(list.T1(3), nil))) list.Print(list.Reverse(l), os.Stdout) // Output: // (3 2 1) }
Jauzey
Jauzey , on

Ah, not Rothfuss but Le Guin herself! Who else but her on the subject of Naming.

Mitch
Mitch, on

And in JS, not so elegent, but can be understood by dummy like me

const cons = (a,b) => (x) => x ? a: b; const list = cons(1,cons(2,cons(3,null))); const printl = (l) => { const inner = (li,str) => { str = str + li(true); if (li(false) == null) console.log(str+')'); else { str += ', '; return inner(li(false),str) } }; return inner(l,'(') }; const reverse = (l) => { const inner = (li, data) => { const newItem = cons(li(true),data); if (li(false) == null) { return newItem; } else { return inner(li(false),newItem); } }; return inner(l,null); }; printl(list); printl(reverse(list));
anonymous
anonymous, on

Here’s a Perl version. I’ve tried to make it as literal as possible, translating line by line.

Some of the changes:

  • use 1 and 0 instead of true and false because Perl doesn’t have a boolean type
  • nil becomes undef, naturally
  • there’s nothing like the loop macro, so use an anonymous function instead
  • reverse is a builtin, so name the function reversed instead

This was quite fun.

use v5.16.0; use warnings; use Function::Parameters qw(:strict); fun cons($h, $t) { fun ($x) { $x ? $h : $t } } { my $x = cons 1, cons 2, undef; say $x->(1); # 1 say $x->(0)->(1); # 2 say $x; # CODE(0x947a5f8) } fun nth($l, $n) { $l and $n == 0 ? $l->(1) : __SUB__->($l->(0), $n - 1) } fun prn_list($l) { print "("; fun ($l) { !defined $l ? print ")\n" : do { print $l->(1); print " " if $l->(0); __SUB__->($l->(0)) } }->($l) } prn_list cons 1, cons 2, cons 3, undef; # (1 2 3) fun reversed($l) { fun ($r, $l) { $l ? __SUB__->(cons($l->(1), $r), $l->(0)) : $r }->(undef, $l) } prn_list reversed cons 1, cons 2, cons 3, undef; # (3 2 1)
Hisham
Hisham, on

In Lua:

function cons(h, t) return function(x) return x and h or t end end x = cons(1, cons(2, cons(3, nil))) function nth(l, n) return n == 0 and l(true) or nth(l(false), n-1) end function prn_list(l) io.write("(") while l do io.write(l(true)..(l(false) and " " or "")) l = l(false) end io.write(")\n") end function reverse(l) local loop loop = function(r, l) return l and loop(cons(l(true), r), l(false)) or r end return loop(nil, l) end prn_list(reverse(x))

In MoonScript:

x = cons 1, cons 2, cons 3, nil prn_list = (l) -> io.write "(" while l io.write (l true) .. ((l false) and " " or "") l = l false io.write ")\n" reverse = (l) -> loop = (r, l) -> l and (loop (cons (l true), r), l false) or r loop nil, l prn_list reverse x
Hisham
Hisham, on

Paste missed a bit of MoonScript:

cons = (h, t) -> (x) -> x and h or t nth = (l, n) -> n == 0 and (l true) or nth (l false), n-1 print nth x, 2
Shane
Shane, on

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.

This is one of the best paragraphs ever written in English.

Marco
Marco, on

And the Java version. Surprisingly it doesn’t look that bad :-)

import java.util.function.Function; public class Main { interface List<T> extends Function<Boolean, Object>{ default T head() { return (T)apply(true); } default List<T> tail() { return (List<T>)apply(false); } default T nth(int idx) { return idx == 0 ? head() : tail() == null ? null : tail().nth(idx - 1); } default String print() { return "(" + printLoop(this); } static <T> String printLoop(List<T> list) { return list.head().toString() + (list.tail() == null ? ")" : " " + printLoop(list.tail())); } default List<T> reverse() { return reverseLoop(null, this); } static <T> List<T> reverseLoop(List<T> reversed, List<T> remainder) { return remainder == null ? reversed : reverseLoop(cons(remainder.head(), reversed), remainder.tail()); } static <T> List<T> cons(T head, List<T> tail) { return (whichOne) -> whichOne ? head : tail; } } public static void main(String[] args) { List<Integer> x = List.cons(1, List.cons(2, List.cons(3, null))); System.out.println(x); System.out.println(x.head()); System.out.println(x.tail()); System.out.println(x.tail().head()); System.out.println(x.tail().tail()); System.out.println(x.nth(0)); System.out.println(x.nth(1)); System.out.println(x.nth(2)); System.out.println(x.nth(3)); System.out.println(x.print()); System.out.println(x.reverse().print()); } }
Scott Maddox
Scott Maddox, on

And here it is in a language I just made up, based on De Bruijn indexed lambda calculus:

-- this is a line comment -- the lines below declare intrinsic values and functions top := intrinsic -- the singular instance of the Top type if_top := intrinsic -- returns second argument if first argument is top; -- otherwise, returns third argument concat := intrinsic -- returns the concatenation of two string literals -- the lines below define derived values and functions; backslashes create lambda abstractions true := \ \ 2 -- returns the first of two arguments false := \ \ 1 -- returns the second of two arguments pair := \ \ \ 1 2 3 -- creates a pair from two terms fst := \ 1 true -- accepts a pair and returns the first term snd := \ 1 false -- accepts a pair and returns the second term list := pair "1" (pair "2" (pair "3" top)) -- example list list_to_string := -- accepts a list and returns a string of its contents \ if_top 1 -- (with a single trailing space) (" ") (concat (concat (fst 1) (" ")) (list_to_string (snd 1))) reverse := \ if_top 1 (top) (pair (reverse (snd 1)) (fst 1)) -- the lines below are semicolon-terminated statements that are evaluated and printed list_to_string list; list_to_string (reverse list);
Aphyr
Aphyr, on

Geo Carncross, on the k mailing list, conjured this delightful gem in k:

cons:{$[z;x;y]} nth:{$[~y;x 1;o[x 0;y-1]]} prn:{,[;")"]"("," "/${$[()~x;();x[1],o[x 0]]}x} reverse:{$[()~x;y;o[x 0;cons[x 1;y]]]}[;()]
Glyph
Glyph, on

No disrespect to the previous Python poster, but I really felt like it wasn’t quite in the spirit of the post.

My own humble attempt:

cons = lambda h, t: lambda w: h if w else t x = cons(1, cons(2, None)) nth = lambda l, n: None if not l else l(True) if n == 0 else nth(l(False), n-1) prn_list = lambda l: "[" + ", ".join(map(str, iter(lambda n=[0]: nth(l, n.append(n[0]+1) or n.pop(0)), None))) + "]" reverse = lambda l, r=None: r if l is None else reverse(l(False), cons(l(True), r))

(available as a Jupyter notebook here https://gist.github.com/glyph/0a77a80e4f2d1cf24514f8cd38617c8b)

Glyph
Glyph, on

Okay, I’m sorry, relying upon the iterator protocol is equally gauche. Please accept this alternate implementation of prn_list, which more properly relies only upon optional parameters and string concatenation for a recursive definition:

prn_list = lambda l, b="[", m="", e="]": ( b + ("" if l is None else m + str(l(True)) + prn_list(l(False), "", ", ", "")) + e )
Wodin
Wodin, on

For the person who asked whether this was lisp:

Yes, it’s a lisp called Clojure.

Cory
Cory, on

We compulsively run ls in every directory for the same reason we prefer to walk around our homes with the light on. The further you go without reorienting yourself, the more likely you make a mistake.

botchagalupe
botchagalupe, on

Young man, you are undeniably brilliant. I would go further than Gibson. I would say you are the David Foster Wallace of distributed computing. With that said, things use to be a lot easier back in my day…

Here’s my tongue and cheek attempt to tell how it was back in the 1980’s with a couple of caveats…

  • I haven’t coded IBM 370 Assembler since 1988.
  • I don’t have a mainframe to test the code.
  • If there are actual coding errors it’s just a joke anyway.
  • Please reread #3.

You might have also noticed that I cheated in a few places.. just a little bit. However, unless I missed the main point… WTF is a list anyway….

.... .... some entry stuff .... LA R1,ALIST PUT 0(,R1),OUTREC MVI 1(R1),=X'F3' MVI 5(R1),=X'F1' PUT 0(,R1),OUTREC * * At this point you're kind of done.. however, if they insist. * LA R1,ALIST SR R2,R2 LOOP1 LA R2,1(,R2) MVC R2(1,R1),0(R2) LA R2,1(,R2) TR R2(1,R1),HEXTAB1 BNZ LOOP1 PUT ALIST,OUTREC LA R1,ALIST SR R2,R2 LOOP2 LA R2,1(,R2) MVC R2(1,R1),0(R2) LA R2,1(,R2) TR R2(1,R1),HEXTAB2 BNZ LOOP2 PUT ALIST,OUTREC .... .... some other clean up stuff .... ALIST DC X'4DF16BF26BF35D' OUTREC DS CL6 HEXTAB1 DS XL256'00' DC C'123' HEXTAB2 DS XL256'00' DC C'321'
David Mathers
David Mathers, on

Ruby:

def cons(h, t) -> w { w ? h : t } end x = cons(1, cons(2, nil)) x.(true) x.(false).(true) def nth(l, n) return if l.nil? if n.zero? l.(true) else nth(l.(false), n.pred) end end def prn_list(l) print '(' until l.nil? print l.(true) print ' ' unless l.(false).nil? l = l.(false) end puts ')' end prn_list(cons(1, cons(2, cons(3, nil)))) def reverse(l) r = nil until l.nil? r = cons(l.(true), r) l = l.(false) end r end prn_list(reverse(cons(1, cons(2, cons(3, nil)))))
Wodin
Wodin, on

@botchagalupe

Here’s a mainframe for you: http://www.hercules-390.org/

anonymous
anonymous, on

“People create programs to direct processes. In effect, we conjure the spirits of the computer with our spells.” - SICP

anonymous
anonymous, on

reverse(list); EOF

anonymous
anonymous, on

Smalltalk:

| cons x nth printList reverse | cons := [ :h :t | [:w | w ifTrue: [ h ] ifFalse: [ t ] ] ]. x := cons value: 1 value: (cons value: 2 value: nil). Transcript show: (x value: true); cr. Transcript show: ((x value: false) value: true); cr. nth := [ :l :n | (n == 1) ifTrue: [ l value: true ] ifFalse: [nth value: (l value: false) value: (n-1)]]. x := cons value: 1 value: (cons value: 2 value: (cons value: 3 value: nil)). Transcript show: (nth value: x value: 1 ); cr. Transcript show: (nth value: x value: 2 ); cr. Transcript show: (nth value: x value: 3 ); cr. printList := [ :l | | p | p := [ :l1 | l1 ifNotNil: [ Transcript show: (l1 value: true). (l1 value: false) ifNotNil: [ Transcript show: ' ' ]. p value: (l1 value: false). ] ]. Transcript show: '('. p value: l. Transcript show: ')'; cr. ]. printList value: (cons value: 1 value: (cons value: 2 value: (cons value: 3 value: nil))). reverse := [ :l | | r l1 | r := nil. l1 := l. [l1 notNil] whileTrue: [ r := cons value: (l1 value: true) value: r. l1 := l1 value: false. ]. r ]. printList value: (reverse value: (cons value: 1 value: (cons value: 2 value: (cons value: 3 value: nil)))).

Post a Comment

Please avoid writing anything here unless you are a computer: This is also a trap:

Supports github-flavored markdown for [links](http://foo.com/), *emphasis*, _underline_, `code`, and > blockquotes. Use ```clj on its own line to start a Clojure code block, and ``` to end the block.

Copyright © 2017 Kyle Kingsbury.
Non-commercial re-use with attribution encouraged; all other rights reserved.
Comments are the property of respective posters.