Data Structures and Algorithms Technical Round Questions &amp; Answers

Show answer

Union-Find, or disjoint set union, tracks which elements belong to the same group with find, returning a representative, and union, merging two groups. Path compression makes every node on a find path point directly to the root, and union by rank or size attaches the smaller tree under the larger. Together they give nearly constant amortised time, the inverse Ackermann function. It is used in Kruskal and dynamic connectivity.

Implement topological sort using Kahn's algorithm.

Show answer

from collections import deque def topo_sort(n, edges): adj = [[] for _ in range(n)] indeg = [0] * n for u, v in edges: # u must come before v adj[u].append(v) indeg[v] += 1 q = deque(i for i in range(n) if indeg[i] == 0) order = [] while q: u = q.popleft() order.append(u) for v in adj[u]: indeg[v] -= 1 if indeg[v] == 0: q.append(v) return order if len(order) == n else [] # empty means a cycle exists

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.

You must build autocomplete for a search box over one million product names. Which data structure would you use?

Show answer

I would use a trie where each node stores, besides children, the top few most popular completions under that prefix. Then typing a prefix walks L nodes and returns precomputed suggestions instantly, without exploring the whole subtree. Memory can be reduced with a compressed radix trie. For typo tolerance or ranking by many signals, a search engine with prefix indexes is more practical at large scale.

Merge K sorted linked lists using a min-heap.

Heaps, Priority Queues and GreedyMedium

Show answer

import heapq def merge_k_lists(lists): heap = [] for i, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, i, node)) # i breaks ties dummy = tail = ListNode() while heap: val, i, node = heapq.heappop(heap) tail.next = node tail = node if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next # O(N log K) for N total nodes

A hash map lookup in your service suddenly becomes very slow under certain traffic. What could cause it?

Arrays, Strings and HashingHard

Show answer

If many keys produce the same hash, they pile into a few buckets and operations degrade toward O(n). This can come from a poor custom hashCode, such as returning a constant or using only one field, or from attackers sending crafted keys. Fixes include a better hash function combining all fields, randomised hashing, which Python uses for strings, and tree-based buckets as in Java 8 HashMap, which caps the worst case at O(log n).

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 amortised analysis? Explain it with dynamic array append.

Show answer

Amortised analysis averages the cost of an operation over a long sequence, even if a few individual operations are expensive. A dynamic array such as Java ArrayList or Python list doubles its capacity when full, which costs O(n) for that append. But doubling happens rarely, and the total copying over n appends is under 2n, so each append costs O(1) amortised. Hash table resizing works the same way.

What are the trade-offs between recursion and iteration?

Show answer

Recursion expresses tree traversal, divide and conquer and backtracking naturally and with less code. However each call uses stack memory and has call overhead, and deep recursion can overflow the stack, about 1000 frames by default in Python. Iteration with an explicit stack or loop uses heap memory and is usually faster. Many interviewers accept recursive solutions but may ask for an iterative version for very deep inputs.

Packages with given weights must be shipped in order within D days. How do you find the minimum ship capacity?

Sorting, Searching and BacktrackingMedium

Show answer

The capacity lies between the heaviest package and the total weight, and if a capacity works, any larger one also works, so binary search the answer. For a candidate capacity, greedily load packages day by day, starting a new day when the next package does not fit, and count days. If the days are within D, try smaller; otherwise try larger. Time is O(n log of total weight).

What is tail recursion and do Java and Python optimise it?

Show answer

A call is tail recursive when the recursive call is the very last action, so nothing remains to be done after it returns, as in a factorial that carries an accumulator. Some languages reuse the same stack frame for such calls, turning recursion into a loop. Neither Java nor CPython performs tail call optimisation, so deep tail recursion still overflows; convert it to a loop manually.

Write a function to validate a binary search tree.

Show answer

def is_valid_bst(root, low=float('-inf'), high=float('inf')): if not root: return True if not (low < root.val < high): return False return (is_valid_bst(root.left, low, root.val) and is_valid_bst(root.right, root.val, high)) # Passing bounds checks the whole-subtree property, not just children. # O(n) time, O(h) space.

Your recursive solution passes with memoisation, but the interviewer asks for a bottom-up version. How do you convert it?

Show answer

I identify the recursion parameters, which become the table dimensions, and the base cases, which become the initial cells. Then I look at which states each call depends on, for example index plus 1, and fill the table in the opposite order, so dependencies are computed first. The recursive transition becomes the loop body. Finally I check whether only the last row is used, so I can reduce space, and walk through a small example.

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

Linked Lists, Stacks and QueuesMedium

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.

Print the level order traversal of a binary tree, one list per level.

Show answer

from collections import deque def level_order(root): if not root: return [] out, q = [], deque([root]) while q: level = [] for _ in range(len(q)): # process exactly one level node = q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) out.append(level) return out

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

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.

An interviewer asks you to reduce your solution's extra space from O(n) to O(1). How do you approach it?

Show answer

I check what the extra structure stores and whether the input itself can hold that information. Common techniques: use two pointers instead of a hash set on sorted data, keep only the last few DP values instead of a full table, modify the input in place, such as marking visited indices by negating values, or use bit manipulation like XOR to find a missing number. I state any trade-offs, such as mutating input.

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

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).

Compute the edit distance between two words.

Dynamic ProgrammingHard

Show answer

def edit_distance(a, b): m, n = len(a), len(b) prev = list(range(n + 1)) # distances from empty prefix of a for i in range(1, m + 1): cur = [i] + [0] * n for j in range(1, n + 1): if a[i - 1] == b[j - 1]: cur[j] = prev[j - 1] else: cur[j] = 1 + min(prev[j], # delete cur[j - 1], # insert prev[j - 1]) # replace prev = cur return prev[n] # edit_distance('horse', 'ros') -> 3; O(m * n) time, O(n) space

What does binary search on the answer mean?

Sorting, Searching and BacktrackingHard

Show answer

Instead of searching an array, you binary search over possible answers when there is a monotonic feasibility check: if capacity X works, any larger capacity also works. Examples include minimum ship capacity to deliver within D days, minimum eating speed, or the largest minimum distance between placed items. Each check is often O(n) greedy, so total time is O(n log of the answer range), which is very efficient.

Implement 0/1 knapsack using a one-dimensional DP array.

Show answer

def knapsack(weights, values, capacity): dp = [0] * (capacity + 1) # dp[w] = best value with capacity w for wt, val in zip(weights, values): for w in range(capacity, wt - 1, -1): # go downwards: each item once dp[w] = max(dp[w], dp[w - wt] + val) return dp[capacity] # knapsack([1, 3, 4], [15, 20, 30], 4) -> 35 # O(n * W) time, O(W) space

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

Arrays, Strings and HashingEasy

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 quickselect and when is it better than sorting?

Sorting, Searching and BacktrackingHard

Show answer

Quickselect finds the kth smallest element by partitioning like quicksort but recursing only into the side that contains position k. On average it does about n plus n over 2 plus n over 4 work, which is O(n), compared with O(n log n) for sorting. The worst case is O(n squared), reduced by random pivots or median of medians for guaranteed O(n). C++ nth_element uses this idea.

Design a simple scheduler that gives each job a fixed time slice in turn.

Linked Lists, Stacks and QueuesMedium

Show answer

Round-robin scheduling fits a queue. Put all jobs in a FIFO queue. Repeatedly dequeue a job, run it for one time slice, and if it is not finished, enqueue it at the back with its remaining time. Each step is O(1). For priorities, keep one queue per priority level or use a priority queue. A circular buffer works well if the number of jobs is bounded, avoiding allocations.

What is edit distance and where is it used?

Show answer

Edit distance, or Levenshtein distance, is the minimum number of insertions, deletions and substitutions to turn one string into another. dp[i][j] is the distance between the first i characters of A and the first j of B; if characters match, take dp[i-1][j-1], otherwise 1 plus the minimum of the three neighbouring cells. It runs in O(m times n) and is used in spell checkers, fuzzy search, DNA alignment and plagiarism detection.

How does Dijkstra's algorithm work and why does it fail with negative edge weights?

Show answer

Dijkstra keeps a min-heap of tentative distances. It repeatedly pops the closest unvisited vertex, marks its distance final and relaxes its outgoing edges, giving O((V plus E) log V). It relies on the fact that once a vertex is popped, no shorter path can appear later. A negative edge breaks that assumption because a longer path could later become cheaper. For negative weights use Bellman-Ford.

Check whether a string is a palindrome, ignoring case and non-alphanumeric characters.

Arrays, Strings and HashingEasy

Show answer

// Java static boolean isPalindrome(String s) { int i = 0, j = s.length() - 1; while (i < j) { char a = s.charAt(i), b = s.charAt(j); if (!Character.isLetterOrDigit(a)) { i++; continue; } if (!Character.isLetterOrDigit(b)) { j--; continue; } if (Character.toLowerCase(a) != Character.toLowerCase(b)) return false; i++; j--; } return true; } // Two pointers, O(n) time, O(1) space.

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.

A teammate's BST validation only checks that each node is greater than its left child and smaller than its right child. Why is that wrong?

Show answer

The BST property applies to entire subtrees, not just direct children. A node deep in the left subtree could be larger than the root and still pass the local check. The correct approach passes a valid range down the recursion: the left child must lie between the lower bound and the node value, the right child between the node value and the upper bound. Alternatively, check that an inorder traversal is strictly increasing.

You can use an O(n log n) algorithm with high constant factors or a simple O(n squared) one. For what inputs might the O(n squared) choice be better?

Complexity Analysis and RecursionHard

Show answer

Big-O ignores constants, so for small n the simpler algorithm can be faster in practice. Insertion sort beats merge sort for arrays below roughly 16 to 32 elements, which is why library sorts such as Timsort switch to insertion sort for small runs. I would benchmark on realistic input sizes, choose the asymptotically better algorithm when n can grow, and use a hybrid when both ranges occur.

A monitoring service must report the median response time over a live stream of requests. How would you design it?

Heaps, Priority Queues and GreedyHard

Show answer

For an exact all-time median, use two heaps, giving O(log n) per insert and O(1) per query. For the median of only the last N minutes, you need deletions, so use two heaps with lazy deletion or a balanced order-statistic tree. At very high volume, exact medians are costly, so production systems use histograms or sketches such as t-digest or HDR histogram to give accurate percentiles with fixed memory.

Compare Kruskal's and Prim's algorithms for minimum spanning trees.

Show answer

Both find a minimum spanning tree, the cheapest set of edges connecting all vertices. Kruskal sorts all edges by weight and adds each edge if it joins two different components, checked with Union-Find, O(E log E); it suits sparse graphs given as edge lists. Prim grows the tree from a start vertex, always adding the cheapest edge leaving the tree using a min-heap, O(E log V), which suits dense graphs with adjacency lists.

How is the longest common subsequence computed with DP?

Show answer

Let dp[i][j] be the LCS length of the first i characters of A and the first j characters of B. If A[i-1] equals B[j-1], dp[i][j] is dp[i-1][j-1] plus 1; otherwise it is the maximum of dp[i-1][j] and dp[i][j-1]. Fill the table row by row in O(m times n) time. Backtracking from dp[m][n] recovers the actual subsequence. LCS underlies diff tools and DNA sequence comparison.

How does a hash table work, and how are collisions handled?

Arrays, Strings and HashingMedium

Show answer

A hash table computes a hash of the key and maps it to a bucket index, giving average O(1) insert, lookup and delete. A collision happens when two keys map to the same bucket. Separate chaining stores a list or tree in each bucket, which Java HashMap uses and converts to a tree after 8 entries. Open addressing probes other slots, which Python dict uses. Tables resize when the load factor grows too high.

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.

Given meeting start and end times for a day, how do you find the minimum number of rooms needed?

Heaps, Priority Queues and GreedyMedium

Show answer

Sort meetings by start time and keep a min-heap of end times for rooms in use. For each meeting, if the earliest ending room is free by its start time, pop it; then push this meeting's end time. The heap size at the end, or its maximum, is the answer. This is O(n log n). An alternative sorts start and end times separately and sweeps with two pointers, counting overlaps.

Compute the length of the longest common subsequence of two strings.