Top 50 DSA Interview Questions with Answers (2026): Fresher to FAANG-Level

💡 Why Interviewers Ask This: Baseline test. A strong candidate knows that choosing the wrong data structure can crash an application under heavy load, while the right one makes it infinitely scalable.

💡 Why Interviewers Ask This: Tests your high-level architectural view of how memory is mapped and how complexity arises from relationships between elements.

Time Complexity measures how the runtime of an algorithm grows as the size of the input data (n) increases. Big-O Notation is the mathematical metric used to describe the worst-case scenario (upper bound) of this growth. Common complexities in order of efficiency:

💡 Why Interviewers Ask This: You cannot pass a DSA interview without knowing Big-O. It is the universal language engineers use to evaluate, compare, and justify code efficiency.

Space Complexity is the total amount of memory space that an algorithm or data structure requires to execute, including both the space used by the input values and any auxiliary (temporary) space allocated during execution. An in-place algorithm like Bubble Sort uses O(1) auxiliary space. Merge Sort uses O(n) auxiliary space for its temporary array. Recursive algorithms use O(depth) stack space — a 1000-level recursion uses O(1000) stack frames.

💡 Why Interviewers Ask This: In modern cloud computing, memory is expensive. Proving you consider RAM usage alongside CPU speed shows production-ready engineering judgment.

Amortized Analysis calculates the average cost per operation over a sequence of operations in the worst case. The classic example: a Dynamic Array (like Python's list). Appending an item is usually O(1), but when the array is full it must resize — copying all n elements to a new array takes O(n). However, because resizing doubles the capacity each time, the cost is spread over n future appends. The amortized cost per append is O(1) — this is why list.append() is fast in practice despite occasional expensive resizes.

💡 Why Interviewers Ask This: Essential for explaining Dynamic Arrays and understanding why Python lists, Java ArrayLists, and C++ vectors can be used efficiently without worrying about their occasional resize overhead.

An Array is a linear data structure consisting of a collection of elements of the same data type, stored in contiguous (adjacent) memory locations. Because elements are stored consecutively, the address of any element can be computed instantly as: base_address + (index × element_size) — enabling O(1) random access by index. The trade-off: inserting or deleting an element in the middle requires shifting all subsequent elements, making these operations O(n).

💡 Why Interviewers Ask This: The most fundamental data structure. You must mention “contiguous memory” — it is precisely this property that gives arrays O(1) read access and distinguishes them from Linked Lists.

💡 Why Interviewers Ask This: Trade-off analysis is the core skill being tested. There is no universally “better” structure — the correct choice always depends on the operation profile of the application.

A Linked List is a linear data structure where elements are not stored in contiguous memory locations. Instead, each element (called a Node) contains two parts: the data and a pointer (reference) to the next Node in the sequence. The list is accessed starting from the Head node, and the last node points to null. This structure allows for O(1) insertions at the head but requires O(n) traversal for lookups.

// Node structure
class Node {
    int data;
    Node next;
}

💡 Why Interviewers Ask This: The foundational dynamic data structure. It sacrifices instant read times in exchange for blazing-fast insertions and dynamic sizing without wasted capacity.

A Doubly Linked List is a variation where each node contains three parts: the data, a pointer to the next node, and a pointer to the previous node. This bidirectional linking enables O(1) traversal in both directions — forward and backward. Deletion of a known node is also O(1) without needing to find its predecessor first (unlike a singly linked list which requires O(n) to find the node before it).

💡 Why Interviewers Ask This: The backward pointer unlocks two-way traversal — required for features like a web browser's Back/Forward navigation history, undo/redo stacks in text editors, and LRU Cache implementations.

The optimal solution is Floyd's Cycle-Finding Algorithm (The Tortoise and the Hare). Use two pointers: a slow pointer moving one node at a time, and a fast pointer moving two nodes at a time. If a cycle exists, the fast pointer will eventually lap the slow pointer and the two pointers will meet at the same node. If the fast pointer reaches null, there is no cycle.

boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

💡 Why Interviewers Ask This: A guaranteed technical screening question at top companies. It tests whether you know the O(n) time, O(1) space optimal solution over the naive O(n) space HashSet approach.

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle — the last element added to the stack is the first one to be removed. Think of a stack of plates: you can only add or remove from the top. Real-world implementations: the Call Stack in memory (manages function call frames and returns), undo operations in text editors, bracket/parenthesis validation in compilers, and browser back navigation.

💡 Why Interviewers Ask This: Essential for understanding recursion. The Call Stack in memory dictates exactly how nested functions execute and return — understanding this is the key to predicting stack overflow errors.

💡 Why Interviewers Ask This: Basic operational vocabulary. All four of these operations must run in O(1) time — any implementation that does not achieve this is incorrect.

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle — the first element added is the first one to be removed, exactly like a real-world line of people at a ticket counter. Elements are added at the rear (enqueue) and removed from the front (dequeue). Applications: CPU process scheduling, print job spooling, BFS graph traversal, and message broker systems (RabbitMQ, Apache Kafka).

💡 Why Interviewers Ask This: The foundation for understanding asynchronous programming and background job processing. When you send an email, it goes into a queue before the mail server processes it.

A Deque (pronounced “deck”) is a generalized queue that allows insertion and deletion of elements from both ends — the front and the rear — in O(1) time. Unlike a standard queue (insert rear only, delete front only) or a stack (insert and delete top only), a Deque supports all four operations at both ends simultaneously.

💡 Why Interviewers Ask This: A Deque can be used as both a Stack and a Queue, making it a highly versatile tool. Python's collections.deque is the preferred implementation for both LIFO and FIFO operations in interviews.

Use two Stacks (Stack 1 and Stack 2):

💡 Why Interviewers Ask This: A classic FAANG interview question that forces you to creatively use one data structure's constraints to simulate another. Demonstrates deep operational understanding of Stacks and Queues.

A Tree is a non-linear, hierarchical data structure consisting of nodes connected by edges. It starts with a single Root node at the top and branches downward into Child nodes. Nodes with no children are called Leaf nodes. Key properties: a tree with n nodes has exactly n-1 edges; there is exactly one path between any two nodes; trees have no cycles. Real-world uses: file systems, HTML DOM, database B-Trees, organizational charts.

💡 Why Interviewers Ask This: Transitions the interview from linear memory-mapped structures to complex hierarchical routing — setting up all subsequent tree questions.

A Binary Tree is a specific type of tree where every node has at most two children, strictly referred to as the left child and the right child. A node can have zero, one, or two children. Binary trees come in specific forms: a Full Binary Tree has every node with exactly 0 or 2 children; a Complete Binary Tree has all levels filled except possibly the last (which is filled left to right); a Perfect Binary Tree has all levels completely filled.

💡 Why Interviewers Ask This: The foundational structure for almost all advanced searching and sorting trees — BSTs, AVL trees, Red-Black trees, Heaps, and B-Trees all build on the Binary Tree concept.

A BST is a Binary Tree with a strict ordering rule: For every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater. This invariant enables search, insert, and delete in O(log n) time on a balanced tree by halving the search space at each step. Without balancing, a BST can degrade to a linked list (O(n)) if elements are inserted in sorted order.

💡 Why Interviewers Ask This: The ordering property is everything — it is what allows the BST to perform searches in O(log n) time, mimicking binary search. The degenerate case (O(n)) motivates why AVL and Red-Black trees exist.

💡 Why Interviewers Ask This: You must memorize and be able to trace all four traversals on a whiteboard. Inorder on a BST producing sorted output is one of the most frequently asked follow-up questions.

A Balanced Binary Tree maintains a small height difference (balance factor) — usually no more than 1 — between the left and right subtrees of every node. This keeps the tree's height at O(log n), preserving efficient O(log n) operations. If a BST becomes unbalanced (skewed) — for example, after inserting elements in ascending order — it degenerates into a linked list with O(n) search, completely eliminating the benefit of using a BST.

💡 Why Interviewers Ask This: Tests your awareness of worst-case BST degradation and motivates why self-balancing trees (AVL, Red-Black) were invented to enforce balance guarantees automatically.

An AVL Tree (named after inventors Adelson-Velsky and Landis) is a self-balancing Binary Search Tree. It automatically maintains balance after every insertion or deletion by ensuring the balance factor (height of left subtree − height of right subtree) for every node stays in the range {-1, 0, +1}. When an insertion violates this, the tree performs one of four rotations (Left-Left, Right-Right, Left-Right, Right-Left) to rebalance. Guarantees O(log n) for all operations.

💡 Why Interviewers Ask This: AVL Trees fix the fatal flaw of standard BSTs. Knowing the four rotation cases demonstrates a thorough understanding of tree balancing — a frequent whiteboard question at senior-level interviews.

A Red-Black Tree is a self-balancing BST where each node carries an extra bit denoting its color (red or black). It enforces five properties: (1) every node is red or black, (2) the root is black, (3) every leaf (null) is black, (4) a red node cannot have a red parent, (5) every path from root to leaf has the same number of black nodes. These rules guarantee the tree height stays within O(log n), and rebalancing after insertions/deletions is faster on average than AVL trees.

💡 Why Interviewers Ask This: Modern language standard library sorted collections are built on Red-Black trees: Java's TreeMap/TreeSet, C++'s std::map/std::set. Knowing this connects theory to real-world library internals.

A Trie is a specialized tree where each node represents a single character of a string, and paths from root to leaf nodes spell out complete words. All words sharing a common prefix share the same path from the root. This makes Tries incredibly fast for prefix-matching operations: insert, search, and prefix-check all run in O(m) where m is the string length — versus O(m × n) for a naive array scan over n strings.

💡 Why Interviewers Ask This: Tries power Google's Search Autocomplete, dictionary spell-checkers, and IP routing tables. Any problem involving “find all words starting with prefix X” requires a Trie.

A Segment Tree is a highly specialized tree data structure used for efficiently storing intervals or array segments and answering range queries. Each node stores the aggregate (sum, min, max) of a subarray range. It allows range queries (e.g., “What is the sum of elements from index 3 to 17?”) and point updates (e.g., “Change element at index 7 to 42”) both in O(log n) time — compared to O(n) for a naive approach.

💡 Why Interviewers Ask This: Advanced competitive programming knowledge tested at senior/staff level interviews. Used in geographic information systems (GIS), financial analytics platforms, and leaderboards requiring real-time range statistics.

A Heap is a specialized Complete Binary Tree that satisfies the Heap Property: in a Max-Heap, every parent node is greater than or equal to its children; in a Min-Heap, every parent is less than or equal to its children. Heaps are almost always stored as a flat array for memory efficiency: for a node at index i, its left child is at 2i+1 and right child at 2i+2. This gives O(1) access to the min/max element (always at the root) and O(log n) insert and extract.

💡 Why Interviewers Ask This: Heaps are crucial for instantly fetching the “highest priority” element — the core operation behind Priority Queues, Heap Sort, and Dijkstra's shortest path algorithm.

💡 Why Interviewers Ask This: Choosing between Min-Heap and Max-Heap is a direct design decision in every algorithm that requires greedy selection of extremes. Python's heapq module is a Min-Heap by default.

A Priority Queue is an abstract data type that operates like a normal queue, but every element has a priority associated with it. Elements with higher priority are dequeued before elements with lower priority, regardless of insertion order. It is almost always implemented using a Heap, giving O(1) peek at the highest priority element, O(log n) insertion, and O(log n) extraction. Used by: OS CPU process schedulers, A* pathfinding (game AI), Dijkstra's shortest path, hospital triage systems.

💡 Why Interviewers Ask This: It is the underlying data structure used by operating systems for CPU scheduling and the critical component of Dijkstra's algorithm and A* search.

Heapify is the algorithmic process of converting a standard binary tree (or unsorted array) into a valid Heap data structure. Heapify-up (bubble up) is used after insertion — the new element swaps with its parent until the heap property is restored. Heapify-down (sift down) is used after extraction of the root — the replacement element swaps downward until the heap property is restored. Building a heap from an unsorted array using bottom-up heapify runs in O(n) time (not O(n log n) as intuition suggests).

💡 Why Interviewers Ask This: Understanding heapify is required to understand Heap Sort (an O(n log n) in-place sorting algorithm) and to explain the surprising O(n) build-heap complexity.

Hashing is a technique that uses a hash function to map variable-size input data (a key) to a fixed-size integer (a hash code), which is then used as an index into an array. An ideal hash function: (1) is deterministic — same key always produces same hash, (2) distributes keys uniformly across the array to minimize collisions, (3) runs in O(1) time. Hashing powers Hash Tables, cryptographic security (SHA-256, bcrypt), data deduplication, and database indexing.

💡 Why Interviewers Ask This: Hashing is the secret to O(1) data lookup at scale. Understanding the hash function's quality directly determines the performance characteristics of the Hash Table built on top of it.

A Hash Table is a data structure that stores key-value pairs and uses a hash function to compute an array index (bucket) for each key. It provides average-case O(1) for search, insert, and delete — the fastest possible lookup. Examples: Python's dict, Java's HashMap, JavaScript objects. Worst-case degrades to O(n) when all keys hash to the same bucket, but good hash functions and dynamic resizing prevent this in practice.

💡 Why Interviewers Ask This: The most frequently used data structure in enterprise software. Almost every “optimize from O(n²) to O(n)” coding problem involves replacing a nested loop with a Hash Table.

A Hash Collision occurs when the hash function generates the same array index for two different keys. Because the array (bucket) space is finite and the possible input keys are effectively infinite, collisions are mathematically inevitable — the Birthday Problem guarantees that with just 23 people in a room, there is a 50%+ chance two share a birthday. The practical impact: without collision handling, one key's value would silently overwrite another, causing data corruption.

💡 Why Interviewers Ask This: You cannot claim mastery of Hash Tables without knowing their failure mode and how to handle it. Every production Hash Map implementation must solve this problem.

💡 Why Interviewers Ask This: Trade-off analysis. Chaining uses more memory (pointers) but is simpler and handles high load factors well. Open Addressing is cache-efficient but degrades severely as the table fills.

The Load Factor (λ) is a measure of how full the Hash Table is: Load Factor = Number of Elements / Size of Array. When the load factor reaches a certain threshold (typically 0.75 in Java's HashMap), the hash table automatically doubles in size and rehashes all existing elements into the new larger array. This rehashing operation costs O(n) but happens infrequently enough that the amortized insert cost remains O(1).

💡 Why Interviewers Ask This: Proves you understand the underlying mechanics of modern Hash Maps. The 0.75 threshold is a deliberate engineering trade-off — higher load = more collisions; lower load = wasted memory.

A Graph is a non-linear data structure consisting of Vertices (nodes) and Edges (connections between nodes). Unlike Trees, graphs can have cycles, multiple edges between nodes, and disconnected components. Graphs represent: social networks (users = vertices, friendships = edges), map navigation (cities = vertices, roads = edges), the internet (web pages = vertices, hyperlinks = edges), and dependency systems (packages = vertices, dependencies = edges).

💡 Why Interviewers Ask This: The most complex and versatile data structure. Any problem description mentioning “network,” “connections,” or “relationships between entities” almost certainly requires a graph solution.

💡 Why Interviewers Ask This: Determines the algorithms you apply. Cycle detection, topological sort, and DAG (Directed Acyclic Graph) analyses are unique to directed graphs.

💡 Why Interviewers Ask This: Adjacency Lists are used in 95% of real-world software engineering graphs. Use an Adjacency Matrix only if the graph is dense (E ≈ V²) and you need O(1) edge existence lookups.

BFS is a graph traversal algorithm that explores nodes level by level. Starting from a source node, it visits all immediate neighbors first, then their neighbors, and so on. BFS uses a Queue to track the frontier. Time: O(V + E), Space: O(V). BFS guarantees the shortest path in an unweighted graph because it always explores the closest nodes first — it cannot discover a node via a longer route before the shortest one. Used by: Google Maps shortest route, peer-to-peer network protocols, web crawlers.

💡 Why Interviewers Ask This: BFS is the algorithm for unweighted shortest path problems. The Queue is non-negotiable — using a Stack instead converts it to DFS.

DFS is a traversal algorithm that starts at a source node and explores as deep as possible along each branch before backtracking. It processes one entire path from source to leaf before exploring alternative paths. DFS uses a Stack (or implicit recursion stack). Time: O(V + E), Space: O(V). Key applications: detecting cycles in graphs, maze solving (always go as far as possible before backtracking), topological sorting, finding strongly connected components.

💡 Why Interviewers Ask This: DFS is the algorithmic basis for cycle detection, topological sort, and backtracking. Many recursive tree traversal problems are DFS in disguise.

Dijkstra's algorithm finds the shortest path from a single source node to all other nodes in a Weighted Graph with non-negative edge weights. Strategy: (1) Initialize all distances to infinity except the source (0), (2) use a Min-Heap Priority Queue to always process the unvisited node with the smallest known distance, (3) for each processed node, “relax” (update) the distances to all its neighbors, (4) repeat until all nodes are processed. Time: O((V + E) log V) with a binary heap.

💡 Why Interviewers Ask This: The foundational algorithm behind GPS navigation, Google Maps, and network routing (OSPF protocol). Important limitation: fails with negative edge weights — use Bellman-Ford instead.

A Spanning Tree is a subgraph of a connected undirected graph that: (1) includes all V vertices of the original graph, (2) has exactly V-1 edges — the minimum needed to connect all vertices, (3) contains no cycles. A graph with n vertices has many possible spanning trees. A Minimum Spanning Tree (MST) is the spanning tree with the smallest total edge weight, found by Kruskal's or Prim's algorithm.

💡 Why Interviewers Ask This: MSTs solve the “minimum cost to connect all nodes” problem. Real applications: designing fiber optic networks, electrical grid layouts, and cluster analysis in machine learning.

Kruskal's Algorithm is a greedy algorithm that finds the Minimum Spanning Tree (MST) of a graph. Steps: (1) Sort all edges by weight ascending, (2) iterate through edges from cheapest to most expensive, (3) add an edge to the MST if it does not create a cycle (checked efficiently using the Union-Find data structure), (4) stop when V-1 edges have been added. Time: O(E log E) dominated by the sorting step.

💡 Why Interviewers Ask This: Highly practical for infrastructure engineering problems — e.g., “connect all servers in a data center with the minimum total cable length.” It also introduces Union-Find, a powerful standalone data structure.

Topological Sort produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge U → V, vertex U appears before V in the output. It is only possible if the graph has no cycles (hence “Acyclic”). Two approaches: (1) DFS-based — run DFS, appending each node to a result stack on finish; (2) Kahn's Algorithm (BFS-based) — iteratively remove nodes with zero in-degree. Time: O(V + E).

💡 Why Interviewers Ask This: This is the algorithm that determines build order in software dependencies (npm install, Maven, Gradle), course prerequisite scheduling, and task planning systems.

Recursion is a programming technique where a function calls itself repeatedly to solve smaller instances of the same problem. Every recursive function requires: (1) a Base Case — the condition that stops the recursion (e.g., if n == 0 return 1), (2) a Recursive Case — the self-referential call that reduces the problem toward the base case. Without a correct base case, the function recurses infinitely and causes a Stack Overflow.

💡 Why Interviewers Ask This: Recursion is the foundation of Tree traversals, all DFS algorithms, Divide & Conquer, and Dynamic Programming. Cannot pass a coding interview without mastering it.

Divide and Conquer is an algorithmic paradigm with three steps: (1) Divide — split the problem into smaller independent subproblems of the same type, (2) Conquer — solve each subproblem recursively, (3) Combine — merge the results to produce the solution to the original problem. The key insight: subproblems are independent (no shared state), which enables parallelization. Classic examples: Merge Sort, Quick Sort, Binary Search.

💡 Why Interviewers Ask This: It is the underlying logic behind Merge Sort and Quick Sort — the two most important efficient sorting algorithms. Distinguishing it from Dynamic Programming (overlapping vs independent subproblems) is a frequent senior-level question.

Dynamic Programming is an optimization technique for solving problems with overlapping subproblems and optimal substructure. It solves each unique subproblem exactly once and stores the result (in a table or cache) to avoid redundant recomputation. This typically reduces exponential O(2ⁿ) brute-force time to polynomial O(n) or O(n²). Two approaches: (1) Top-Down (Memoization) — recursive with a cache; (2) Bottom-Up (Tabulation) — iterative, fills a DP table from smallest to largest subproblem. Classic problems: Fibonacci, 0/1 Knapsack, Longest Common Subsequence, Coin Change.

💡 Why Interviewers Ask This: DP is considered the hardest part of coding interviews at FAANG. The ability to identify “this is a DP problem” and define the state transition equation separates top candidates from the rest.

Memoization is the Top-Down approach to Dynamic Programming. It wraps a recursive function with a cache (typically a Hash Map) that stores the result of each unique function call. Before computing a result, the function checks if it already exists in the cache — if yes, return the cached value immediately (O(1)); if no, compute it, store it, and return it. Memoization transforms an exponential recursive solution into a linear one with minimal code change.

# Fibonacci with memoization
cache = {}
def fib(n):
    if n in cache: return cache[n]
    if n <= 1: return n
    cache[n] = fib(n-1) + fib(n-2)
    return cache[n]  # O(n) vs O(2^n) brute force

💡 Why Interviewers Ask This: It is the primary mechanism that makes DP fast. The technique of “add a cache dict, add a cache check at the top” is a pattern candidates are expected to apply instinctively.

A Greedy Algorithm builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit (the local optimum) without reconsidering past choices or anticipating future consequences. Greedy algorithms are fast and simple — typically O(n log n) — but unlike DP, they are not guaranteed to find the globally optimal solution for all problem types. They work correctly for specific problem structures. Examples: Dijkstra's shortest path, Kruskal's MST, Huffman Coding (lossless compression), Activity Selection.

💡 Why Interviewers Ask This: Tests your ability to recognize when a greedy choice is provably optimal vs. when DP is required. Making a greedy choice on a Knapsack problem gives a wrong answer — demonstrating you know this separates strong candidates.

Backtracking is an algorithmic technique that builds a solution incrementally, one component at a time. As soon as it determines that a partial solution cannot possibly lead to a valid complete solution, it abandons (“backtracks”) that branch and tries the next alternative — pruning the search tree to avoid unnecessary work. It is essentially an optimized brute-force approach. Applications: Sudoku solver, N-Queens problem, generating all permutations and subsets, maze pathfinding, Crossword puzzle generation.

💡 Why Interviewers Ask This: The definitive algorithm for constraint-satisfaction problems. Learning to implement the “choose → explore → unchoose” template is a high-value interview pattern that solves entire categories of problems.

To detect a cycle in a Directed Graph, use DFS with a “recursion stack” boolean array. Maintain two arrays: visited[] (nodes ever visited) and recStack[] (nodes in the current DFS path). When you visit a node, mark it in both arrays. When you finish processing a node (return from DFS), remove it from recStack[]. If you encounter a node that is already in recStack[], a back edge exists — a cycle is found. Time: O(V + E).

💡 Why Interviewers Ask This: Cycle detection in directed graphs is critical for: preventing infinite loops in dependency resolution (circular imports), detecting OS deadlocks (circular resource waits), and validating DAGs before topological sort.

Union-Find (Disjoint Set Union, DSU) tracks a collection of elements partitioned into non-overlapping subsets. Two core operations: Find(x) — returns the representative (root) of the subset containing element x; Union(x, y) — merges the subsets containing x and y. With two optimizations: (1) Path Compression (flatten the tree during Find) and (2) Union by Rank (always attach the smaller tree under the larger), both operations run in amortized O(α(n)) — practically constant time.

💡 Why Interviewers Ask This: Union-Find is the engine inside Kruskal's MST algorithm (detecting whether adding an edge creates a cycle) and is essential for solving “connected components” and “number of islands” problems efficiently.