Data Structures and Algorithms Interview Questions in Gurgaon

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.

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

Sorting, Searching and BacktrackingMedium

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

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.

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

Heaps, Priority Queues and GreedyMedium

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

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

How does merge sort work and what are its properties?

Sorting, Searching and BacktrackingMedium

Show answer

Merge sort splits the array into halves, recursively sorts each half and merges the two sorted halves in linear time. The recurrence T(n) = 2T(n/2) + n gives O(n log n) in every case. It is stable and works well for linked lists and external sorting of large files, but needs O(n) extra space for arrays. It also adapts to counting inversions during the merge step.

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

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.

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

Arrays, Strings and HashingEasy

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.

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

Heaps, Priority Queues and GreedyMedium

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

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

Linked Lists, Stacks and QueuesHard

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.

What is a monotonic stack and which problems does it solve?

Linked Lists, Stacks and QueuesMedium

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.

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

Linked Lists, Stacks and QueuesMedium

Show answer

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

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

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

Sorting, Searching and BacktrackingEasy

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

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

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.

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

Trees and Binary Search TreesMedium

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

Strings are immutable in Java and Python. How does that affect algorithm complexity?

Arrays, Strings and HashingEasy

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.

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

What is the difference between Big-O, Big-Omega and Big-Theta?

Complexity Analysis and RecursionEasy

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.

Implement topological sort using Kahn's algorithm.

Show answer

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

What is Kadane's algorithm?

Arrays, Strings and HashingMedium

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.

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.

Where do you see yourself in five years?

Graphs and Graph AlgorithmsEasy

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.

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.

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

Show answer

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

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

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.

Explain the sliding window technique with fixed and variable windows.

Arrays, Strings and HashingMedium

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

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.

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

Arrays, Strings and HashingMedium

Show answer

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

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

Dynamic ProgrammingEasy

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

Check whether a string of brackets is valid.

Linked Lists, Stacks and QueuesEasy

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.

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