Facebook, Take II
23 Oct 2013When 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