bad answers to interview questions

2013.Apr.29

I updated my posting schedule: I’ll try to post every day, skipping weekends.


Here are some extreme examples of code you shouldn’t use to answer some common interview questions.

Let’s start with everyone’s favourite interview question, Fizzbuz!

The standard formulation is as follows.

Fizzbuzz: for the sequence of numbers 1..N, output fizz if the number is divisible by 3, buzz if the number is divisible by 5, and fizzbuzz if the number is divisble by both.

First, the boring solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# such a boring way to go...
def fizzbuzz_boring(n):
	for x in xrange(1,n):
		if not x % 15:
			yield 'fizzbuzz'
		elif not x % 5:
			yield 'buzz'
		elif not x % 3:
			yield 'fizz'
		else:
			yield str(x)

assert list(fizzbuzz_boring(21)) == \
       [   '1',     '2',  'fizz',     '4',      'buzz',
        'fizz',     '7',     '8',  'fizz',      'buzz',
          '11',  'fizz',    '13',    '14',  'fizzbuzz',
          '16',    '17',  'fizz',    '19'       'buzz']

A single-line, generalised solution that returns a lazy, infinite iterable and has no explicit conditions (i.e., if-statements):

1
2
3
4
5
6
7
8
9
10
11
12
from itertools import chain, combinations, count
from operator import mul, add
fizzbuzz_awful = lambda terms: (lambda terms: ({x%d:w for d,w in terms}.get(0,str(x)) for x in count(1)))(tuple((lambda (d,w):(reduce(mul,d),reduce(add,w)))(zip(*x)) for x in chain.from_iterable(combinations(sorted(terms.iteritems()),s) for s in xrange(1,len(terms)+1))))

from itertools import islice
terms = {3:'fizz', 5:'buzz', 7:'baz'}
assert list(islice(fizzbuzz_awful(terms),None,25)) == \
       [      '1',     '2',  'fizz',     '4',      'buzz',
           'fizz',   'baz',     '8',  'fizz',      'buzz',
             '11',  'fizz',    '13',   'baz',  'fizzbuzz',
             '16',    '17',  'fizz',    '19',      'buzz',
        'fizzbaz',    '22',    '23',  'fizz',      'buzz']

Back in the day, printing out lines of Pascal’s triangle was also a popular interview question.

The standard formulation

Pascal’s Triangle: Print out N rows of Pascal’s triangle

A single-line solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from itertools import tee, izip, chain, islice
pascal = lambda rows: reduce(lambda acc,_: acc+[[sum(x) for x in izip(*(islice(it,pos,None) for pos,it in enumerate(tee(chain((0,),acc[-1],(0,)),2))))]], xrange(rows), [[1]])

assert pascal(9) == \
      [[1], 
       [1, 1], 
       [1, 2, 1], 
       [1, 3, 3, 1], 
       [1, 4, 6, 4, 1], 
       [1, 5, 10, 10, 5, 1], 
       [1, 6, 15, 20, 15, 6, 1], 
       [1, 7, 21, 35, 35, 21, 7, 1], 
       [1, 8, 28, 56, 70, 56, 28, 8, 1], 
       [1, 9, 36, 84, 126, 126, 84, 36, 9, 1]]

This solution is fairly obfuscated. Expanded:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from itertools import tee, izip, chain, islice
# our standard nwise/pairwise generator; covered in depth yesterday
nwise = lambda it,n=2: izip(*(islice(it,pos,None) for pos,it in enumerate(tee(it,2))))

# given a row, find the next row:
#   pad (chain) the given row with a leading & trailing 0
#   and calculate the paired sums:
#   0, 1, 0 -> (0,1), (1,0) -> 1, 1
#   0, 1, 1, 0 -> (0,1), (1,1), (1,0) -> 1, 2, 1
# this matches how we calculate pascal's triangle by hand
def nextrow(row):
	return [[sum(x) for x in nwise(chain([0],row,[0]))]]

# use reduce to manage state: apply a function x times with shared state
#   start with a seed of [[1]]
#   in each step, just append the next row to the collection of rows
#   using our nextrow function on the last row we've seen
pascal = lambda num_rows: reduce(lambda rows,_: rows+nextrow(rows[-1]), xrange(num_rows), [[1]])

assert pascal(9) == \
      [[1], 
       [1, 1], 
       [1, 2, 1], 
       [1, 3, 3, 1], 
       [1, 4, 6, 4, 1], 
       [1, 5, 10, 10, 5, 1], 
       [1, 6, 15, 20, 15, 6, 1], 
       [1, 7, 21, 35, 35, 21, 7, 1], 
       [1, 8, 28, 56, 70, 56, 28, 8, 1], 
       [1, 9, 36, 84, 126, 126, 84, 36, 9, 1]]

Another question (that I saw on pyreddit.)

Parenthesis: Given N pair of parenthesis, write an algorithm to print out all balanced permutations.

A single-line solution:

1
2
3
permute = lambda n, s='{}': {s.format('()')} if n < 4 else permute(n-2, s.format('({})')) | permute(n-2, s.format('{}()')) | (permute(n-2, s.format('(){}')) if n > 5 else set())

assert permute(6) == {'()()()', '(()())', '()(())', '(())()', '((()))'}

This solution is actually fairly reasonable. Expanded:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def permute(n, s='{}'): 
	# if we have fewer than 4 parens to place, then there's only
	#   one way to place them: in the middle of whatever
	#   expression we've built up
	if n < 4:
		return {s.format('()')} 

	# otherwise, we have at least 4 parens to place
	#   try placing them on the outside, to the side 
	# however, if there aren't at least 6 parens left,
	#   there's no point placing them to the left and
	#   and to the right: there's no difference
	return permute(n-2, s.format('({})')) |\
	       permute(n-2, s.format('{}()')) |\
	      (permute(n-2, s.format('(){}')) if n > 5 else set())

assert permute(6) == {'()()()', '(()())', '()(())', '(())()', '((()))'}

But, please, do not use any of this code!

Next time: 1. the knight’s tour problem