A bunch of Algo solutions (algos for search)

000-bunch-of-algo-solutions.md

Bunch of Algo Solutions

This gist contains a bunch of algo solutions

A01-bunch-of-graph-and-tree-solutions.md

Graph and Tree solutions

So stuff from DFS, BFS, iteration, recursion, tree construction, graph construction, grids, etc. You know, the standard stuff.

A02-is-symmetric.py

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

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        
        return self.checkSymmetry(root.left, root.right)
        
    def checkSymmetry(self, left, right):
        if not left and not right:
            return True
        
        if not left or not right:
            return False
        
        
        return (left.val == right.val) and self.checkSymmetry(left.left, right.right) and self.checkSymmetry(left.right, right.left)


if __name__ == "__main__":
    solution = Solution()

    # Example 1
    #      1
    #    /   \
    #   2     2
    #  / \   / \
    # 3   4 4   3
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(2)
    root.left.left = TreeNode(3)
    root.left.right = TreeNode(4)
    root.right.left = TreeNode(4)
    root.right.right = TreeNode(3)

    print(solution.isSymmetric(root)) # True

    # Example 2
    #      1
    #    /   \
    #   2     2
    #  / \   / \
    # 3   4 4   3
    #    /       \
    #   5         5
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(2)
    root.left.left = TreeNode(3)
    root.left.right = TreeNode(4)
    root.right.left = TreeNode(4)
    root.right.right = TreeNode(3)
    root.left.right.left = TreeNode(5)
    root.right.right.right = TreeNode(5)

    print(solution.isSymmetric(root)) # False


    # Example 3
    #      1
    #    /   \
    #   2     2
    #  / \   / \
    # 3   4 4   3
    #    /   \
    #   5     5
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(2)
    root.left.left = TreeNode(3)
    root.left.right = TreeNode(4)
    root.right.left = TreeNode(4)
    root.right.right = TreeNode(3)
    root.left.right.left = TreeNode(5)
    root.right.left.right = TreeNode(5)

    print(solution.isSymmetric(root)) # True

A03-obtaining-results-from-dfs-iterative.py

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

class Solution:
    def obtainTreeValues(self, root: TreeNode) -> bool:
        if not root:
            return 

        stack = [root]
        result = []

        while stack:
            top = stack.pop()

            if not top:
                continue
            
            result.append(top.val)
            
            stack.append(top.left)
            stack.append(top.right)

        return result

if __name__ == "__main__":
    # Example usage
    #      1
    #    /   \
    #   2     2
    #  / \   / \
    # 3   4 4   3
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(2)
    root.left.left = TreeNode(3)
    root.left.right = TreeNode(4)
    root.right.left = TreeNode(4)
    root.right.right = TreeNode(3)

    solution = Solution()
    result = solution.obtainTreeValues(root)
    print(result)  # Output: [1, 2, 3, 4, 2, 4, 3]

A04-obtaining-results-from-dfs-recursive.py

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

class Solution:
    def obtainTreeValues(self, root: TreeNode) -> bool:
        if not root:
            return 

        result = []

        self.dfs(root, result)
        
        return result

    def dfs(self, root: TreeNode, result):
        if not root:
            return
          
        result.append(root.val)

        self.dfs(root.left, result)
        self.dfs(root.right, result)

if __name__ == "__main__":
    # Example usage
    #      1
    #    /   \
    #   2     2
    #  / \   / \
    # 3   4 4   3
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(2)
    root.left.left = TreeNode(3)
    root.left.right = TreeNode(4)
    root.right.left = TreeNode(4)
    root.right.right = TreeNode(3)

    solution = Solution()
    result = solution.obtainTreeValues(root)
    print(result)  # Output: [1, 2, 3, 4, 2, 4, 3]

A05-binary-tree-level-order-traversal.py

'''
This solution focuses on level order traversal using the breadth-first search algorithm

It uses a for-loop to lock in on a particular level of the tree and work on all the nodes of that level
'''

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

from collections import defaultdict

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        results = []
        output = []

        queue = deque([root])
        level = 0

        while queue:
            # process nodes at the current level
            for i in range(len(queue)):
                leftmost = queue.popleft()
                
                if not leftmost:
                    continue
                
                results.append((leftmost.val, level))
                
                if leftmost.left:
                    queue.append(leftmost.left)
                if leftmost.right:
                    queue.append(leftmost.right)

            level += 1

        hashmap = defaultdict(list)

        for value,level in results:
            hashmap[level].append(value)

        for i in range(level, -1, -1):
            if hashmap[i]:
                output.append(hashmap[i])

        return output

A06-recursive-breadth-first-search.py

'''
This is a recursive approach to breadth-first search. It is not very elegant as the iterative approach and you won't find it
in many places but it works anyways.
```

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


def recursive_bfs(queue, output):
    if not queue:
        return
    
    new_queue = []
    for node in queue:
        if not node:
            continue

        output.append(node.val)

        new_queue.append(node.left)
        new_queue.append(node.right)

    recursive_bfs(new_queue, output)



if __name__ == "__main__":
    # Example 1
    #      1
    #    /   \
    #   2     2
    #  / \   / \
    # 3   4 4   3
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(2)
    root.left.left = TreeNode(3)
    root.left.right = TreeNode(4)
    root.right.left = TreeNode(4)
    root.right.right = TreeNode(3)

    queue = [root]
    output = []

    recursive_bfs(queue, output)
    print(output) # 1, 2, 2, 3, 4, 4, 3

B01-stack-problems.md

A bunch of stack problems

Stack problems involve using the stack data structure. This data structure is used when you want to store things for further processing. You add things to the stack and get to them later when you pop from the end of the stack.

new concept: monotonically decreasing stack - A stack that only allows smaller subsequent elements.

B02-daily-temperatures.py

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        '''
        higher -> lower

        stack = [(76,6),(73,7)]
        result = [1,1,4,2,1,1,0,0]

        result[popedvalue[1]] = i - popedvalue[1]

        [73,74,75,71,69,72,76,73]
                              i

        stack is decreasing (higher to lower)
        so if current value in loop is greater than top of stack
            use while loop to pop from stack
        else
            add to the stack
        '''
        result = [0]*len(temperatures)
        stack = []

        for i in range(len(temperatures)):
            while stack and temperatures[i] > stack[-1][0]:
                top = stack.pop()
                result[top[1]] = i - top[1]
            
            stack.append((temperatures[i], i))
                    
                    
        return result

C01-Linked-List-Problems.md

Linked List Problems

Linked list problems involve using a pointer to move through a linked list to work with

We deal with four problems here:

1. Reverse a linked list
2. Reorder a linked list such that the start and end nodes alternate
3. Merge two sorted linked lists
4. Remove the nth node from a linked list (use offset and a normal pointer)

Here's infographic for reversing a linked list

C01-reverse-linked-list.py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        '''
        temp = 2
        iterr = 1

        temp.next = iterr

        1 -> 2 -> 3 -> 4 -> 5

        tail = None
        temp = None
        iterr = head (1)

        # first iteration (head = 1)
        temp = 2 (iterr.next)
        iterr.next = tail
        tail = iterr
        iterr = temp


        1 -> None
        2 -> 3 -> 4 -> 5

        # second iteration 
        temp = iterr.next (3)
        iterr.next = tail
        tail = iterr
        iterr = temp


        2 -> 1 -> None
        3 -> 4 -> 5


        '''
        tail = None
        iterr = head

        while iterr:
            temp = iterr.next
            iterr.next = tail
            tail = iterr
            iterr = temp

        return tail

       

C02-reorder-linked-list.py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        - break list into two
        - reverse the second list
        - initialize pointers for the two halves
        - alternatively point the nodes of the first list to values in the second list
        - stop looping when either goes out of bound
        """

        # find half the list
        fast = head
        slow = head
        slowslow = ListNode(next=head)

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

            if fast:
                fast = fast.next

            slowslow = slowslow.next

        slowslow.next = None

        # reverse second list
        tail = None
        iterator = slow

        while iterator:
            temp = iterator.next
            iterator.next = tail
            tail = iterator
            iterator = temp

        list1ptr = head
        list2ptr = tail

        while list2ptr:
            temp1 = list1ptr.next
            list1ptr.next = list2ptr
            temp2 = list2ptr.next
            list2ptr.next = temp1

            list1ptr = temp1
            list2ptr = temp2

C03-merge-two-sorted-linked-lists.py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()

        list1ptr = list1
        list2ptr = list2
        dummyptr = dummy

        while list1ptr and list2ptr:
            if list1ptr.val >= list2ptr.val:
                dummyptr.next = list2ptr
                dummyptr = dummyptr.next
                list2ptr = list2ptr.next
            else:
                dummyptr.next = list1ptr
                dummyptr = dummyptr.next
                list1ptr = list1ptr.next

        if list1ptr:
            dummyptr.next = list1ptr
        elif list2ptr:
            dummyptr.next = list2ptr

        return dummy.next

        

C04-remove-nth-node-from-linked-list.py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # 1 -> 2 -> 3 -> 4 -> 5
        #                     O 
        #           P
        dummy = ListNode(next=head)
        ptr = dummy
        offset = head

        for _ in range(n):
            offset = offset.next

        while offset:
            ptr = ptr.next
            offset = offset.next


        ptr.next = ptr.next.next
     
        return dummy.next

D01-Grid-Graph-Problems.md

Grid Graph Problems

Grid graph problems involve a sort of matrix or grid that has to be traversed in all four directions (up, left, bottom, right). These problems are usually solved using depth-first search. The general idea is to traverse the grid and store the coordinates that satisfy a condition.

This gist contains 2 problems:

1. Pacific Atlantic Water Flow
2. Word Search

D02-pacific-atlantic-water-flow.py

def pacific_atlantic_waterflow(land):
    ROWS, COLS = len(land), len(land[0])
    atl_visited, pac_visited = set(), set()
    result = []

    def dfs(r, c, visited, prev_height):
        # invalid conditions
        if (
            r >= ROWS or 
            c >= COLS or 
            r < 0 or 
            c < 0 or 
            (r, c) in visited or 
            land[r][c] < prev_height
        ):
            return
        
        # condition is valid, add current cell to the visited set
        visited.add((r, c))
        cur_height = land[r][c]

        # use depth-first search to check the next four possible directions
        dfs(r, c - 1, visited, cur_height)
        dfs(r - 1, c, visited, cur_height)
        dfs(r, c + 1, visited, cur_height)
        dfs(r + 1, c, visited, cur_height)

    # starting point for left and right... prev_height is the value of cell at this starting point
    for r in range(ROWS):
        dfs(r, 0, pac_visited, land[r][0])
        dfs(r, COLS - 1, atl_visited, land[r][COLS - 1])

    # starting point for top and bottom
    for c in range(COLS):
        dfs(0, c, pac_visited, land[0][c])
        dfs(ROWS - 1, c, atl_visited, land[ROWS - 1][c])

    # process results
    for r in range(ROWS):
        for c in range(COLS):
            if (r, c) in atl_visited and (r, c) in pac_visited:
                result.append([r, c])

    return result

if __name__ == "__main__":
    land = [
        [1,2,2,3,5],
        [3,2,3,4,4],
        [2,4,5,3,1],
        [6,7,1,4,5],
        [5,1,1,2,4]]
    
    print(pacific_atlantic_waterflow(land)) # [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]

D03-word-search.py

def word_search(matrix, word):
    ROWS, COLS = len(matrix), len(matrix[0])

    def dfs(r, c, i):
        if len(word) == i:
            return True
        
        if r >= ROWS or c >= COLS or r < 0 or c < 0 or matrix[r][c] != word[i] or matrix[r][c] == "#":
            return False
        
        temp, matrix[r][c] = matrix[r][c], "#"
        
        found = (
            dfs(r + 1, c, i+1) or
            dfs(r, c + 1, i+1) or
            dfs(r - 1, c, i+1) or
            dfs(r, c - 1, i+1)
        )

        matrix[r][c] = temp

        return found
    
    for r in range(ROWS):
        for c in range(COLS):
            if matrix[r][c] == word[0]:
                found = dfs(r, c, 0)

                if found:
                    return True

    return False

if __name__ == "__main__":
    matrix = [
        ["A", "B", "D", "F"],
        ["E", "E", "F", "I"],
        ["E", "N", "I", "N"]
    ]
    word1 = "FEB"
    word2 = "BEN"
    word3 = "FINER"

    print(word_search(matrix, word1)) # TRUE
    print(word_search(matrix, word2)) # TRUE
    print(word_search(matrix, word3)) # FALSE

E01-Sorting-Algorithms.md

Sorting Algorithms

While sorting algorithms are not usually asked in interviews, it's helpful to know how to implement them. Here are the basic sort algorithms:

1. Merge Sort - A divide and conquer algorithm that allows you to break an array into the smallest bits and build it back up. It takes O(n log(n)) time to execute and stores the subarrays in O(n log(n)) space.

E02-merge-sort.py

class MergeSort():
    def sort(self, arr):
        # base case
        if len(arr) <= 1:
            return arr
        
        # divide
        m = len(arr)//2
        left = arr[0:m]
        right = arr[m:]

        # sort
        sorted_left = self.sort(left)
        sorted_right = self.sort(right)

        # merge
        return self.merge(sorted_left, sorted_right)

    def merge(self, left, right):
        merged = []

        l, r = 0, 0

        # move the pointers and insert the smaller element into the merged array
        while l < len(left) and r < len(right):
            if left[l] < right[r]:
                merged.append(left[l])
                l += 1
            else:
                merged.append(right[r])
                r += 1

        # insert remaining elements into the merge array
        merged.extend(left[l:])
        merged.extend(right[r:])

        return merged


if __name__ == "__main__":
    arr = [9, 3, 1, 2, 4, 8, 16, 4, 3]
    sorter = MergeSort()
    print(sorter.sort(arr)) # [1, 2, 3, 3, 4, 4, 8, 9, 16]

    # Simple example

    # [5, 2, 3] - original array
    # [5] [2, 3] - first division
    # [5] [2] [3] - right sub array from previous step is further divided
    # [5] [2, 3] - right sub array is then merged using the two pointers technique
    # [2, 3, 5] - original left and right sub arrays are then merged using the two pointers technique

F01-Prefix-Tree.md

Prefix Tree

A Prefix Tree also known as Trie is a data structure that allows one to add strings in a big tree. It's basically a nested dictionary data structure. Search takes O(n) time and does not involve hashing like you'd do with a hashset. This is how it looks when pretty printed

        {
            "a": {
                "p": {
                    "p": {}
                }
            }
        }

F02-prefix-tree-implementation.py

import json

class TrieNode():
    def __init__(self):
        self.children = {}

class PrefixTree():
    def __init__(self):
        self.root = TrieNode()

    def insert(self, string):
        ptr = self.root

        for char in string:
            # if this character is not in the tree, initialize this character as a new node
            if char not in ptr.children:
                ptr.children[char] = TrieNode()

            # then go one step into the node
            ptr = ptr.children[char]

    def search(self, string):
        ptr = self.root

        for char in string:
            if char in ptr.children:
                ptr = ptr.children[char]
            else:
                return False
            
        return True
            

    def dictrep(self, node):
        rep = dict()

        if not node.children:
            return {}

        for key in node.children:
            rep[key] = self.dictrep(node.children[key])

        return rep
    
    def pretty_print(self, indent=1):
        '''
        pretty-print rep
        {
            "a": {
                "p": {
                    "p": {}
                }
            }
        }
        '''
        out = self.dictrep(self.root)
        print(json.dumps(out, indent=indent))
    

        

if __name__ == "__main__":
    tree = PrefixTree()

    tree.insert("boy")
    tree.insert("brother")
    tree.insert("man")
    tree.insert("masculine")

    tree.pretty_print()

    print(tree.search("man")) # True
    print(tree.search("manny")) # False
    print(tree.search("da-boss")) # False

G01-heap-problems.md

Heap Problems

These problems involve using a min and max heap to get the smallest and largest values in an array.

G02-kth-largest-element-in-array.py

import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums = [-1 * num for num in nums]
        heapq.heapify(nums)

        for _ in range(k-1):
            heapq.heappop(nums)

        return -1 * nums[0]

G03-kth-largest-element-in-stream.py

import heapq

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.heap = [num for num in nums]
        self.k = k
        heapq.heapify(self.heap)

        while k < len(self.heap):
            heapq.heappop(self.heap)

    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)

        if len(self.heap) > self.k:
            heapq.heappop(self.heap)

        return self.heap[0]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

G05-find-median-from-data-stream.py

class MedianFinder:
    def __init__(self):
        self.min_heap = []
        self.max_heap = []

    def addNum(self, num: int) -> None:
        if self.min_heap and num < self.min_heap[0]:
            self.maxheappush(num)
        else:
            heapq.heappush(self.min_heap, num)

        if len(self.min_heap) - len(self.max_heap) == 2:
            top = heapq.heappop(self.min_heap)
            self.maxheappush(top)
        elif len(self.max_heap) - len(self.min_heap) == 2:
            top = self.maxheappop()
            heapq.heappush(self.min_heap, top)

    def maxheappop(self) -> int:
        return -1 * heapq.heappop(self.max_heap)
    
    def maxheappush(self, val):
        heapq.heappush(self.max_heap, -1 * val)
    
    def maxheaptop(self):
        return -1 * self.max_heap[0]


    def findMedian(self) -> float:
        if len(self.min_heap) > len(self.max_heap):
            return self.min_heap[0]
        elif len(self.min_heap) < len(self.max_heap):
            return self.maxheaptop()
        
        return (self.min_heap[0] + self.maxheaptop())/2
        
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

H01-Array-Problems.md

Array Problems

Array problems can be solved using two pointers and sliding window

H02-array-index-and-element-equality.py

def index_equals_value_search(arr):
  left = 0
  right = len(arr) - 1
  last = -1 
  
  currentIndex = 0
  
  while left < right:
    currentIndex = (left + right)//2
    
    if arr[currentIndex] - currentIndex < 0:
      left = currentIndex + 1
    elif arr[currentIndex] == currentIndex:
      right = currentIndex - 1
      last = currentIndex
    else:
      right = currentIndex - 1
      
  if arr[left] == left:
    return left
  
  return last

two-sum.sh

#!/bin/bash

array=(11 3 9 13 2 1 5 8)
target=8

for i in "${!array[@]}"; do
  for j in "${!array[@]}"; do
    if [ $i -ne $j ]; then
        if (( array[i] + array[j] == target )); then
            echo $i, $j
            exit 0
        fi
    fi
  done
done