Medium Data Structures and Algorithms Interview Questions

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.

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.

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

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.

Explain best, average and worst case complexity using quicksort.

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.

A problem has n up to 100000. Which time complexities are acceptable for a 1-second limit?

Show answer

A common rule is that judges run about 10 to the power 8 simple operations per second. With n equal to 10 to the power 5, O(n log n) is about 1.7 million operations and O(n) is trivial, both fine. O(n squared) is 10 to the power 10 operations, far too slow. So I would look for sorting, hashing, two pointers, binary search or prefix sums rather than nested loops over all pairs.

A recursive DFS in Python crashes with RecursionError on a deep input. How do you fix it?

Show answer

CPython limits recursion depth to about 1000 by default. Raising the limit with sys.setrecursionlimit works for moderate depth but can crash the interpreter on very deep inputs because the C stack is limited. The reliable fix is to rewrite the DFS iteratively with an explicit stack, pushing nodes and processing them in a loop. In Java the same issue appears as StackOverflowError and has the same solution.

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.

Implement fast exponentiation to compute x to the power n in O(log n).

Show answer

def power(x, n): if n < 0: x, n = 1 / x, -n result = 1 while n > 0: if n & 1: # odd bit set: multiply current base in result *= x x *= x # square the base n >>= 1 # move to next bit return result # power(2, 10) == 1024; use % mod after each multiply for modular power

Generate all subsets of a list of distinct numbers.

Show answer

def subsets(nums): result = [] current = [] def backtrack(i): if i == len(nums): result.append(current[:]) return current.append(nums[i]) # include nums[i] backtrack(i + 1) current.pop() # exclude nums[i] backtrack(i + 1) backtrack(0) return result # 2^n subsets, each up to n long: O(n * 2^n) time

What is the time complexity of an outer loop from 0 to n with an inner loop where j starts at 1 and doubles until it reaches n?

Show answer

The outer loop runs n times. In the inner loop j takes values 1, 2, 4, 8 and so on until it reaches n, which is about log base 2 of n iterations. Because the inner loop does not depend on the outer index, the total is n times log n, so the complexity is O(n log n). If instead the inner loop ran from 0 to i, the total would be n squared over 2, which is O(n squared).

How did you prepare for data structures and algorithms rounds?

Show answer

Situation: I was weak at DSA in my third year. Task: become placement-ready in five months. Action: I followed a topic-wise plan, solved around 300 problems by pattern such as sliding window, BFS and DP, kept a notebook of mistakes, revised weekly and took timed contests every weekend. I also practised explaining solutions aloud. Result: my speed improved steadily and I cleared coding rounds at two product companies.

Explain the sliding window technique with fixed and variable windows.

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

What are prefix sums and what problems do they solve?

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.

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

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 Kadane's algorithm?

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 load factor of a hash table and why does it matter?

Show answer

Load factor is the number of stored entries divided by the number of buckets. As it rises, collisions increase and operations slow down. Java HashMap resizes when the load factor passes 0.75, doubling buckets and rehashing every entry, which costs O(n) occasionally but keeps operations O(1) amortised. If you know the final size, set the initial capacity to avoid repeated resizing in performance-sensitive code.

What is the Dutch National Flag algorithm?

Show answer

It sorts an array of three distinct values, such as 0, 1 and 2, in one pass with O(1) space. It keeps three pointers: low, mid and high. If arr[mid] is 0, swap it with arr[low] and advance both; if 1, advance mid; if 2, swap it with arr[high] and decrease high without advancing mid. It runs in O(n) and is the basis of three-way partitioning in quicksort.

An array of size 100000 must answer 100000 queries asking for the sum between two indices. What approach would you use?

Show answer

Recomputing each sum is O(n) per query, about 10 to the power 10 operations in total, which is too slow. Since the array does not change, I would build a prefix sum array once in O(n) and answer each query in O(1) as pre[r+1] minus pre[l], giving O(n plus q) overall. If the array also receives updates, I would switch to a Fenwick tree or segment tree for O(log n) updates and queries.

Your brute-force solution for the longest substring without repeating characters is O(n cubed). How would you improve it?

Show answer

I would use a variable sliding window. Keep a map from character to its last index and a left pointer. Move the right pointer through the string; when the current character was seen at an index at or after left, move left to that index plus one. Update the best length at each step. Each character is processed a constant number of times, giving O(n) time and O(alphabet size) space.

You must merge two sorted arrays where the first array has enough empty space at the end for the second. How would you do it in place?

Show answer

Merging from the front would overwrite unread elements, so merge from the back. Use three pointers: the last real element of the first array, the last element of the second, and the last slot of the first array. Repeatedly place the larger of the two candidates at the write position and move pointers left. When the second array is exhausted, the rest is already in place. This takes O(m plus n) time and O(1) space.

Find the length of the longest substring without repeating characters.

Show answer

def length_of_longest_substring(s): last = {} # char -> last index seen left = best = 0 for right, ch in enumerate(s): if ch in last and last[ch] >= left: left = last[ch] + 1 last[ch] = right best = max(best, right - left + 1) return best # 'abcabcbb' -> 3, 'bbbbb' -> 1, 'pwwkew' -> 3; O(n) time

Rotate an array to the right by k steps in place.

Show answer

def rotate(nums, k): n = len(nums) k %= n def reverse(l, r): while l < r: nums[l], nums[r] = nums[r], nums[l] l += 1 r -= 1 reverse(0, n - 1) # reverse all reverse(0, k - 1) # reverse first k reverse(k, n - 1) # reverse the rest # [1,2,3,4,5,6,7], k=3 -> [5,6,7,1,2,3,4]; O(n) time, O(1) space

Tell me about a time you used the right data structure to solve a real problem in a project or job.

Show answer

Situation: in my internship, a duplicate-detection script for customer records took hours because it compared every pair. Task: make it run within the nightly window. Action: I normalised names and phone numbers into a key and grouped records in a hash map, comparing only records within the same group. Result: runtime dropped from four hours to six minutes, and my mentor asked me to present the approach to the team.

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

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

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.

You are building undo and redo for a text editor. Which data structures would you use?

Show answer

I would use two stacks. Every user action is pushed onto the undo stack as a command object that knows how to reverse itself. Undo pops from the undo stack, reverts the action and pushes it onto the redo stack. Redo pops from the redo stack and re-applies it. Any new action clears the redo stack. For memory limits, cap the undo stack size, for example using a deque that drops the oldest entries.

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

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.

A trading application needs a stack that also returns the current minimum in O(1). How would you design it?

Show answer

Keep a second stack of minimums. On push, push the value onto the main stack and push the smaller of the value and the current minimum onto the min stack. On pop, pop both. getMin returns the top of the min stack in O(1). To save space, push onto the min stack only when the new value is less than or equal to the current minimum, and pop it only when the popped value equals it.

Detect whether a linked list has a cycle and return the node where the cycle begins.

Show answer

def detect_cycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: # cycle found slow = head while slow is not fast: # move both one step slow = slow.next fast = fast.next return slow # start of the cycle return None # O(n) time, O(1) space

Find the next greater element for every element of an array.

Show answer

def next_greater(nums): res = [-1] * len(nums) stack = [] # indices with decreasing values for i, x in enumerate(nums): while stack and nums[stack[-1]] < x: res[stack.pop()] = x stack.append(i) return res # [4, 5, 2, 25] -> [5, 25, 25, -1] # Each index is pushed and popped once: O(n)

Tell me about a time you explained a technical idea to a non-technical person.

Show answer

Situation: a product manager asked why a search feature became slow as data grew. Task: explain the cause and the fix without jargon. Action: I compared the current approach to checking every book in a library one by one and the fix to using the catalogue index, then showed a simple chart of response times before and after a prototype. Result: the manager approved two sprints for the change and later reused my analogy with clients.

Describe a team project where one member was not contributing. What did you do?

Show answer

Situation: in my final-year project a teammate missed several deadlines. Task: complete the project without conflict. Action: I spoke to him privately and learned he struggled with the graph algorithms part. We swapped tasks so he took the UI, and I paired with him for an hour on the core logic. I also set up a weekly checklist for everyone. Result: we submitted on time and he presented the UI section confidently.

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

How do DFS and BFS differ in memory use on a tree?

Show answer

DFS uses a stack, either the call stack or an explicit one, holding at most the height of the tree, so O(h) memory: about log n for balanced trees but n for skewed ones. BFS uses a queue holding an entire level, up to about n over 2 nodes in the last level of a complete tree. So DFS is lighter for wide balanced trees, while BFS is natural for shortest paths and level-wise processing.

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.

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.

An application needs sorted data with frequent inserts, deletes and range queries such as all orders between two timestamps. Which structure fits?

Show answer

A balanced BST, such as Java TreeMap or a sorted container in Python, gives O(log n) insert and delete and O(log n plus k) range queries using floor, ceiling or subMap operations. A sorted array has fast range queries but O(n) inserts, and a hash map cannot do ranges at all. If the data lives in a database, a B-tree index on the timestamp column solves the same problem.

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.

In a company org chart stored as a tree, how would you find the closest common manager of two employees?

Show answer

This is the lowest common ancestor problem. If each employee stores a parent pointer, collect the ancestors of the first employee in a set and walk up from the second until a match is found, O(h). Without parent pointers, use the recursive LCA on the tree from the CEO, O(n). For many repeated queries on a large chart, preprocess with binary lifting to answer each query in O(log n).

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

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.

Find the lowest common ancestor of two nodes in a binary tree.

Show answer

def lca(root, p, q): if root is None or root is p or root is q: return root left = lca(root.left, p, q) right = lca(root.right, p, q) if left and right: # p and q are on different sides return root return left or right # O(n) time, O(h) space; assumes both nodes exist in the tree

Tell me about an interview or exam you failed and what you learned.

Show answer

Situation: I was rejected after a coding round because I could not solve a tree problem in time. Task: understand the gap honestly. Action: I wrote down the question, realised I memorised solutions instead of patterns, and reorganised my practice by patterns such as postorder aggregation and BFS by level, explaining each solution aloud. Result: three months later I cleared a similar round comfortably, and I now review every mistake within a day.

What are the complexities of heap operations, and why does building a heap take O(n)?

Show answer

Peek at the root is O(1). Insert adds at the end and sifts up, and extract removes the root, moves the last element to the top and sifts down, both O(log n). Building a heap from n elements by sifting down from the last internal node to the root takes O(n), not O(n log n), because most nodes are near the bottom and move only a few levels; the sum of heights is linear.

How does heap sort work and how does it compare with quicksort and merge sort?

Show answer

Heap sort builds a max-heap in O(n), then repeatedly swaps the root with the last element, shrinks the heap and sifts down, giving O(n log n) in all cases with O(1) extra space. It is not stable and has poor cache locality, so in practice it is slower than quicksort. Merge sort is stable but needs O(n) space. Introsort switches from quicksort to heap sort to guarantee O(n log n).

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

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.

How do you decide between a greedy approach and dynamic programming?

Show answer

Try to find a simple counterexample to the greedy rule on small inputs; if one exists, greedy is wrong and you likely need DP, which explores all choices of overlapping subproblems. If you can argue with an exchange argument that the greedy choice is always safe, greedy is simpler and faster. Coin change with arbitrary coins needs DP, while interval scheduling by earliest end time is safely greedy.

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

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.

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

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 two heaps maintain the running median of a stream?

Show answer

Keep a max-heap for the smaller half of the numbers and a min-heap for the larger half, balanced so their sizes differ by at most one. Insert each number into the correct heap, then move the top element across if sizes become unbalanced. The median is the top of the larger heap, or the average of both tops when sizes are equal. Insertion is O(log n) and finding the median is O(1).

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

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.

A hospital emergency system must treat patients by severity, and patients with equal severity in arrival order. How would you implement it?

Show answer

Use a priority queue ordered by severity, with a tie-breaker on an increasing arrival counter, so equal-severity patients come out first-in, first-out. In Python push tuples such as (minus severity, counter, patient); in Java use a comparator on severity then sequence number. Insert and extract are O(log n). If severity can change while waiting, use lazy deletion with a version number or an indexed priority queue.

Merge K sorted linked lists using a min-heap.

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

Find the minimum number of railway platforms needed given arrival and departure times.

Show answer

// Java static int minPlatforms(int[] arr, int[] dep) { Arrays.sort(arr); Arrays.sort(dep); int i = 0, j = 0, cur = 0, best = 0; while (i < arr.length) { if (arr[i] <= dep[j]) { // a train arrives before the next departs cur++; i++; best = Math.max(best, cur); } else { cur--; j++; } } return best; } // O(n log n) for sorting, O(1) extra space.

Solve jump game: can you reach the last index if nums[i] is the maximum jump from i?

Show answer

def can_jump(nums): farthest = 0 for i, step in enumerate(nums): if i > farthest: # this index is unreachable return False farthest = max(farthest, i + step) if farthest >= len(nums) - 1: return True return True # [2,3,1,1,4] -> True, [3,2,1,0,4] -> False # Greedy: track the farthest reachable index, O(n) time, O(1) space

How do you prioritise when several tasks have deadlines at the same time?

Show answer

Situation: in one sprint I had a bug fix, a feature and interview preparation for a new hire panel all due together. Task: deliver without dropping quality. Action: I listed the tasks with impact and deadline, discussed the order with my lead, finished the customer-facing bug first, split the feature into smaller deliverables and blocked calendar time for each. Result: everything was delivered within the week and nothing urgent slipped.

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.

What is topological sorting and how is it done?

Show answer

A topological order lists the vertices of a DAG so every edge goes from earlier to later, such as an order to take courses. Kahn's algorithm computes in-degrees, pushes zero in-degree vertices into a queue and repeatedly removes them while decreasing neighbours' in-degrees; if not all vertices are output, a cycle exists. The DFS method adds a vertex to a list after visiting its descendants and reverses the list. Both are O(V plus E).

What is the Union-Find data structure and what optimisations make it fast?

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.

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.

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

A learning platform has courses with prerequisites. How do you find a valid order, and what if none exists?

Show answer

Model courses as vertices with an edge from each prerequisite to the course that needs it, then run topological sort with Kahn's algorithm. Courses with no pending prerequisites enter a queue first, and taking one reduces the in-degree of dependent courses. If the output has fewer courses than the total, there is a cycle, so no valid order exists, and I would report the courses involved so the content team can fix them.

How would you generate friend suggestions as friends of friends in a social network?

Show answer

Run a BFS limited to depth 2 from the user. For every friend, look at their friends, skip the user and existing friends, and count how many mutual friends each candidate has using a hash map. Rank candidates by mutual friend count and other signals. For users with thousands of friends this gets expensive, so production systems precompute suggestions offline in batch jobs and cache them.

A build system hangs because some services depend on each other in a loop. How would you detect and report the cycle?

Show answer

Model services as a directed graph and run DFS with three colours. When DFS reaches a node that is still on the current stack, it has found a back edge, and walking the parent pointers from the current node back to that node gives the exact cycle to report, such as A to B to C to A. Running this check in CI before every build prevents the problem, and Kahn's algorithm can list all nodes involved.

Find the shortest path length from the top-left to the bottom-right of a grid where 1 is a wall.

Show answer

from collections import deque def shortest_path(grid): R, C = len(grid), len(grid[0]) if grid[0][0] or grid[R-1][C-1]: return -1 q = deque([(0, 0, 1)]) seen = {(0, 0)} while q: r, c, d = q.popleft() if (r, c) == (R - 1, C - 1): return d for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc = r + dr, c + dc if 0 <= nr < R and 0 <= nc < C and not grid[nr][nc] and (nr, nc) not in seen: seen.add((nr, nc)) q.append((nr, nc, d + 1)) return -1 # BFS: O(R * C)

Implement Dijkstra's algorithm with a priority queue.

Show answer

import heapq def dijkstra(graph, src): # graph: {node: [(neighbour, weight), ...]} dist = {src: 0} heap = [(0, src)] while heap: d, u = heapq.heappop(heap) if d > dist.get(u, float('inf')): continue # stale entry for v, w in graph.get(u, []): nd = d + w if nd < dist.get(v, float('inf')): dist[v] = nd heapq.heappush(heap, (nd, v)) return dist # O((V + E) log V); weights must be non-negative

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

Tell me about a time you worked with people from other teams to solve a complex problem.

Show answer

Situation: delivery route suggestions in our app were slow and the data team blamed the backend while we blamed the data. Task: find the real issue. Action: I set up a joint session, we traced one slow request end to end and found the graph was rebuilt from raw tables on every call. I proposed caching the adjacency lists, and the data team added change notifications. Result: response time dropped from 3 seconds to 200 milliseconds.

How do you handle disagreement with a reviewer about your solution in a code review?

Show answer

Situation: a reviewer wanted me to replace my BFS solution with a more complex bidirectional search. Task: reach the best decision for the code, not win the argument. Action: I asked about their concern, which was latency on large graphs, then shared measurements showing our graphs were small and the simpler code was faster to maintain, and agreed to add a benchmark that would alert us if size grew. Result: the reviewer approved and we documented the trade-off.

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.

Explain the recurrence for the 0/1 knapsack problem.

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.

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 can you reduce the space used by a DP solution?

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

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.

A search box must suggest the closest dictionary words when a user makes a typo. How would you approach it?

Show answer

Compute edit distance between the typed word and candidate words, suggesting those within distance 1 or 2. Running O(m times n) DP against a whole dictionary is slow, so narrow candidates first using a BK-tree indexed by edit distance, a trie with bounded edit distance search, or n-gram indexes. Then rank candidates by distance and word popularity. Keyboard-aware substitution costs can improve suggestions further.

You need to build a tool that shows the differences between two versions of a file line by line. What algorithm would you use?

Show answer

The core is the longest common subsequence over lines: lines in the LCS are unchanged, and the rest are additions or deletions. Hash each line first so comparisons are fast. Classic LCS DP is O(m times n), which is too slow for large files, so real diff tools use Myers' algorithm, which runs in O((m plus n) times d), where d is the number of differences, fast when versions are similar.

Find the minimum number of coins needed to make an amount.

Show answer

def coin_change(coins, amount): INF = amount + 1 dp = [0] + [INF] * amount # dp[x] = min coins for amount x for x in range(1, amount + 1): for c in coins: if c <= x and dp[x - c] + 1 < dp[x]: dp[x] = dp[x - c] + 1 return dp[amount] if dp[amount] != INF else -1 # coin_change([1, 3, 4], 6) -> 2 (3 + 3) # O(amount * len(coins)) time, O(amount) space

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

Show answer

// Java static int lcs(String a, String b) { int m = a.length(), n = b.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (a.charAt(i - 1) == b.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } return dp[m][n]; } // lcs(abcde, ace) = 3; O(m * n) time and space

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

How do you handle pressure during a timed online coding test?

Show answer

Situation: in a 90-minute test I faced three problems, one of them a tough DP. Task: maximise my score. Action: I read all problems first, solved the easiest one quickly to secure marks, wrote a brute-force version of the DP problem for partial credit, then improved it to memoised DP once I spotted the state. I kept an eye on time at fixed checkpoints. Result: I cleared all test cases on two problems and most of the third.

How does merge sort work and what are its properties?

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 does quicksort work and why does pivot choice matter?

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 are lower bound and upper bound, and what common bugs appear in binary search?

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.

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

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

A sorted array has been rotated at an unknown point. How can you still search it in O(log n)?

Show answer

At every step of binary search, at least one half around mid is sorted. Compare nums[low] with nums[mid]: if the left half is sorted and the target lies within its range, search left, otherwise search right. If the right half is sorted, apply the same check on the right. This keeps O(log n). With duplicates allowed, equal values can hide which half is sorted, and the worst case becomes O(n).

Implement merge sort.

Show answer

def merge_sort(a): if len(a) <= 1: return a mid = len(a) // 2 left = merge_sort(a[:mid]) right = merge_sort(a[mid:]) out, i, j = [], 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: # <= keeps the sort stable out.append(left[i]); i += 1 else: out.append(right[j]); j += 1 out.extend(left[i:]) out.extend(right[j:]) return out # O(n log n) time, O(n) extra space

Find the first and last position of a target in a sorted array.

Show answer

from bisect import bisect_left, bisect_right def search_range(nums, target): lo = bisect_left(nums, target) # first index >= target if lo == len(nums) or nums[lo] != target: return [-1, -1] hi = bisect_right(nums, target) - 1 # last index <= target return [lo, hi] # [5,7,7,8,8,10], 8 -> [3, 4]; two binary searches: O(log n)

Generate all permutations of a list of distinct numbers using backtracking.

Show answer

def permutations(nums): result, path = [], [] used = [False] * len(nums) def backtrack(): if len(path) == len(nums): result.append(path[:]) return for i, x in enumerate(nums): if used[i]: continue used[i] = True path.append(x) backtrack() path.pop() # undo the choice used[i] = False backtrack() return result # n! permutations: O(n * n!) time

Why are you looking for a change from your current job?