Data Structures and Algorithms Managerial Round Questions &amp; Answers

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.

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

Complexity Analysis and RecursionMedium

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.

Compare AVL trees and red-black trees.

Trees and Binary Search TreesMedium

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.

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

Sorting, Searching and BacktrackingHard

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.

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.

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?

Trees and Binary Search TreesMedium

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.

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

Linked Lists, Stacks and QueuesMedium

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.

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.

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.

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

Heaps, Priority Queues and GreedyEasy

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.

Merge K sorted linked lists using a min-heap.

Heaps, Priority Queues and GreedyMedium

Show answer

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

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

Show answer

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

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

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.

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.

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?

Heaps, Priority Queues and GreedyHard

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.

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

Graphs and Graph AlgorithmsMedium

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.

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

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

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

Arrays, Strings and HashingHard

Show answer

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

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

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

Trees and Binary Search TreesMedium

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

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

Heaps, Priority Queues and GreedyHard

Show answer

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

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

Linked Lists, Stacks and QueuesMedium

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.

What is topological sorting and how is it done?

Graphs and Graph AlgorithmsMedium

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

Implement merge sort.

Sorting, Searching and BacktrackingMedium

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

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.

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

Trees and Binary Search TreesHard

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.

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

Sorting, Searching and BacktrackingMedium

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.

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.

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

Graphs and Graph AlgorithmsMedium

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.

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

Sorting, Searching and BacktrackingMedium

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

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