Solving Interview Coding Problems

Lets examine how a simple step by step approach could lead to solving a challenging coding problem in an interview.

The Question

Imagine we got the following coding question in an interview.

There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase.

Step 1: Think of the underlying structure of the problem

The underlying structure of this problem can be thought of as a tree. Every step of the staircase is the node of the tree. And from every step, we can go either 1 step or 2 steps. Thinking of the problem as a tree, leads us to a solution idea using depth-first-search (DFS).

Step 2: Implement simple DFS using recursion

The number of ways we can climb to a step n is the sum of number of ways we can climb to (n-1) step and number ways we can climb to (n-2) step. We can use this to create the recursive method.

int countWays(int n) {
  return countWays(n-1) + countWays(n-2);
}

Step 3: Implement Recursion Base Case

Now we just need to think of the base case to stop the recursion. Say n = 2. The number of ways to get to step 2 are 2 (1, 1 and 2). Using the equation above, this becomes:

CountWays(1) + CountWays(0) = CountWays(0) + CountWays(-1) + CountWays(0)

This mean whenever we have n=0, we return 1 count, and whenever we have n=-1, we return 0.

int countWays(int n) {
  if (n<0) {
    return 0; 
  } else if (n == 0) {
    return 1;
  }

  return countWays(n-1) + countWays(n-2);
}

Step 4: Think of Runtime and Optimize

The runtime is exponential, O(2^N), since each call branches to 2 more calls. We can fix this with memoization.

int countWays(int n) {
  if (n<0) {
    return 0; 
  } else if (n == 0) {
    return 1;
  } 

  // memoization
  if (cache.containsKey(n)){
    return cache.get(n);
  }

  int ways = countWays(n-1) + countWays(n-2);

  cache.put(ways);
  return ways;
} 

Step 5: Think of edge cases

Integer will overflow soon. Using a Long or BigInteger will help.

long countWays(int n) {
  if (n<0) {
    return 0; 
  } else if (n == 0) {
    return 1;
  } 

  // memoization
  if (cache.containsKey(n)){
    return cache.get(n);
  }

  long ways = countWays(n-1) + countWays(n-2);

  cache.put(ways);
  return ways;
}

Enhancing the Question

We knew this was going to happen. The interviewer was going to extend the problem to make it more challenging.

What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time.

Step 6: Again think of the underlying problem

This becomes a backtracking problem. We try all steps from the given set, until we reach the end (n=0).

long countWays(int n, Set<int> x) {
  if (n<0) {
    return 0; 
  } else if (n == 0) {
    return 1;
  } 

  if (cache.containsKey(n)){
    return cache.get(n);
  }

  // backtracking
  long ways = 0; 
  for (int st in x) {
    ways += countWays(n - st);
  }

  cache.put(ways);
  return ways;
} 

Conclusion

Every (good) interview question has some underlying structure. These structures are handful in number. We don’t need to solve every leetcode problem to ace the interview. Just remember these handful of structures. We examined a few in this post - Trees, DFS, Recursion, Memoization, and Backtracking.