Algorithm Implementations - Python

Question 1

Two Pointers - Opposite Ends (Converging)

Answer 1

Python Implementation

ef two_pointers(arr1):
    left = 0
    right = len(arr1) -1

    while left < right:
        # Do some logic depending on the problem
        # Do some logic to determine the following
        # - left += 1
        # - right -= 1
        # - both left += 1 and right -=1
        pass

Question 2

Two Pointers - Multiple Arrays/Strings (Parallel)

Answer 2

Python Implementation

def two_pointers(arr1, arr2):
    i = j = 0

    while i < len(arr1) and j < len(arr2):
        # Do some logic depending on the problem
        # Do some logic to decide on the following:
        # 1. i += 1
        # 2. j += 1
        # 3. i += 1 and j += 1
        pass

    # Make sure both iterables are exhausted
    # Only one of these loops will run
    while i < len(arr1):
        # Do some logic depending on the problem
        i += 1
        pass

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

Question 3

Sliding Window – Dynamic Window

Answer 3

Python Implementation

def sliding_window(arr):
    left = 0

    for right in range(len(arr)):
        # Do some logic to add arr[right] to window

        while WINDOW_IS_INVALID:
            # Do some logic to remove arr[left] from the window
            left += 1
            pass

        # Do some logic to update the answer

Question 4

Sliding Window - Fixed Window

Answer 4

Python Implementation

def sliding_window(arr, k):
    curr = 0 # Some data to track the window

    # Build the first window
    for i in range(k):
        # Do something with curr or other variables
        pass

    ans = curr

    # Slide the window
    for i in range(k, len(arr)):
        # Add arr[i] to window
        # Remove arr[i-k] from window
        # Update ans
        pass

    return ans

Question 5

Prefix Sum

Answer 5

Python Implementation

```python
def prefix_sum(nums: list[int]):
prefix = [nums[0]]

for i in range(1, len(nums)):
    prefix.append(nums[i] + prefix[-1])

return prefix

Sum between i and j is:
# sum = prefix[j] - prefix[i] + nums[i]
~~~

Question 6

Describe an algorithm to efficiently build a string

Answer 6

arr is a list of characters

def build_string(s: str):
    arr = []

    # Convert a string into an array
    for c in s:
        arr.append(c)

    # Convert an array to a string
    return "".join(arr)

Question 7

Describe an algorithm to find the number of subarrays that fit an exact criteria

Answer 7

from collections import defaultdict

def fn(arr, k):
    counts = defaultdict(int)
    counts[0] = 1
    ans = curr = 0

    for num in arr:
        # do logic to change curr
        ans += counts[curr - k]
        counts[curr] += 1
    
    return ans

Question 8

Describe an algorithm to implement fast and slow pointers in a linked list

Answer 8

def fn(head):
    slow = head
    fast = head
    ans = 0

    while fast and fast.next:
        # do logic
        slow = slow.next
        fast = fast.next.next
    
    return ans

Question 9

Describe an algorithm to return the middle of a linked list

Answer 9

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

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

    return slow.val

Question 10

Describe an algorithm to find cycles in a linked list

Answer 10

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

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

    return False

Question 11

Describe an algorithm to reverse a linked list

Answer 11

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

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

    return prev

Question 12

Describe an algorithm to build/maintain a monotonic increasing stack

Answer 12

def fn(arr):
    stack = []
    ans = 0

    for num in arr:
        # for monotonic decreasing, just flip the > to <
        while stack and stack[-1] > num:
            # do logic
            stack.pop()
        stack.append(num)
    
    return ans

Question 13

Describe and algorithm to perform a DFS (recursive) on a binary tree

Answer 13

def dfs(root):
    if not root:
        return
    
    ans = 0

    # do logic
    dfs(root.left)
    dfs(root.right)
    return ans

Question 14

Describe an algorithm to perform a DFS (iterative) on a binary tree

Answer 14

def dfs(root):
    stack = [root]
    ans = 0

    while stack:
        node = stack.pop()
        # do logic
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

    return ans

Question 15

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

Answer 15

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

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

Question 16

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

Answer 16

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

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

Question 17

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

Answer 17

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

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

Question 18

Describe an algorithm to perform Breadth First Search (BFS) on a binary tree

Answer 18

from collections import deque

def bfs(root):
    queue = deque([root])
    while queue:
        nodes_in_current_level = len(queue)
        # Do some logic on the current level

        for _ in range(nodes_in_current_level):
            node = queue.popleft()
            # Do some logic on the current node
            print(node.val)
            if node.left:
                queue.append(node.left)

            if node.right:
                queue.append(node.right)

Question 19

Describe an algorithm to insert a value into a Binary Search Tree (BST)

Answer 19

def insertIntoBST(root, val):
    if not root:
        return TreeNode(val)

    if val < root.val:
        root.left = insertInotBST(root.left, val)
    else:
        root.right = insertInotBST(root.right, val)

    return root

Question 20

Describe an algorithm to build an adjacency list given an array of directed edges

Answer 20

from collections import defaultdict

def build_graph(edges):
    graph = defaultdict(list)
    for x, y in edges:
        graph[x].append(y)
        # uncomment if undirected
        #graph[y].append(x)

    return graph

Question 21

Describe an algorithm to build a graph given an adjacency matrix

Answer 21

from collections import defaultdict

def build_graph_from_adjacency_matrix(adj_matrix):
    graph = defaultdict(list)
    n = len(adj_matrix)
    m = len(adj_matrix[0])
    for i in range(n):
        for j in range(m):
            if adj_matrix[i][j] == 1:
                graph[i].append(j)

    return graph

Question 22

Describe an algorithm to perform a Depth First Search (DFS) on a graph

Answer 22

# build graph

seen = set()

def dfs(node):
    for neighbor in graph[node]:
        if neighbor not in seen:
            print(neighbor)
            seen.add(neighbor)
            dfs(neighbor)

for i in range(len(graph)):
    if i not in seen:
        print(i)
        seen.add(i)
        dfs(i)

Question 23

Describe and algorithm to perform a Depth First Search (DFS) to find the number of islands given a a binary matrix

Answer 23

def island_count(grid):

        m = len(grid)
        n = len(grid[0])
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        seen = set()
        islands = 0

        def is_valid(row: int, col: int) -> bool:
            return 0 <= row < m and 0 <= col < n and grid[row][col] == 1:

        def dfs(row, col):
            size = 1
            for dx, dy in directions:
                next_row, next_col = row + dy, col + dx
                if is_valid(next_row, next_col) and (next_row, next_col) not in seen:
                    seen.add((next_row, next_col))
                    size += dfs(next_row, next_col)

            return size

        for row in range(m):
            for col in range(n):
                if (row, col) not in seen and is_valid(row,col):
                    islands += 1
                    seen.add((row,col))
                    dfs(row,col)

        return islands

Question 24

Describe an algorithm to perform a Breadth First Search (BFS) to find the shortest path given a a binary matrix

Answer 24

from collections import deque

def shortest_path_binary_matrix(grid):
    if grid[0][0] == 1:
        return -1

    n = len(grid)
    m = len(grid[0])
    seen = set((0,0))
    queue = deque([(0,0,1)]) # right, left, steps

    directions = [
        (1,0),
        (1,1),
        (0,1),
        (-1,1),
        (-1,0),
        (-1,-1),
        (0,-1),
        (1,-1)
    ]

    def is_valid(row, col):
        return 0 <= row < m and 0 <= col < n and grid[row][col] == 0

    while queue:
        row, col, steps = queue.popleft()
        if (row, col) == (n-1, m-1):
            return steps

        for dx, dy in directions:
            next_row, next_col = row + dy, col + dx
            if is_valid(next_row, next_col) and (next_row, next_col) not in seen:
                seen.add((next_row, next_col))
                queue.append((next_row, next_col, steps + 1))

    return -1

Question 25

Describe the **binary search** algorithm for a sorted array with no duplicates and give it's time and space complexity

Answer 25

Time: `O(log n)` Space: `O(1)` ``` def binary_search(arr, target): left = 0 right = len(arr) - 1 while left <= right: mid = (right + left) // 2 print(mid) if arr[mid] == target: # Found return if arr[mid] > target: right = mid -1 else: left = mid + 1 return left ```

Question 26

Describe the **binary search** algorithm for an array that contains duplicates and returns the left-most index. Also give it's time and space complexity

Answer 26

Time: `O(log n)` Space: `O(1)` ``` def binary_search_first_pos(arr, target): left = 0 right = len(arr) while left < right: mid = (left + right) // 2 if arr[mid] >= target: right = mid else: left = mid + 1 return left ```

Question 27

Describe the **binary search** algorithm for an array that contains duplicates and returns the right-most **insertion point**. Also give it's time and space complexity

Answer 27

Time: `O(log n)` Space: `O(1)` ``` def binary_search_last_pos(arr, target): left = 0 right = len(arr) while left < right: mid = (left + right) // 2 if arr[mid] > target: right = mid else: left = mid + 1 return left ```

Question 28

Describe the generic **backtracking** algorithm

Answer 28

``` def backtrack(curr, OTHER_ARGUMENTS...): if (BASE_CASE): # modify the answer return ans = 0 for (ITERATE_OVER_INPUT): # modify the current state ans += backtrack(curr, OTHER_ARGUMENTS...) # undo the modification of the current state return ans ```

Question 29

Describe a generic **trie** algorithm

Answer 29

``` class TrieNode: def __init__(self): # you can store data at nodes if you wish self.data = None self.children = {} def fn(words): root = TrieNode() for word in words: curr = root for c in word: if c not in curr.children: curr.children[c] = TrieNode() curr = curr.children[c] # at this point, you have a full word at curr # you can perform more logic here to give curr an attribute if you want return root ```