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

## 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(N^{2}). 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 i^{th} 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 i^{th} 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*.*