?

Log in

No account? Create an account
Jane Street internship interview - Lindsey Kuper [entries|archive|friends|userinfo]
Lindsey Kuper

[ website | composition.al ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Jane Street internship interview [Jan. 31st, 2010|02:40 am]
Lindsey Kuper
[Tags|, ]

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 create, add, remove, and 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 dequeue using 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.


  1. 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.
LinkReply

Comments:
[User Picture]From: deepdistraction
2010-01-31 04:33 pm (UTC)
Good job, Lindsey! I hope they call soon. The waiting is the hard part.
(Reply) (Thread)
[User Picture]From: pmb
2010-01-31 06:10 pm (UTC)
Excellent! I want to here more about the last adventure, too.

But for now, I have a nerdsniping question: FIFO, LIFO, sure. FIFO I can see you could do by maintaining two LIFOs (input and output) and whenever you want to dequeue you pop off of output, or, if output is empty, you pop and push everything off of input and onto output and then pop off of output. O(1) (amortized) time. What about a deque?
(Reply) (Thread)
[User Picture]From: lindseykuper
2010-01-31 08:07 pm (UTC)
FIFO I can see you could do by maintaining two LIFOs (input and output) and whenever you want to dequeue you pop off of output, or, if output is empty, you pop and push everything off of input and onto output and then pop off of output. O(1) (amortized) time.

Yep, that's exactly it.

What about a deque?

Ooh! Okasaki has an article about that. See section 6, "Double-ended Queues". I need to read it more closely, but the idea is to represent the deque as four lazy lists...
(Reply) (Parent) (Thread)
[User Picture]From: pmb
2010-01-31 08:32 pm (UTC)
That FIFO from two LIFOs, while O(1) amortized time, has unbounded variance in the time it might take dequeue to execute. That's bothersome., but it looks like it is partially dealt with in the linked article. I'll spot you that 4 lazy lists will probably work to make a deque, but I remain bothered that something that is 20 lines of C code for sophomores is (or semi-recently was) a research topic in the functional programming community. It makes it hard for me as an algorithms person to get super-psyched about programming languages things when the easy stuff is so hard.

Anyhow, those are my issues with FP from a algorithms/data structures perspective, which I trot out whenever someone mentions Chris Okasaki's book. Is there a variant of FP (either a relaxation of some axioms or a strengthening of others or some special language/implementation that allows you to break out state in a non-crapy way) which makes data structures and algorithms non-painful? Students have enough trouble implementing Dijkstra's algorithm as it is -- I can barely imagine the howls of pain if I forced them to do it purely functionally.
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2010-01-31 09:34 pm (UTC)
It depends on your notion of what's easy and hard, I suppose. On the one hand, what you said. On the other hand, two-line quicksort. Sometimes FP is the wrong tool, and sometimes it's the right one. *shrug* Perhaps one of the reasons I like FP is that I came to it as a brand-new programmer with no preconceived notions of what should be easy and what should be hard, so to me there was no apparent contradiction.

A variant of FP that makes data structures and algorithms non-painful? These days, I'm trying not to evangelize for any specific language, but I actually think Scheme does a decent job of this; it encourages one to use side effects judiciously, when it makes sense. Scala? Clojure? I dunno.
(Reply) (Parent) (Thread)
[User Picture]From: pmb
2010-01-31 09:57 pm (UTC)
I see your point - it's similar to Eugene Wallingford's point ( http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2010-01.html#e2010-01-05T15_25_06.htm ) and I generally agree with it. I was hoping that pure functional programming had found some sort of magic dust that made data structures programming straightforward. Like how monads, while tricky, make output in Haskell both work like a person might want and allow it to remain lazy and pure. I want Dastructoids or something like that for complex data structures so that I can have purity cake and eat my data structures too. Also, I want a pony.
(Reply) (Parent) (Thread)
[User Picture]From: floydcollins
2010-02-02 08:36 pm (UTC)
I'm not sure Haskell is really the droid you're looking for here. In Haskell, the very first thing most* people want to do with a language (print "hello"), mires one in the tarpit, maybe purity is a little overrated :). I feel like Haskell is a great (okay, good) implementation, of a set of ideas, but that set of ideas ends up not being what I want.

In hearing this nastiness about dequeue's I'm reminded of the implementations of graphs in sql. Sure it's *doable* and *clean* but heckaboo, it's ugly.

Maybe try Scala? I'm not a java guy, but I like it better than clojure.
(Reply) (Parent) (Thread)
[User Picture]From: nwhitehe
2010-02-07 01:22 am (UTC)
I would say that OCaml is such a relaxation that you are looking for. In OCaml you can do pointer operations and implement data structures in a non-purely-functional traditional way. Or you can work through Okasaki's book and figure out how to do things purely functionally. Solving things like LIFO and FIFOs purely functionally is harder because the solutions do more. For example, you can add in undo/redo trivially.
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2010-01-31 10:06 pm (UTC)

The last adventure

I'm done at Jane Street at 1:30, but my flight doesn't leave until sevenish. I can take a cab to the airport and get Jane Street to foot the bill, but since I have no shortage of time, I want to see if I can get there on public transportation. Trains are easy, but this trip has to involve a bus, and I've never taken an MTA bus before. (Buses are scary. There are more possibilities, which means more ways to screw up, and you're more likely to end up in no man's land should you get off the bus at the wrong place.) It works out fine, though; I manage the train-bus transfer and walk into the Delta terminal a comfortable two and a half hours before my flight leaves.

I go to a kiosk, try to look up my reservation so I can get my boarding pass, and...my reservation isn't found. I try again, using a different method. Still not found. Third try. Still nothing. I get in line to talk to a real person. While I'm waiting, I take one last look at the email confirmation, just to make sure I didn't misread it somehow -- and, to my utter horror, it says that I have a flight leaving at 7:02 p.m. from JFK. It's 4:40 p.m. on a Friday, and I am at the wrong airport.

There are three possibilities. I can go to the ticket counter and tell them, "Hi! I'm a moron who came to the wrong airport! Will you please charge me $100 to change my flight to the next one from here to Indianapolis?" I can take a cab, but that would be expensive, too, and I can't very well ask Jane Street to pay for it, considering that it should have been unnecessary. Or, I can figure out how to get there on public transportation. Google Transit suggests a four-stage trip involving a bus and three trains that will just barely work, assuming that nothing goes wrong. I run to the bus stop with my big carry-on bag, pray that my MetroCard has enough money on it, take the Q33 bus to the 7 train to the E train to the AirTrain, and walk into JFK exactly one hour before my flight leaves, which turns out to be just enough time to get through security and find my gate.

This may not all seem so bad to a native, but it was unfamiliar territory for me, and the fact that it was twenty degrees out and getting progressively darker didn't help. So I'm proud of myself that I managed it! And even if nothing else comes out of the trip, I can at least say that I'm not scared of MTA buses anymore.
(Reply) (Parent) (Thread)
[User Picture]From: pmb
2010-01-31 10:32 pm (UTC)

Re: The last adventure

That's actually pretty bad-ass.
(Reply) (Parent) (Thread)
[User Picture]From: purebugbeauty
2010-01-31 10:43 pm (UTC)

Re: The last adventure

you should have called me or ed! we could have counseled and reassured. or in the very worst case scenario, conceivably have picked you up and driven you from one airport to the other. that said, HOORAY. you handled it admirably. i live here and i would have been freaked as hell.
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2010-02-01 02:52 am (UTC)

Re: The last adventure

Thanks, Rosemary! I was freaked out, but it helped a lot that I can use Google Maps (and therefore Transit) on my phone, so I had more or less step-by-step instructions.

If I find out that I'm going to be in NYC for the summer, your counseling and reassurement, especially on the topic of where to live, will be much appreciated! Also, I'd love to see you again.

Edited at 2010-02-01 02:52 am (UTC)
(Reply) (Parent) (Thread)
[User Picture]From: nwhitehe
2010-02-07 01:25 am (UTC)
Thanks for posting this writeup, fun stuff. I love hearing about interview questions and working them out for myself to see how I would have done.
(Reply) (Thread)
[User Picture]From: lindseykuper
2010-05-10 08:24 pm (UTC)
You're welcome. I really enjoyed this interview and the ones that led up to it, even though I ultimately wasn't offered the internship.
(Reply) (Parent) (Thread)