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).
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent