A great way to improve your coding skills is by solving coding challenges. Solving different types of challenges and puzzles can help you become a better problem solver, learn the intricacies of a programming language, prepare for job interviews, learn new algorithms, and more.

This post, listed some recent interview coding problems asked by top companies like Google, Amazon, Uber, Facebook, Twitter etc.  Note that Python is the programming language used to solve the below coding challenges.

This post is the second article of the Interview Coding Problems series. You can find the rest of the posts here:

https://gdcoder.com/interview-coding-problems/


Table of Contents

  • Count the number of unival subtrees of a binary tree
  • Find the largest sum of non-adjacent numbers of a list
  • Staircase Problem
  • Conclusion
  • References
Photo by Denys Nevozhai / Unsplash

Count the number of unival subtrees of a binary tree - [Easy]

Problem description

A unival tree (which stands for "universal value") is a tree where all nodes under it have the same value. Given the root to a binary tree, count the number of unival subtrees.

For example, the following tree has 5 unival subtrees:

   0
  / \
 1   0
    / \
   1   0
  / \
 1   1

Solution

Before we solve this, let's take some time to think about it first! To start off, we should go through some examples.

This tree has 3 unival subtrees: the two ‘a’ leaves and the one ‘A’ leaf. The ‘A’ leaf causes all its parents to not be counted as a unival tree, however:

This tree has 5 unival subtrees: the leaf at ‘c’, and every ‘b’. Before we proceed and write a function let's replicate the above tree using the below functions:

class Node:
    def __init__(self, val, left=None, right=None):
        self.value = val
        self.left = left
        self.right = right

node = Node('a', Node('c'), Node('b',Node('b'),Node('b',None,Node('b'))))

We can start off by first writing a function that checks whether a tree is unival or not. Then, perhaps we could use this to count up all the nodes in the tree.

To check whether a tree is a unival tree, we must check that every node in the tree has the same value. To start off, we could define an is_unival function that takes in a root to a tree. We would do this recursively with a helper function. Recall that a leaf qualifies as a unival tree.

def is_unival(root):
    if root == None:
        return True
    if root.left != None: # check left value equal to root value
        if root.value != root.left.value:
            return False
    if root.right != None: # check left value equal to root value
        if root.value != root.right.value:
            return False
    if (not is_unival(root.left)) & (is_unival(root.right)): 
		# check left right subtree are unival
        return True
    return False

And then our function that counts the number of subtrees could simply use that function:

def count_unival_subtrees(root):
    if root == None:
        return 0
    left = count_unival_subtrees(root.left)
    right = count_unival_subtrees(root.right)
    return 1 + left + right if is_unival(root) else left + right

However, this runs in O(n^2) time. Let's show that with an example:

 3
  \
   3
    \
     3
      \
       3

So we will need to run count_unival_subtrees for the whole tree then for the whole tree except from the first 3 and so on. So:

T(N) = O(n)+O(n-1)+O(n-2)+...=O(n²/2)=O(n²)

For each node of the tree, we're evaluating each node in its subtree again as well. We can improve the runtime by starting at the leaves of the tree, and keeping track of the unival subtree count and value as we percolate back up.

However, this runs in O(n^2) time. Let's show that with an example:

def helper(root):
    if root == None:
        return (0,True)
    left, is_left_unival = helper(root.left) 
    right, is_right_unival = helper(root.right) 
    is_unival = True
    if (not is_left_unival) | (not is_right_unival):
        is_unival = False
    if root.left != None:
        if root.value != root.left.value:
            is_unival = False
    if root.right != None:
        if root.value != root.right.value:
            is_unival = False
    return (1+left+right,True) if is_unival else (right + left,False)

def count_unival_subtrees(root):
    count, _ = helper(root)
    return count

count_unival_subtrees(node)

This should evaluate each node only once, making it run in O(n) time.

Find the largest sum of non-adjacent numbers of a list - [Hard]

Problem description

Given a list of integers, write a function that returns the largest sum of non-adjacent numbers.Numbers can be zero or positive.

For example, [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10, since we pick 5 and 5. Can you do this in O(N) time and constant space?

Solution

This problem seems easy from the surface, but is actually quite tricky. It's tempting to try to use a greedy strategy like pick the largest number (or first), then the 2nd-largest if it's non-adjacent and so on, but these don't work -- there will always be some edge case that breaks it.

Instead, we should look at this problem recursively. Say we had a function that already returns the largest sum of non-adjacent integers on smaller inputs. How could we use it to figure out what we want?

Say we used this function on our array from a[1:] and a[2:]. Then our solution should be a[1:] OR a[0] + a[2:], whichever is largest. This is because choosing a[1:] precludes us from picking a[0]. So, we could write a straightforward recursive solution like this:

def sum_non_adjacent(l):
    if l== []:
        return 0
    return max(sum_non_adjacent(l[1:]),sum_non_adjacent(l[2:])+l[0])

However, this solution runs in O(2n) time, since with each call, we're making two further recursive calls. We could memoize the results, or use dynamic programming to store, in an array, the largest sum of non-adjacent numbers from index 0 up to that point. Like so:

def sum_non_adjacent(l):
    if l== []:
        return 0
    if len(l)<=2:
        return max(0,max(l))
    cache = [0 for i in l]
    cache[0] = max(0,l[0])
    cache[1] = max(cache[0],l[1])
    for i in range(2,len(l)):
        cache[i] = max(cache[i-1],cache[i-2]+l[i])
    return cache[-1]

This code should run in O(n) and in O(n) space. But we can improve this even further. Notice that we only ever use the last two elements of the cache when iterating through the array. This suggests that we could just get rid of most of the array and just store them as variables:

def sum_non_adjacent(l):
    if len(l)<=2:
        return max(0,max(l))
    max_exc_last = max(0,l[0])
    max_inc_last = max(max_exc_last,l[1])
    for i in l[2:]:
        tmp = max_inc_last
        max_inc_last = max(max_exc_last+i,max_inc_last)
        max_exc_last = tmp
    return max(max_exc_last,max_inc_last)

Staircase Problem - [Hard]

Problem description

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. The order of the steps does matter.

For example, if N is 4, then there are 5 unique ways:

  • 1, 1, 1, 1
  • 2, 1, 1
  • 1, 2, 1
  • 1, 1, 2
  • 2, 2

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.

Solution

It’s always a good strategy to start off with some test cases. Let’s start with small cases and see if we can find some sort of pattern.

  • N = 1, 1 way to climb: [1]
  • N = 2, 2 ways to climb: [1, 1], [2]
  • N = 3, 3 ways to climb: [1, 2], [1, 1, 1], [2, 1]
  • N = 4, 5 ways to climb: [1, 1, 2], [2, 2], [1, 2, 1], [1, 1, 1, 1], [2, 1, 1]
  • N = 5, 8 ways to climb: [1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 1], [1, 2, 1, 1], [2, 1, 1, 1], [2, 2, 1] , [1, 2, 2], [2, 1, 2]

Do you notice anything? When we look at N = 3, the number of ways to get to 3 steps is 3, and they’re based off N = 1 and N = 2. What’s the relationship?
The only ways to get to N = 3, is to first get to N = 1, and then go up by 2 steps, or get to N = 2 and go up by 1 step. So f(3) = f(2) + f(1).

Does this hold for N = 4? Yes, it does. Since we can only get to the 4th step by getting to the 3rd step and going up by one, or by getting to the 2nd step and going up by two. So f(4) = f(3) + f(2).

Similarly, for N=5. f(5) = f(4) + f(3)

So the relationship looks like this: f(n) = f(n - 1) + f(n - 2), and f(1) = 1 and f(2) = 2. That’s just the Fibonacci sequence, except shifted by one.

def num_ways(n):
    if n <= 1:
        return 1
    return num_ways(n-1) + num_ways(n-2)
num_ways(8)

Of course, this is really slow (O(2^N)) – we are doing a lot of repeated computations! We can do it a lot faster by just computing iteratively:

def num_ways(n):
    if n == 1:
        return 1
    a , b = 1, 2
    for _ in range(n-2):
        a, b = b, a + b
    return b
num_ways(8)

Now, let’s try to generalise what we’ve learned so that it works if you can take a number of steps from the set X. Similar reasoning tells us that if X = {1, 3, 5}, then our algorithm should be f(n) = f(n - 1) + f(n - 3) + f(n - 5). If n < 0, then we should return 0, since we can’t start from a negative number of steps. Similarly,  if n=1 we should return 1. For proof let's examine if this work for the following examples:

  • N = 1, 1 way to climb: [1]
  • N = 2, 1 ways to climb: [1, 1]
  • N = 3, 2 ways to climb: [1, 1, 1], [3],
  • N = 4, 3 ways to climb: [1, 1, 1], [1, 3], [3, 1],
  • N = 5, 5 ways to climb: [1, 1, 1, 1, 1], [1, 1, 3], [5], [1, 3, 1], [3, 1, 1]
  • N=6 , 8 ways to climb: [1, 1, 1, 1, 1, 1], [1, 1, 1, 3], [1, 1, 3, 1], [1, 3, 1, 1], [3, 1, 1, 1], [3, 3], [1, 5], [5, 1]
def num_ways(n, X):
    if n < 0:
        return 0
    elif n ==0:
        return 1
    elif n in X: # for the case that X has duplicate values
        return 1 + sum([num_ways(n-x,X) for x in X if x < n])
    else:
        return sum([num_ways(n-x,X) for x in X if x < n])
num_ways(8,[1,3,3,5])

This is again, very slow (O(|X|^N)) since we are repeating computations again. We can use dynamic programming and memoization to speed it up.

Each entry cache[i] will contain the number of ways we can get to step i with the set X. Then, we’ll build up the array from zero using the same recurrence as before:

def num_ways(n, X):
    cache = [0 for _ in range(n+1)]
    cache[0] = 1
    X = set(X) # eliminate duplicate values
    for i in range(1,n+1):
        cache[i] = sum([cache[i-x] for x in X if x <= i])
    return cache[-1]

num_ways(8,[1,2,5])

This now takes O(N * |X|) time and O(N) space.

Conclusion

Hope you find it interesting and please remember that a great way to improve your coding skills is by solving coding challenges.

Thanks for reading and I am looking forward to hearing your questions :)
Stay tuned and Happy Coding.


References