Curated questions covering arrays, linked lists, trees, graphs, sorting, searching, dynamic programming, and Big O notation.
Big O notation describes the worst-case time or space complexity of an algorithm in terms of input size n. It represents the growth rate. Common complexities: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n^2) quadratic, O(2^n) exponential, O(n!) factorial.
// Array: O(1) access
int arr[5] = {1,2,3,4,5};
arr[2]; // O(1)
// Linked list: O(n) access
struct Node { int data; Node* next; };A stack is a LIFO (Last In First Out) data structure. Operations: push (add to top), pop (remove from top), peek/top (view top), isEmpty. Used for: function call stack, undo operations, expression evaluation, DFS.
class Stack {
constructor() { this.items = []; }
push(x) { this.items.push(x); }
pop() { return this.items.pop(); }
peek() { return this.items[this.items.length - 1]; }
isEmpty(){ return this.items.length === 0; }
}A queue is a FIFO (First In First Out) data structure. Operations: enqueue (add to rear), dequeue (remove from front), peek/front, isEmpty. Used for: BFS, task scheduling, print queues, producer-consumer.
class Queue {
constructor() { this.items = []; }
enqueue(x) { this.items.push(x); }
dequeue() { return this.items.shift(); }
front() { return this.items[0]; }
isEmpty() { return this.items.length === 0; }
}A BST is a binary tree where each node's left subtree contains only nodes with smaller values, and the right subtree contains only nodes with larger values. Operations: search, insert, delete - O(log n) average, O(n) worst case (unbalanced).
function search(node, target) {
if (!node) return null;
if (target === node.val) return node;
if (target < node.val) return search(node.left, target);
return search(node.right, target);
}// BFS
function bfs(graph, start) {
const queue = [start], visited = new Set([start]);
while (queue.length) {
const node = queue.shift();
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) { visited.add(neighbor); queue.push(neighbor); }
}
}
}Binary search finds a target in a sorted array by repeatedly halving the search space. Time complexity: O(log n). Requires the array to be sorted.
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}// Merge Sort
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}Dynamic programming solves problems by breaking them into overlapping subproblems and storing results (memoization or tabulation) to avoid redundant computation. Used for: Fibonacci, knapsack, longest common subsequence, shortest path.
// Fibonacci with memoization
function fib(n, memo = {}) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
return memo[n] = fib(n-1, memo) + fib(n-2, memo);
}
// Tabulation
function fibTab(n) {
const dp = [0, 1];
for (let i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}A hash tl-table maps keys to values using a hash function. Average O(1) for insert, delete, and lookup. Collisions are handled by chaining (linked lists) or open addressing (probing).
// JavaScript Map (hash table)
const map = new Map();
map.set("key", "value");
map.get("key"); // O(1)
map.has("key"); // O(1)
map.delete("key"); // O(1)// Min-heap using array
class MinHeap {
constructor() { this.heap = []; }
push(val) { this.heap.push(val); this._bubbleUp(); }
pop() { /* swap root with last, remove, sift down */ }
}A trie (prefix tree) is a tree where each node represents a character. Used for efficient string search, autocomplete, and spell checking. Search/insert: O(m) where m is string length.
class TrieNode {
constructor() { this.children = {}; this.isEnd = false; }
}
class Trie {
constructor() { this.root = new TrieNode(); }
insert(word) {
let node = this.root;
for (const ch of word) {
if (!node.children[ch]) node.children[ch] = new TrieNode();
node = node.children[ch];
}
node.isEnd = true;
}
}Topological sort orders vertices of a directed acyclic graph (DAG) such that for every edge u->v, u comes before v. Used for task scheduling, build systems, and dependency resolution. Implemented with DFS or Kahn's algorithm (BFS).
// Kahn's algorithm (BFS)\nfunction topoSort(graph, n) {\n const inDegree = new Array(n).fill(0);\n for (const [u, v] of graph) inDegree[v]++;\n const queue = [];\n for (let i = 0; i < n; i++) if (inDegree[i] === 0) queue.push(i);\n const result = [];\n while (queue.length) {\n const u = queue.shift();\n result.push(u);\n for (const v of adj[u]) if (--inDegree[v] === 0) queue.push(v);\n }\n return result;\n}Dijkstra's algorithm finds the shortest path from a source to all vertices in a weighted graph with non-negative edges. Uses a min-heap (priority queue). Time complexity: O((V+E) log V).
function dijkstra(graph, start) {
const dist = {};
const pq = [[0, start]]; // [distance, node]
dist[start] = 0;
while (pq.length) {
const [d, u] = pq.shift(); // use min-heap in practice
if (d > (dist[u] ?? Infinity)) continue;
for (const [v, w] of graph[u]) {
if ((dist[u] + w) < (dist[v] ?? Infinity)) {
dist[v] = dist[u] + w;
pq.push([dist[v], v]);
}
}
}
return dist;
}Two pointers use two indices to traverse an array or linked list, often from both ends or at different speeds. Used for: finding pairs with a sum, removing duplicates, detecting cycles (Floyd's algorithm).
// Find pair with target sum in sorted array
function twoSum(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo < hi) {
const sum = arr[lo] + arr[hi];
if (sum === target) return [lo, hi];
else if (sum < target) lo++;
else hi--;
}
return null;
}The sliding window technique maintains a window of elements and slides it across the array to solve subarray/substring problems efficiently. Reduces O(n^2) brute force to O(n).
// Maximum sum subarray of size k
function maxSumSubarray(arr, k) {
let sum = arr.slice(0, k).reduce((a, b) => a + b, 0);
let max = sum;
for (let i = k; i < arr.length; i++) {
sum += arr[i] - arr[i - k];
max = Math.max(max, sum);
}
return max;
}Floyd's algorithm (tortoise and hare) detects cycles in a linked list using two pointers - slow (moves 1 step) and fast (moves 2 steps). If they meet, a cycle exists. Time: O(n), Space: O(1).
function hasCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}// Adjacency list
const graph = {
A: ["B", "C"],
B: ["A", "D"],
C: ["A"],
D: ["B"]
};
// Adjacency matrix
const matrix = [
[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 0],
[0, 1, 0, 0]
];The 0/1 knapsack problem: given items with weights and values, find the maximum value that fits in a knapsack of capacity W. Each item can be taken (1) or not (0). Solved with DP in O(nW) time.
function knapsack(weights, values, W) {
const n = weights.length;
const dp = Array(n+1).fill(null).map(() => Array(W+1).fill(0));
for (let i = 1; i <= n; i++)
for (let w = 0; w <= W; w++) {
dp[i][w] = dp[i-1][w];
if (weights[i-1] <= w)
dp[i][w] = Math.max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1]);
}
return dp[n][W];
}// Priority queue (min-heap) in JavaScript
const pq = new MinPriorityQueue();
pq.enqueue("task1", 3); // priority 3
pq.enqueue("task2", 1); // priority 1
pq.dequeue(); // returns task2 (lowest priority number)function inOrder(node) {
if (!node) return;
inOrder(node.left);
console.log(node.val); // sorted for BST
inOrder(node.right);
}// Fenwick tree prefix sum
class BIT {
constructor(n) { this.tree = new Array(n+1).fill(0); }
update(i, delta) { for (; i < this.tree.length; i += i & -i) this.tree[i] += delta; }
query(i) { let s = 0; for (; i > 0; i -= i & -i) s += this.tree[i]; return s; }
}Disjoint set union (DSU), also called union-find, tracks groups of connected elements. It supports find and union operations efficiently using path compression and union by rank/size. It is used in Kruskal MST, cycle detection, connected components, and dynamic connectivity problems.
function find(parent, x) {
if (parent[x] !== x) parent[x] = find(parent, parent[x]);
return parent[x];
}
function union(parent, rank, a, b) {
let pa = find(parent, a), pb = find(parent, b);
if (pa === pb) return false;
if (rank[pa] < rank[pb]) [pa, pb] = [pb, pa];
parent[pb] = pa;
if (rank[pa] === rank[pb]) rank[pa]++;
return true;
}Sliding window is used for array or string problems where a contiguous range is expanded and shrunk while maintaining useful state. It avoids recomputing from scratch and often reduces O(n^2) brute force solutions to O(n).
function maxSum(nums, k) {
let sum = 0, best = -Infinity;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
if (i >= k) sum -= nums[i - k];
if (i >= k - 1) best = Math.max(best, sum);
}
return best;
}The two-pointer technique uses two indexes that move through an array or string to find pairs, ranges, or partitions efficiently. It is common in sorted arrays, palindrome checks, merging, and removing duplicates.
function twoSumSorted(nums, target) {
let left = 0, right = nums.length - 1;
while (left < right) {
const sum = nums[left] + nums[right];
if (sum === target) return [left, right];
if (sum < target) left++; else right--;
}
return [-1, -1];
}Explore 500+ free tutorials across 20+ languages and frameworks.