Top 10 Data Structures & AlgorithmsInterview Questions & Answers (2025)

Big-O notation describes the worst-case time (or space) complexity of an algorithm as input size n grows. O(1) is constant, O(log n) is logarithmic (halving search space each step — binary search), O(n) is linear, O(n log n) is linearithmic (efficient sorting like merge sort), O(n²) is quadratic (nested loops), O(2^n) is exponential (recursive brute force). Focus on eliminating nested loops and repeated work.

Arrays store elements in contiguous memory — O(1) random access by index, O(n) insertion/deletion in middle (shifting required). Linked lists store elements in nodes with next pointers — O(n) access by index, O(1) insertion/deletion if you have the node pointer (no shifting). Arrays are better for cache performance and random access; linked lists for frequent insertions/deletions at known positions.

A stack is a LIFO (Last In, First Out) data structure with push, pop, and peek operations, all O(1). Used for: function call stack, undo operations, expression evaluation (infix to postfix), validating brackets (classic problem), DFS traversal (can replace recursion), and backtracking algorithms. Implement with a dynamic array or linked list.

A queue is a FIFO (First In, First Out) data structure with enqueue and dequeue operations, O(1) each. Used for: BFS graph traversal, level-order tree traversal, task scheduling, printer/CPU job queues, and sliding window problems (deque). A deque (double-ended queue) supports O(1) operations at both ends and is useful for monotonic queue patterns.

A BST is a binary tree where every node's left subtree contains only nodes with values less than the node, and the right subtree only greater values. Search, insert, and delete are O(h) where h is height. A balanced BST (AVL, Red-Black Tree) guarantees O(log n) height. In-order traversal of a BST gives sorted output — a key property for many problems.

A hash map maps keys to values using a hash function to compute an array index. Hash collisions (two keys map to the same index) are handled by chaining (each bucket stores a linked list of entries — Java's HashMap) or open addressing (probe for the next empty slot — linear or quadratic probing). Average O(1) for get/put; O(n) worst case with many collisions.

BFS (Breadth-First Search) explores level by level using a queue — finds the shortest path in unweighted graphs, level-order tree traversal, checking connectivity. DFS (Depth-First Search) explores as deep as possible using a stack/recursion — detects cycles, topological sort, finding connected components, maze-solving, and problems requiring backtracking. BFS for shortest path; DFS for exhaustive search and graph properties.

Dynamic programming solves problems by breaking them into overlapping subproblems, computing each once, and storing results (memoization or tabulation) to avoid redundant work. Key insight: identify optimal substructure (optimal solution contains optimal solutions to subproblems) and overlapping subproblems. Classic problems: Fibonacci, coin change, longest common subsequence, knapsack, matrix chain multiplication.

The sliding window maintains a window (subarray or substring) over data and slides it to compute a result without reprocessing elements. Fixes an O(n²) brute-force to O(n). Fixed-size window: track a running sum/count, add the new element, remove the oldest. Variable-size window: expand the right pointer, shrink the left when a constraint is violated. Used for: maximum subarray sum of size k, longest substring without repeating characters.

Two pointers start at different positions and move toward each other (or in the same direction) to solve array/string problems in O(n) instead of O(n²). Common patterns: left and right pointers on a sorted array (two-sum, container with most water, three-sum), fast and slow pointers on a linked list (detect cycle, find middle), and meeting in the middle.