Data Structures and Algorithms Interview Questions &amp; Answers

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 the difference between Big-O, Big-Omega and Big-Theta?

Show answer

Big-O is an upper bound: the algorithm grows no faster than this. Big-Omega is a lower bound: it grows at least this fast. Big-Theta is a tight bound, when the upper and lower bounds match. Merge sort is Theta(n log n) because it always does that much work. In interviews people usually say Big-O to mean the tight worst-case bound, but you should know the formal difference.

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.

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

Write recursive Fibonacci and then optimise it with memoisation.

Show answer

from functools import lru_cache def fib_naive(n): # O(2^n) time if n < 2: return n return fib_naive(n - 1) + fib_naive(n - 2) @lru_cache(maxsize=None) def fib_memo(n): # O(n) time, O(n) space if n < 2: return n return fib_memo(n - 1) + fib_memo(n - 2) def fib_iter(n): # O(n) time, O(1) space a, b = 0, 1 for _ in range(n): a, b = b, a + b return a

Solve the Tower of Hanoi problem recursively.

Show answer

def hanoi(n, src, dst, aux, moves): if n == 0: return hanoi(n - 1, src, aux, dst, moves) # move n-1 disks out of the way moves.append((src, dst)) # move the largest disk hanoi(n - 1, aux, dst, src, moves) # move n-1 disks on top of it moves = [] hanoi(3, 'A', 'C', 'B', moves) print(len(moves)) # 7, since the count is 2^n - 1

Find the GCD of two numbers using the Euclidean algorithm.

Show answer

// Java static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); } static long lcm(long a, long b) { return a / gcd(a, b) * b; // divide first to avoid overflow } // Runs in O(log(min(a, b))) because remainders shrink quickly.

How do you approach a coding problem you have never seen before in an interview?

Show answer

Situation: in a mock interview I got an unfamiliar graph problem. Task: solve it while keeping the interviewer involved. Action: I restated the problem, asked about constraints and edge cases, worked through a small example by hand, explained a brute-force idea with its complexity, then improved it step by step and coded only after agreement. I tested with edge cases aloud. Result: I reached an optimal solution and got positive feedback on communication.

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.

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.

What is the Master Theorem and how do you apply it?

Show answer

The Master Theorem solves recurrences of the form T(n) = a T(n/b) + f(n). Compare f(n) with n to the power log base b of a. If f(n) is smaller, the answer is n to that power; if equal, multiply by log n; if larger, f(n) dominates. Merge sort has a = 2, b = 2, f(n) = n, giving O(n log n). Binary search has a = 1, b = 2, f(n) = 1, giving O(log n).

Your solution passes the sample tests but gets Time Limit Exceeded on large inputs. How do you analyse and fix it?

Show answer

First I estimate the complexity of my code against the constraints and find the dominant loop. Often a nested loop or repeated search inside a loop makes it O(n squared). I then look for a better pattern such as a hash map for lookups, sorting plus two pointers, prefix sums or memoisation of repeated subproblems. I also check hidden costs like string concatenation in loops or list.pop(0) in Python.

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?

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 report generation function loops over all users and, for each user, scans all orders. It was fine at launch but is now very slow. How do you explain and fix it?

Show answer

The loop is O(users times orders), so when both grow ten times, the work grows a hundred times. I would explain this with numbers and a quick profile. The fix is to group orders by user ID once using a hash map, making the total O(users plus orders), or to push the grouping into a database query with an index. I would add a performance test with production-scale data.

What is the difference between a static array and a dynamic array?

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

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

How would you check whether two strings are anagrams, and what changes if input can contain any Unicode characters?

Show answer

For lowercase English letters, compare character counts using an array of 26 integers in O(n) time and O(1) space; sorting both strings also works in O(n log n). With arbitrary Unicode, use a hash map of counts instead of a fixed array. I would also clarify whether case and spaces matter and whether to normalise accented characters, since visually identical text can have different code point sequences.

Solve two sum: return the indices of two numbers that add up to the target.

Show answer

def two_sum(nums, target): seen = {} # value -> index for i, x in enumerate(nums): need = target - x if need in seen: return [seen[need], i] seen[x] = i return [] # two_sum([2, 7, 11, 15], 9) -> [0, 1] # O(n) time, O(n) space; sorting + two pointers gives O(1) space but loses indices

Implement Kadane's algorithm for the maximum subarray sum.

Show answer

def max_subarray(nums): best = current = nums[0] for x in nums[1:]: current = max(x, current + x) # extend or start fresh best = max(best, current) return best # max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) -> 6 (subarray 4, -1, 2, 1)

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

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.

Describe a time you got stuck during a coding interview or contest. How did you recover?

Show answer

Situation: in an online round I could not find an efficient approach for a subarray problem. Task: still score well under time pressure. Action: I first submitted a correct brute-force solution for partial marks, then wrote out small examples and noticed the prefix sums pattern, which led to an O(n) solution with a hash map. Result: I solved it with ten minutes left and learned to secure a working solution before optimising.

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 do the KMP and Rabin-Karp string matching algorithms work?

Show answer

Naive matching is O(n times m). KMP precomputes a longest prefix-suffix array for the pattern, so after a mismatch it shifts the pattern without re-reading text characters, giving O(n plus m) worst case. Rabin-Karp computes a rolling hash of each text window and compares characters only when hashes match, averaging O(n plus m) and extending well to multiple patterns, but collisions can make the worst case O(n times m).

You have a 100 GB file of integers and only 4 GB of RAM. How would you find the duplicates?

Show answer

The data does not fit in memory, so I would partition it. Read the file in streaming fashion and write each number to one of, say, 50 bucket files based on hash of the number modulo 50, so equal numbers land in the same bucket. Each bucket of about 2 GB fits in memory, where a hash set finds duplicates. Alternatively use external merge sort and scan adjacent values. A Bloom filter can pre-screen candidates.

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

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

Return an array where each element is the product of all other elements, without using division.

Show answer

def product_except_self(nums): n = len(nums) out = [1] * n prefix = 1 for i in range(n): # product of everything to the left out[i] = prefix prefix *= nums[i] suffix = 1 for i in range(n - 1, -1, -1): # multiply by everything to the right out[i] *= suffix suffix *= nums[i] return out # [1,2,3,4] -> [24,12,8,6]; O(n) time, O(1) extra space besides output

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.

Compare singly, doubly and circular linked lists.

Show answer

A singly linked list node points only to the next node, using less memory but allowing traversal in one direction. A doubly linked list node also points to the previous node, enabling backward traversal and O(1) deletion of a given node, which LRU caches need. A circular list connects the last node back to the first, useful for round-robin scheduling and buffers. Each extra pointer adds memory and update complexity.

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

How would you implement browser back and forward navigation?

Show answer

Use two stacks plus the current page. Visiting a new page pushes the current page onto the back stack, sets the new page as current and clears the forward stack. Back pushes current onto the forward stack and pops the back stack into current. Forward does the reverse. Each operation is O(1). A doubly linked list with a cursor is an alternative that makes it easy to show the full history.

Users enter formulas with brackets in a spreadsheet tool. How do you validate that the brackets are balanced?

Show answer

Scan the formula once with a stack. Push every opening bracket; on a closing bracket, check that the stack is not empty and its top is the matching opening type, then pop. Ignore other characters. At the end the stack must be empty. This is O(n) time and handles nested mixes such as parentheses inside square brackets. To show useful errors, record the position of the first mismatch or unclosed bracket.

Merge two sorted linked lists into one sorted list.

Show answer

class ListNode: def __init__(self, val=0, nxt=None): self.val = val self.next = nxt def merge(a, b): dummy = tail = ListNode() while a and b: if a.val <= b.val: tail.next, a = a, a.next else: tail.next, b = b, b.next tail = tail.next tail.next = a or b return dummy.next # O(m + n) time, O(1) extra space

Check whether a string of brackets is valid.

Show answer

// Java static boolean isValid(String s) { Deque<Character> st = new ArrayDeque<>(); for (char c : s.toCharArray()) { if (c == '(') st.push(')'); else if (c == '[') st.push(']'); else if (c == '{') st.push('}'); else if (st.isEmpty() || st.pop() != c) return false; } return st.isEmpty(); } // Push the expected closing bracket; O(n) time, O(n) space.

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.

How does a monotonic deque find the maximum of every sliding window in O(n)?

Show answer

Keep a deque of indices whose values are in decreasing order. For each new element, pop from the back while the back value is smaller, since those elements can never be the maximum again, then push the new index. Pop from the front if its index has left the window. The front is always the maximum of the current window. Every index enters and leaves once, so the total time is O(n) instead of O(n times k).

Why are linked lists often slower than arrays in practice, and what is a skip list?

Show answer

Linked list nodes are scattered in memory, so traversal causes cache misses, and each node needs extra memory for pointers. Arrays are contiguous and benefit from CPU caching and prefetching, so even O(n) shifts can be fast for moderate sizes. A skip list is a layered linked list with express lanes chosen randomly, giving O(log n) average search, insert and delete; Redis uses it for sorted sets.

Two linked lists merge at some node and share the rest. How do you find the merge point efficiently?

Show answer

A hash set of the first list's nodes works in O(m plus n) time but uses O(m) space. The O(1) space trick uses two pointers: walk each list, and when a pointer reaches the end, redirect it to the head of the other list. Both pointers travel m plus n steps, so they meet at the intersection, or both become null if there is none. Comparing node references, not values, is essential.

Design a rate limiter that allows at most 100 requests per user in any rolling 60-second window.

Show answer

For each user keep a deque of request timestamps. On a request, pop timestamps older than now minus 60 seconds from the front, then allow the request only if fewer than 100 remain, pushing the new timestamp at the back. This sliding window log is exact but uses memory per request. At scale I would use a sliding window counter or token bucket stored in Redis with atomic operations to save memory and work across servers.

Reverse a linked list in groups of k nodes.

Show answer

def reverse_k_group(head, k): # check that k nodes are available node, count = head, 0 while node and count < k: node = node.next count += 1 if count < k: return head # leave the remainder as is prev, cur = None, head for _ in range(k): # reverse k nodes cur.next, prev, cur = prev, cur, cur.next head.next = reverse_k_group(cur, k) # old head is now the group tail return prev # 1-2-3-4-5, k=2 -> 2-1-4-3-5; O(n) time

Tell me about a time you received critical feedback on your code.

Show answer

Situation: a senior reviewer rejected my pull request because my queue processing code was O(n squared) and had no tests. Task: fix it and learn from it. Action: I asked for a short walkthrough, replaced repeated list removals with a deque, added unit tests for edge cases and asked for a second review. Result: the change merged with a ten times speed-up, and I now self-review complexity and tests before raising any pull request.

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.

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.

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.

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.

Write an iterative inorder traversal of a binary tree.

Show answer

def inorder(root): result, stack = [], [] node = root while node or stack: while node: # go as far left as possible stack.append(node) node = node.left node = stack.pop() result.append(node.val) # visit node = node.right # then the right subtree return result # O(n) time, O(h) space; no recursion limit issues

Find the maximum depth of a binary tree.

Show answer

// Java static int maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); } // Each node visited once: O(n) time, O(h) stack space. // BFS alternative: count levels while processing the queue level by level.

Tell me about the project you are most proud of.

Show answer

Situation: in college I noticed students struggled to find relevant previous-year questions. Task: build a searchable question bank. Action: I built a small web app with a trie-based autocomplete for topics and an inverted index for keyword search, wrote tests and collected feedback from classmates. Result: over 400 students used it during exams, search stayed under 50 milliseconds, and I learned how data structure choices affect real users.

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.

Compare segment trees and Fenwick trees.

Show answer

Both answer range queries with point updates in O(log n). A Fenwick tree, or binary indexed tree, is compact, simple to code and ideal for prefix sums and counts, but supports mainly invertible operations. A segment tree stores an aggregate for each segment, handles any associative operation such as min, max or gcd, and supports range updates with lazy propagation, at the cost of about 4n memory and longer code.

What is a B-tree and why do databases use it for indexes?

Show answer

A B-tree is a balanced search tree where each node holds many keys and has many children, often hundreds. This keeps the tree very shallow, so a lookup among millions of rows touches only three or four nodes. Each node is sized to a disk or memory page, minimising expensive I/O. B+ trees, used by MySQL InnoDB and PostgreSQL, keep all values in linked leaves, making range scans efficient.

A recursive tree traversal crashes on a skewed tree with one million nodes. How do you fix it?

Show answer

A skewed tree has height about n, so recursion needs a million stack frames and overflows. Rewrite the traversal iteratively with an explicit stack stored on the heap, or use Morris traversal, which threads temporary links through the tree to achieve O(1) extra space. If the tree is built by our code, also consider why it is skewed and switch to a self-balancing tree so height stays O(log n).

A game leaderboard with millions of players needs fast score updates and queries like what rank is this player. How would you design it?

Show answer

Sorting on every query is too slow. I would bucket scores and use a Fenwick tree or segment tree over score values, storing how many players have each score; a player's rank is the count of players with higher scores, found in O(log S). Updates move a player between buckets in O(log S). An order-statistic balanced tree also works, and in production Redis sorted sets, built on skip lists, provide this directly.

100

Serialize a binary tree to a string and deserialize it back.

Show answer

def serialize(root): out = [] def dfs(node): if not node: out.append('#') return out.append(str(node.val)) dfs(node.left) dfs(node.right) dfs(root) return ','.join(out) def deserialize(data): vals = iter(data.split(',')) def build(): v = next(vals) if v == '#': return None node = TreeNode(int(v)) node.left = build() node.right = build() return node return build() # Preorder with null markers uniquely encodes the tree: O(n) both ways.

101

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

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.

102

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

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

103

A cashier system uses the greedy rule of always giving the largest coin first. When can this fail?

Show answer

Greedy coin change is optimal for canonical systems such as Indian rupee denominations, but fails for arbitrary coin sets. With coins 1, 3 and 4 and amount 6, greedy gives 4 plus 1 plus 1, three coins, while 3 plus 3 uses only two. For arbitrary denominations, use dynamic programming where dp of x is the minimum coins for amount x, computed in O(amount times number of coins).

104

Find the kth largest element in an array using a heap.

Show answer

import heapq def kth_largest(nums, k): heap = [] for x in nums: heapq.heappush(heap, x) if len(heap) > k: heapq.heappop(heap) # drop the smallest return heap[0] # smallest of the k largest # kth_largest([3, 2, 1, 5, 6, 4], 2) -> 5 # O(n log k) time, O(k) space; quickselect gives O(n) average

105

Tell me about a time you had to make a decision with incomplete information.

Show answer

Situation: during a release, a performance test showed occasional slow responses but the logs were incomplete. Task: decide whether to ship on schedule. Action: I listed what we knew, estimated the impact using the available percentiles, proposed shipping behind a feature flag with extra monitoring, and prepared a rollback plan. Result: we shipped on time, the extra metrics revealed a slow cache warm-up that we fixed in the next patch with no user complaints.

106

Why do you want to work at a product company as a software engineer?

Show answer

Situation: during my internship I worked on a feature used by thousands of people and saw how algorithm choices changed response times. Task: I want a role where engineering quality directly affects users. Action: I have practised data structures, system basics and clean coding, and built projects end to end. Result: I believe a product company will let me own features, learn from strong engineers and see the real impact of my work.

107

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.

108

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

109

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.

110

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.

111

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.

112

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

113

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

114

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.

115

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.

116

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

117

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.

118

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

119

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.

120

How does Huffman coding work?

Show answer

Huffman coding builds an optimal prefix-free binary code for compression. Put each character with its frequency into a min-heap. Repeatedly remove the two least frequent nodes, merge them into a new node whose frequency is their sum, and push it back. The final tree gives codes: left edges are 0 and right edges are 1, so frequent characters get shorter codes. It runs in O(n log n) and is used in ZIP and JPEG.

121

How do you prove that a greedy algorithm is correct?

Show answer

The common method is an exchange argument: take any optimal solution, show that replacing its first choice with the greedy choice does not make it worse, then apply the same reasoning to the remaining subproblem by induction. Another method is showing greedy stays ahead, meaning after each step its partial solution is at least as good as any other. In interviews, stating the argument briefly and testing small counterexamples builds confidence.

122

You need to merge K sorted log files from different servers into one sorted output. How would you do it efficiently?

Show answer

Use a min-heap of size K holding the current smallest line from each file, keyed by timestamp. Pop the smallest, write it out, and push the next line from the same file. Each line is pushed and popped once, so total time is O(N log K) for N lines, and memory is O(K) plus buffers, which works even when files are larger than RAM. Buffered reading and writing keeps I/O efficient.

123

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

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.

124

CPU tasks labelled by type must be scheduled with a cooldown of n slots between two tasks of the same type. How do you minimise total time?

Show answer

Greedily run the most frequent available task each slot. Use a max-heap of remaining counts and a queue of tasks cooling down with the time they become available. Each slot, move ready tasks back to the heap, pop the most frequent, decrement and enqueue it with time plus n. A closed formula also exists: max of total tasks and (maxFreq minus 1) times (n plus 1) plus the number of tasks with maxFreq.

125

Implement a data structure that returns the median of all numbers added so far.

Show answer

import heapq class MedianFinder: def __init__(self): self.low = [] # max-heap via negation (smaller half) self.high = [] # min-heap (larger half) def add(self, x): heapq.heappush(self.low, -x) heapq.heappush(self.high, -heapq.heappop(self.low)) if len(self.high) > len(self.low): heapq.heappush(self.low, -heapq.heappop(self.high)) def median(self): if len(self.low) > len(self.high): return -self.low[0] return (-self.low[0] + self.high[0]) / 2 # add is O(log n), median is O(1)

126

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

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.

127

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

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.

128

Explain directed, undirected, weighted graphs and DAGs.

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.

129

A metro app must find the route with the fewest stations between two stops. Which algorithm would you use?

Show answer

If every hop counts equally, the network is an unweighted graph and BFS from the source gives the minimum number of stations in O(V plus E). I would store a parent for each visited station to reconstruct the path. If the goal changes to minimum travel time with different segment durations or interchange penalties, I would switch to Dijkstra with those weights, adding interchange cost as edges between line nodes.

130

A satellite image is a grid of land and water cells. How do you count the islands?

Show answer

Treat each land cell as a vertex connected to its four neighbours that are also land. Scan the grid; when you find unvisited land, increase the island count and run DFS or BFS to mark the whole connected island as visited. Each cell is visited once, so the time is O(rows times columns). Use BFS or an explicit stack for very large grids to avoid recursion limits, or Union-Find if cells arrive over time.

131

Count the number of islands in a grid of 1s and 0s.

Show answer

// Java static int numIslands(char[][] g) { int count = 0; for (int r = 0; r < g.length; r++) for (int c = 0; c < g[0].length; c++) if (g[r][c] == '1') { count++; sink(g, r, c); } return count; } static void sink(char[][] g, int r, int c) { if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return; g[r][c] = '0'; // mark visited sink(g, r + 1, c); sink(g, r - 1, c); sink(g, r, c + 1); sink(g, r, c - 1); } // O(rows * cols) time

132

Where do you see yourself in five years?

Show answer

Situation: I am starting my career with a strong interest in solving algorithmic and system problems. Task: grow into an engineer others rely on. Action: in the first years I want to master the codebase, deliver features reliably and deepen my skills in data structures, system design and the domain. Result: in five years I see myself as a senior engineer owning important components, mentoring juniors and contributing to design decisions in this team.

133

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.

134

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

135

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.

136

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.

137

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

138

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.

139

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.

140

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.

141

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)

142

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

143

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

144

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.

145

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.

146

Compare Bellman-Ford and Floyd-Warshall.

Show answer

Bellman-Ford finds single-source shortest paths with negative weights by relaxing all edges V minus 1 times, O(V times E), and one more pass detects negative cycles. Floyd-Warshall finds shortest paths between all pairs using dynamic programming over intermediate vertices, O(V cubed) time and O(V squared) space, suitable for small dense graphs of a few hundred nodes. For all pairs on large sparse graphs, running Dijkstra from each vertex is faster.

147

How does cycle detection differ in directed and undirected graphs?

Show answer

In an undirected graph, DFS finds a cycle when it reaches an already visited vertex that is not the parent of the current vertex; Union-Find also works by checking whether an edge joins vertices already in the same set. In a directed graph you need three states, unvisited, in the current recursion stack and finished, and a cycle exists when DFS reaches a vertex still on the stack. Kahn's algorithm also detects directed cycles.

148

Find the cheapest flight from one city to another using at most K stops. Why does plain Dijkstra not work directly?

Show answer

Plain Dijkstra finalises the cheapest path to a city, but that path may use too many stops, while a costlier path with fewer stops could still lead to a valid answer. One fix is Bellman-Ford limited to K plus 1 rounds, copying distances each round, O(K times E). Another is Dijkstra on states of city and stops used, or a BFS by levels that tracks cost, pruning states that are worse in both cost and stops.

149

A network has 10 million devices and connections are added continuously. You must answer whether two devices are connected in real time. How?

Show answer

Running BFS for every query is too slow. Since connections are only added, Union-Find is ideal: each new link is a union, and each query compares find results, both nearly O(1) amortised with path compression and union by size. Memory is two integer arrays of 10 million entries, about 80 MB. If links can also be removed, the problem becomes much harder and needs offline processing or specialised dynamic connectivity structures.

150

Implement Union-Find with path compression and union by size.

Show answer

class DSU: def __init__(self, n): self.parent = list(range(n)) self.size = [1] * n def find(self, x): while self.parent[x] != x: self.parent[x] = self.parent[self.parent[x]] # path halving x = self.parent[x] return x def union(self, a, b): ra, rb = self.find(a), self.find(b) if ra == rb: return False if self.size[ra] < self.size[rb]: ra, rb = rb, ra self.parent[rb] = ra self.size[ra] += self.size[rb] return True # Nearly O(1) amortised per operation

151

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

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.

152

What is the difference between memoisation and tabulation?

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.

153

A warehouse robot moves only right or down on a grid with some blocked cells. How do you count the number of paths?

Show answer

Use DP where dp[r][c] is the number of ways to reach cell r, c. A blocked cell has 0 ways; the start has 1; every other cell is dp[r-1][c] plus dp[r][c-1]. Fill row by row in O(rows times columns), and keep a single row array to use O(columns) space. Counts can become huge, so problems often ask for the result modulo 10 to the power 9 plus 7.

154

Solve climbing stairs: how many ways are there to climb n steps taking 1 or 2 steps at a time?

Show answer

def climb_stairs(n): if n <= 2: return n prev2, prev1 = 1, 2 # ways(1), ways(2) for _ in range(3, n + 1): prev2, prev1 = prev1, prev1 + prev2 return prev1 # ways(n) = ways(n-1) + ways(n-2): a Fibonacci pattern # climb_stairs(5) -> 8; O(n) time, O(1) space

155

Solve house robber: maximise money robbed from houses in a row without robbing two adjacent houses.

Show answer

def rob(nums): take, skip = 0, 0 # best if the previous house is taken or skipped for x in nums: take, skip = skip + x, max(take, skip) return max(take, skip) # rob([2, 7, 9, 3, 1]) -> 12 (2 + 9 + 1) # dp[i] = max(dp[i-1], dp[i-2] + nums[i]); O(n) time, O(1) space

156

Tell me about a time you kept working on a hard problem when others had given up.

Show answer

Situation: a scheduling feature produced suboptimal plans and the team was ready to accept it. Task: I believed an exact solution was possible for our sizes. Action: I spent evenings modelling it, found the number of shifts was small enough for bitmask DP, built a prototype, and validated it against the old greedy output on 200 real cases. Result: plans improved by about 12 percent in cost, and the feature shipped with the new algorithm.

157

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.

158

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.

159

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.

160

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.

161

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.

162

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.

163

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.

164

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.

165

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

166

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

167

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

168

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.

169

What is bitmask DP and when is it used?

Show answer

Bitmask DP represents a subset of up to about 20 items as the bits of an integer, so the state can be the set of items already used plus perhaps the last item. The travelling salesman problem uses dp[mask][last], the minimum cost to visit the cities in mask ending at last, giving O(2 to the power n times n squared) instead of n factorial. It is used for assignment, scheduling and covering problems with small n.

170

What is DP on trees? Give an example.

Show answer

DP on trees computes values for each node from the values of its children, usually in a postorder DFS. For the maximum independent set, where no two chosen nodes are adjacent, each node keeps two values: the best if it is taken, which is its value plus the not-taken values of children, and the best if it is not taken, the sum of each child's better option. This runs in O(n) and also solves house robber on a tree.

171

What is interval DP? Explain with matrix chain multiplication.

Show answer

Interval DP defines states over a range i to j and combines smaller ranges. In matrix chain multiplication, dp[i][j] is the minimum scalar multiplications to multiply matrices i through j. Try every split point k between i and j: dp[i][k] plus dp[k+1][j] plus the cost of multiplying the two results. Fill by increasing interval length, O(n cubed). Similar patterns solve burst balloons and palindrome partitioning.

172

How do you find the longest increasing subsequence in O(n log n)?

Show answer

The simple DP is O(n squared): dp[i] is the LIS ending at i. The faster method keeps an array tails, where tails[k] is the smallest possible last value of an increasing subsequence of length k plus 1. For each number, binary search tails for the first value not less than it and replace it, or append if none. The length of tails is the LIS length. This patience sorting idea also helps in envelope nesting problems.

173

A company has a fixed budget and several projects with costs and expected returns. How would you choose projects to maximise return?

Show answer

If each project is all or nothing, this is the 0/1 knapsack problem: budget is capacity, cost is weight and return is value, solved with DP in O(projects times budget), and tracking choices lets me list selected projects. If the budget is very large, I would scale costs to units such as lakhs to keep the table small, or use DP over value instead. Extra constraints like dependencies change the state design.

174

Your knapsack DP has n equal to 100 items but capacity up to 10 to the power 9, so the table does not fit in memory. What do you do?

Show answer

A table indexed by capacity is impossible, so I change the state. If item values are small, use dp[v] as the minimum weight needed to achieve value v, then pick the largest v whose weight fits the capacity; that is O(n times total value). If n is about 40, meet in the middle: enumerate subsets of each half, sort one side and binary search. Otherwise approximation or branch and bound are options.

175

Compute the edit distance between two words.

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

176

How does binary search work and what does it require?

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.

177

What is a stable sort and why does stability matter?

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.

178

What is backtracking?

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.

179

A bug appeared somewhere in the last 1000 commits. How would you find the commit that introduced it quickly?

Show answer

Commits form an ordered sequence where everything after the bad commit fails and everything before passes, which is a monotonic condition, so binary search applies. Test the middle commit; if it fails, search the earlier half, otherwise the later half. About 10 tests find the culprit among 1000 commits. git bisect automates this, and git bisect run can execute a test script at each step.

180

HR wants an employee list sorted by department, and by salary within each department. How would you do it?

Show answer

Either sort once with a composite key, department first and salary second, using a comparator in Java or a tuple key in Python, or do two passes with a stable sort: first by salary, then by department, relying on stability to keep salary order within departments. The single composite-key sort is clearer. Both are O(n log n), and I would clarify whether salary should be ascending or descending.

181

Write an iterative binary search that returns the index of a target or -1.

Show answer

// Java static int binarySearch(int[] a, int target) { int lo = 0, hi = a.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // avoids overflow if (a[mid] == target) return mid; if (a[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; } // O(log n) time, O(1) space

182

Compute the integer square root of a number using binary search.

Show answer

def int_sqrt(x): lo, hi = 0, x ans = 0 while lo <= hi: mid = (lo + hi) // 2 if mid * mid <= x: ans = mid # mid is a valid candidate lo = mid + 1 else: hi = mid - 1 return ans # int_sqrt(8) -> 2, int_sqrt(16) -> 4; O(log x)

183

Tell me about yourself for a software engineer role.

Show answer

Situation: I am a computer science graduate who enjoys problem solving. Task: become a strong software engineer. Action: I have solved over 400 data structures and algorithms problems, built a campus event app and a file search tool using tries and hashing, and completed an internship where I fixed performance issues in a backend service. Result: I can write clean, efficient code, explain trade-offs clearly, and I am eager to contribute to your engineering team.

184

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.

185

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.

186

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.

187

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

188

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

189

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

190

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)

191

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

192

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

Show answer

Situation: in my current role I have learned a lot maintaining internal tools for two years. Task: I want to grow into harder engineering problems. Action: I have been strengthening my data structures, system design and backend skills through projects and by taking ownership of performance work in my team. Result: I am now ready for a role with larger scale and more technical depth, which is why this position appeals to me.

193

Why can comparison sorts not beat O(n log n), and how do counting and radix sort get around it?

Show answer

Any comparison sort can be modelled as a decision tree with n factorial leaves, one per possible ordering, so its height, the number of comparisons, is at least log of n factorial, which is about n log n. Counting sort avoids comparisons by counting occurrences of each key in a small range k, giving O(n plus k). Radix sort applies a stable counting sort digit by digit, O(d times (n plus base)), great for fixed-length integers.

194

What does binary search on the answer mean?

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.

195

What is Timsort and why do Python and Java use it?

Show answer

Timsort is a hybrid of merge sort and insertion sort. It scans the data for already sorted runs, extends short runs with insertion sort and merges runs using a stack with balancing rules and galloping mode. Real data is often partially sorted, so Timsort is close to O(n) on such input while keeping O(n log n) worst case and stability. Python uses it for all sorts and Java for sorting objects.

196

What is quickselect and when is it better than sorting?

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.

197

You must sort a 10 GB file of records on a machine with 1 GB of RAM. How would you do it?

Show answer

Use external merge sort. Read the file in chunks of about 800 MB, sort each chunk in memory and write it to disk as a sorted run, giving around 13 runs. Then perform a K-way merge: open all runs, keep a min-heap with the current record from each, repeatedly output the smallest and refill from that run, using buffered I/O. Total work is O(n log n) with roughly two passes over the data.

198

A Sudoku solver using plain backtracking is too slow on hard puzzles. How would you speed it up?

Show answer

Add stronger pruning and better choice ordering. Keep bitmasks of used digits for each row, column and box, so validity checks are O(1). Always fill the empty cell with the fewest candidates first, the minimum remaining values heuristic, which shrinks the search tree dramatically. Apply constraint propagation, filling cells with a single candidate before guessing. For the hardest cases, exact cover with Dancing Links is very fast.

199

Search for a target in a rotated sorted array.

Show answer

def search_rotated(nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = (lo + hi) // 2 if nums[mid] == target: return mid if nums[lo] <= nums[mid]: # left half sorted if nums[lo] <= target < nums[mid]: hi = mid - 1 else: lo = mid + 1 else: # right half sorted if nums[mid] < target <= nums[hi]: lo = mid + 1 else: hi = mid - 1 return -1 # [4,5,6,7,0,1,2], 0 -> 4; O(log n)

200

Tell me about a time you made slow code significantly faster at work.