Facebook, Take II

When last I wrote about a Facebook interview, the news wasn't what I would normally call good. Rather than recap that incident, I'll just refer you to the previous writeup but suffice it to say this round went better. A whole lot better.

In interviews, I've routinely heard the lie "use whatever you are comfortable with". I call this a lie, because ultimately your interviwer needs to comprehend whatever dark magic you chose to work on the whiteboard and if there's a language barrier while you may be able to slip some small bugs through the interviewer won't be able to validate that you really understand what's going on by trying to poke holes in your code. Combine this with the unfortunate tendancy of the programmers I've met to rapidly loose focus when presented with Lisp dialects I tend to code in Python for interviews. It's not functional, it's not typed, but damnit anyone can read it.

So the question. I got a two part, presumably the "can you code" and it's mate the "so you can code, but can you to this?".

The initial problem

Build a function f such that

f([1])     -> [[1]]
f([1 2])   -> [[1] [1 2] [2]]
f([1 2 3]) -> [[1] [1 2] [1 3] [1 2 3] [2] [2 3] [3]]
...

The insight required for this problem is that the answer is fundimentally recursive. Don't believe me? Check out this value...

f([2 3]) -> [[2] [2 3] [3]]

Does that look familiar? it should...

f([1 2 3]) -> [[1] [1 2] [1 3] [1 2 3] [2] [2 3] [3]]
f([2 3])   -> [[2] [2 3] [3]]

So if you preppend 1 to f([2 3]), you have a subsequence of f([1 2 3])! This is awesome, because it implies that f is really

1
2
3
4
5
6
def foo(seq):
  for i in seq:
    yield [i]
    for j in foo([x for x in seq
                  if x != i]):
    yield [i] + j

Which works... but isn't especially nice since it involves this O(N) filter. It also doesn't do a nice job of the empty input case. Realizing that an order property exists in the sample cases that filter can become tricks with the list index:

1
2
3
4
5
6
7
8
9
def foo(seq):
  if(len(seq)):
    i = 0
    for i in range(len(seq)):
      yield [seq[i]]
      for j in foo(seq[i+1:]):
        yield [seq[i]] + j
  else:
    yield []

And that snippet totally works, and is O(N) for what it's worth.

The tricky bit

The problem was redefined to be

Build a function f such that

f([1])     -> [[1]]
f([1 1])   -> [[1] [1 1]]
f([1 1 2]) -> [[1] [1 1] [1 1 2] [1 2] [2]]
...

Now this is almost the original function.. but there's this funky new requirement that repeated values do not generate duplicate permutations. The trick here, is to sort the input sequence. Think about it. By rendering the input sequence sorted, the same (order ignored) set of permutations will be generated but our algorithm would be able to decern in constant time if the next iteration of the loop would generate a previously computed permutation and could skip ahead. Okay, so that would be

1
2
3
4
5
6
7
8
9
10
11
12
def foo(seq):
  if(len(seq)):
    i = 0
    while i < len(seq):
      yield seq[i]
      for j in foo(seq[i+1:]):
        yield [seq[i]] + j
    while(seq[i] == seq[i + 1]):
      i = i + 1
    i = i + 1
  else:
    yield []

Which totally works... but it's explicitly iterative and really bloody stateful. Not that I trust myself to cook this up on the spot in an interview, but how to do this in a real language like Clojure? Well, since the second problem is a special case of the first, lets consider the first. Our spec was

f([1])     -> [[1]]
f([1 2])   -> [[1] [1 2] [2]]
f([1 2 3]) -> [[1] [1 2] [1 3] [1 2 3] [2] [2 3] [3]]
...

One approach in Clojure would be

1
2
3
4
5
(defn foo [sequence]
    (cons []
        (for [i (range (count sequence))]
            (cons (get sequence i)
                (foo (drop sequence i))))))

Which isn't exactly to spec, because f([]) is undefined, but here it's effectively [[]] for the sake of achieving the [[1]] case without anything funky to yield two values.

The Clojure version of the second part really cheats...

1
2
3
4
5
6
7
8
9
(defn foo [sequence]
    (cons []
        (for [this (range (count sequence))
             :let [next (inc i)]
             :when (or (= (count sequence) next)
                       (not (= (get sequence this)
                            (get sequence next))))]
            (cons (get sequence this)
                  (foo (drop sequence this))))))

By using the :when keyword option to skip the duplicate states, ensuring that the loop will only generate those values such that the (i+1)th term is not equal to the ith term, this being the same loop condition as the python code above.

The Clojure version is nicer, but was written with full access to the docs and the prior knowlege of the insights that make the Python version(s) work. If the Python verisons were reworked to incorperate the [[]] base case, then they'd shrink by three lines and an indentation level. There is also a bug in the Python version, where the input [ 1 1 ] would cause an index out of bounds exception in the de-duplication loop. The Clojure implementation silently lacks this flaw. I'd call it even... neither version will run in constant space due to both being lazy generators, but the Clojure version will do it faster thanks to the JVM. Sadly at this small problem size I don't really think that the Clojure Way really has its chance to shine.

^d