Master Interview‑Ready Algorithms & Data Structures with This Open‑Source Guide

Data Structures

Stack

Definition: a collection supporting push to add an element and pop to remove the top element.

Order: LIFO (last‑in‑first‑out).

Time complexity: index O(n), search O(n), insert O(1), remove O(1).

Linked List

Linear collection of nodes where each node points to the next (and optionally the previous) node.

Variants: singly linked list, doubly linked list, circular linked list.

Time complexity: index O(n), search O(n), insert O(1), remove O(1).

Queue

Collection supporting enqueue to add at the tail and dequeue to remove from the head.

Order: FIFO (first‑in‑first‑out).

Time complexity: index O(n), search O(n), insert O(1), remove O(1).

Binary Search Tree (BST)

Binary tree where each node’s value is ≥ all values in its left subtree and ≤ all values in its right subtree.

Time complexity (balanced tree): index, search, insert, delete O(log(n)).

Trie (Prefix Tree)

Tree‑like structure for storing a dynamic set of strings; each node represents a common prefix.

Enables efficient retrieval of keys with shared prefixes.

Segment Tree

Tree structure that stores intervals or segments, allowing fast range queries.

Time complexity: range query O(log(n)), update O(log(n)).

Hash Table

Maps keys to values using a hash function; collisions are handled by separate chaining or open addressing.

Separate chaining stores colliding keys in linked lists per bucket.

Open addressing probes for the next free slot when a collision occurs.

Graph

Data structure representing many‑to‑many relationships between elements.

Undirected graph: edges have no direction; adjacency matrix is symmetric.

Directed graph: edges have direction; adjacency matrix is asymmetric.

Heap

Tree‑based structure satisfying the heap property; max‑heap stores the largest element at the root, min‑heap stores the smallest.

Time complexity: access max/min O(1), insert O(log(n)), remove max/min O(log(n)).

Algorithms

Merge Sort

Divide‑and‑conquer algorithm that recursively splits an array, sorts each half, and merges them.

Stable: yes.

Time complexity (best, average, worst): O(nlog(n)).

Quick Sort

Divide‑and‑conquer algorithm that selects a pivot, partitions the array, and recursively sorts the partitions.

Stable: no.

Time complexity: best O(nlog(n)), average O(nlog(n)), worst O(n^2).

Depth‑First Search (DFS)

Graph traversal that explores as far as possible along each branch before backtracking.

Time complexity: O(|V| + |E|).

Breadth‑First Search (BFS)

Graph traversal that explores all neighbors at the current depth before moving to the next level.

Time complexity: O(|V| + |E|).

Topological Sort

Linear ordering of directed‑graph vertices such that for every directed edge u→v, u appears before v.

Time complexity: O(|V| + |E|).

GitHub repository: https://github.com/kdn251/interviews