My solutions to leet code questions. Includes cheat sheet of code for common patterns.

The questions & solutions are also orginized in tables by pattern category.

• leetcode
  • Table of Contents
  • Interview stages cheat sheet
  • Problem solving
  • Cheat Sheet / Common Patterns
  • Common Interview Questions
  • Must know questions before an interview
  • My favorite questions (by decending order)
  • Common Leetcode Patterns
  • Python tricks
  • Problems by pattern / category
    • Dynamic programming
    • Binary Tree Traversal, DFS, BFS
    • Backtracking
    • Sliding window
    • Two pointers
    • Binary search
    • Matrix
    • Stack
    • Hashmap / Hashset
    • Memorization
    • Prefix pattern
    • Bit manipulation
    • Heap/Priority Queue
    • Linked List
    • Subsets
  • Meta interview questions
    • Dinosour Question
  • Interview preparation tips from real Meta recruiter

Stage 1: Introductions

• Have a rehearsed 30-60 second introduction regarding your education, work experience, and interests prepared.
• Smile and speak with confidence.
• Pay attention when the interviewer talks about themselves and incorporate their work into your questions later.

Stage 2: Problem statement

• Paraphrase the problem back to the interviewer after they have read it to you.
• Ask clarifying questions about the input such as the expected input size, edge cases, and invalid inputs.
• Quickly walk through an example test case to confirm you understand the problem.

Stage 3: Brainstorming DS&A

• Always be thinking out loud.
• Break the problem down: figure out what you need to do, and think about what data structure or algorithm can accomplish it with a good time complexity.
• Be receptive to any comments or feedback from the interviewer, they are probably trying to hint you towards the correct solution.
• Once you have an idea, before coding, explain your idea to the interviewer and make sure they understand and agree that it is a reasonable approach.

Stage 4: Implementation

• Explain your decision-making as you implement. When you declare things like sets, explain what the purpose is.
• Write clean code that conforms to your programming language's conventions.
• Avoid writing duplicate code - use a helper function or for loop if you are writing similar code multiple times.
• If you are stuck, don't panic - communicate your concerns with your interviewer.
• Don't be scared to start with a brute force solution (while acknowledging that it is brute force), then improve it by optimizing the "slow" parts.
• Keep thinking out loud and talk with your interviewer. It makes it easier for them to give you hints.

Stage 5: Testing & debugging

• When walking through test cases, keep track of the variables by writing at the bottom of the file, and continuously update them. Condense trivial parts like creating a prefix sum to save time.
• If there are errors and the environment supports running code, put print statements in your algorithm and walk through a small test case, comparing the expected value of variables and the actual values.
• Be vocal and keep talking with your interviewer if you run into any problems.

Stage 6: Explanations and follow-ups

Questions you should be prepared to answer:

• Time and space complexity, average and worst case.
• Why did you choose this data structure, algorithm, or logic?
• Do you think the algorithm could be improved in terms of complexity? If they ask you this, then the answer is usually yes, especially if your algorithm is slower than o(n).

Stage 7: Outro

• Have questions regarding the company prepared.
• Be interested, smile, and ask follow-up questions to your interviewer's responses.

The best way to solve leetcode is first to consider the brute force approach. Then, think about how you can optimize it. If you can't think of anything or can't implement it, try to look at the solution. Don't try to solve it. This is the best way to learn leetcode patterns.

• Leetcode Blind 75 with notes: here
• DFS, BFS, recursive
• DFS, BFS, iterative
• Two Sum variations
• Max sub array (kadane's algo)
• Reverse a linked list

1. Find substring with find() function.

2. Find substring, starting from the right with rfind() function.

3. Reverse array: arr.reverse()

4. Reverse string or array: str_or_arr[::-1] which is slice from beginning to end with negative step (so it reverses).

5. Deep copy array: deep_copy = my_arr[:], that means id(deep_copy) != id(my_arr) which is different memory address (truly copy). You can change one and not affect the other.

6. The lookup runtime of set() is O(1), so you can ask: if num in my_set and it takes O(1). Under the hood it uses a hash table.

7. Max-heap insertion time complexity (average): O(1), worst case: O(log n), pop root (maximum element in the heap) time complexity: O(log n). Code:

   import heapq
   heap = [] # Empty list to represent the heap
   heapq.heappush(heap, 5) # Adding elements to the heap
   max_element = heap[0] # Peek max element without removing
   max_element = heapq.heappop(heap) # Remove and return the maximum element

8. Insert text into string between two indexes: str[:start_index] + text + str[end_index:]

9. For matrix problems, instead of keeping track of visited cells, we can modify the matrix itself (if we can) and mark visited cells with a special character. Only works if the cells values are specific range/values.

Dynamic programming: top-down memoization:

def fn(arr):
    def dp(STATE):
        if BASE_CASE:
            return 0
        
        if STATE in memo:
            return memo[STATE]
        
        ans = RECURRENCE_RELATION(STATE)
        memo[STATE] = ans
        return ans

    memo = {}
    return dp(STATE_FOR_WHOLE_INPUT)

In DFS we usually recursivly go left, right and only then we write code to deal with the leafs first:

def dfs(root):
    if not root:
        return
    # ... do something here
    dfs(root.left)
    dfs(root.right)
    # ... do something here (usually leafs)

General BFS code for binary tree:

def bfs(root):
    queue = [root]
    while queue:
        curr_level = [] # Populate current level (tree height) with nodes of current height
        for _ in range(len(queue)):
            node = queue.pop(0)
            curr_level.append(node.val) # Instead of node.val you can also do 'node' depending on the question
            # Append children to the queue
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        # ... do something with curr_level

Another BFS code for binary tree (here we use deque - double ended queue library instead of regular list):

from collections import deque

def fn(root):
    queue = deque([root])
    ans = 0

    while queue:
        current_length = len(queue)
        # do logic for current level

        for _ in range(current_length):
            node = queue.popleft()
            # do logic
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return ans

General BFS code for graph:

def bfs(root) -> int:
    queue = [(root, 0, None)] # Current node, it's level, and parent
    while queue:
        curr, level, parent = queue.pop(0)
        print(f"Node: {curr}, level: {level}")
        # Where graph is hashmap of adjacency list (graph[u] = [v1, v2, ...] and graph[v1] = [u1, u2, ...])
        for child in graph[curr]:
            # Instead of visited set we keep track of parent (better memory complexity)
            if child != parent:
                queue.append((child, level+1, curr))

Iterative DFS (notice, in recursion we have stack frame, here we emulating the same thing):

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

Another iterative DFS:

def fn(graph):
    stack = [START_NODE]
    seen = {START_NODE}
    ans = 0

    while stack:
        node = stack.pop()
        # do some logic
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                stack.append(neighbor)
    
    return ans

In backtracking we think decision tree. Each step we choose to do something. We usually have a function that we call (once or more), usually recursivly. Its like iterating the tree and adding to the result, then returning the result.

• For each element, we have two choices: either pick the element or don't pick it (for example).
• At each level of the recursive tree, we make a choice for each subsequent element as we traverse down the tree.

It look something like:

res = []
def backtrack(curr_solution, constraints):
    res.append(curr_solution)
    backtrack(curr_solution[:] + [choice], constraints)
backtrack([], constraints)
return res

Another general code for backtracking:

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

Another example code:

letters = ['a', 'b', 'c', 'd', 'a', 'b']
words = [...]
def backtrack(candidate_index, counter):
    if candidate_index == n:
        # do something with the current solution
        return
    
    # Skip current candidate
    best = backtrack(candidate_index + 1, counter)

    # Take current candidate, only if valid
    if VALID:
        f = Counter(words[candidate_index])
        counter -= f # Modify the counter after we choose current candidate word
        best = max(best, backtrack(candidate_index + 1, counter))
        counter += f # Restore the counter
    
    return best

backtrack(0, Counter(letters))

Notice instead of appending to curr_solution we use deep copy, because curr_solution pointer can be accessed and modified multiple times. Its safer this way.

The trick for sliding window is to use left, right pointers that represent the current window (think about sub-arrays). It look something like this:

l, r = 0, 0
while r < len(arr):
    if <some condition>:
        r += 1
    else:
        l += 1

Sliding window

def fn(arr):
    left = ans = curr = 0

    for right in range(len(arr)):
        # do logic here to add arr[right] to curr

        while WINDOW_CONDITION_BROKEN:
            # remove arr[left] from curr
            left += 1

        # update ans
    
    return ans

Sometimes we want to increase the left pointer until we reach a rule:

while r < len(arr):
    while <some condition>:
        l += 1
    r += 1

You can use sliding window to get all substrings of given string:

def all_substrings(s):
    substrings = []
    n = len(s)
    
    for window_size in range(1, n + 1):
        for start in range(n - window_size + 1):
            end = start + window_size
            substrings.append(s[start:end])
    
    return substrings

We have the two pointers pattern.

1. Either one starts from the beginning and the other from the end.
2. Or both pointers start from the beginning but one pointer moves at faster pace (usually twice as fast) than the other pointer (we call this fast & slow pointers, usually we see this in linked list).

Two pointers: one input, opposite ends

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

    while left < right:
        # do some logic here with left and right
        if CONDITION:
            left += 1
        else:
            right -= 1
    
    return ans

Two pointers: two inputs, exhaust both

def fn(arr1, arr2):
    i = j = ans = 0

    while i < len(arr1) and j < len(arr2):
        # do some logic here
        if CONDITION:
            i += 1
        else:
            j += 1
    
    while i < len(arr1):
        # do logic
        i += 1
    
    while j < len(arr2):
        # do logic
        j += 1
    
    return ans

General code for binary search:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target: # Check if target is present at mid
            return mid
        elif arr[mid] < target: # If target is greater, ignore left half
            left = mid + 1
        else: # If target is smaller, ignore right half
            right = mid - 1
    return -1 # If target is not present in array

Usually in matrix questions, we convert the question to a graph problem. Then we can use DFS/BFS to traverse the matrix.

General code for stack in python:

stack = []
stack.append(1) # Push
stack.pop() # Pop

Build a prefix sum

def fn(arr):
    prefix = [arr[0]]
    for i in range(1, len(arr)):
        prefix.append(prefix[-1] + arr[i])
    
    return prefix

Find top k elements with heap:

import heapq

def fn(arr, k):
    heap = []
    for num in arr:
        # do some logic to push onto heap according to problem's criteria
        heapq.heappush(heap, (CRITERIA, num))
        if len(heap) > k:
            heapq.heappop(heap)
    
    return [num for num in heap]

Slow, fast pointers:

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

Reversing linked list:

def fn(head):
    curr = head
    prev = None
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node 
        
    return prev

To return all subsets of given array nums:

"""
If nums == [2,4,6]
Then the output will be: [[], [2], [2, 4], [2, 4, 6], [2, 6], [4], [4, 6], [6]]
Runtime complexity: O(n * 2^n) > O(2^n)
"""
def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(path)
        for i in range(start, len(nums)):
            backtrack(i + 1, path + [nums[i]])
    
    backtrack(0, [])
    return res

Another pattern is to use counter

Non-leetcode questions:

You will be supplied with two data files in CSV format.

The first file contains statistics about various dinosaurs. The second file contains additional data.

Given the following formula, speed = ((STRIDE_LENGTH / LEG_LENGTH) - 1) * SQRT(LEG_LENGTH * g)

Where g = 9.8 m/s^2 (gravitational constant)

Write a program to read in the data files from disk, it must then print the names of only the bipedal dinosaurs from fastest to slowest.

Do not print any other information.

$ cat dataset1.csv
NAME,LEG_LENGTH,DIET
Hadrosaurus,1.4,herbivore
Struthiomimus,0.72,omnivore
Velociraptor,1.8,carnivore
Triceratops,0.47,herbivore
Euoplocephalus,2.6,herbivore
Stegosaurus,1.50,herbivore
Tyrannosaurus Rex,6.5,carnivore

$ cat dataset2.csv 
NAME,STRIDE_LENGTH,STANCE
Euoplocephalus,1.97,quadrupedal
Stegosaurus,1.70,quadrupedal
Tyrannosaurus Rex,4.76,bipedal
Hadrosaurus,1.3,bipedal
Deinonychus,1.11,bipedal
Struthiomimus,1.24,bipedal
Velociraptorr,2.62,bipedal

Possible solution:

import csv
from math import sqrt

# Read data from dataset1.csv and dataset2.csv
def read_data(file_path):
    data = {}
    with open(file_path, newline='') as csvfile:
        reader = csv.DictReader(csvfile)
        for row in reader:
            data[row['NAME']] = row
    return data

dataset1 = read_data("dataset1.csv")
dataset2 = read_data("dataset2.csv")

# Calculate speed for bipedal dinosaurs
g = 9.8  # gravitational constant

bipedal_dinosaurs = []
for name in dataset1:
    if name in dataset2 and dataset2[name]['STANCE'] == 'bipedal':
        leg_length = float(dataset1[name]['LEG_LENGTH'])
        stride_length = float(dataset2[name]['STRIDE_LENGTH'])
        speed = ((stride_length / leg_length) - 1) * sqrt(leg_length * g)
        bipedal_dinosaurs.append((name, speed))

# Sort bipedal dinosaurs by speed
bipedal_dinosaurs.sort(key=lambda x: x[1], reverse=True)

# Print names of bipedal dinosaurs from fastest to slowest
for dinosaur in bipedal_dinosaurs:
    print(dinosaur[0])

7 steps to success in your coding interview:

1. Do not jump straight into coding, take a few mins to understand the problem and ask any clarifying questions (but not too long).

2. Describe your solution to your interviewer and get their thoughts on your solution.

3. Think about your algorithm(s) (sorting, divide-and-conquer, recursion...), including the complexity and approximate runtime. Ask the interviewer if it’s ok or if you should think about something more optimized. Then figure out your data structure ((Array, Stack/Queue, Hashset/Hashmap/Hashtable/Dictionary, Tree/Binary Tree, Heap, Graph, Bloom Filter, etc.) and implement.

4. Importantly, after you have finished writing your code, run through it verbally with your interviewer. This is really important at this point. Does it really do what you think it does? Make sure to read what is there, not what you think is there.

5. Test your code, put in an input to see what happens. We’re looking for you to find the bugs yourself and fix anything that comes up

6. Restate the complexity. Is it the same, or different to your initial thinking based on what you have actually coded up? Make sure you’re thinking about both space and time

7. Optimize. Proactively suggest ways to optimize to the interviewer and get their feedback to ensure what you’re trying to do is not overly complex and is correct, then code it up.