Problem Statement:

You are the bottom of a staircase of \(N\) steps. Each time, you can either go up by one step, or go up by two steps (skipping a step inbetween). How many ways are there of climbing the staircase ?

Let us call the number of ways to climb a staircase of \(X\) stairs \(f(X)\). The answer we are looking for then is \(f(N)\). As you might have noticed, this problem will involve recursion. Let’s look at the base cases. There is only one way of climbing a staircase of \(0\) steps, that is to take no steps at all. For a staircase of one way, you have precisely one way of climbing it - you take one step. Hence, the base cases are: \[ F(0) = 1 \\ F(1) = 1 \] Imagine now you are the top of the staircase of \(N\) steps. You had two ways of getting there. Either, you were on step \(N-2\) and took a step of size \(2\), or you were at step \(N-1\) and took a step of size \(1\). Hence, the number of ways to getting to step \(N\) is recursively defined in terms of \(N-1\) and \(N-2\). \[ F(N) = F(N-1) + F(N-2) \] You might notice that the solution to this problem is the Fibonacci sequence!

Now that we have the answer for the case of taking a step of size one or two each time, we can generalize the problem by saying that at each time you take a step, you can step anywhere between \(1\) and \(x\). Let us define the number of ways to climb a staircase of \(N\) steps, each time taking a step of size from \(1\) to \(x\), as \(F_x(N)\). The solution to the above problem is then \(F_2(N)\).

Firstly, let’s write out some of the solutions by hand to get the intuition behind the problem.

X | Sequence
------------
2 | 1 1 2 3 5 8
3 | 1 1 2 4 7 13
4 | 1 1 2 4 8 15

Let’s look at the case of \(X=3\). For \(N=0\), \(1\), \(2\), the solutions are exactly the same as for \(X=2\). This is because a step of size \(3\) is useless to us when we need to cover a distance of length less than \(3\). Then, for any \(N\), \(N<X\), the solution is simply \(f_N(N)\).

Otherwise, if \(N \geq X\), we can calculate \(f_X(N)\) just like in the simple \(X=2\) case, \(f_X(N) = \sum_{i=1}^{X}f_X(N-i)\).

We now have the full recursive formulation, which we can translate to Python as follows:

def fib(N,X):
  if(N == 0 or N == 1):
    return 1
  if(N < X):
    return fib(N,N)
  if(N >= X):
    ret = 0
    for i in range(1,X+1):
      ret += fib(N-i, X)
    return ret

This is just a generalization of Fibonacci numbers. You can of course memoize the above piece of code.

Problem Statement:

Given an integer number \(N\), output all the possible text strings that number could make when interpreted on a standard T9 phone keyboard. For example, \(2\) maps to ["a","b","c"].

You can think of the problem as a large tree, and where each next number corresponds to a choice point between all the available letters. For example, for the input \(23\), the first node has three branches, ["a","b","c"], and each of these sub-branches has a node with another three branches, ["d","e","f"]. From this, you can see that there are \(9\) answers to this question, and in general, if every integer maps to \(3\) letters, we will have \(3^n\) combinations.

In code, we can think about this recursively. If we have only one integer \(x\), we simply return the list of all letters that \(x\) maps to in our dictionary. Otherwise, assume we have a list of integers \(L\) of length \(n\). Take the first element \(L_1\), and recursively compute all the possible combinations \(C\) of the leftover sequence \(L_2 \ldots L_n\). Then, what’s left to do is to for every combination \(c\) in \(C\), and for every letter \(l\), \(L_1\) maps to, prepend \(l\) to \(c\) and append it to our result.

The following python code demonstrates this. Notice we have to set up the dictionary first.

t9 = dict()
t9[2] = ['a','b','c']
t9[3] = ['d','e','f']
t9[4] = ['g','h','i']
t9[5] = ['j','k','l']
t9[6] = ['m','n','o']
t9[7] = ['p','q','r','s']
t9[8] = ['t','u','v']
t9[9] = ['w','x','y','z']
t9[0] = [' ']

def decode(l):
  if(len(l) == 1):
    return t9[l[0]]

  ret = []
  for d in decode(l[1:]):
    for ch in t9[l[0]]:
      ret.append(ch+d)

  return ret

Testing the above:

> print(decode([2,3,4]))
['adg', 'bdg', 'cdg', 'aeg', 'beg', 'ceg', 'afg', 'bfg', 'cfg', 'adh', 
 'bdh', 'cdh', 'aeh', 'beh', 'ceh', 'afh', 'bfh', 'cfh', 'adi', 'bdi', 
 'cdi', 'aei', 'bei', 'cei', 'afi', 'bfi', 'cfi']

Problem Statement:

Generate all the permutations of a list

This is another rather simple interview-type question, quite similar in spirit to that of generating the power set.

Imagine a list \(L\), and an element \(x_i\). Generate all the possible permutations of \(L - x_i\). Then, intersperse \(x_i\) into every possible position for every element of the permutations of \(L - x_i\).

For example, given a list [1,2], take the sublist [2], and generate a list of all possible permutations, [[2]]. Now, add the element 1 into every possible position for [2], that is at index \(0\) and at index \(1\). This generates the list [[1,2],[2,1]], our required answer.

We turn the above into a simple Python code:

def permutations(s):
  if(s == []): return [[]]

  ret = []
  for k in permutations(s[1:]):
    for i in range(len(k)+1):
      ret.append(k[0:i] + [s[0]] + k[i:])

  return ret

Testing it with a simple example:

> print(permutations([1,2,3]))
[[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]

This confirms the code is correct.

Problem Statement:

Generate the power set of a set \(S\) of \(n\) elements.

This is also a nice, short, and quick interview question. Straight away we know that our algorithm will be exponential, \(O(2^n)\) since that’s the size of the powerset.

We can easily think about this recursively. The power set of the empty set is a set with one element, the empty set. The empty set is part of the powerset of any set. Then, think of an element \(x_i\) from \(S\). Assuming we have the solution for the powerset \(P_1\) of \(S - \{x_i\}\) }, we can put \(x_i\) into every element of that set, and take the union of it with \(P_1\):

Translating this into simple code is as follows. In the code, \(i\) is the index from which we want the to take the powerset of \(S\). We get the whole powerset of \(S\) when \(i=0\).

def powerset(s):
  return powerset1(s,0)

def powerset1(s,i):
  if(i == len(s)): return [[]]
  
  p1 = powerset1(s,i+1)
  
  ret = []
  for p in p1:
    ret.append([s[i]] + p)
  return ret + p1

Testing it with a simple example…

> print(powerset([1,2,3]))
[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

This confirms the code is correct.

Problem Statement:

Given an integer \(n\), print all valid combinations of brackets “(” and “)”. This means that there is an equal amount of left brackets and right brackets, and at no point in the string are there more right brackets than left brackets. For example, given \(n=2\), you have the two possible bracketings [(()),()()].

I saw this a couple of times as an interview question, and thought it’s worth exploring.

Firstly, I want the list of all possible bracketings stored at returned, not just printed.

We can notice straight away that this problem lends itself to a recursive solution. The answer for \(n=0\) is no bracketings, or the empty string. Otherwise, I found it extremely helpful to write what a valid bracket expression is in Backus-Naur form. It’s as such: \[ \begin{aligned} b &:= \epsilon \\ b &:= \text{'(' } b \text{ ')' } b \end{aligned} \] where \(b\) is a bracket expression and \(\epsilon\) is the empty string. This generates all possible bracketings. This simply means that a valid bracket expression is an empty expression, or a bracket, followed by a valid bracket expression, followed by another bracket, followed by another bracket expression.

We now want to restrict ourselves to bracketings of length \(n\). Again, we can think recursively here. Let \(B(n)\) represent the set of all bracketings of length \(n\) (meaning a total of \(2n\) brackets). Then, \[ \begin{aligned} S(0) &= \{\} \\ S(n) &= \bigcup_{i=0}^{n-1} \text{'('} \times S(i) \times \text{')'} \times S(n-i-1) \end{aligned} \] with a little bit abuse of notation. I mean \(\times\) to represent the Cartesian product that instead of returning tuples, joins strings it one.

We now have to just turn the above into Python code!

def getBrackets(n):
  if(n == 0):
    return [""]

  ret = []

  for i in range(n):

    brackets1 = getBrackets(i)
    brackets2 = getBrackets(n-i-1)

    for b1 in brackets1:
      for b2 in brackets2:
        ret.append( "(" + b1 + ")" + b2)

  return ret

Let’s test it out.

> print(getBrackets(3))
['()()()', '()(())', '(())()', '(()())', '((()))']

which is correct, there are 5 ways.

The above is a perfect example of overlapping subproblems. The code, as it’s executing the for loop, will keep on needing to get the same results for \(getBrackets(i)\), and will have to recompute them every time. We can solve it by keeping a hashmap of previous results for every \(i\).

# Returns a list of all bracketings
bracketDict = dict()

def getBrackets(n):
  if(n == 0):
    return [""]
  if(n in bracketDict):
    return bracketDict[n]

  ret = []

  for i in range(n):

    brackets1 = getBrackets(i)
    brackets2 = getBrackets(n-i-1)

    for b1 in brackets1:
      for b2 in brackets2:
        ret.append( "(" + b1 + ")" + b2)

  bracketDict[n] = ret
  return ret

The above works very well, and in my opinion is much clearer than this second method that I’m about to present (I’ve seen it somewhere online, and a friend of mine claims it’s more clear).

The approach is also recursive, and uses an accumulator which keeps the current string, as well as counters saying how many left brackets we have left and right brackets we have left to use up. When both counters reach 0, we have a valid bracketing and can output it (or store it somewhere). Otherwise, if we can still add “left” brackets, we do so, and in another recursive call, we check if we can put a “right” bracket by checking how many “left” and “right” brackets we currently used up. Here is the code:

def printAllBrackets(n):
  printAllBracketsR("",n,n)

def printAllBracketsR(s,left,right):
  if(left == 0 and right == 0):
    print s
    return
  if(left > 0):
    printAllBracketsR(s+"(",left-1,right)
  if(left < right):
    printAllBracketsR(s+")",left,right-1)

This produces the same valid results as the previous approach, although I find it further away from the generative approach using BNF above.

Hope this was helpful. If you are interested, the number of possible bracketings forms the very well known sequence of Catalan Numbers which is the answer to many other combinatorial problems.

Problem Statement:

Assuming you have an infinite supply of coins of various denominations, in how many ways can you make change for a certain amount of money? Formally, given a set \(S\) of \(m\) positive integers and a positive integer \(N\), how many distinct solutions are there to the equation \(\sum_{i=1}^m V_i S_i = N\) where \(V_i\) is an integer greater than 0.

Let’s look at a simple example. Assuming you have cent coins [1,2,5], and want to make change for \(5\) cents, you can do that in \(4\) ways, mainly:

[
 [1, 1, 1, 1, 1], 
 [1, 1, 1, 2], 
 [1, 2, 2], 
 [5]
]

Let’s deconstruct the problem into these facts:

• Given an element \(S_i\) from \(S\), any solution must either exclude \(S_i\), or include at least one \(S_i\).
• To make \(0\), regardless of \(S\), there is only one solution, the empty solution.
• If \(N < 0\), there are no solutions
• If \(S = \{\}\), and \(N > 0\), there are no solutions.

Since it might be useful, in the following code snippet, we not only count all the possibilities, but also output them.

memo = dict()

# Returns a list of lists of all possibilities
def coin_count(amount,poss,curpos):
  if amount == 0:
    return [[]]
  elif amount < 0 or curpos >= len(poss):
    return []
  elif (amount,curpos) in memo: # memoized
    return memo[(amount,curpos)]

  # either use poss[0]
  out = []
  for sublist in coin_count(amount-poss[curpos], poss, curpos):
    out.append( [poss[curpos]] + sublist)

  # or don't use it
  out1 = coin_count(amount,poss,curpos+1)

  # memoize
  memo[(amount,curpos)] = out + out1

  return out + out1

Notice that the above solution also has memoization.

Let’s try this out on making change on a 2 pound coin, using all the coins, ie \(S=\{200,100,50,20,10,5,2,1\}\).

coins = [200,100,50,20,10,5,2,1]
print len(coin_count(200,coins,0))

We get the correct answer of \(73682\).

Notice that we can use this to solve the solve the unordered integer partition problem.

Let’s try it out to find all the possible integer partitions of \(5\).

[
  [1, 1, 1, 1, 1], 
  [1, 1, 1, 2], 
  [1, 1, 3],
  [1, 2, 2], 
  [1, 4], 
  [2, 3], 
  [5]
]

Code available as a gist

Problem Statement:

Given an array \(A\) of unsorted integers and an integer \(C\), find a contiguous subsequences of \(A\) that sums to \(C\)

Firstly, remember that a contiguous subsequence is a subarray of another array - the elements have to appear in order. For example, the answer to the question for A = [1,2,-3,1], C = 0 would be either [1,2,-3] or [2,-3,1].

The naive solution is to take all possible subsequences. Take the first element, and get all subsequences starting with it - there are \(n\) of them. Repeat for second element. The total number of steps is \(n + (n-1) + (n-2) \dots 1 = \frac{n(n+1)}{2}\).

Define a partial sum \(S_n = \sum_{i=0}^n A[i]\). It then follows that if \(S_i - S_j = C, i > j\), the subsequence \(A[j+1], A[j+2] \ldots A[i]\) sums up to C.

In code, this means we need to traverse the array, and keep a hashmap of partial sums to the index at which they appear at. If at any point we see that the \(curSum - C\) was found beforehand, we have found our subsequence.

In python code:

# 'A' is an unsorted array of integers
# Find any contigous subsequence of A that sums to C.
def cont_subsequence_sum(A, C):
  m = dict() # Maps number to index
  curSum = 0
  m[0] = -1
  for i in range(len(A)):
    curSum += A[i]
    if( (curSum - C) in m ):
      answer = [A[j] for j in range(m[curSum-C]+1,i+1)]
      return answer
    m[curSum] = i
  return []

Also available as a gist

Have a look in the archives for more posts.