Data Structures & Algorithms Interview Questions

An array stores elements in contiguous memory with O(1) random access but O(n) insertion/deletion. A linked list stores elements in nodes with pointers, allowing O(1) insertion/deletion at known positions but O(n) access time.

Big O notation describes the upper bound of an algorithm's time or space complexity as input size grows. It helps compare algorithms independently of hardware, enabling developers to choose the most efficient solution for large inputs.

A stack follows LIFO (Last In, First Out) order, while a queue follows FIFO (First In, First Out). Stacks use push/pop operations; queues use enqueue/dequeue operations.

A hash table maps keys to values using a hash function to compute an index. Collisions (two keys mapping to the same index) are handled via chaining (linked lists at each bucket) or open addressing (probing for the next empty slot).

Binary search runs in O(log n) time. It requires the input array to be sorted, as it repeatedly halves the search space by comparing the target to the middle element.

BFS (Breadth-First Search) explores nodes level by level using a queue, making it ideal for finding shortest paths in unweighted graphs. DFS (Depth-First Search) explores as far as possible along each branch using a stack or recursion, suited for cycle detection, topological sort, and pathfinding.

A BST is a binary tree where each node's left subtree contains only smaller values and the right subtree contains only larger values. Average-case search, insertion, and deletion are all O(log n), but degrade to O(n) in the worst case (a skewed tree).

A heap is a complete binary tree where each parent is greater (max-heap) or smaller (min-heap) than its children. A priority queue is efficiently implemented with a heap, giving O(log n) insertion and deletion and O(1) access to the min/max element.

Dynamic programming solves problems by breaking them into overlapping subproblems and storing results to avoid redundant computation (memoization or tabulation). It applies when a problem has optimal substructure and overlapping subproblems, such as Fibonacci, knapsack, or longest common subsequence.

Memoization is a top-down approach where recursive calls cache results on demand. Tabulation is a bottom-up approach that fills a table iteratively from base cases. Tabulation avoids recursion overhead; memoization only computes needed subproblems.

Use Floyd's Cycle Detection Algorithm (two pointers): a slow pointer moves one step and a fast pointer moves two steps. If they ever meet, a cycle exists; if the fast pointer reaches null, there is no cycle. This runs in O(n) time and O(1) space.

A trie is a tree where each node represents a character and paths from root to leaves spell out strings. It enables O(m) search, insert, and prefix lookup (m = key length), making it ideal for autocomplete, spell-checking, and IP routing tables.

Dijkstra's finds the shortest path from a source node to all others in a weighted graph with non-negative edges. Using a min-heap priority queue, its complexity is O((V + E) log V). It does not work with negative edge weights.

Prim's grows the MST one vertex at a time from a starting node using a greedy approach on adjacent edges; it is efficient on dense graphs. Kruskal's sorts all edges by weight and adds them if they don't form a cycle using a union-find structure; it is efficient on sparse graphs.

AVL trees are self-balancing BSTs where the heights of a node's two subtrees differ by at most one. After insertions or deletions, they restore balance through single or double rotations (LL, RR, LR, RL), keeping all operations at O(log n).

Amortized analysis computes the average cost per operation over a sequence of operations, even if individual operations vary. For example, a dynamic array doubles capacity when full: most appends are O(1), but occasional resizing is O(n). Amortized over n appends, the cost is still O(1) per operation.

NP problems are verifiable in polynomial time. NP-Hard problems are at least as hard as every NP problem but not necessarily in NP. NP-Complete problems are both NP and NP-Hard — they are verifiable in polynomial time and every NP problem reduces to them (e.g., 3-SAT, traveling salesman decision version).

Quicksort selects a pivot, partitions the array so smaller elements are left and larger are right, then recursively sorts each partition. Average case is O(n log n) with good pivot selection; worst case is O(n²) when the pivot is always the smallest or largest element (e.g., sorted input with naive pivot choice).

A segment tree is a binary tree where each node stores aggregate data (sum, min, max) for a range of an array. It supports range queries and point updates in O(log n) time, making it ideal for problems requiring frequent range queries on mutable arrays.

Union-Find tracks elements partitioned into disjoint sets, supporting find (which set) and union (merge sets) operations. With path compression and union by rank, both operations run in nearly O(1) amortized time (O(α(n)), where α is the inverse Ackermann function), making it essential for Kruskal's MST and cycle detection.