For interview questions and what to ask, check out this doc. Otherwise, keep reading for basic data structures, sorting algorithms, and time complexities. I'll add a section on technical tips too later.
Sorting data and everything, including rebalancing, can be done in O(log n).
Generally use unique values (don't want duplicates).
| Operation | Average | Worst |
|---|---|---|
| Insert | O(log n) | O(n) |
| Remove | O(log n) | O(n) |
| Search | O(log n) | O(n) |
Storing and accessing sequential data, temporarily storing, as an IO buffer (when reading from a file), lookup table, and hack for multiple return values.
Can implement a dynamic arrays from static ones by continuously allocating double the space once the array is full.
| Operation | Average | Worst |
|---|---|---|
| Access | O(1) | O(1) |
| Append | --- | O(1) |
| Insert | --- | O(n) |
| Remove | --- | O(n) |
| Search | O(n) | O(n) |
Useful in lists, queues, and stacks. Often used for circular (round robin) or adjacency lists.
Singly-linked will save up on space and it's simpler to implement but it can make it more difficult to access previous nodes. Doubly-linked takes up double the space since we have 2x the pointers but easier to traverse backwards.
| Operation | Average | Worst |
|---|---|---|
| Insert (T/H) | O(1) | O(1) |
| Insert | O(n) | O(n) |
| Remove | O(n) | O(n) |
| Search | O(n) | O(n) |
Useful for undo functions, checking for matching braces, other syntax (or TMs), supports recursion behind the scenes, and is used in DFS on a graph.
Has 2 primary operations: push and pop. Last in, first out: what you most recently pushed will be what comes out when you pop.
| Operation | Average | Worst |
|---|---|---|
| Push | O(1) | O(1) |
| Pop | O(1) | O(1) |
| Peek/Top | O(1) | O(1) |
| Search | O(n) | O(n) |
Used to model a real-world queue like standing in line, a sequence of elements, web server manager for first come, first serve, or BFS graph traversal.
It's a linear data structure with has 2 main operations: dequeue ("polling") and enqueue ("offering"). You remove elements from the front and add elements to the back. Often done via singly-linked list since arrays (static) might not be big enough.
| Operation | Average | Worst |
|---|---|---|
| Enqueue | O(1) | O(1) |
| Dequeue | O(1) | O(1) |
| Peek/Top | O(1) | O(1) |
| Contains | O(n) | O(n) |
| Remove | O(n) | O(n) |
Helpful for tracking item frequencies, if large files have equal contents (without opening files),
Provides a mapping from keys to values via hashing (called a "key-value" pair where keys are unique). Keys are immutable.
-
Open Addressing: Find another place within hash table by using an offset from original hash.
-
Separate Chaining: Use a separate data structure like a list to hold all different values (key-value pairs).
| Operation | Average | Worst |
|---|---|---|
| Lookup | O(1) | O(n) |
| Remove | O(1) | O(n) |
| Insert | O(1) | O(n) |
...
| Best | Average | Worst | Space |
|---|---|---|---|
| O(n) | O(n^2) | O(n^2) | O(1) |
...
| Best | Average | Worst | Space |
|---|---|---|---|
| O(n^2) | O(n^2) | O(n^2) | O(1) |
Ideal for combining lists.
| Best | Average | Worst | Space |
|---|---|---|---|
| O(nlogn) | O(nlogn) | O(nlogn) | O(n) |
...
| Best | Average | Worst | Space |
|---|---|---|---|
| O(nlogn) | O(nlogn) | O(n^2) | O(logn) |
Can be chosen over quick sort because, in the case of a partially sorted array, it's worst case will always be O(nlogn) not O(n^2).
| Best | Average | Worst | Space |
|---|---|---|---|
| O(n) | O(nlogn) | O(nlogn) | O(1) |
Start at a node, add its neighbors to queue, and visit their neighbors (add to queue). We know if all nodes have been visited by marking them as visited (bool).