I arrive at LaGuardia at 5:30 p.m. on Thursday afternoon. I've been told that a car will meet me at the airport, but I don't have any more specific information than that. Then, roughly ten seconds after I step off the plane, I get a call from a friendly-sounding guy who tells me to head to the nearest exit, where he will be pulling up momentarily. Clearly, Jane Street has already planted a tracking device on me.
He drives us to Manhattan -- the last few blocks of the drive taking roughly as long as the first nine miles -- and drops me off at the place they have me staying, which is a fancy, modern hotel near Times Square. By "fancy" and "modern" I mean that it isn't immediately apparent how to get to the room after I'm checked in. On my first try, I end up taking the wrong elevator, which dumps me back out on the street again. It's hard to look cool when you have to go back to the fancy, modern check-in desk to ask how to get to your room. Once I finally make it to the room, which is on the fifty-second floor, it takes some effort to figure out how to turn on the fancy, modern sculpture fountain bathroom sink. I can only assume that all this is part of the interview process.
I manage to get settled, though, and that night I go out and meet up with Joe, an old friend and musical collaborator from college whom I haven't seen in a few years. We have a drink and make a solemn pact to record an EP together if I end up in New York for the summer. Back in my room, I sleep soundly until my 8 a.m. wake-up call the next morning and head down to the financial district on the subway with the expert help of Google Transit. I'm ten minutes early for my appointment, and they take me to a room to wait. I gradually realize that the table I'm sitting at is a poker table and is covered with chips and playing cards, which elicits equal parts delight and consternation.
A little while later, my first interviewer comes in and takes me to a different room, this one with a fantastic view of the East River and
Governors Island, and we're off. He asks me to come up with an implementation for a
"bag" data structure with
iter methods and more or less constant-time
random access. The catch is that we can assume nothing about the
elements the bag is holding. I wonder how we can get specific elements
out of the bag once they've gone in, since if they have no
attributes that we can access (or even know about), we can't very
well pick them out by, say, color or scent or general demeanor. "You get to
figure that out!" my interviewer says. I suggest putting each
element in a wrapper with a unique integer key. (This is exciting, because at the moment my voice is saying "wrapper", my brain is saying "lambda".) The
add method then has
to return the key, so that the caller will have
some hope of getting the element it's just added back out
again at some point in the future. And we can put the wrapped
elements in a hash table, I suggest. (For those of you playing
Technical Interview Bingo at home, you may now check off the boxes for
"hash table" and "unique integer key".)
I start sketching this out on the whiteboard. I'm afraid he's going to actually make me implement hash tables, but to my relief, he writes out the signature for a Hashtbl module in OCaml, and then asks me to implement the Bag methods in terms of Hashtbl. Most of it is
pretty straightforward, although
iter requires a little higher-order trickiness to make the types work out. I'm kind of proud, actually -- my wrapper idea works out fine, although my interviewer has to help me quite a lot with OCaml syntax.
When we're through with this, my first interviewer leaves, and I have a few minutes to pace around and get nervous. I notice that this room, too, is filled with playing cards; I pick up a stray piece of paper from a table, and it contains instructions for playing bridge. I consider grabbing one of several decks of Jane-Street-branded cards as a souvenir, but it occurs to me that stealing stuff from the company interviewing you is probably not a great way to get a job.
Eventually, my second interviewer comes in, holding a copy of my CV. He asks me to implement a purely functional queue data structure that has amortized constant-time access (Technical Interview Bingo: "amortized constant time"). I don't have a sense of how to do it aside from "um, use lists", so he suggests a design1, and then it's my turn to actually implement the thing. I start putting a muddled mix of Haskell and OCaml on the board, and honestly, it's not going so well, so when my interviewer
suggests that I switch to Scheme ("it's all lambda-calculus to me!"),
I happily do so. That goes much better. My interviewer suggests I start by defining the empty queue, and from there it's straightforward to write enqueue and dequeue operations and explain them. I make a couple of mistakes, but I catch and fix them myself as I'm going along. Then, since he's been reading my CV for the last several minutes and knows that I've worked on a paper about a pattern matcher, my interviewer asks if I can write
pattern matching. As soon as he suggests it, I see that my code is screaming out for it, so I write a new version using pmatch, the little pattern matcher that we teach in C311 these days. Using pmatch tightens up the code quite a bit. My interviewer has to leave the room briefly, but eventually, he comes back and I have a couple of minutes to explain how it works. He asks me if the
system is smart enough to know if I've accidentally left out a case, and I have to admit, "Oh...um...no. That's where OCaml wins." Then I go and get a knife and perform seppuku.
Just kidding. Then we have lunch! I get to meet all three of the quants I've already communicated with by phone and email, as well as a fourth who is new to me. They have some interesting insights about the difference between being a quant and being a trader. Quite often, they say, quants and traders are almost identical on paper; many of the traders at Jane Street have CS or math backgrounds. The difference, they tell me, is in personality -- quants are much more risk-averse. Jane Street has mock trading sessions to train new traders, and some of the quants participate in those, but they kept getting smoked so bad, they say, that they had to start having special mock trading for quants. "Is there remedial OCaml for traders?" I ask, intending it as a joke, but they say, "Yes!"
At one point, one of them says that he has no intuition for statistics at all, so I pull The Cartoon Guide to Statistics out of my bag and hand it to him across the table. He flips it open to a page in the middle. "Central limit theorem! Why'd they put that in the middle?" "Because it's central," someone else cracks. Groans all around.
When lunch is over, they tell me that they don't have anything else scheduled for me, and that I'll hear from them in a few days (Technical Interview Bingo: "You'll hear from us in a few days..."), but that I should feel free to stick around in the office and finish my salad, which I've barely touched. I'm a little concerned that the interview seems to be over so soon, but on the whole, I feel that things went roughly as well as they had gone in the two phone interviews, and those seem to have worked out all right. I fly home that night -- with an unintended adventure on the way to the airport that actually demands more of me, adrenaline-wise, than the interview, but that's a story for another time -- wolf down a midnight pizza at Mother Bear's with Alex oniugnip, and sleep at last.
- Back last April, one of my friends -- the same one who kept asking me what was so great about Scheme -- told me he was frustrated about the way Scheme made him "twist everything into a recursive, list-based form". I told him that I was having a hard time thinking of a problem that didn't fit that form, and he said, "How about a FIFO?" Thus nerdsniped, I went looking for constant-time, purely functional queue implementations in Scheme, and I was able to dig up this paper for him. (This was before I'd ever heard of Chris Okasaki's book.) I didn't actually, you know, read the paper before sending it to him, but now that I look at it, the representation described in section 2.2 is precisely what my interviewer suggested. It's a cute idea, and not that hard to implement.