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.


Table of Contents

  • First Challenge
  • Second Challenge
  • Third Challenge
  • Conclusion
  • References
Coding
Photo by Christopher Gower / Unsplash

First Challenge

Problem description

Given a list of numbers and a number  s, return whether any two numbers from the list add up to k.

For example, given [20, 5, 13, 7] and k of 12, return true since 5 + 7 is 12.

Solution

This problem can be solved in several different ways. Assuming:

l = [20, 5, 13, 7]
k = 12

Brute force way would involve a nested iteration to check for every pair of numbers:

def two_sum(l, k):
    for i in range(len(l)):
        for j in range(len(l)):
            if i != j and l[i] + l[j] == k:
                return True
    return False

OR

def two_sum(l, k):
    for i in range(len(l)):
        for j in range(i+1,len(l)):
            print(i,j)
            if l[i] + l[j] == k:
                return True
    return False

Both of them results in O(N2). If you are interested to know why please read this excellent stackoverflow question: https://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop

Another way is to use a set to remember the numbers we've seen so far. Then for a given number, we can check if there is another number that, if added, would sum to k. This would be O(N) since lookups of sets are O(1) each.

def two_sum(l, k):
    seen = set()
    for num in l:
        if k - num in seen:
            return True
        seen.add(num)
    return False

Yet another solution involves sorting the list. We can then iterate through the list and run a binary search on K - l[i]. Since we run binary search on N elements, this would give O(N log N). Note that the binary search algorithm has O(logN) .

## Binary search algorithm

def binary_search(l, target, L, R):
    if R>=L:
        mid = (L + R) // 2
        print(mid)
        if l[mid] == target:
            return mid
        elif l[mid] > target:
            return binary_search(l,target,L,mid-1)
        else:
            return binary_search(l,target,mid+1,R)
    else:
        return -1

def two_sum(l,k):
    l.sort()
    for i in range(len(l)):
        target = k - l[i]
        ind = binary_search(l,target,0,len(l)-1)
        
        # Check that binary search found the target and that it's not 
        # in the same index as i. If it is in the same index, we can 
        # check l[i + 1] and l[i - 1] to see if there's another number
        # that's the same value as l[i].
        
        if j == -1:
            continue
        elif j != i:
            return True
        elif j + 1 < len(l) and l[j + 1] == target:
            return True
        elif j - 1 >= 0 and l[j - 1] == target:
            return True
    return False

If you are interested to refresh your memory about binary research please do watch this excellent YouTube video: https://www.youtube.com/watch?v=T2sFYY-fT5o


Second Challenge

Problem description

Given an list of integers, return a new list such that each element at index i of the new list is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6]. Note that is not allowed to use division.

Solution

Observing the fact that the ith element is simply the product of numbers before i and the product of numbers after i we could simply multiply those two numbers to get our desired product.

Assuming:

l = [1, 2, 3, 4, 5]
we expect to get as output: [120, 60, 40, 30, 24]

Similarly for l = [1,2,0,3]
we expect to get as output: [0, 0, 6, 0]

In order to find the product of numbers before i, we can generate a list of prefix products. Specifically, the ith element in the list would be a product of all numbers including i. Similarly, we would generate the list of suffix products.

def products(l):
    # Generate prefix products
    prefix_products = []
    for num in l:
        if prefix_products:
            prefix_products.append(prefix_products[-1] * num)
        else:
            prefix_products.append(num)

    # Generate suffix products
    suffix_products = []
    for num in reversed(l):
        if suffix_products:
            suffix_products.append(suffix_products[-1] * num)
        else:
            suffix_products.append(num)
    suffix_products = list(reversed(suffix_products))

    # Generate result
    result = []
    for i in range(len(l)):
        if i == 0:
            result.append(suffix_products[i + 1])
        elif i == len(l) - 1:
            result.append(prefix_products[i - 1])
        else:
            result.append(prefix_products[i - 1] * suffix_products[i + 1])
    return result

This runs in O(N) time and space, since iterating over the list takes O(N) time and creating the prefix and suffix arrays take up O(N) space.


Third Challenge

Problem description

Given the root to a binary tree, implement serialize(root), which serializes a binary tree into a string, and deserialize(s), which deserializes the string back into the tree.

For example, given the following Node class

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

The following test should pass:

node = Node('root', Node('left', Node('left.left')), Node('right'))
assert deserialize(serialize(node)).left.left.val == 'left.left'

Solution

At first let's revise what a binary tree is:

A binary tree is made of nodes, where each node contains a "left" reference, a "right" reference, and a data element. The topmost node in the tree is called the root. Every node (excluding a root) in a tree is connected by a directed edge from exactly one other node. This node is called a parent. On the other hand, each node can be connected to arbitrary number of nodes, called children. Nodes with no children are called leaves, or external nodes. Nodes which are not leaves are called internal nodes. Nodes with the same parent are called siblings.

To sum up, a binary tree is a tree where each node has 0, 1, or 2 children. The important bit is that 2 is the max – that’s why it’s binary.

First, let's create our tree using the provided Node class.

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

node = Node('root', Node('left', Node('left.left')), Node('right'))

Let's run some tests to check the structure of the tree:

assert node.val == 'root'
assert node.left.val == 'left'
assert node.left.left.val == 'left.left'
assert node.left.left.left == None
assert node.left.left.right == None
assert node.left.right == None
assert node.right.val == 'right'
assert node.right.left == None
assert node.right.right == None

All the above check are successfully passed. Lets' now approach this problem by first figuring out what we would like the serialized tree to look like. Ideally, it would contain the minimum information required to encode all the necessary information about the binary tree. One possible encoding might be to borrow S-expressions from Lisp. The tree Node(1, Node(2), Node(3)) would then look like '(1 (2 () ()) (3 () ()))', where the empty brackets denote nulls.

To minimize data over the hypothetical wire, we could go a step further and prune out some unnecessary brackets. We could also replace the 2-character '()' with '#'. We can then infer leaf nodes by their form 'val # #' and thus get the structure of the tree that way. Then our tree would look like 1 2 # # 3 # #.

def serialize(root):
    if root is None:
        return '#'
    return f'{root.val} {serialize(root.left)} {serialize(root.right)}'

serialize(node)
# output
'root left left.left # # # right # #'

Let's build a deserialize function now:

def deserialize(data):
    vals = iter(data.split())
    def helper():
        val = next(vals)
        if val == '#':
            return None
        node = Node(val)
        node.left = helper()
        node.right = helper()
        return node
    
    return helper()

Everything is working fine and we can double check by running the following command:

assert deserialize(serialize(node)).val == 'root'
assert deserialize(serialize(node)).left.val == 'left'
assert deserialize(serialize(node)).left.left.val == 'left.left'
assert deserialize(serialize(node)).left.left.left == None
assert deserialize(serialize(node)).left.left.right == None
assert deserialize(serialize(node)).left.right == None
assert deserialize(serialize(node)).right.val == 'right'
assert deserialize(serialize(node)).right.left == None
assert deserialize(serialize(node)).right.right == None

This runs in O(N) time and space, since we iterate over the whole tree when serializing and deserializing.


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