Jane Street 2nd Round Phone

Detailed In-Person Jane Street Interview: 1st and 2nd phone interviews (Originally Posted: 10/28/2010)

Two phone interviews about a week apart. I was then invited to their offices in NYC. The questions involved advanced functional programming techniqiues such as continuous passing style (CPS), lazy evaluation, memoization, and futures.

• 1st phone interview:
• Three bags: Oranges, Apples, Mixed. All mislabeled.
• Compute a random permutation so that each permutation is equally probable.

• Test the randomness of a black box that outputs random 64-bit floats.

• 2nd phone interview:

• Give the type of a binary tree and an algorithm to compute its depth:

type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree

let depth = function | Leaf -> 0 | Node (_, left, right) -> 1 + max (depth left) (depth right)

• Make it tail recursive (not told to use CPS):

let depth n = let rec loop n k = match n with | Leaf -> k 0 | Node (_, left, right) -> loop left (fun v1 -> loop right (fun v2 -> k (1 + max v1 v2))) in loop n (fun x -> x)

• 1st in-person interview:
• Given the signature: val lazy : (unit -> 'a) -> (unit -> 'a)

Implement 'lazy' that takes a function f and returns a function g such that f is only called if g is called, and f is only called at most once. g will always return the same result as if f was called. Non-obvious caveats are: the function f might raise an exception, or the use of the function g may be within a concurrent system.

type 'a lazy_option = None_lazy | Some_lazy 'a | Exn_lazy exn

let lazy f = let res = ref None_lazy in let lock = Mutex.create () in (fun () -> (* Try a non-blocking look up first ) match !res with | Some_lazy v -> v | Exn_lazy e -> raise e | None_lazy -> ( Obtain the lock and make sure it is really None_lazy *) Mutex.lock lock; match !res with | Some_lazy v -> Mutex.unlock lock; v | Exn_lazy e -> Mutex.unlock lock; raise e | None_lazy -> try let v = f () in res := Some_lazy v; Mutex.unlock lock; v with e -> res := Exn_lazy e; Mutex.unlock lock; raise e )

• 2nd in-person interview (right after 1st):
• Given the signature to a regular expression parser (perl style), give the implementation. The function 'match' should return the first match of an expression within a string and a new function 'more' that you can use to successively iterate all possible matches. You have 45 minutes to write this on a white board.

Keys: Once you are able to match a range of characters (e.g. A-Z), use this over and over. Decide early on whether * and + are greedy or non-greedy.

• 3rd in-person interview:
• You are given a module with the following signature:

type 'a ivar type 'a deferred

val create : unit -> 'a ivar * 'a deferred val upon : 'a deferred -> ('a -> unit) -> unit val fill : 'a ivar -> 'a -> unit

val read_file : string -> string deferred

• I was left guessing what this module does. Ask questions to clarify! This represents the future value of some computation. Use 'upon' to register a function to be invoked with the value written to the ivar at a future time. Some process will invoke 'fill' on an ivar to set its value once its computation is finished. Given this module (it is a black box), write the following function:

val file_size : string -> int deferred

• An example usage is the following: upon (file_size "some_file") print_int

• One implementation of 'file_size' may look like: let file_size name = let i, d = create () in upon (read_file name) (fun s -> fill i (String.length s)); d

• Generalize this to use any function that returns 'a deferred. This was horribly ill-defined and left even my two interviewers disagreeing as to what was desired. The desired solution mapped an 'a deferred to a 'b deferred:

val map_deferred : 'a deferred -> ('a -> 'b) -> 'b deferred

let map_deferred x f = let i, d = create () in upon x (fun v -> fill i (f v)); d

I got the impression that the interview process was going well until the last question. I was told the firm decided not to offer me a position, without any explanation. Reading other scenarios, Jane Street has either set the bar unattainably high, or you have to be part of the "boy's club" to get in.

On another note, the work environment is a crowded open space with people constantly yelling to each other. They advertise a 50 hour work week with no lunch break. My impression is that your base salary is just over $100k, without any indication of bonuses for software engineers. Given their skill requirements and the number of hours required, the compensation does not seem adequate (especially for NYC). You can earn more and be treated better elsewhere.