Jane Street Interview Question: Find the smallest sublist siz... | Glassdoor

Interview Question

Software Developer Interview

Find the smallest sublist size in a list of lists. Then

  after I came up with an algorithm that used List.length to compare which is an O(n^2) algorithm, he asked how could this be improved, which stumped me.
algorithm, ocaml

Interview Answer

3 Answers


If n is the total number of elements in all the lists of list, then it should be O(N), as you can just record the min, and use List.length for each sublist and update min if you meet the smaller size.

let min_sub ll = List.fold_left ~init:max_int ~f:(fun min l -> let len = List.length l in if len < min then len else min) ll

Dimi on May 31, 2014

^ this is incorrect. List.length is O(n) as stated in the problem so using it is O(n^2). Here's an O(nlog(n)) algorithm.

Find length of the first sublist. Call this L. Then, for each subsequent sublist, check if L is a valid index into that list. If so, ignore it. Else, use binary search (starting from L) to find the length of this smaller sublist. It's length is the new L. Repeat going through the list and you win.

Nick Jonas on Oct 18, 2017

^ This doesn't make any sense. Knowing if L is a valid index in that list takes O(n). The best you're going to get it to make the whole algorithm O(nm), where n is the number of lists and m is the length of the first list.

Binary search on a list that doesn't provide any kind of random access guarantees (as functional lists don't) is nonsensical.

Anonymous on May 6, 2018

Add Answers or Comments

To comment on this, Sign In or Sign Up.