Introduction

Practice Interviews!

A collection of 75 of the best leetcode questions to do.

If you have an interview soon, do the Most Important Problems.

If you want general practice, we have General Conceptual Problems you can practice!

Download these problems as an Anki text file! This allows you do to spaced repetition and find the best timing to learn and practice problems, especially those you forget.

Ever forget Python syntax, or a common data structure in Python? We have a Python Interview Cheat Sheet.

Python Data Structures Cheat Sheet

Lists

lst = []
lst = [3, 2, 7, 5]
lst = [i for i in range(10)] # comprehensions
lst = [0 for _ in range(10)]

lst = []
lst[5] # IndexError out of range

lst = [3, 2, 7, 5]
val = lst[3]
print(val) # 5

lst[3] = 2
print(lst[3]) # 2


lst = [None, True, 2, "Hello"]
lst.append(4)
lst.extend([3, True])
lst.insert(2, "yeet")

lst.remove(True) # finds first and remove
list.pop() # last elm
list.pop(2) # second elm

list.sort() # key=None, reverse=False, ALSO in place
list.reverse() # in place

# iterate list backwards
for i in range(len(list) - 1, -1, -1):
    print(i)

2D Arrays

# can be different size rows, most times same for a rectangle matrix

arr = [[0, 1, 2],
    [3, 4, 5],
    [6, 7, 8]]

arr = [[j for j in range(3 * i, 3 * i + 3)] for i in range(3)]

# first for which row, second for where in row
print(arr[0][0]) # 0
print(arr[0][2]) # 2
print(arr[2][0]) # 6
print(arr[2][2]) # 8

for y in range(len(arr)):
    for x in range(len(arr[y])):
        print(arr[y][x])

Stacks

# using deque
from collections import deque

stack = deque()
stack.append(5)
stack.pop() 
print(stack[-1]) # peek

# using list
stack = []
stack.append(5) # push
stack.pop() # pop
print(stack[-1]) # peek

# both
while len(stack) != 0:
  val = stack.pop()

# Stack is visualized as a vertical structure and hence has depth - DFS.

Queues

# using deque
from collections import deque

queue = deque()
queue.append(5) # push right
queue.popleft() # pop left
print(queue[-1]) # peek

# using list (not recommended)
queue = []
queue.append(5) # push right
queue.pop(0) # pop left
print(stack[-1]) # peek

# both
while len(queue) != 0:
  val = queue.pop()

# Queue can be generally thought as horizontal in structure i.e, breadth/width can be attributed to it - BFS.

Priority Queue

import heapq

q = []

heapq.heappush(q, (2, 'code')) # priority based on first value
heapq.heappush(q, (1, 'eat'))
heapq.heappush(q, (3, 'sleep'))

while q:
    next_item = heapq.heappop(q)
    print(next_item)

# Result:
#   (1, 'eat')
#   (2, 'code')
#   (3, 'sleep')

is_empty = len(q) == 0

# uses heaps, which are implemented as Python List

Dicts/HashMap

m = {}
# or
m = dict()

m = {
  2 : "Hello",
  "ee" : "TSM"
}

m[3] = True
m["Hello"] = 1
m[False] = None

a = m[3]
b = m[4] # KeyError

in_key_set = 3 in m # True in KeySet


len(m) # num elm

is_empty = len(m) == 0

m[9] += 1 # KeyError

if 9 in m:
  m[9] += 1
else:
  m[9] = 1


for k in m:
  v = m[k]
  print("k: %s, v: %s" % (k, v))
  
for k, v in m.items():
  print("k: %s, v: %s" % (k, v))
  
m.keys() # dict_keys([2, 'ee', ...])
m.values() # dict_values(['Hello', 'TSM', ..])

Sets

s = set()
s.add(5)

in_set = 3 in s
s.pop(5)

len(s) # num elm

is_empty = len(s) == 0

# intersect AND, union OR, ^ XOR

Tuples

t = ()
t = (1, 5)
t = (3, "eh", True)
a, b, c = (3, "eh", True)

def a():
    return (5, 2)

x, y = a()

tuple_contains = 5 in t

is_empty = len(t) == 0

Linked List

Simple

class LinkNode:
    
    def __init__(self, data):
        self.data = data
        self.next = None

a = LinkNode(5) # [5, null]
b = LinkNode(6) 
c = LinkNode(7) 
a.next = b # [5, -]-> [6, null]
b.next = c # [5, -]-> [6, -]-> [7, null]

cur = a # pointer
while cur != None:
  print(cur.data)
  cur = cur.next

# alt build backwards
a2 = LinkNode(7) # [7, null]
temp = LinkNode(6)
temp.next = a2 
a2 = temp # [6, -]-> [7, null]
temp = LinkNode(5)
temp.next = a2
a2 = temp # [5, -]-> [6, -]-> [7, null]

# alt build with pointer from front
a3 = LinkNode(5)
a3.next = LinkNode(6)
a3.next.next = LinkNode(7)

# alt build step by step
a4 = LinkNode(5)
cur = a4
cur.next = LinkNode(6)
cur = cur.next
cur.next = LinkNode(7)

Head Pointer Deque (Stack and/or Queue)

class LinkedDeque:
    def __init__(self):
        self.head = None
        
    def add_front(self, data):
        temp = LinkNode(data)
        temp.next = self.head
        self.head = temp
    
    def add_back(self, data):
        if self.head == None:
            self.head = LinkNode(data)
        else:
            ptr = self.head
            while ptr.next != None:
                ptr = ptr.next
            ptr.next = LinkNode(data)
    
    def remove_front(self):
        if self.head == None:
            raise Exception("nothing to remove")
        else:
            self.head = self.head.next
        
    
    def remove_back(self):
        if self.head == None:
            raise Exception("nothing to remove")
        else:
            if self.head.next == None:
                self.head = None
            else:
                ptr = self.head
                while ptr.next.next != None:
                    ptr = ptr.next
                ptr.next = None

Using Dummy Head

class LinkedDeque:
    def __init__(self):
        self.head = link_node(None)
        
    def add_front(self, data):
        temp = link_node(data)
        temp.next = self.head.next
        self.head.next = temp
    
    def add_back(self, data):
        ptr = self.head
        while ptr.next != None:
            ptr = ptr.next
        ptr.next = link_node(data)
    
    def remove_front(self):
        if self.head.next == None:
            raise Exception("nothing to remove")
        else:
            self.head.next = self.head.next.next
        
    
    def remove_back(self):
        if self.head.next == None:
            raise Exception("nothing to remove")
        else:
            if self.head.next.next == None:
                self.head.next = None
            else:
                ptr = self.head.next
                while ptr.next.next != None:
                    ptr = ptr.next
                ptr.next = None

Double Linked List with Head and Tail: Deque

class DLinkNode():
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DLinkedDeque():
    def __init__(self):
        self.head = None
        self.tail = None
        
    def add_front(self, data):
        if self.head == None:
            self.head = DLinkNode(data)
            self.tail = self.head
        else:
            temp = DLinkNode(data)
            temp.next = self.head
            self.head.prev = temp
            self.head = temp
    
    def add_back(self, data):
        if self.head == None:
            self.head = DLinkNode(data)
            self.tail = self.head
        else:
            temp = DLinkNode(data)
            self.tail.next = temp
            temp.prev = self.tail
            self.tail = temp
    
    def remove_front(self):
        if self.head == None:
            raise Exception("nothing to remove")
        else:
            self.head.next = None
            self.head = self.head.next
        
    
    def remove_back(self):
        if self.head == None:
            raise Exception("nothing to remove")
        else:
            self.tail.prev.next = None
            self.tail = self.tail.prev

Linked List as a List

Double Linked generalizes

class LinkedList():
    # a = LinkedList()
    def __init__(self):
        self.head = None
        self.size = 0 # don't need can also choose to recalc
    
    # len(a)
    def __len__(self):
        return self.size
    
    # a[x] = c
    def __setitem__(self, data, index):
        if x > self.size:
            raise Exception("out of bounds")
            
        if self.head == None: # x must equal 0 as size is 0
            self.head = LinkNode(data) 
            self.size += 1
        else if x == 0: # size does not equal 0
            temp = LinkNode(data)
            temp.next = self.head.next
            self.head = temp
            self.size += 1
        else: # insert normally into list
            ptr = self.head
            for i in range(x - 1): # x >= 1
                ptr = ptr.next
            temp = LinkNode(data)
            temp.next = ptr.next
            ptr.next = temp
            self.size += 1
        
    # b = a[x]
    def __getitem__(self, index):
        if x >= self.size:
            raise Exception("out of bounds")
        
        ptr = self.head
        for i in range(self.size):
            if i == index:
                return ptr.data
            ptr = ptr.next
    
    # del a[x]
    def __delitem__(self, index)
        if x >= self.size:
            raise Exception("out of bounds")
        
        if self.size == 1: # x must be 0
            self.head = None
            self.size -= 1
        else:
            for i in range(self.size - 1):
                if i + 1 == index:
                    ptr.next = ptr.next.next
                    self.size -= 1
                    return
                ptr = ptr.next

Circular

a = LinkNode(5)
a.next = LinkNode(6)
a.next.next = LinkNode(7)
a.next.next.next = a # to front

# no None end

Dict to LinkedList (LRU Cache)

Description: want to map a -> b but store order b is inserted Create link(b) front on stack, most recently used map a -> link(b)

Trees

class Node: 
    def __init__(self, key): 
        self.left = None
        self.right = None
        self.val = key

DFS

# A function to do inorder tree traversal 
def printInorder(node): 
    if not node: 
        return

    # First recur on left child 
    printInorder(node.left) 
    # then print the data of node 
    print(node.val)
    # or do action at this node
    # now recur on right child 
    printInorder(node.right) 

'''
preorder:
print(node.val)
printInorder(node.left)
printInorder(node.right) 

postorder
printInorder(node.left)
printInorder(node.right) 
print(node.val)
'''

BFS

def printLevelOrder(root): 
    # Base Case 
    if root is None: 
        return
      
    # Create an empty queue for level order traversal 
    queue = [] 
  
    # Enqueue Root and initialize height 
    queue.append(root) 
  
    while queue: 
        # Print front of queue and remove it from queue 
        print(queue[0].val)
        # or do action with this node
        node = queue.pop(0) 
  
        #Enqueue left child 
        if node.left is not None: 
            queue.append(node.left) 
  
        # Enqueue right child 
        if node.right is not None: 
            queue.append(node.right) 
  
#Driver Program to test above function 
root = Node(1) 
root.left = Node(2) 
root.right = Node(3) 
root.left.left = Node(4) 
root.left.right = Node(5) 
  
print("Level Order Traversal of binary tree is -")
printLevelOrder(root) 
#This code is contributed by Nikhil Kumar Singh(nickzuck_007)

A common pattern is to use a set() visited to ignore where you have visited.

BFS guarantees finding the shortest path first while DFS might find longer paths before finding the shortest one.

Dijkstra's algorithm

import heapq

class GenericSearch:
    def __init__(self, graph):
        self.graph = graph

    def dijkstra_search(self, start, goal):
        open_set = []
        heapq.heappush(open_set, (0, start))
        came_from = {}
        cost_so_far = {start: 0}

        while open_set:
            current_cost, current = heapq.heappop(open_set)

            if current == goal:
                path = []
                while current in came_from:
                    path.append(current)
                    current = came_from[current]
                path.append(start)
                return path[::-1]

            for neighbor in self.graph[current]:
                new_cost = cost_so_far[current] + self.graph[current][neighbor]
                if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
                    cost_so_far[neighbor] = new_cost
                    came_from[neighbor] = current
                    heapq.heappush(open_set, (new_cost, neighbor))

        return None  # No path found

# Example graph
graph = {
    'A': {'B': 1, 'C': 3},
    'B': {'D': 5, 'E': 7},
    'C': {'F': 2},
    'D': {},
    'E': {'F': 1},
    'F': {}
}


# Example usage
search = GenericSearch(graph)
print("Dijkstra Search:", search.dijkstra_search('A', 'F'))

A* search algorithm

import heapq

class GenericSearch:
    def __init__(self, graph):
        self.graph = graph

    def heuristic(self, node, goal):
        return 0

    def a_star_search(self, start, goal):
        open_set = []
        heapq.heappush(open_set, (0, start))
        came_from = {}
        g_score = {node: float('inf') for node in self.graph}
        g_score[start] = 0
        f_score = {node: float('inf') for node in self.graph}
        f_score[start] = self.heuristic(start, goal)

        while open_set:
            current = heapq.heappop(open_set)[1]

            if current == goal:
                path = []
                while current in came_from:
                    path.append(current)
                    current = came_from[current]
                path.append(start)
                return path[::-1]

            for neighbor in self.graph[current]:
                tentative_g_score = g_score[current] + self.graph[current][neighbor]
                if tentative_g_score < g_score[neighbor]:
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g_score
                    f_score[neighbor] = tentative_g_score + self.heuristic(neighbor, goal)
                    if neighbor not in [node[1] for node in open_set]:
                        heapq.heappush(open_set, (f_score[neighbor], neighbor))

        return None  # No path found


# Example graph
graph = {
    'A': {'B': 1, 'C': 3},
    'B': {'D': 5, 'E': 7},
    'C': {'F': 2},
    'D': {},
    'E': {'F': 1},
    'F': {}
}

# Example usage
search = GenericSearch(graph)
print("A* Search:", search.a_star_search('A', 'F'))

Tries

# make trie
trie = {}
for w in words:
    t = trie
    for c in w:
        if c not in t:
            t[c] = {}
        t = t[c]
    t['#'] = '#'

Graphs

# Definition for a Node for a Graph.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

Most Important Problems!

Jeremy Aguilon's Ranking Interview Questions by Cram Score

Level 1: Interview Tomorrow 😫

Number of Islands

Given a 2-D Array, count the number of islands in it, where land is connected in the NSEW direction. Tags: Recursion, Search, Union-Find

Solution

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs_marking(grid, i, j);
                    count += 1
                    
        return count
    
    def dfs_marking(self, grid, i, j):
        if i < 0 or i >= len(grid):
            return
        if j < 0 or j >= len(grid[0]):
            return
        if grid[i][j] != '1':
            return
        
        grid[i][j] = '0'
        self.dfs_marking(grid, i + 1, j)
        self.dfs_marking(grid, i - 1, j)
        self.dfs_marking(grid, i, j + 1)
        self.dfs_marking(grid, i, j - 1)

Coin Change

Given a target of N cents and a collection of coins, how many ways can you form N cents? Tags: Dynamic Programming, Recursion

Solution

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf') for i in range(amount + 1)]
        dp[0] = 0
        for i in range(1, amount + 1):
            for coin in coins:
                if i - coin >= 0 and dp[i - coin] + 1 < dp[i]:
                    dp[i] = dp[i - coin] + 1


        if dp[amount] == float('inf'):
            return -1
        return dp[amount]

Minimum Window Substring

Given a string and a collection of characters, find the shortest substring that contains all the characters. Tags: Sliding Window

Solution

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        t_counter = collections.Counter(t)
        t_needed = len(t)
        left = 0
        right = 0
        min_len = float('inf')
        min_str = ''

        while right < len(s):
            c_right = s[right]
            if c_right in t_counter:
                count = t_counter[c_right]
                if count > 0:
                    t_needed -= 1
                t_counter[c_right] -= 1

            while t_needed == 0:
                c_left = s[left]
                if c_left in t_counter:
                    count = t_counter[c_left]
                    if count == 0:
                        t_needed += 1
                    t_counter[c_left] += 1

                if right - left + 1 < min_len:
                    min_len = right - left + 1
                    min_str = s[left:right + 1]
                left += 1
            right += 1

        return min_str

Buying and Selling Stock

Given a list of starting and ending days for a stock, maximize your profit Tags: Greedy

Solution

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        lowest = prices[0]
        max_gain = 0
        for i in range(1, len(prices)):
            price = prices[i]
            if price - lowest > max_gain:
                max_gain = price - lowest
            if price < lowest:
                lowest = price
        return max_gain

Range Sum Query (Deprecated)

Efficiently compute the sum of the numbers between two indexes of an array. Tags: Dynamic Programming

Solution

class NumArray:

    def __init__(self, nums: List[int]):
        for i in range(1, len(nums)):
            nums[i] += nums[i - 1]
        self.sum = nums

    def sumRange(self, i: int, j: int) -> int:
        if i == 0:
            return self.sum[j]
        else:
            return self.sum[j] - self.sum[i - 1]

Merge Intervals

Given a list of intervals with a start and end value, merge the intervals. Tags: Sorting

Solution

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        ans = []
        if len(intervals) < 2:
            return intervals
        intervals.sort(key=lambda x: x[0])
        
        cur = intervals[0]
        
        for i in range(len(intervals)):
            interval = intervals[i]
            if cur[1] >= interval[0]:
                cur[1] = max(cur[1], interval[1])
            else:
                ans.append(cur)
                cur = interval
        ans.append(cur)
        return ans

Maximum Subarray

Given an array, find the subarray with the maximum sum. Tags: Dynamic Programming

Solution

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = nums[0]
        cur_total = 0

        for n in nums:
            cur_total += n
            ans = max(ans, cur_total)
            if cur_total < 0:
                cur_total = 0

        return ans

Level 2: Week to Prepare 😬

Range Sum Query Mutable (Deprecated)

Given a mutable array of integers, find the sum of elements between i and j. Tags: Recursion, Trees

Solution

class Node:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.total = 0
        self.left = None
        self.right = None

class NumArray:

    def __init__(self, nums: List[int]):
        def create_tree(self, start, end):
            if start > end:
                return None
            elif start == end:
                node = Node(start, end)
                node.total = nums[start]
                return node
            else:
                mid = start + (end - start) // 2
                node = Node(start, end)
                node.left = create_tree(nums, start, mid)
                node.right = create_tree(nums, mid + 1, end)
                node.total = node.left.total + node.right.total
                return node
        
        self.root = create_tree(nums, 0, len(nums) - 1)
        

    def update(self, index: int, val: int) -> None:
        def update_val(node, index, val):
            if node.start == node.end:
                node.total = val
                return

            mid = node.start + (node.end - node.start) // 2
            if index <= mid:
                update_val(node.left, index, val)
            else:
                update_val(node.right, index, val)
            node.total = node.left.total + node.right.total
            
        update_val(self.root, index, val)

    def sumRange(self, left: int, right: int) -> int:
        def sum_range(node, i, j):
            if node.start == i and node.end == j:
                return node.total
            
            mid = node.start + (node.end - node.start) // 2
            if j <= mid:
                return sum_range(node.left, i, j)
            elif i > mid:
                return sum_range(node.right, i, j)
            else:
                return sum_range(node.left, i, mid) + sum_range(node.right, mid + 1, j)
        
        return sum_range(self.root, left, right)
        
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(index,val)
# param_2 = obj.sumRange(left,right)

Word Search II (Deprecated)

Given a 2-D array of characters and a list of valid words, find the number of words on the board. Tags: Recursion, Search, Trees

Solution

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        visited = [[False for c in range(len(board[0]))] for r in range(len(board))]
        ans = set()
        
        trie = {}
        for word in words:
            level = trie
            for letter in word:
                if letter not in level:
                    level[letter] = {}
                level = level[letter]
            level['#'] = '#'
            
        for r in range(len(board)):
            for c in range(len(board[0])):
                cur = ''
                self.dfs(board, visited, r, c, trie, cur, ans)
        
        return list(ans)
    
    def dfs(self, board, visited, r, c, trie, cur, ans):
        if '#' in trie:
            ans.add(cur)
        
        if r < 0 or r >= len(board):
            return
        if c < 0 or c >= len(board[0]):
            return
        if visited[r][c]:
            return
        if board[r][c] not in trie:
            return

        letter = board[r][c]
        if letter in trie:
            cur += letter
            trie = trie[letter]

            visited[r][c] = True
            self.dfs(board, visited, r + 1, c, trie, cur, ans)
            self.dfs(board, visited, r - 1, c, trie, cur, ans)
            self.dfs(board, visited, r, c + 1, trie, cur, ans)
            self.dfs(board, visited, r, c - 1, trie, cur, ans)
            visited[r][c] = False

Task Scheduler

Given an array of tasks an a cooldown period, given an efficient ordering. Tags: Greedy, Priority Queue

Solution

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        task_counter = {}
        for task in tasks:
            if task not in task_counter:
                task_counter[task] = 0
            task_counter[task] += 1
        
        # -count is the way to create max-heap in python. The heapq default is min-heap.
        max_heap = []
        for task in task_counter:
            count = task_counter[task]
            heapq.heappush(max_heap, -count)
        
        tot_count = 0
        while max_heap:
            task_counts = []
            for i in range(n + 1):
                if max_heap:
                    count = heapq.heappop(max_heap)
                    task_counts.append(count)
            
            for task_count in task_counts:
                if task_count < -1: # if task_count is equal to -1, it is being used.
                    heapq.heappush(max_heap, task_count + 1)
            
            if max_heap:
                tot_count += n + 1 # + 1 due to difference in indexing +1 for spacing
            else:
                tot_count += len(task_counts)
        return tot_count

Non-overlapping Intervals (Deprecated)

Given a collection of intervals, find the number of intervals you need to remove to make the rest of the intervals non-overlapping. Tags: Greedy, Sorting

Solution

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[0])
        
        count = 0
        prev = intervals[0]
        for i in range(1, len(intervals)):
            cur = intervals[i]
            if prev[1] > cur[0]:
                count += 1
                prev[1] = min(prev[1], cur[1])
            else:
                prev = cur
                
        return count

Preorder Serialization Verification of a Binary Tree (Deprecated)

Given a particular kind of preorder serialization of a binary tree, verify that it's valid. Tags: Recursion, Trees

Solution

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        # remember how many empty slots we have
        # non-null nodes occupy one slot but create two new slots
        # null nodes occupy one slot
        
        preorder = preorder.split(',')
        
        #initially we have one empty slot to put the root in it
        count = 1
        for node in preorder:
            
            # no empty slot to put the current node
            if count == 0:
                return False
                
            # a null node?
            if node == '#':
                # ocuppy slot
                count -= 1
            else:
                # use a slot, create 2 new slots
                count += 1
        
        #we don't allow empty slots at the end
        return count == 0

Level 3: Sixth Sense Problems 🧐

Find the Duplicate Number (Deprecated)

Find the duplicate number in an array AND use O(1) space. Tags: Search

Solution

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        hare = nums[0]
        tortoise = nums[0]
        while True:
            hare = nums[nums[hare]]
            tortoise = nums[tortoise]
            if hare == tortoise:
                break
        ptr1 = nums[0]
        ptr2 = tortoise
        while ptr1 != ptr2:
            ptr1 = nums[ptr1]
            ptr2 = nums[ptr2]
        return ptr1

Construct Binary Tree from Preorder and Inorder Traversal

Given the preorder and inorder serialization of a binary tree, construct a tree data structure. Tags: Recursion, Search, Trees

Solution

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not inorder:
            return None
        
        root = preorder.pop(0)
        idx = inorder.index(root)
        node = TreeNode(root)
        node.left = self.buildTree(preorder, inorder[:idx])
        node.right = self.buildTree(preorder, inorder[idx + 1:])
        return node

Decode Ways (Deprecated)

Given an encoding from letters to numbers, count the number of ways to decode a string of numbers. Tags: Dynamic Programming, Recursion

Solution

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = [0 for i in range(len(s) + 1)]
        dp[0] = 1
        if 1 <= int(s[0]) <= 9:
            dp[1] = 1
        
        for i in range(2, len(s) + 1):
            if 1 <= int(s[i - 1]) <= 9:
                dp[i] += dp[i - 1]
            if 10 <= int(s[i - 2:i]) <= 26:
                dp[i] += dp[i - 2]
            
        return dp[-1]

Jump Game II (Deprecated)

Given a non-negative integer array where each index represents the maxmimum you can iterate forward, minimize the number of jumps to reach the end of the array. Tags: Greedy

Solution

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        
        reachable = 0
        last_jump_idx = 0
        count = 0
        
        for i in range(len(nums)):
            # use greedy strategy
            reachable = max(reachable, i + nums[i])
                
            if i == last_jump_idx:
                last_jump_idx = reachable
                count += 1
                if last_jump_idx == len(nums) - 1:
                    # if we land on last index but don't include this case, we add an extra jump
                    return count
        return count

Find the Edit Distance Between Two Words (Deprecated)

Given two words, find the minimum number of edits to mutate one word into the other. Tags: Dynamic Programming, Recursion

Solution

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0 for x in range(len(word2) + 1)] for y in range(len(word1) + 1)]
        for y in range(len(word1) + 1):
            dp[y][0] = y 
        for x in range(len(word2) + 1):
            dp[0][x] = x
        
        for y in range(1, len(word1) + 1):
            for x in range(1, len(word2) + 1):
                if word1[y - 1] == word2[x - 1]:
                    dp[y][x] = dp[y - 1][x - 1]
                else:
                    dp[y][x] = 1 + min([
                        dp[y - 1][x],
                        dp[y][x - 1],
                        dp[y - 1][x - 1],
                    ])
        return dp[len(word1)][len(word2)]

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. Tags: String

Solution

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        chars_used = set()

        l = 0
        r = 0

        max_len = 0

        while r < len(s):
            c_r = s[r]
            if c_r not in chars_used:
                chars_used.add(c_r)
                if r - l + 1 > max_len:
                    max_len = r - l + 1
                r += 1
            else:
                c_l = s[l]
                chars_used.remove(c_l)
                l += 1
        
        return max_len

Longest Repeating Character Replacement

Find the length of the longest substring containing all repeating letters you can get after changing at most k characters. Tags: String

Solution

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left = 0
        right = 0
        max_len = 0
        max_count = 0 
        char_counter = {}
        
        while right < len(s):
            c = s[right]
            if c not in char_counter:
                char_counter[c] = 0    
            char_counter[c] += 1
            max_count = max(max_count, char_counter[c])
            
            while right - left + 1 - max_count > k:
                c = s[left]
                char_counter[c] -= 1
                left += 1
            
            max_len = max(max_len, right - left + 1)
            right += 1
        
        return max_len

Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s. Tags: String

Solution

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        t_count = {}
        for c in t:
            if c not in t_count:
                t_count[c] = 0
            t_count[c] += 1
        
        for c in s:
            if c not in t_count:
                return False
            else:
                t_count[c] -= 1
        
        for c in t_count:
            if t_count[c] != 0:
                return False
        return True

Group Anagrams

Given an array of strings, group anagrams together. Tags: String

Solution

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = {}
        for word in strs:
            key = tuple(sorted(word))
            
            if key not in groups:
                groups[key] = []
            groups[key].append(word)
        
        return groups.values()

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. Tags: String

Solution

class Solution:
    def isValid(self, s: str) -> bool:
        pair = {
            ')': '(',
            '}': '{',
            ']': '['
        }
        
        stack = []
        for c in s:
            if c in pair:
                if not stack:
                    return False
                top = stack.pop()
                if top != pair[c]:
                    return False
            else:
                stack.append(c)
        
        return len(stack) == 0

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. Tags: String

Solution

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1
        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            
            while left < right and not s[right].isalnum():
                right -= 1
            
            if s[left].lower() != s[right].lower():
                return False
            
            left += 1
            right -= 1
        return True

Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. Tags: String

Solution

Dynamic Programming Solution

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False for j in range(n)] for i in range(n)]

        ans = ''
        # every string with one char is a palindrome
        for i in range(n):
            dp[i][i] = True
            ans = s[i]
        
        # upper dp
        for start in range(n - 1, -1, -1):
            for end in range(start + 1, n):
                if s[start] == s[end]:
                    if end - start == 1 or dp[start + 1][end - 1]:
                        dp[start][end] = True
                        if end - start + 1 > len(ans):
                            ans = s[start:end + 1]
        return ans

Expand from middle solution

class Solution:
    def longestPalindrome(self, s: str) -> str:
        max_len = 0
        max_str = ''
        
        for i in range(len(s)):
            # odd
            j = i
            k = i
            while j >= 0 and k < len(s) and s[j] == s[k]:
                if k - j + 1 > max_len:
                    max_len = k - j + 1
                    max_str = s[j:k + 1]
                j -= 1
                k += 1
            # even
            j = i
            k = i + 1
            while j >= 0 and k < len(s) and s[j] == s[k]:
                if k - j + 1 > max_len:
                    max_len = k - j + 1
                    max_str = s[j:k + 1]
                j -= 1
                k += 1

        return max_str

Palindromic Substrings

Given a string, your task is to count how many palindromic substrings in this string. Tags: String

Solution

class Solution:
    def countSubstrings(self, s: str) -> int:
        count = 0
        for i in range(len(s)):
            # odd
            j = i
            k = i
            while j >= 0 and k < len(s) and s[j] == s[k]:
                count += 1
                j -= 1 
                k += 1

            # even
            j = i
            k = i + 1
            while j >= 0 and k < len(s) and s[j] == s[k]:
                count += 1
                j -= 1
                k += 1
                
        return count

Longest Palindrome

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters. Tags: String

Solution

import collections

class Solution:
    def longestPalindrome(self, s: str) -> int:
        counter = collections.Counter(s)

        longest = 0
        has_odd = False
        for c in counter:
            count = counter[c]

            if count % 2 == 0:
                longest += count
            else:
                longest += count - 1
                has_odd = True
        
        if has_odd:
            longest += 1
        return longest

String to Integer (atoi)

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer. Tags: String

Solution

class Solution:
    def myAtoi(self, s: str) -> int:
        MIN = -2 ** 31
        MAX = 2 ** 31 - 1
        i = 0
        num = 0
        sign = 1

        while i < len(s) and s[i] == ' ':
            i += 1
        
        if i < len(s) and s[i] == '+':
            i += 1
        elif i < len(s) and s[i] == '-':
            sign = -1
            i += 1
        
        while i < len(s) and str.isdigit(s[i]):
            num = 10 * num + int(s[i])
            i += 1
        
        ans = sign * num
        if ans < MIN:
            return MIN
        elif ans > MAX:
            return MAX
        else:
            return ans

Find All Anagrams in a String

Given two strings s and p, return an array of all the start indices of p's anagrams in s. Tags: String

Solution

import collections

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        p_counter = collections.Counter(p)
        window_counter = collections.Counter()

        start_idx = 0
        ans = []

        for i in range(len(s)):
            c_end = s[i]
            window_counter[c_end] += 1

            # first true case window is [0, len(p) - 1]
            if i >= len(p) - 1:
                if p_counter == window_counter:
                    ans.append(start_idx)
                c_start = s[start_idx]
                if c_start in window_counter:
                    window_counter[c_start] -= 1
                    if window_counter[c_start] == 0:
                        del window_counter[c_start]
                start_idx += 1
        return ans

Array

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target. Tags: Array

Solution

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        target_dif = {}
        for i in range(len(nums)):
            num = nums[i]
            if num in target_dif:
                return [target_dif[num], i]
            else:
                dif = target - num
                target_dif[dif] = i

Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Tags: Array

Solution

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        num_exists = set()
        for num in nums:
            if num in num_exists:
                return True
            else:
                num_exists.add(num)
        return False

Product of Array Except Self

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Tags: Array

Solution

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ans = [1 for i in range(len(nums))]

        p = 1
        for i in range(len(nums)):
            ans[i] *= p
            p *= nums[i]
        
        p = 1
        for i in range(len(nums) - 1, -1, -1):
            ans[i] *= p
            p *= nums[i]
        
        return ans

Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product. Tags: Array

Solution

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max_prod = nums[0]
        prev_max = nums[0]
        prev_min = nums[0]

        for num in nums[1:]:
            cur_max = max(num, num * prev_max, num * prev_min)
            cur_min = min(num, num * prev_max, num * prev_min)
            max_prod = max(max_prod, cur_max)
            prev_max = cur_max
            prev_min = cur_min
        return max_prod

Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element. Tags: Array

Solution

class Solution:
    def findMin(self, nums: List[int]) -> int:
        lo = 0
        hi = len(nums) - 1
        
        while lo < hi:
            mid = lo + (hi - lo) // 2
            # important to do mid, hi comparison so we converge down to min instead of highest lo num
            if nums[mid] < nums[hi]:
                hi = mid
            else:
                lo = mid + 1

        return nums[lo]

Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. You are given a target value to search. If found in the array return its index, otherwise return -1. Tags: Array

Interviewing Notes