Data Structures and Algorithms Rapid-Fire Questions &amp; Answers

Show answer

A static array has a fixed size set at creation, such as int[] in Java, and offers O(1) index access with contiguous memory. A dynamic array such as Java ArrayList or Python list grows automatically by allocating a larger block and copying elements, giving amortised O(1) append. Both have O(n) insertion or deletion in the middle because elements must shift. Dynamic arrays trade a little memory for flexibility.

What is dynamic programming, and what are overlapping subproblems and optimal substructure?

Dynamic ProgrammingEasy

Show answer

Dynamic programming solves a problem by combining solutions of smaller subproblems and storing them so each is computed only once. It applies when a problem has overlapping subproblems, meaning the same smaller problems repeat, as in Fibonacci, and optimal substructure, meaning the best answer can be built from best answers to subproblems, as in shortest paths. DP often turns exponential brute force into polynomial time.

Explain the sliding window technique with fixed and variable windows.

Arrays, Strings and HashingMedium

Show answer

A sliding window keeps a contiguous range and updates its result incrementally instead of recomputing. A fixed window of size k, such as the maximum sum of k consecutive elements, adds the new element and removes the old one each step in O(n). A variable window grows the right end and shrinks the left end while a condition is violated, as in the longest substring without repeating characters. Both turn O(n squared) into O(n).

How can you implement a queue using two stacks, and what is its complexity?

Show answer

Use an in-stack for enqueue and an out-stack for dequeue. Enqueue pushes onto the in-stack in O(1). For dequeue, if the out-stack is empty, pop everything from the in-stack and push it onto the out-stack, which reverses the order, then pop from the out-stack. Each element moves at most once between stacks, so dequeue is O(1) amortised even though a single transfer can be O(n).

Compare AVL trees and red-black trees.

Show answer

Both are self-balancing BSTs with O(log n) operations. AVL trees keep the heights of sibling subtrees within one, so they are more strictly balanced and give faster lookups, but need more rotations on insert and delete. Red-black trees allow looser balance using node colours, so updates are cheaper. That is why Java TreeMap and C++ std::map use red-black trees, while AVL suits read-heavy workloads.

What is the difference between BFS and DFS, and when do you use each?

Graphs and Graph AlgorithmsEasy

Show answer

BFS explores level by level with a queue and finds shortest paths in unweighted graphs, such as minimum moves on a board. DFS goes as deep as possible with recursion or a stack and suits cycle detection, topological sorting, connected components, path existence and backtracking. Both run in O(V plus E). BFS can use more memory on wide graphs, while DFS can hit recursion limits on deep ones.

What are a queue, a deque and a circular queue?

Show answer

A queue is first-in, first-out with enqueue at the back and dequeue at the front, used in BFS, task scheduling and buffering. A deque allows insertion and removal at both ends in O(1), as in Python collections.deque or Java ArrayDeque. A circular queue uses a fixed array with head and tail indices that wrap around modulo capacity, avoiding shifting and wasted space, common in ring buffers and OS schedulers.

What is a heap and how is it stored in an array?

Heaps, Priority Queues and GreedyEasy

Show answer

A binary heap is a complete binary tree where every parent is smaller than its children in a min-heap or larger in a max-heap, so the root is the minimum or maximum. Because the tree is complete, it is stored in an array without pointers: for index i, children are at 2i plus 1 and 2i plus 2 and the parent at (i minus 1) divided by 2. This layout is compact and cache friendly.

What is the difference between full, complete and perfect binary trees?

Show answer

In a full binary tree every node has zero or two children. In a complete binary tree every level except possibly the last is completely filled, and the last level is filled from the left, which is exactly the shape of a binary heap and allows array storage. A perfect binary tree has all internal nodes with two children and all leaves at the same level, containing 2 to the power h plus 1, minus 1 nodes.

What is a stable sort and why does stability matter?

Sorting, Searching and BacktrackingEasy

Show answer

A stable sort keeps elements with equal keys in their original relative order. It matters when sorting by multiple keys in passes: sort employees by salary, then stably by department, and salaries stay ordered within each department. Merge sort, insertion sort and Timsort are stable; quicksort and heap sort usually are not. Java uses a stable sort for objects, and Python's sorted is always stable.

What is backtracking?

Sorting, Searching and BacktrackingEasy

Show answer

Backtracking builds a solution step by step and abandons a partial solution as soon as it cannot lead to a valid answer, then undoes the last choice and tries the next. It is a DFS over the space of choices. It solves permutations, combinations, subsets, N-Queens, Sudoku and word search. The worst case is often exponential, so good pruning, such as checking constraints early, is what makes it practical.

What is recursion and why is a base case essential?

Show answer

Recursion is when a function solves a problem by calling itself on smaller subproblems. Each call gets its own frame on the call stack holding parameters and local variables. The base case is the condition where the function returns directly without recursing, such as n equal to 0 for factorial. Without a correct base case, calls never stop and the program fails with a stack overflow.

What is space complexity and how is auxiliary space different?

Show answer

Space complexity is the total memory an algorithm uses relative to input size, including the input itself. Auxiliary space counts only the extra memory beyond the input, such as temporary arrays, hash maps and the recursion stack. Merge sort needs O(n) auxiliary space for merging, while heap sort needs O(1). Interviewers usually mean auxiliary space when they ask you to reduce space usage.

How does Floyd's cycle detection algorithm work and why is it correct?

Show answer

Floyd uses a slow pointer moving one step and a fast pointer moving two steps. If there is no cycle, fast reaches the end. If there is a cycle, fast gains one step per iteration on slow inside the loop, so they must meet. To find the cycle start, reset one pointer to the head and move both one step at a time; they meet at the start because the distances from head and from the meeting point are equal modulo the cycle length.

What is the difference between memoisation and tabulation?

Dynamic ProgrammingEasy

Show answer

Memoisation is top-down: write the natural recursion and cache results in a map or array, so only needed states are computed, but recursion depth can be a problem. Tabulation is bottom-up: fill a table iteratively from base cases in an order where dependencies are ready, avoiding recursion overhead and making space optimisation easier. Both usually have the same time complexity; choose whichever is clearer for the problem.

What is time complexity and what does Big-O notation mean?

Show answer

Time complexity describes how the number of steps an algorithm performs grows as the input size n grows, ignoring machine speed. Big-O gives an upper bound on that growth for large n and drops constants and lower terms, so 3n squared plus 5n becomes O(n squared). It lets you compare approaches before coding; for example binary search at O(log n) beats linear search at O(n) on large sorted data.

What is a monotonic stack and which problems does it solve?

Show answer

A monotonic stack keeps its elements in increasing or decreasing order by popping elements that break the order before each push. Each element is pushed and popped at most once, so a full pass is O(n). It solves next greater or next smaller element, daily temperatures, stock span, largest rectangle in a histogram and trapping rain water, replacing O(n squared) nested scans with a single linear scan.

Strings are immutable in Java and Python. How does that affect algorithm complexity?

Show answer

Every modification creates a new string, so building a string by concatenation inside a loop can copy characters repeatedly and become O(n squared). Use StringBuilder in Java or collect parts in a list and call join in Python, which is O(n) overall. Immutability also makes strings safe as hash map keys and lets runtimes cache their hash codes, which is why they are good dictionary keys.

What are prefix sums and what problems do they solve?

Arrays, Strings and HashingMedium

Show answer

A prefix sum array stores pre[i] as the sum of the first i elements, built in O(n). The sum of any range from l to r is then pre[r+1] minus pre[l] in O(1). Combined with a hash map of prefix sums, it counts subarrays with sum k in O(n). 2D prefix sums answer rectangle sum queries on grids, and difference arrays apply many range updates efficiently.

In activity selection, why do we sort by end time rather than start time or duration?

Heaps, Priority Queues and GreedyMedium

Show answer

Choosing the activity that finishes earliest leaves the most remaining time for others, and an exchange argument shows that any optimal schedule can swap its first activity for the earliest-finishing one without losing count. Sorting by start time fails when an early activity runs very long, and sorting by duration fails when a short activity overlaps two compatible ones. The algorithm is O(n log n) for sorting plus one pass.

What is a dummy or sentinel node and why is it useful in linked list problems?

Show answer

A dummy node is an extra node placed before the real head. It removes special cases for operations that may change the head, such as deleting the first element, merging lists or inserting at the start. You build the result after dummy and return dummy.next at the end. This leads to shorter, less error-prone code, which matters a lot when writing linked list solutions under interview pressure.

How does quicksort work and why does pivot choice matter?

Sorting, Searching and BacktrackingMedium

Show answer

Quicksort picks a pivot, partitions the array so smaller elements go left and larger go right, then recursively sorts both sides. It sorts in place with O(log n) stack space on average and is very cache friendly, averaging O(n log n). A bad pivot, such as always the first element on sorted input, gives unbalanced partitions and O(n squared). Random pivots, median-of-three and three-way partitioning for duplicates avoid this.

What is a binary search tree and what is its time complexity?

Show answer

In a BST every node's left subtree contains smaller keys and the right subtree larger keys. Search, insert and delete follow one path from the root, so they take O(h) time, where h is the height. A balanced tree has h about log n, giving O(log n). Inserting sorted data into a plain BST creates a skewed tree that behaves like a linked list with O(n) operations, which is why balanced variants exist.

Why is naive recursive Fibonacci exponential, and how do you fix it?

Complexity Analysis and RecursionMedium

Show answer

fib(n) calls fib(n-1) and fib(n-2), and each of those branches again, so the call tree has roughly 1.6 to the power n nodes and the same subproblems are recomputed many times. fib(40) makes over 300 million calls. Memoisation stores each result after the first computation, reducing it to O(n) time. A bottom-up loop keeping only the last two values gives O(n) time and O(1) space.

What is the difference between a linked list and an array?

Show answer

An array stores elements contiguously, giving O(1) index access and good cache performance, but inserting or deleting in the middle costs O(n) because elements shift. A linked list stores nodes with pointers to the next node, so insertion and deletion at a known node are O(1), but finding the i-th element takes O(n) and each node has pointer overhead. Arrays suit read-heavy work, lists suit frequent splicing.

How does merge sort work and what are its properties?

Sorting, Searching and BacktrackingMedium

Show answer

Merge sort splits the array into halves, recursively sorts each half and merges the two sorted halves in linear time. The recurrence T(n) = 2T(n/2) + n gives O(n log n) in every case. It is stable and works well for linked lists and external sorting of large files, but needs O(n) extra space for arrays. It also adapts to counting inversions during the merge step.

How do you use a priority queue in Java and Python?

Heaps, Priority Queues and GreedyEasy

Show answer

Java's PriorityQueue is a min-heap by default; pass Comparator.reverseOrder() or a lambda for a max-heap or custom ordering, and use offer, poll and peek. Python's heapq module works on a plain list as a min-heap with heappush, heappop and heapify. For a max-heap in Python, push negated values. To order by priority with ties, push tuples such as (priority, counter, item).

Explain the recurrence for the 0/1 knapsack problem.

Dynamic ProgrammingMedium

Show answer

Let dp[i][w] be the maximum value using the first i items with capacity w. For item i with weight wt and value val, either skip it, giving dp[i-1][w], or take it if wt is at most w, giving dp[i-1][w - wt] plus val; take the larger. Base cases are zero items or zero capacity. Time and space are O(n times W), and space can drop to O(W) by iterating w downwards in a single array.

List common complexity classes from fastest to slowest with examples.

Show answer

O(1): array index access or a hash lookup on average. O(log n): binary search. O(n): linear scan. O(n log n): merge sort and heap sort. O(n squared): nested loops over pairs, as in bubble sort. O(2 to the power n): generating all subsets. O(n factorial): generating all permutations. For n around one lakh, anything up to O(n log n) is comfortable, while O(n squared) usually times out.

What is a bipartite graph and how do you check for one?

Graphs and Graph AlgorithmsMedium

Show answer

A graph is bipartite if its vertices can be split into two groups so every edge connects vertices from different groups, which is equivalent to having no odd-length cycle. To check, colour vertices with BFS or DFS: give the start vertex colour 0, its neighbours colour 1 and so on; if any edge connects two vertices of the same colour, it is not bipartite. Run it on each component, O(V plus E).

Explain best, average and worst case complexity using quicksort.

Complexity Analysis and RecursionMedium

Show answer

Best case is the minimum work over inputs of size n, worst case the maximum and average case the expected work over typical inputs. Quicksort averages O(n log n) because random pivots split arrays reasonably evenly. Its worst case is O(n squared) when the pivot is always the smallest or largest element, such as sorted input with a first-element pivot. Random pivots or median-of-three make the worst case very unlikely.

What are the ways to represent a graph and when would you use each?

Graphs and Graph AlgorithmsEasy

Show answer

An adjacency list stores, for each vertex, a list of neighbours, using O(V plus E) memory; it is best for sparse graphs such as road or social networks and makes iterating neighbours fast. An adjacency matrix uses a V by V grid, O(V squared) memory, with O(1) edge checks; it suits dense or small graphs and Floyd-Warshall. An edge list is a simple list of pairs, convenient for Kruskal's algorithm.

What are inorder, preorder, postorder and level order traversals?

Show answer

Inorder visits left subtree, node, then right subtree, and gives sorted order for a BST. Preorder visits node, left, then right, which is useful for copying or serialising a tree. Postorder visits left, right, then node, used for deleting trees or computing subtree results. Level order visits nodes level by level using a queue. All take O(n) time; recursive versions use O(h) stack space.

Why does greedy work for fractional knapsack but fail for 0/1 knapsack?

Heaps, Priority Queues and GreedyMedium

Show answer

In fractional knapsack you may take part of an item, so taking items in decreasing value per weight and filling the remainder with a fraction is optimal. In 0/1 knapsack items are all or nothing; the best ratio item may leave wasted capacity that a combination of other items would fill better. Example: capacity 50 with items of weight 10, 20 and 30 shows greedy by ratio losing. 0/1 knapsack needs DP in O(n times W).

How can you reduce the space used by a DP solution?

Dynamic ProgrammingMedium

Show answer

If each row of the table depends only on the previous row, keep two rows or even a single array, reducing O(n times m) space to O(m). Fibonacci-like problems need only the last two values, so O(1). For 0/1 knapsack in one array, iterate capacity from high to low so each item is used once; for unbounded knapsack iterate low to high. The trade-off is that reconstructing the actual solution becomes harder.

What is a stack and where is it used?

Show answer

A stack is a last-in, first-out structure with push, pop and peek, each O(1). It can be built on an array or a linked list. Uses include function call management, undo features, expression evaluation and conversion between infix and postfix, bracket matching, browser history and iterative DFS. In Java use ArrayDeque rather than the legacy Stack class; in Python a list with append and pop works well.

What are lower bound and upper bound, and what common bugs appear in binary search?

Sorting, Searching and BacktrackingMedium

Show answer

Lower bound returns the first index whose value is not less than the target, and upper bound the first index whose value is greater, so their difference counts occurrences. Common bugs are off-by-one errors in the loop condition, infinite loops when mid does not move, and integer overflow from (low plus high) divided by 2 in Java or C++; use low plus (high minus low) divided by 2. Python's bisect module provides both functions.

What is the two pointer technique and when is it used?

Show answer

Two pointers move through an array or string, often from both ends or at different speeds, to avoid nested loops. On a sorted array you can find a pair with a given sum in O(n) by moving left or right depending on the current sum. It is also used for reversing, removing duplicates in place, merging sorted arrays, palindrome checks and partitioning. It usually needs sorted data or a monotonic condition.

What is the diameter of a binary tree and how do you compute it efficiently?

Show answer

The diameter is the number of edges on the longest path between any two nodes, which may not pass through the root. Compute it in one postorder traversal: for each node, get the heights of the left and right subtrees, update a global best with left plus right, and return 1 plus the larger height to the parent. This visits each node once, giving O(n) time instead of O(n squared) from recomputing heights.

What is a trie and where is it used?

Show answer

A trie, or prefix tree, stores strings character by character, with each edge representing a character and a flag marking word ends. Insert and search take O(L) for a word of length L regardless of how many words are stored, and all words sharing a prefix sit under one node. Tries power autocomplete, spell checkers, IP routing with longest prefix match and word search games. Memory use can be high, so compressed tries exist.

How do you recognise a DP problem and define its state?

Dynamic ProgrammingMedium

Show answer

Signals include asking for a minimum, maximum, count of ways or whether something is possible, with choices at each step that affect later options. Start from brute-force recursion and ask what parameters fully describe a subproblem, such as index, remaining capacity or last chosen item; those become the state. Then write the transition between states, the base cases and the order of computation, and check the state count times transition cost fits limits.

What is Kadane's algorithm?

Arrays, Strings and HashingMedium

Show answer

Kadane's algorithm finds the maximum sum contiguous subarray in O(n) time and O(1) space. At each element it decides whether to extend the current subarray or start fresh: current = max(x, current + x), and best = max(best, current). The insight is that a negative running sum never helps a future subarray. For an all-negative array it correctly returns the largest single element when initialised with the first value.

What is the difference between a subarray, a subsequence and a substring?

Show answer

A subarray is a contiguous part of an array, and an array of n elements has n times n plus 1 over 2 of them. A substring is the same idea for strings. A subsequence keeps the original order but may skip elements, so there are 2 to the power n of them. This matters for choosing techniques: sliding window and prefix sums suit subarrays, while subsequence problems often need dynamic programming.

What is a greedy algorithm and when does it give the optimal answer?

Heaps, Priority Queues and GreedyMedium

Show answer

A greedy algorithm builds a solution step by step, always taking the choice that looks best right now and never revisiting it. It is optimal only when the problem has the greedy choice property, meaning a locally best choice is part of some optimal solution, and optimal substructure. Examples where greedy works are activity selection, Huffman coding, Dijkstra and Kruskal. For many problems, such as 0/1 knapsack, it fails.

Explain directed, undirected, weighted graphs and DAGs.

Graphs and Graph AlgorithmsEasy

Show answer

In an undirected graph edges work both ways, like friendships. In a directed graph edges have direction, like follows or web links. A weighted graph attaches a cost to each edge, like distance or price, which matters for shortest path algorithms. A DAG is a directed acyclic graph with no cycles; it models dependencies such as course prerequisites or build steps and allows topological ordering and linear-time shortest paths.

Explain basic binary tree terminology: root, leaf, height and depth.

Show answer

The root is the top node with no parent. A leaf has no children. The depth of a node is the number of edges from the root to it, and the height of a node is the number of edges on the longest path down to a leaf; the tree's height is the root's height. In a binary tree each node has at most two children. A tree with n nodes has n minus 1 edges.

How does binary search work and what does it require?

Sorting, Searching and BacktrackingEasy

Show answer

Binary search works on sorted data or any monotonic condition. Compare the middle element with the target; if equal, return it, if the target is smaller search the left half, otherwise the right half. Each step halves the search space, giving O(log n) time, so a million elements need about 20 comparisons. It requires random access, so it suits arrays but not linked lists.

How do you find the lowest common ancestor in a BST versus in a general binary tree?

Show answer

In a BST, start at the root: if both values are smaller go left, if both are larger go right, otherwise the current node is the LCA, taking O(h). In a general binary tree, recurse: if the node is null or matches either target, return it; otherwise search both subtrees. If both sides return non-null, the current node is the LCA; else return the non-null side. That takes O(n).

Compare singly, doubly and circular linked lists.