Algorithms

Question 1

Describe the tow pointers algorithm where the pointers start at the ends of the array

Answer 1

def function(arr):
  left = 0
  right = len(arr) - 1

  while left < right:
    # Do some logic depengin on the problem
    # Do some more logic to decide one of the following
    # 1. left += 1
    # 2. right -= 1
    # 3. left += 1 and right -= 1

Question 2

Describe the two pointers algorighm where there are multiple arrays

Answer 2

Note that only one of these loops will run

def function(arr1, arr2):
  i = j = 0
  while i < len(arr1) and j < len(arr2):
    # Do some logic depending on the problem
    # Do some more logic to decide one of the following
    # 1. i += 1
    # 2. j += 1
    # 3. i += 1 and j += 1

Make sure both iterables are exhausted

#Only one of these loops will run
while i < len(arr1):
  # Do logic depending on the problem
  i += 1

while j < len(arr2):
  # Do logic depending on the problem
  j += 1

Question 3

Describe the sliding window algorithm

Answer 3

def function(self, arr: List[int]) -> int:
    left = right = 0

    for right in range(len(arr)):
        
        # Do some logic to "add" elements at arr[right]
        while <windows_is_invalid>:
            # Do logic to "remove" element at arr[left]
            left += 1

Time complexity O(n). The inner loop has an amortized time complexity of O(1)

Question 4

Describe the sliding window algorithm with a fixed window

Answer 4

def fixed_window(self, arr, k) -> int:
    sum = # some data to track
    
    # Build first window
    for i in range(k):
        # logic to build first window
    
    ans = # answer variable

    # Build next windows
    for i in range(k, len(nums)):
        # add arr[i] to window
        # remove arr[i-k] from window
        # update answer
    
    return ans

Question 5

Describe the prefix sum algorithm

Answer 5

def prefix_sum(nums: List[int]) -> List[int]:
    prefix = [nums[0]]
    for i in range(1, len(nums)):
        prefix.append(nums[i] + prefix[i-1])
    
    return prefix

The sum between index i and j is
prefix[j] - prefix[i-1]
or
prefix[j] - prefix[i] + nums[i]

Question 6

Describe an algorithm to build a string

Answer 6

def build_strings(s):
    arr = []
    for c in s:
        arr.append(c)

    return "".join(arr)

Question 7

Describe an algorithm to count the number of subarrays with an “exact” constraint

Answer 7

from collections import defaultdict

def solution(nums: List[int], k: int) -> int:
    count = defaultdict(int)
    count[0] = 1
    ans = curr = 0

    for num in nums:
        curr += num
        ans += count[curr - k]
        count[curr] += 1

    return ans

Question 8

Describe an algorithm to return the value in a middle of a linked list

Answer 8

def get_middle(head):
    slow = head
    fast = head

    while slow and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow.val

Question 9

Describe an algorithm to find cycles in a linked list

Answer 9

def cycle_exists(head) -> bool:
    slow = head
    fast = head

    while slow and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True

    return False

Question 10

Describe an algorithm to reverse a linked list

Answer 10

def reverse_linked_list(head):
    curr = head
    prev = None

    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    return prev

Question 11

Describe an algorithm to build/maintain a monotonic increasing stack

Answer 11

def monotonic_inc_stack(nums: List[int]) -> List[int]:
    stack = []

    for num in nums:
        while stack and stack[-1] > num:
            stack.pop()
        stack.append(num)
    return stack

Question 12

Describe and algorithm to perform Depth First Search (DFS) on a binary tree

Answer 12

def dfs(node):
    if node == None:
        return

    dfs(node.left)
    dfs(node.right)
    return

Question 13

Describe and algorithm to perform preorder Depth First Search (DFS) on a binary tree

Answer 13

def preorder_dfs(node):
    if node == None:
        return

    print(node.value)
    preorder_dfs(node.left)
    preorder_dfs(node.right)
    return

Question 14

Describe and algorithm to perform inorder Depth First Search (DFS) on a binary tree

Answer 14

def inorder_dfs(node):
    if node == None:
        return

    inorder_dfs(node.left)
    print(node.value)
    inorder_dfs(node.right)
    return

Question 15

Describe and algorithm to perform postorder Depth First Search (DFS) on a binary tree

Answer 15

def postorder_dfs(node):
    if node == None:
        return

    postorder_dfs(node.left)
    postorder_dfs(node.right)
    print(node.value)
    return