Friedrich Ewald My Personal Website

Coding Interview

To learn

  • graphs
  • trees
  • array two pointers
  • Topological sort (BFS)
  • Python bisect module
  • Matrix algorithms
  • Sliding window algorithm

Below is a collection of (technical) tips for coding interviews. This list is based on my experience and might not be exhaustive.

Data Structures

Array

  • Initialize array with values
    • 1-D: [0] * n
    • 2-D: [[0] * cols for _ in range(rows)]
  • Arrays/lists are the same in Python, initialized via l = []
  • Find first zero-based index of element with l.index('foo')
  • Slice l[start:end] where start is inclusive and end is exclusive
  • Retrieve last item with l[-1]
  • A matrix of size M * N has M + N - 1 diagonals
  • Diagonals can be computed either via -i + j or i + j, depending on the direction and then added to a map / dict.
  • When counting elements in an array, it makes sense to advance the second pointer p2 and then check for violation of constraints. Afterwards advance the pointer p1 until the violation is resolved
  • range(start, stop, step) has start inclusive and stop exclusive
  • When iterating through an array it might make sense to move the boundaries instead of changing the pointer, see this
arr = [1,2,3,4]
item = 3

def search(arr, item):
  left = 0
  right = len(arr) - 1
  while left <= right:
    middle = (left + right) // 2
    if arr[middle] == item:
      return middle

    if arr[middle] > item:
      right = middle - 1
    else:
      left = middle + 1
  return -1

search(arr, item)
def sliding_window(arr):
  idx_start = 0
  for idx_end in range(len(arr)):
    # Condition to stop the sliding window
    if arr[idx_end] == 5:
      condition = True
    
    # Move start pointer
    while condition:
      if arr[idx_start] == 5:
        condition = False
      idx_start += 1
    # idx_start is now on the condition

Boolean

  • It’s possible to add up boolean values True + True + False == 2

Lists

  • Pop first item of a list l.pop(0), otherwise l.pop() pops the last item.
  • sortedcontainers.SortedList is a special (open-source) implementation of a sorted list

Map

  • A map in Python is a dict
  • d = collections.defaultdict(list) provides a dictionary with a factory method
    • Then use d['missing_key'].append(...) to append to a missing key

Set

  • Sets are unordered in Python
  • Initialize via s = set()
  • Get first/only item list(s)[0]
  • Intersection of two sets intersect = a & b
  • Union of two sets union = a | b
  • This also works with dict.keys()

Stack

  • A list can be used as a stack in Python by using
    • l.append(item) to add a new item to the stack
    • l.pop() to return and remove an item from the stack
    • pop will return an IndexError if no item is on the stack, it should be checked before calling

Strings

  • Get ASCII position of characters via ord('a')
  • Distance between two ASCII positions ord('a') - ord('b')
  • When comparing the distance with wrapping, use ord('a') - ord('z') == -25 % 26 == 1 == ord('b') - ord('a')
  • s.isdecimal() returns true if s is a decimal number
  • s.isalnum() returns True if s is alphanumeric [0-9a-z]

Heap

  • Also known as Priority Queue
  • In Python there’s the heapq library which implements a min-heap
    • Push to heap via heapq.heappush(heap, item)
    • Pop from heap via heapq.heappop(heap)
  • The smallest element is always at the front heap[0]
  • Time complexity to build: O(n * log n)
  • Time complexity to insert one element: O(log n)

Sorting

Tree

  • Number of nodes in a binary tree, if all nodes are there: pow(2, height) - 1
  • Height of (complete) binary tree: h = log2(n)
  • A tree can be converted into a graph to find arbitrary nodes
import collections

graph = collections.defaultdict(list)
def build_graph(cur, parent):
    if cur and parent:
        graph[cur.val].append(parent.val)
        graph[parent.val].append(cur.val)
    if cur.left:
        build_graph(cur.left, cur)
    if cur.right:
        build_graph(cur.right, cur)
build_graph(root, None)
  • Deep copy of binary tree
def cloneGraph(node: Optional['Node']) -> Optional['Node']:
  # Handle edge case
  if node is None:
    return None
  
  # Define queue with the root node
  q = [node]

  # Memorize visited nodes
  m = {node.val: Node(node.val)}

  # Clone root node
  node_clone = m[node.val]

  while len(q) > 0:
    curr = q.pop(0)
      
    # Clone the node if not already cloned
    if curr.val in m:
      curr_clone = m[curr.val]
    else:
      curr_clone = Node(curr.val)
      m[curr.val] = curr_clone
      
    for neighbor in curr.neighbors:
      if neighbor.val not in m:
        n = Node(neighbor.val)
        m[neighbor.val] = n
        q.append(neighbor)
        
      curr_clone.neighbors.append(m[neighbor.val])
  for node in m.values():
    print(node.val, node.neighbors)
  return node_clone

Pre-order, NLR

Visit the current node. Recursively traverse the current node’s left subtree. Recursively traverse the current node’s right subtree. The pre-order traversal is a topologically sorted one, because a parent node is processed before any of its child nodes is done.

Post-order, LRN

Recursively traverse the current node’s left subtree. Recursively traverse the current node’s right subtree. Visit the current node. Post-order traversal can be useful to get postfix expression of a binary expression tree.

In-order, LNR

Recursively traverse the current node’s left subtree. Visit the current node. Recursively traverse the current node’s right subtree. In a binary search tree ordered such that in each node the key is greater than all keys in its left subtree and less than all keys in its right subtree, in-order traversal retrieves the keys in ascending sorted order.[7]

Graph

  • A graph is a tree with loops
  • Time complexity
  • Space complexity
  • Deep copy of graph: TODO Algorithm

Breadth First Search (BFS)

  • Use whenever there is a question for shortest path
  • Iterative is easy to use with queue, stop when queue is empty
  • Tip for directions = [[1,0], [0,1], [-1,0], [0,-1], [1,1], [-1,-1], [1,-1], [-1,1]]
  • Improvement is A* algorithm
  • Can also be used with a queue = [(node1, distance1)] to find nodes within a distance from origin. Important to keep track of visited = set() nodes to avoid loops

Depth First Search (DFS)

  • Use to find nodes with distance n from target node
  • Use to find size of island, more efficient than BFS

Trie

Short for retrieval tree.

Bloom Filter

  • Created via multiple hash functions (look up murmurhash)
  • Stored as a bitarray.
  • Does not give false negatives, but might produce false positives
  • Is append only, data can only be added, not removed

Example Python implementation

# TODO

Math

  • 37^100 is 37 * 37^99 is 37^50 * 37^50, Thus we only have to compute the left part and need log2(100) iterations. This is useful for implementing pow(x,y)

Random

  • Use random.choice(list) to pick a random element from a list

Multithreading

  • threading.Semaphore(n) provides a semaphore with n capacity that can be used via acquire() and release()
  • threading.Barrier(n) provides a barrier where all threads have to wait() until the capacity is reached

HTTP

Codes

  • 200 - OK
  • 400 - Bad Request
  • 401 - Unauthorized
  • 403 - Forbidden
  • 404 - Not found
  • 406 - Not acceptable (Cannot produce response according to defined accepted responses, e.g. JSON)

GET

response = requests.get('https://github.com/timeline.json')
print(response.json())

POST

response = requests.post('https://github.com/timeline.json', headers={}, data={}, json={})
print(response.json())

System design

Database

  • Low write/high read choose SQL
  • Try not to be too clever in solutions, leave room for follow up questions

REST

  • Simplified either list or card/detail endpoints
  • Follow Ruby on Rails routing schema (plural, /companies, /companies/1)
  • Use HTTP verbs (GET, PUT, POST, DELETE)
  • Return the whole data that is needed in the response, unless to expensive
    • Too expensive can be if stored in another database
    • Almost never want to have the frontend request the data