Data Structures and Algorithms Interview Questions in Mumbai

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.

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.

Explain the recurrence for the 0/1 knapsack problem.

Show answer

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

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

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.

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

Heaps, Priority Queues and GreedyEasy

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.

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

Sorting, Searching and BacktrackingMedium

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)

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

Heaps, Priority Queues and GreedyMedium

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.

What is amortised analysis? Explain it with dynamic array append.

Complexity Analysis and RecursionMedium

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.

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

Linked Lists, Stacks and QueuesHard

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.

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

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

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.

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)

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.

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

Graphs and Graph AlgorithmsEasy

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.

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)

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.

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

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

What does binary search on the answer mean?

Sorting, Searching and BacktrackingHard

Show answer

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

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.

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.

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.

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

Show answer

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

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

Heaps, Priority Queues and GreedyMedium

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.

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.

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.

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

Sorting, Searching and BacktrackingEasy

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.

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

Heaps, Priority Queues and GreedyMedium

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.

What is the Dutch National Flag algorithm?