7.7 Detailed In-Person Jane Street Interview (Software Engineer)

[fysx]

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 (the ideal solution uses 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' such that it 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.

 

[Andy D.]

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.

Yeah I think you are right here. You could make a few grand less but get a much better deal a bit further outside NY, probably with flexi hours and work from home.

I guess at the end of the day though, if the work is the kind of thing you want to do then that is what really matters (as long as you can cover the bills).

 

[fysx]

Questions for Intern vs Engineer

I don't see why they wouldn't ask questions of similar difficulty. I'd be very surprised if they asked the exact same questions. There's a chance it's something similar but obfuscated. Likely I'd expect questions involving concurrency and lazy evaluation.

I suspect they might be more forgiving about your answers, since as an intern, they expect to train you and that your duration with them is limited. I heard them say in regards to hiring for a permanent position, that this was akin to marriage and that when they hire someone they had better be willing to keep this person on indefinitely. So if you are looking for a permanent position, it's probably helpful to give them the impression that you are looking to spend out the rest of your days at JaneStreet (even if this isn't true)!

In any event, best of luck with your interview! And when you are finished, it would be excellent if you were willing to post details about the interview (even though they will ask that you don't).

Thanks