Flashcards in InterviewCake Deck (18)
A greedy algorithm builds up a solution by choosing the option that looks the best at every step. Sometimes a greedy algorithm doesn't give you an optimal solution! (eg Give money back, biggest coin first...)
Avoid recursion (top-down), saving the memory cost that recursion incurs when it builds up the call stack as well as the risk of stack overflow error. (eg product from 1 to n)
Overlapping Subproblems and Memoization
A problem has overlapping subproblems if finding its solution involves solving the same subproblem multiple times. (eg Fibonacci) Memoization ensures that a function doesn't run for the same inputs more than once by keeping a record of the results for the given inputs (usually in a dictionary).
Short Circuit Evaluation
Avoid unnecessary work (don't evaluate a part of the condition). We can use this to our advantage.
A garbage collector automatically frees up memory that a program isn't using anymore. tracing garbage collection VS reference counting VS manual memory management
Careful: you are allocating a new list and copying the elements from the original list to the new list O(n) time and O(n) space, where n is the number of elements in the resulting list. Even if the variable is not saved.
Operates directly on its input and changes it (destructive). Working in-place is a good way to save space. An in-place algorithm will generally have O(1) space cost.
Arrays - space, lookup, append, insert, delete
O(n), O(1), O(1), O(n), O(n). Fixed size, one after another in memory.
Dynamic Array - space, lookup, append, insert, delete
O(n), O(1), O(1) - amortized, O(n), O(n)
Hash Tables - space, lookup, append, insert, delete
O(n), O(1) - amortized, O(1) - amortized, O(1) - amortized
Flexible keys (any datatype), Fast lookups but Unordered, Single-directional lookups (O(n) to get the key of a value), Not cache-friendly (uses linked-lists, data not next to each other in memory)
Linked List - space, prepend, append, lookup, insert, delete
O(n), O(1), O(1), O(n), O(n), O(n)
An item in a linked list is called a node. The first node is called the head. The last node is called the tail.
Fast operations on the ends, Flexible size but Costly lookups (used for stacks and queues)
Queue - space, enqueue, dequeue, peek
O(n), O(1), O(1), O(1)
A queue stores items in a first-in, first-out (FIFO) order. Fast operations (BFS, processes...)
Stack - space, push, pop, peek
O(n), O(1), O(1), O(1)
A stack stores items in a last-in, first-out (LIFO) order. Fast operations (DFS...)
def __init__(self, value):
self.value = value
self.left = None
self.right = None
perfect: every level of the tree is completely full (half of our nodes are on the last level)
n = 2^h + 1
log2(n - 1) = h
(level starts at 0 with 2^0 node...)
Bitwise AND, OR, XOR, NOT, bitshifting
5 & 6 → 4
5 | 6 → 7
5 ^ 6 → 3
~ 5 → -6
0010 << 1 → 0100
1011010 >> 3 → 0001011
Shifting left multiplies by 2. Shifting right divides by 2, throwing out any remainders.
Two's complement encoding
The leftmost digit is negative, and the rest of the digits are positive. ex: 101 = -3