Data Structures and Algorithms

An array is a list where each item has a fixed position.

Read by index: O(1), insert/delete in middle: O(n)

A string is text data. Many interview tasks ask you to scan or compare text.

Linear scan: O(n)

A hash map stores key-value pairs for very fast lookups.

Insert/find average: O(1)

A stack is last-in, first-out. Think browser back button history.

Push/pop/top: O(1)

A queue is first-in, first-out. Think checkout line behavior.

Enqueue/dequeue: O(1)

A linked list connects nodes with pointers instead of fixed indexes.

Traversal: O(n), insert/delete at node: O(1)

Bubble sort repeatedly compares adjacent pairs and swaps them if they are out of order.

Average/Worst O(n^2), Best O(n) with early-exit optimization

Selection sort scans for the smallest remaining value and swaps it into position.

Time O(n^2), Space O(1), Swaps O(n)

Insertion sort grows a sorted section by inserting each new value into the correct position.

Average/Worst O(n^2), Best O(n), Space O(1)

Merge sort divides data into halves, sorts each half, then merges them back in order.

Time O(n log n), Space O(n)

Quick sort picks a pivot, partitions values around it, then recursively sorts partitions.

Average O(n log n), Worst O(n^2), Space O(log n) recursion

Heap sort builds a max-heap, then repeatedly removes the largest value to fill the array from the back.

Time O(n log n) (best/avg/worst), Space O(1)

Binary search repeatedly halves a sorted search space.

Search: O(log n)

Two pointers move through data from different positions to avoid nested loops.

Typical traversal: O(n)

A sliding window keeps a moving subset of data while scanning once.

Typical traversal: O(n)

Kadane's algorithm finds the largest contiguous subarray sum in a single linear pass.

Time O(n), Space O(1)

Traversal means visiting each tree node in a defined order.

Visit all nodes: O(n)

BFS explores a graph layer by layer using a queue, closest nodes first.

Time O(V + E), Space O(V)

DFS dives as deep as possible down each branch before backtracking, usually with recursion or a stack.

Time O(V + E), Space O(V) recursion depth

Depth-first search and breadth-first search are two core ways to traverse connected graphs.

O(V + E)

A trie stores text so shared prefixes are reused.

Insert/search prefix: O(length of word)

Many algorithm problems can be solved either recursively or iteratively.

Often same time complexity; memory and operational behavior differ

Backtracking tries choices, then undoes them when they fail.

Often exponential in worst case

DP stores subproblem answers so you do not recompute them.

Varies, often reduces exponential to polynomial

A heap quickly gives you the smallest or largest item.

Push/pop: O(log n), peek: O(1)

Union-Find tracks groups of connected items efficiently.

Near O(1) amortized

Segment tree answers range queries while supporting updates.

Query/update: O(log n)

Topological sort orders tasks where dependencies must come first.

O(V + E)

Dijkstra finds shortest path from one node when edge weights are non-negative.

O((V + E) log V) with heap