2022 SWE interview preparation

Resources:

coding-interview-university.
Algorithms

Patterns

Monotonic Queue

Tree preoder

while root or len(stack) != 0:
    while root:
        stack.push(root)
        root == root.left
    
    root = stack.pop()
    # extra checks
    # e.g: pre and pre.value > root.value
    pre = root
    root = root.right

Tree level order traversal

q = deque()
while q:
    size = len(q)
    level = []

    for i, node in enumerate(q):
        level += node,
        if node.left: q += node.left
        if node.right: q += node.right

    res += level

in order traversal

    def inorderTraversal(self, root):
        result = []
        stack = []
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            result.append(root.val)
            root = root.right

        return result

max depth

   def maxDepth(self, root):
        if root is None:
            return 0
        if root.left is None:
            return 1 + self.maxDepth(root.right)
        if root.right is None:
            return 1 + self.maxDepth(root.left)
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Problems & Solutions

Category	Title	Solution	Basic idea (One line)
Matrix traversal	1 Two Sum	Py	1. Hash O(n) and O(n) space. 2. Sort and search with two points O(n) and O(1) space.
Matrix traversal	54 Spiral matrix	Py	1. Similar to 59 2. matrix -> array assignment 3. easier for loop traversal with boundary updating from outer to inner matrix
Matrix traversal	59 Spiral matrix II	Py	1. Set direction with coordinates 2. Loop n*n with boundary check and matrix availability verification
Matrix traversal	2326 Spiral matrix II	Py	1. Set direction with coordinates, check boundary and result slot is unset 2. while loop check for head.next != None and assign the lastest value after last run
Interval	1419 Minimum Number of Frogs Croaking	Py	1. Since only whole sentence represents a frog, +1 when first char shows, return -1 when previous char is not appeared 2. Handle corner case: needs to remove uncompleted sentence
Interval	1419 Divide Intervals Into Minimum Number of Groups	Py	1. Method 1: minheap to push every element that needs to be counted in a loop 2. Method 2: using line sweep to have cur watermarking the rightmost element within the for loop of the sorted collection
Dp	1986 min working hours	Py
Hashset	129 Longest Consecutive Sequence	Py	use hashset to check if in set, then if not visited (x - 1 not in set), loop over to x + i to find longest and update size
Mono Queue	1425 Constrained Subsequence Sum	Py	Use decreasing queue to record summation within `k` constraint 1. calculate summation over current `i` index by adding towards first of decreasing queue 2. if current ele's index is less than `k` constraint, pop left 3. while current ele's summation is more than any previous summation, pop out (right)
Counting	1010 Pairs of Songs	Py
2 sum idea: hashset with counteraparts for a given target

yangjiao2/INTERVIEW-PREPARATION

2022 SWE interview preparation

Patterns

Problems & Solutions