Comprehensive answers to the most frequently asked Data Structures & Algorithms questions in technical interviews. Covers 50–60% of typical interview weightage.
An Array stores elements in contiguous memory locations, allowing O(1) random access but O(n) insertion/deletion. A Linked List stores elements as nodes with pointers, allowing O(1) insertion/deletion at known positions but O(n) random access. Arrays have better cache performance; Linked Lists have dynamic size without reallocation.
Time Complexity measures how an algorithm's runtime grows with input size. Space Complexity measures memory usage. Example: Linear Search has O(n) time and O(1) space. Merge Sort has O(n log n) time and O(n) space. We use Big-O notation to describe worst-case bounds like O(1), O(log n), O(n), O(n²), etc.
A Stack is a LIFO (Last In First Out) data structure supporting push, pop, and peek operations in O(1). Real-world uses include: function call stack in recursion, undo/redo in editors, browser back-navigation, balanced parentheses checking, and expression evaluation (infix to postfix). Implemented using arrays or linked lists.
A Queue is a FIFO (First In First Out) data structure. Types include: Simple Queue, Circular Queue (avoids wasted space), Deque (Double Ended Queue — insertion/deletion from both ends), and Priority Queue (elements dequeued by priority). Used in BFS, CPU scheduling, printer spooling, and asynchronous data transfer.
Binary Search finds a target in a sorted array by repeatedly halving the search space. Compare target with middle element — if equal, return; if smaller, search left half; if larger, search right half. Time complexity: O(log n). Space: O(1) iteratively, O(log n) recursively. Requires sorted input as a prerequisite.
A Binary Tree is a tree where each node has at most 2 children (left and right). A Binary Search Tree (BST) additionally enforces: all left subtree values < node value < all right subtree values. BST allows O(log n) average search, insert, delete. Worst case is O(n) for a skewed tree. Self-balancing BSTs like AVL and Red-Black Trees maintain O(log n) always.
A Hash Table maps keys to values using a hash function that converts keys to array indices. Average O(1) for insert, search, delete. Collisions occur when two keys hash to the same index. Resolution techniques: Chaining (each index holds a linked list of entries) and Open Addressing (probe for next empty slot using linear probing, quadratic probing, or double hashing).
BFS (Breadth First Search) explores level by level using a queue. Time/Space: O(V+E). Used for: shortest path in unweighted graphs, level-order traversal, and finding connected components. DFS (Depth First Search) explores as deep as possible using a stack/recursion. Time: O(V+E). Used for: topological sort, cycle detection, path finding, and strongly connected components.
Dynamic Programming (DP) solves problems by breaking them into overlapping subproblems and storing results (memoization/tabulation) to avoid redundant computation. Key properties: Optimal Substructure and Overlapping Subproblems. Example: Fibonacci — naive recursion is O(2^n), but DP makes it O(n). Classic DP problems: Knapsack, Longest Common Subsequence, Matrix Chain Multiplication, Coin Change.
Greedy makes the locally optimal choice at each step hoping to reach the global optimum — fast but doesn't always work. DP considers all possibilities and stores solutions — always correct for applicable problems but uses more space. Example: Fractional Knapsack works with greedy; 0/1 Knapsack requires DP. Greedy: O(n log n) typically. DP: usually O(n²) or O(n*W).
Merge Sort: Divide array into halves, recursively sort, then merge. Always O(n log n), stable sort, O(n) extra space. Quick Sort: Pick a pivot, partition elements around it, recursively sort. Average O(n log n), worst O(n²) with bad pivot. O(log n) space. Quick Sort is faster in practice due to cache efficiency and lower constant factors. Merge Sort is preferred for linked lists and when stability matters.
A Heap is a complete binary tree satisfying the heap property: Max-Heap (parent ≥ children) or Min-Heap (parent ≤ children). Operations: insert and extract in O(log n), peek in O(1). Heap Sort: Build a max-heap from array (O(n)), then repeatedly extract max and place at end (O(n log n)). Total: O(n log n), in-place, but not stable. Used in Priority Queue implementation.
A Graph G = (V, E) consists of vertices (V) and edges (E). Types: Directed/Undirected, Weighted/Unweighted, Cyclic/Acyclic. Representations: Adjacency Matrix (O(V²) space, O(1) edge lookup — good for dense graphs) and Adjacency List (O(V+E) space — good for sparse graphs). Adjacency List is most common in interviews.
Topological Sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u→v, vertex u comes before v. Algorithms: Kahn's Algorithm (BFS-based, detects cycles) and DFS-based using a stack. Time: O(V+E). Use cases: task scheduling, course prerequisite ordering, build dependency resolution, and package managers.
Dijkstra's Algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edges. It uses a min-priority queue and a greedy approach. Time: O((V+E) log V) with a binary heap. Limitation: Does NOT work with negative edge weights. For negative edges, use Bellman-Ford (O(VE)) which also detects negative cycles.
Two Pointers uses two indices to traverse a data structure, reducing time from O(n²) to O(n). Variations: Opposite ends (e.g., Two Sum in sorted array, Container With Most Water) and Same direction/Sliding Window (e.g., Longest Substring Without Repeating Characters, Find all anagrams). Essential for solving array and string problems efficiently.
Sliding Window maintains a window of elements and slides it across the input, updating the result incrementally. Fixed window: Maximum sum subarray of size k — O(n). Variable window: Longest substring with at most k distinct characters. Avoids nested loops, reducing complexity from O(n²) to O(n). Key pattern: expand right pointer, shrink left pointer when condition is violated.
A Trie is a tree-like data structure where each node represents a character, and paths from root represent strings. Insert and Search: O(m) where m is string length. Space: O(alphabet_size × m × n). Applications: Autocomplete systems, spell checkers, IP routing (Longest Prefix Matching), word search in a matrix, and implementing dictionaries. More space-efficient alternatives: Compressed Trie, Ternary Search Tree.
Key string algorithms:
1) KMP (Knuth-Morris-Pratt): O(n+m) pattern matching using failure function.
2) Rabin-Karp: Rolling hash for pattern matching, O(n+m) average.
3) Z-algorithm: O(n) pattern matching.
4) Manacher's: O(n) for longest palindromic substring.
5) Anagram detection using character frequency arrays. Most interviews test: palindromes, anagrams, string reversal, and pattern matching.
Backtracking is a refined recursion that builds solutions incrementally and abandons a path (backtracks) when it cannot lead to a valid solution. It explores all possibilities systematically. Recursion is a general technique; backtracking adds the 'undo step'. Classic problems: N-Queens, Sudoku Solver, Permutations/Combinations, Word Search in a matrix. Time complexity is often exponential but pruning makes it practical.