Algorithms

Problem Solving Steps

1. Communication: The goal is to solve real-world problems collaboratively with the interviewer.
2. Clarify the Objective: Confirming what is asked is very important. For example, if the problem requires returning values instead of indices, then storing index information is meaningless.
   • Identify boundary cases.
   • Ask valuable questions.
   • Don’t rush to code; first confirm you are solving the correct problem.
3. Formulate the Problem: To solve algorithm questions, you need to build a formula that describes how to get the result. Then look at all known conditions (such as whether the data is sorted, or any useful data characteristics. You can even preprocess data by youself). This helps decide how the formula converges and whether to use loops or recursion.
4. Explain Your Approach: Before coding, explain your thought process to the interviewer and get confirmation.
5. Code:
   • Use a consistent coding style. Use meaningful variable names, and comments.
   • Avoid premature optimization; focus on correctness first.
   • If you are stuck, try to simplify the problem or break it down into smaller parts.
6. Test Your Code: After coding, run several test cases including edge cases. Run the code manually step by step.
7. Optimize: Improve time and space complexity if possible. Dont forget that.

General Principles

• Distinguish primary and secondary bottlenecks.
• Time is often more important than Space.
• Avoid redundant iterations, do as much as possible in a single recursion or loop.
• Storing the states at each step can help avoid redundant calculations.
• Changing original data can helps avoid unnecessary space usage.

Tricks

General

• Default values often act like an if statement in certain cases, eg: dict.get.
• Use float('inf') and float('-inf') for maximum and minimum default values.
• When accessing out-of-bound indices, use min and max functions to clamp values within a reasonable range.
• Directly use if instead of None check, e.g., if x: instead of if x is not None:. 0, '' will be treated as False.
• Python does not have block scope, only function scope. Use nonlocal to modify variables in an outer scope.
• 1 << k == 2 ** k
• Handle the circular problems with techniques like total-sum-minus-worst-segment or array doubling.
  • Use % to handle circular arrays, e.g., i % n to wrap around indices.
  • Use fast and slow pointers to find cycles in linked lists.

Strings

If the string consists purely of letters, you can convert characters to ASCII codes to build a hashmap.

• For example, a-z, A-Z, 0-9 can be mapped to 0-61.
• When frequency matters, sorting can sometimes help.
• Relationships with Trees:
  • use Wildcard Bucketing Method to find similar strings. eg: a?c can match abc, acc, adc, etc. (must be of the same length)
  • if start with ‘ab*’, try to use trie. The number of letters is limited to 26, So we can use a Trie to store all possible strings in a large search space.
  • Some string matching can be seen as a graph traversal problem. (DFS or BFS)

Two Pointers

Sliding Window

The essence of the sliding window technique is to reuse information for judgment.

• The right and left pointers move one step at a time and incrementally update the condition, rather than recalculating every time.
  • For example, first expand the window by moving the right pointer until the condition is met, then shrink the window by moving the left pointer until the condition is no longer met, which can help find the optimal solution.

Matrices

• In-place problems
  • You can extend the value range to solve them (introducing new information without overwriting old data).
  • Use temporary variables.
  • Swap coordinates: $(x, y) = (y, x)$.
• Matrix rotation is equivalent to:
  • First transpose, then flip.
  • Or first flip, then transpose.

    newMap = [[0] * n for _ in range(n)] # Wrong: newMap = [[0] * n] * n. Same row reference. Right: [0] * 2, 0 is immutable

Hashmaps(Dictionaries)

• Use defaultdict(int) for counting frequencies.
• Check length and boundary conditions upfront, not mixed in the main logic.
• Double hashmaps can be used to create unique mappings.

Linked Lists

• Use slow and fast pointers to find cycles. ( slow, fast = head, head.next )
• During List processing, we can insert new elements between existing elements, since we can’t get list by index.
• Use temporary pointer when swapping elements.
• For a divide and conquer problem, it can be broken down into two separate linked lists.
• Doubly linked lists can use two dummy nodes (a dummy head and a dummy tail) to avoid null checks

Binary Tree

• BFS -> queue
  • Usually need to count the number of nodes at each level.
• DFS -> stack or recursion (pre-order, in-order, post-order)
  • in-order/post-order should not init the stack with the root node. Put all left children into the stack first. Then handle the right child after pop a node.
  • Don’t need to define a function, just define a queue.
• Binary Search Tree: in-order traversal gives sorted order.
• Morris Traversal: use predecessor to traverse without extra space or recursion.
• If height is h, then the number of nodes is at most $2^h - 1$. A binary tree can have at most $2^{h-1}$ nodes at level h.
• Visited node check before adding a node to the stack or queue.

Graphs

• Use adjacency list for sparse graphs, adjacency matrix for dense graphs.
  • Use tuples for weights in adjacency lists.

    graph = {
    	"A": [("B", 5), ("C", 2)],
    	"B": [("D", 1)],
    	"C": [],
    	"D": []
    }

• Undirected Graph
  • Union-Find
    • Used to check if connected.
    • No directed edges.
    • Is a forest structure.
  • Kruskal: find minimum spanning tree by connecting different components (sets) with minimum edges.
• Directed Graph
  • Topological Sort
    • Used to find a linear order of nodes.
    • Must be a DAG (Directed Acyclic Graph), Which has sink node (no out-degree) and source nodes (no in-degree)
    • Can be done using DFS (three-color mark visited) or Kahn.
      • Kahn’s Algorithm: Remove start nodes with no in-degree. If the graph has a loop, cannot remove all nodes.
  • DFS and BFS both can use visited set to avoid cycles.
    • BFS is better for shortest path, while DFS is better to check connectivity (if it’s reachable).

Trie

• also called prefix tree
• use dict to implement: key is char, value is dict of next char

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

Backtracking

• Use current stack to store the current state.
• Branch all possible options by changing the parameters passed into recursion, need deep copy
  • Parentheses problem brannch by adding ‘(‘ or ‘)’.
• Minimize the number of branches by pruning branches that cannot lead to a solution.

Divide and Conquer

• Merge sort, quick sort, binary search
• In-place can be used to reduce space complexity.
• Binary Search: Using a while loop with left and right pointers is more efficient and practical than recursion for binary search
  • Use left <= right to avoid infinite loop.
  • Use mid = left + (right - left) // 2 to avoid overflow.

Dynamic Programming

Dynamic Programming is an optimization over decision trees.

The decision tree represents the full state space of a dynamic programming solution.

• Define the state: uniquely represent the current subproblem. Sometimes we need to convert behaviors into state changes.
• State Transition: Define how to transition from one state to another. eg: f(n) = f(n-1) + f(n-2). Figure out what is f(n). f(n) usually is the best solution of n.
• Top-Down Approach: Start from the final problem and break it down into smaller subproblems. (Recursiv: dp to tree to tabulation)
  • Use recursion to solve the problem.
  • Memoization: Store results of subproblems to avoid redundant calculations.(if params are immutable: functools -> @lru_cache(None))
  • Identify overlapping subproblems.
• Bottom-Up Approach: Start from the smallest subproblem and build up to the final solution. (Iterative: tabulation to tree to dp)
  • Tabulation: Use a table to store results of subproblems. Fill the table iteratively.
  • Space optimization: Use only the necessary states to save space. How many states in dp[] are needed? Last two states or n states?

Python Methods

Arrays

lst = [3, 1, 2]
# mutate the original list
lst.append(4)	# [3, 1, 2, 4]
lst.extend([5, 6])	# [3, 1, 2, 4, 5, 6]
lst.insert(2, 99)	# [3, 1, 99, 2, 4, 5, 6]
lst.remove(99)	# [3, 1, 2, 4, 5, 6]
lst.pop(i)	# same with del my_list[2]
lst.pop()	# → 6; lst → [3, 1, 2, 4, 5]
lst.index(4)	# → 3
lst.count(1)	# → 1
lst.sort()	# [1, 2, 3, 4, 5], lst.sort(reverse=True)
lst.reverse()	# [5, 4, 3, 2, 1]
lst.clear()	# []

Stack & Queue

from collections import deque

dq = deque([1, 2, 3])

dq.append(4)	# [1, 2, 3, 4]
dq.appendleft(0)	# [0, 1, 2, 3, 4]

dq.pop()	# -> 4, dq: [0, 1, 2, 3]
dq.popleft()	# -> 0, dq: [1, 2, 3]

dq[-1]	# -> 3

dq.clear()	# []

Heap (Priority Queue)

import heapq

heap = [3, 1, 4]
heapq.heapify(heap)  # heap: [1, 3, 4]

heapq.heappush(heap, 2)  # heap: [1, 2, 4, 3]
heapq.heappop(heap)  # return 1; heap: [2, 3, 4]; ERROR if heap is empty, use `if heap`:

heapq.heappushpop(heap, 0)  # return 0; heap: [2, 3, 4]
heapq.heapreplace(heap, 5)  # return 2; heap: [3, 5, 4]

heapq.nsmallest(2, heap)  # [3, 4]
heapq.nlargest(2, heap)   # [5, 4]

Sets

my_set = {1, 2, 3}
my_set = set([1, 2, 3, 3])	# -> {1, 2, 3}
add(x)
update([x, y]) # add multiple elements
remove(x) # raises KeyError if x not in set
discard(x) # safer
pop() # removes and returns an arbitrary element
clear()
4 not in my_set	# -> True
len(my_set)	# -> 3

Dictionaries

d = {'a': 1, 'b': 2}
d['a']
d.get(key, default)
d['c'] = 3
del d['a']
d.pop(key, default)
'a' in d
len(d)

from collections import defaultdict

defaultdict(list)	# []
defaultdict(int)	# 0
defaultdict(set)	# set()
defaultdict(str)	# ''
defaultdict(lambda: 1)	# 1, lambda excute when key not found

Intervals

for index in range(len(list)):	# range(stop)
for i in range(2, 6):	# range(start, stop)
for i in range(10, 0, -2):	# range(start, stop, step)

for value in (list/string/tuple):	# list string tuple -> value
for index, value in enumerate(list/string/tuple):	# list string tuple -> index, value
for key in dict:
for key, value in dict.items():
if char in a_map.values()

# comprehension:  
[key for key in dict.keys() if key < 3]	# List
{k: v * 2 for k, v in dict.items() if key < 3}	# Dict
(x if x > 0 else 0 for x in lst)	# Generator	

a = [1, 2, 3]	# zip
b = ['a', 'b', 'c']
for i, j in zip(a, b):
    print(i, j)	# -> 1 a 2 b 3 c

Reverse

list.reverse()	# in-place reverse, no return value
new_list = list[::-1]	# returns a new reversed list (slice)
new_list = list(reversed(list))	# returns a lazy iterator
for item in reversed(list):        

Higher-Order Functions

list(map(lambda x: x * 2, [1, 2, 3])) → [2, 4, 6]
list(filter(lambda x: x > 0, [-1, 0, 2])) → [2]
reduce(lambda x, y: x + y, [1, 2, 3, 4]) → 10	# from functools import reduce
list(enumerate(['a', 'b'])) → [(0, 'a'), (1, 'b')]

Math

divmod(a, b)	# Returns (a // b, a % b)
a // b	# Integer division: 7//3=2
a % b	# Modulus: 7%3=1
pow(x, y)	# Returns x ** y
math.ceil(x)	# Returns the smallest integer greater than or equal to x
bin(8) # '0b1000'
int(10.7) # 10
int('0b1000', 2) # 8

# Bit Manipulation must be used with integers
a = 5      # 0b0101
b = 3      # 0b0011

print(a & b)   # 1    -> 0b0001
print(a | b)   # 7    -> 0b0111
print(a ^ b)   # 6    -> 0b0110
print(a << 1)  # 10   -> 0b1010
print(a >> 1)  # 2    -> 0b0010
print(~a)      # -6   -> 0b...11111010 (two's complement representation)

Snippets

BFS & DFS

BFS

from collections import deque

def bfs(root):
    if not root:
        return 0

    queue = deque([(root, 1)])  # tuple: (node, current_depth)
    max_depth = 0

    while queue:
        node, depth = queue.popleft()
        max_depth = max(max_depth, depth)

        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

    return max_depth

DFS(recursion)

def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

DFS(stack), usually use recursion instead of stack

def preorder_iterative(root):
    if not root:
        return []

    stack = [root]
    result = []

    while stack:
        node = stack.pop()
        result.append(node.val)

        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

def inorder_iterative(root):
    stack = []
    result = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right

    return result

def postorder_iterative(root):
	if not root:
		return []

	stack = [root]
	result = []

	while stack:
		node = stack.pop()
		result.append(node.val)

		if node.left:
			stack.append(node.left)
		if node.right:
			stack.append(node.right)

	return result[::-1]  # Reverse the result for postorder

HOCs (Higher-Order Functions)

## map(function, iterable)
nums = [1, 2, 3]
squares = list(map(lambda x: x**2, nums))  # -> [1, 4, 9]

## filter(function, iterable)
nums = [1, 2, 3, 4]
evens = list(filter(lambda x: x % 2 == 0, nums))  # -> [2, 4]

## reduce(function, iterable) — from functools
from functools import reduce
nums = [1, 2, 3, 4]
product = reduce(lambda x, y: x * y, nums)  # -> 24

## sorted(iterable, key=function)
words = ['apple', 'banana', 'cherry']
sorted_by_len = sorted(words, key=lambda x: len(x))  # -> ['apple', 'banana', 'cherry']
nums = [5, 2, 9, 1]
sorted_desc = sorted(nums, reverse=True)  # -> [9, 5, 2, 1]

## all() / any() with map()
nums = [1, 2, 3]
all(map(lambda x: x > 0, nums))  # -> True
any(map(lambda x: x > 2, nums))  # -> True

## Closure
def make_adder(n):
    return lambda x: x + n

add5 = make_adder(5)
add5(10)  # -> 15

## Decorator pattern
def decorator(func):
    def wrapper():
        print("Before")
        func()
        print("After")
    return wrapper

@decorator
def greet():
    print("Hello")

greet()
# Output:
# Before
# Hello
# After

JS Methods

Arrays

// Create an array
let arr = [3, 1, 2];
const arr2 = Array(3); // [ <3 empty items> ]
const arr3 = Array(3).fill(0); // [0, 0, 0]
arr3.fill(value, start, end); // fills values in place
const arr4 = Array.from("abc"); // ['a', 'b', 'c']
const arr5 = [..."abc"]; // ['a', 'b', 'c']

// Adding and removing elements
arr.push(4);
arr.pop(); // remove from end
arr.unshift(0); // add to start
arr.shift(); // remove from start

arr.splice(start, deleteCount, ...items); // insert/remove/replace **in place**
arr.slice(start, end); // **returns** new shallow copy

// searching
arr.includes(3); // true
arr.indexOf(2); // returns index or -1
arr.lastIndexOf(2);
arr.find(fn); // returns value or undefined
arr.findIndex(fn); // returns index or -1

// Iterating
arr.forEach((val, i) => console.log(i, val));
for (let val of arr) {}
for (let i in arr) {}

// Transforming
arr.map(fn); // return new array
arr.filter(fn); // return filtered array
arr.reduce(fn, init); // accumulates to a value
arr.reduceRight(fn); // same, but right to left
arr.flat(depth); // flattens nested arrays
arr.flatMap(fn); // map + flat(1)

arr.reverse(); // reverse in place
arr.sort(); // sort in place (string by default)
arr.sort((a, b) => a - b); // numeric sort ascending
arr.copyWithin(target, start, end?); // copies part of array to another
arr.toReversed(); // ✅ ES2023: returns reversed copy
arr.toSorted(); // ✅ ES2023: returns sorted copy
arr.toSpliced(); // ✅ ES2023: like splice, but immutable

arr.concat([4, 5]); // combine arrays
arr.join(", "); // → "1, 2, 3"
arr.toString(); // → "1,2,3"

arr.every(fn); // true if all pass
arr.some(fn); // true if at least one passes

arr.length; // get or set array length
[...arr]; // shallow clone
arr.at(-1); // last element (ES2022+)

const [a, b, ...rest] = arr; // destructuring
const copy = [...arr]; // spread clone
const merged = [...arr1, ...arr2];

Array.from('abc'); // ['a', 'b', 'c']
Array.from([1, 2, 3], x => x * 2); // [2, 4, 6]
Array.of(1, 2, 3); // [1, 2, 3] — ensures always an array

// Map → Filter → Reduce example
[1, 2, 3, 4]
  .map(x => x * 2)
  .filter(x => x > 4)
  .reduce((sum, x) => sum + x, 0); // → 14

String

const str1 = 'hello';
const str2 = "world";
const str3 = `Hello, ${str2}`;   // template literal
const str4 = String(123);        // → "123"

// searching and testing
str.includes(substring);        // true if substring exists
str.startsWith(prefix);         // true if starts with prefix
str.endsWith(suffix);           // true if ends with suffix
str.indexOf(substr);            // first index or -1
str.lastIndexOf(substr);        // last index or -1
str.search(regex);              // index or -1
str.match(regex);               // array of matches
str.matchAll(regex);            // ES2020: iterable of matches
str.test?.(regex);              // custom: not built-in

// extracting
str.slice(start, end);          // substring by index (supports negative)
str.substring(start, end);      // like slice, but no negative index
str.substr(start, length);      // deprecated
str.at(index);                  // ES2022: supports negative index
char = str[0];                  // char access
str.charAt(index);              // same as str[index]
str.charCodeAt(index);          // UTF-16 code

str.trim();                     // remove whitespace from both ends
str.trimStart();                // ES2019: from start only
str.trimEnd();                  // ES2019: from end only
str.padStart(length, padStr);  // pad beginning
str.padEnd(length, padStr);    // pad end
str.replace(old, newVal);      // replace first match
str.replaceAll(old, newVal);   // ES2021: replace all
str.toLowerCase();
str.toUpperCase();

str.split(separator, limit);   // returns array, limited number of splits
['a', 'b'].join('-');          // → "a-b"
str.repeat(3);                 // return repeated string

btoa(str) // Binary to ASCII
atob(str) // ASCII to Binary
encodeURI(str);                // escape full URI, keep :, /, ?, #, &, = 
decodeURI(str);
encodeURIComponent(str);       // escape a URI component. encode all special characters
decodeURIComponent(str);

// Reverse a string
[...str].reverse().join('');

// Capitalize first letter
str[0].toUpperCase() + str.slice(1);

// Count characters
[...str].reduce((acc, c) => {
  acc[c] = (acc[c] || 0) + 1;
  return acc;
}, {});

Set

// Create a set
const set1 = new Set();                    // empty Set
const set2 = new Set([1, 2, 3]);           // from array
const set3 = new Set("hello");            // → {'h', 'e', 'l', 'o'}

set1.add(42);
set1.add("hello");
set1.add(42);      // duplicate — ignored

set1.has(42);        // → true
set1.delete(42);     // → true if deleted
set1.clear();        // removes all elements

set1.size;  // → number of unique elements

for (const val of set1) {
  console.log(val);
}
set1.forEach((val) => console.log(val));

const arr = Array.from(set1);
const arr2 = [...set1];

const setFromArr = new Set([1, 2, 2, 3]);  // → {1, 2, 3}

Map

const map = new Map();

const objKey = { id: 1 };
map.set(objKey, "value");
map.set("a", 100);
map.set(true, "bool");

map.get(objKey);  // "value"
map.has("a");     // true
map.delete("a");  // true
map.size;         // 2
map.clear();      // removes all entries

for (const [key, value] of map) {
  console.log(key, value);
}

map.forEach((value, key) => {
  console.log(key, value);
});

[...map.keys()]
[...map.values()]
[...map.entries()]

Objects

// Create an object
const obj1 = {};                          // literal
const obj2 = new Object();               // constructor
const obj3 = Object.create(null);        // no prototype
const obj4 = { name: "Alice", age: 25 }; // with properties

obj.name = "Bob";            // set value
obj["age"] = 30;             // set using string key
const val = obj.name;        // get
const val2 = obj["name"];    // get using bracket

delete obj.age;              // remove property
"age" in obj;                // check existence: true/false
Object.hasOwn(obj, "name");  // more precise check (ES2022+)

// Enumerate Properties
Object.keys(obj);    // → ["name", "age"]
Object.values(obj);  // → ["Bob", 30]
Object.entries(obj); // → [["name", "Bob"], ["age", 30]]

for (let key in obj) {
  if (obj.hasOwnProperty(key)) {
    console.log(key, obj[key]);
  }
}

for (const [key, value] of Object.entries(obj)) {
  console.log(key, value);
}

// Shallow copy
const copy = { ...obj };
const clone = Object.assign({}, obj);

// Merge
const merged = Object.assign({}, obj1, obj2);
const merged2 = { ...obj1, ...obj2 };

// Freeze, Seal, Prevent Extensions
Object.freeze(obj);           // ❄️ Can't add/change/delete properties
Object.seal(obj);             // 🔒 Can't add/delete, can modify existing
Object.preventExtensions(obj); // 🚫 Can't add properties

Object.isFrozen(obj);         // → true/false
Object.isSealed(obj);         // → true/false
Object.isExtensible(obj);     // → true/false

Math

Math.abs(x)         // Absolute value                         
Math.ceil(x)        // Round **up** to nearest integer        
Math.floor(x)       // Round **down**                         
Math.round(x)       // Round to nearest integer               
Math.trunc(x)       // Remove decimal part (newer)            
Math.max(a, b, ...) // Largest value                          
Math.min(a, b, ...) // Smallest value                         
Math.random()       // Float in range [0, 1)                  
Math.pow(x, y)      // x to the power of y                    
Math.sqrt(x)        // Square root                            
Math.cbrt(x)        // Cube root                              
Math.sign(x)        // Returns -1, 0, or 1                    
Math.log(x)         // Natural log (base e)                   
Math.log2(x)        // Log base 2                             
Math.log10(x)       // Log base 10                            
Math.exp(x)         // e^x       
```              

## Bitwise
```javascript
let bin = 0b1010; // 10 in decimal
let hex = 0xFF;   // 255
let oct = 0o77;   // 63
bin.toString(2); // "1010"
hex.toString(16); // "ff"
oct.toString(8); // "77"
& // AND 5 & 3 => 1
| // OR
^ // XOR
~ // NOT
<< // Left shift
>> // Right shift
>>> // Unsigned right shift