Data Structures & Algorithms

What is Big-O notation?

A mathematical notation describing the upper bound of an algorithm's time or space complexity as input size n grows. E.g. O(1) constant, O(log n) logarithmic, O(n) linear, O(n²) quadratic.

What is a hash table?

A data structure that maps keys to values using a hash function. Average O(1) for insert, lookup, and delete. Collisions handled by chaining or open addressing.

Difference between a stack and a queue?

Stack: LIFO (Last In, First Out) — push/pop from the top. Queue: FIFO (First In, First Out) — enqueue at back, dequeue from front.

What is a binary search tree (BST)?

A binary tree where each node's left subtree contains only values less than the node, and the right subtree contains only greater values. Average O(log n) search.

What is Dijkstra's algorithm?

A greedy algorithm to find the shortest path from a source node to all other nodes in a weighted graph with non-negative edges. Time: O((V+E) log V) with a min-heap.

What is dynamic programming?

An optimisation technique that solves complex problems by breaking them into overlapping subproblems and storing results (memoisation or tabulation) to avoid redundant computation.

What is a linked list?

A sequence of nodes where each node contains data and a pointer to the next node. O(1) insert/delete at known position; O(n) access by index. No contiguous memory needed.

What is the difference between BFS and DFS?

BFS (Breadth-First Search): explores level by level using a queue — good for shortest path in unweighted graphs. DFS (Depth-First Search): explores as far as possible using a stack/recursion — good for connectivity and cycle detection.

What is a heap?

A complete binary tree satisfying the heap property: max-heap (parent ≥ children) or min-heap (parent ≤ children). Used for priority queues. O(log n) insert/extract.

What is the time complexity of merge sort?

O(n log n) in all cases (best, average, worst). Space: O(n). Stable sort that works by dividing the array in half, sorting each half, then merging.

What is a trie?

A tree-like data structure for storing strings where each node represents a character. Enables O(m) search/insert (m = string length). Used in autocomplete and spell checkers.

What is amortised analysis?

A method of averaging the cost of operations over a sequence of operations, even if individual operations can be expensive. E.g. dynamic array append is O(1) amortised despite occasional O(n) resizing.