# Preperation for the Coding interview

### Cheat sheets:
https://www.stratascratch.com/blog/a-comprehensive-statistics-cheat-sheet-for-data-science-interviews/
https://towardsdatascience.com/40-statistics-interview-problems-and-answers-for-data-scientists-6971a02b7eee

15 days cheat sheet for hacking technical interviews at big tech companies:
https://medium.com/@nhudinhtuan/15-days-cheat-sheet-for-hacking-technical-interviews-at-big-tech-companies-d780717dcec1

### Topics:
1. Arrays
2. Strings
3. Linked Lists
4. Stacks and Queues
5. Binary Trees
6. Heaps
7. Searching
8. Hash Tables
9. Sorting
10. Binary Search Trees
11. Recursion
12. Dynamic Programming
13. Greedy Algorithms
14. Graphs
15. Design Problems

## Catch up:
### Graphs:
A summary in a blog post: [link](https://towardsdatascience.com/graph-data-structure-cheat-sheet-for-coding-interviews-a38aadf8aa87)

Graphs are represented using adjacency matrix or list.

DFS: Complexity, Graph: O(V+E), Tree: O(V)

# adjacency list
graph = {
    'A' : ['B','C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
}

# recursive
visited = set() # Set to keep track of visited nodes.

def dfs(visited, graph, node):
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

# iterative
visited = []
stack = []

def dfs(visited, graph, node):
    visited.append(node)
    stack.append(node)
    while stack:
        s = stack.pop()
        print(s)
        for neighbour in graph[s]:
            if neighbour not in visited:
                visited.append(neighbour)
                stack.append(neighbour)
            

BFS:

visited = []
queue = []

def bfs(visited, graph, node):
    visited.append(node)
    queue.append(node)
    while queue:
        s = queue.pop(0)
        print(s)
        for neighbour in graph[s]:
            if neighbour not in visited:
                visited.append(neighbour)
                queue.append(neighbour)

Detect cycle in undirected graphs:
We can use something similar to DFS. We have a cycle if we reach a visited node that is not the parent of the current node.

visited = set()

for u in range(len(graph)):
    if u not in visited:
        if is_cyclic(u, -1):
            return True

def is_cyclic(node, parent):
    visited.add(node)
    for v in graph[node]:
        if v not in visited:
            if is_cyclic(v, node):
                return True
        elif v != parent:
            return True
    return False

Detect cycle in directed graphs:
We can use something similar to DFS. A cycle exists if we visit one ancestor of a node. We need two sets because the graph is directed.

visited = set()
ancestors = set()

for u in range(len(graph)):
    if u not in visited:
        if is_cyclic(u):
            return True

def is_cyclic(node):
    visited.add(node)
    ancestors.add(node)
    for v in graph[node]:
        if v not in visited:
            if is_cyclic(v):
                return True
        elif v in ancestors:
            return True
    # The following line is important
    ancestors.remove(node)
    return False

BFS from multiple sources, e.g., in the rotting oranges question [link](https://leetcode.com/problems/rotting-oranges/).
How long does it take for all the oranges to rot?

visited = []
queue = []

def orangesRotting(grid):
    for node in grid that is rotten:
        visited.append(node)
        # 0 is the depth
        queue.append((node, 0))
    while queue:
        s, d = queue.pop(0)
        print(s)
        for neighbour in four_directions(node):
            if neighbour not in visited:
                visited.append(neighbour)
                queue.append((neighbour, d + 1))
    for node in grid:
        if node is not rotten:
            return -1
    return d

Topological sort in a DAG:
Each for every eadge u->v, u comes before v.
We use DFS but print node after calling the children.

def top_sort():
    visited = set()
    stack = []
    for all non visited node:
        recur(visited, stack, node)
    print(stack[::-1])

def recur(visited, stack, node):
    if node not in visited:
        # print (node)`
        visited.add(node)
        for neighbour in graph[node]:
            recur(visited, graph, neighbour)
        stack.append(node)

Shortest path in an unweighted graph:
We use BFS but store the predecessor of each node.

visited = []
queue = []
# s: start, d: destination
def find_shortest_path(graph, s, d):
    # new
    preds = [-1] * len(graph)
    visited.append(s)
    queue.append(s)
    while queue:
        node = queue.pop(0)
        for v in graph[node]:
            if v not in visited:
                visited.append(v)
                queue.append(v)
                pred[v] = node
                # reach to the destination
                if v == d:
                    break
    # no path to d
    if pred[d] == -1:
        return []
    # retrieve the path
    path = [d]
    current = d
    while pred[current] != -1:
        current = pred[current]
        path.append(current)

    return path[::-1]

dijkstra:

import heapq
# graph is represented by adjacency list: List[List[pair]]
# s is the source vertex
def dijkstra(graph, s):
    # set is used to mark finalized vertices
    visited = set()
    # an array to keep the distance from s to this vertex.
    # initialize all distances as infinite, except s
    dist = [float('inf')] * len(graph)
    dist[s] = 0
    # priority queue containing (distance, vertex)
    min_heap = [(0, s)]

    while min_heap:
        # pop the vertex with the minimum distance
        _, u = heapq.heappop(min_heap)
        # skip if the vertex has already been visited
        if u in visited:
            continue
        visited.add(u)

        for v, weight in graph[u]:
            if v not in visited:
                # If there is shorted path from s to v through u.
                # s -> u -> v
                if dist[v] > (dist[u] + weight):
                    # Updating distance of v
                    dist[v] = dist[u] + weight
                    # insert to the queue
                    heapq.heappush(min_heap, (dist[v], v))

    return dist

---------------------------------------
### Binary Trees:
https://miro.medium.com/max/1000/1*Pb-E0-OOBcM_yKhhLbHF9A.jpeg

#### 1. Inorder traversal: left, node, right (LNR): for ascending sorted BST
Inorder traversal for the above tree: 4 2 5 1 3

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# recursive version
def inorder_traversal_recursive(root):
    result = []

    def recur(node):
        # base case
        if not node:
            return

        # traverse the left subtree
        recur(node.left)
        # visit node
        result.append(node.val)
        # traverse the right subtree
        recur(node.right)

    recur(root)
    return result

def inorder_traversal_iterating(root):
    result = []
    # using stack
    stack = []
    current = root
    while stack or current:
        if current:
            # traverse the left subtree
            stack.append(current)
            current = current.left
            continue
        # visit node
        current = stack.pop()
        result.append(current.val)
        # traverse the right subtree
        current = current.right
    return result

#### Preorder traversal: node, left, right (NLR): for cloning

def preorder_traversal_recursive(root):
    result = []

    def recur(node):
        # base case
        if not node:
            return

        # visit node
        result.append(node.val)
        # traverse the left subtree
        recur(node.left)
        # traverse the right subtree
        recur(node.right)

    recur(root)
    return result

def preorder_traversal_iterating(root):
    if not root:
        return []
    
    result = []
    # using stack
    stack = [root]
    while stack:
        current = stack.pop()
        # visit node
        result.append(current.val)
        # put right to stack first as we want to visit right after left!!
        if current.right:
            stack.append(current.right)
        if current.left:
            stack.append(current.left)
    return result

#### postorder LRN: for deleting

def postorder_traversal_recursive(root):
    result = []

    def recur(node):
        # base case
        if not node:
            return

        # traverse the left subtree
        recur(node.left)
        # traverse the right subtree
        recur(node.right)
        # visit node
        result.append(node.val)

    recur(root)
    return result

def postorder_traversal_iterating(root):
    if not root:
        return []

    result = []
    stack = [root]
    # get the result in order of node, right, left
    while stack:
        current = stack.pop()
        if current.left:
            stack.append(current.left)
        if current.right:
            stack.append(current.right)
        # visit node
        result.append(current.val)
    # reverse the result to get the target output as left, right node
    return result[::-1]  

#### Level order traversal (BFS like)

The following code is in fact applying DFS but the result in like BFS.

def levelorder_traversal_recursive(root):
    result = []

    def recur(node, level):
        # base case:
        if not node:
            return

        # start a new level array
        if len(result) == level:
            result.append([])

        # append the current node value
        result[level].append(node.val)

        # process child nodes for the next level from left to right
        recur(node.left, level + 1)
        recur(node.right, level + 1)

    recur(root, 0)
    return result

from collections import deque

def levelorder_traversal_iterating(root):
    if not root:
        return []

    result = []
    # using queue
    queue = deque([root])
    while queue:
        # start a new level array
        result.append([])
        current_level_size = len(queue)
        # visit all items in the current level
        for i in range(current_level_size):
            current = queue.popleft()
            result[-1].append(current.val)
            if current.left:
                queue.append(current.left)
            if current.right:
                queue.append(current.right)

    return result

---

### BST
make: O(nlog(n))
search: O(log(n))

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Find the first position of element:

def find_first_pos(arr, target):
    left = 0
    right = len(arr) - 1

    first_position = -1     # keep track of the latest valid mid position
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            first_position = mid
            right = mid - 1     # continue searching to the left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return first_position

Find the left border element:

def find_left_border(arr, target):
    left = 0
    right = len(arr) - 1

    left_border = -1        # keep track of the latest smaller number
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left_border = mid
            left = mid + 1
        else:   # in case arr[mid] >= target
            right = mid - 1

    return left_border

-------------------
## Trie:
https://medium.com/quick-code/trie-data-structure-cheat-sheet-for-coding-interviews-a828fd374b84
Good for prefix! But bad memory. To check existense, hash is better.
three basic functions: add word, search word, search for a prefix

class TrieNode(object):

    def __init__(self):
        self.children = {}
        self.is_word = False    # mark the end of a word


class Trie(object):

    def __init__(self):
        # initialize the root node
        self.root = TrieNode()

    def add(self, word):
        # add a new word to the trie
        current = self.root
        for c in word:
            if c not in current.children:
                # create new node if the character is not in children
                current.children[c] = TrieNode()
            current = current.children[c]
        # mark the end of word
        current.is_word = True

    def search(self, word):
        # return True if the word is in the trie
        current = self.root
        for c in word:
            if c not in current.children:
                return False
            current = current.children[c]
        return current.is_word

    def search_prefix(self, prefix):
        # return True if the prefix is in the trie
        current = self.root
        for c in prefix:
            if c not in current.children:
                return False
            current = current.children[c]
        # we don't need a completed word for prefix
        return True