Skip to content
Data Structures and Algorithms
All coursesPlacement Report
‹ Back to previous sectionCourse homeAll page URLs

Data Structures and Algorithms Interview Questions in Kolkata

36 practice questions with answers for Data Structures and Algorithms interviews in Kolkata.

Data Structures and Algorithms jobs in Kolkata

Kolkata has a steady IT-services and BFSI technology job market around Salt Lake Sector V and New Town. Many openings are with service companies and their delivery centres, with a focus on strong fundamentals.

Below are 36 questions that match the mix of service, product and domain employers hiring software engineer (fresher / sde-1)s in Kolkata.

Solved for KolkataStart practicing
3 QUESTIONS FREESign up to unlock the full question bank and track your progress.Unlock every question and answer, then continue practising company-wise and package-wise.
3 questions free Unlock the rest in seconds
01

Merge K sorted linked lists using a min-heap.

Heaps, Priority Queues and GreedyMedium
Save to ▾
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
02

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
Save to ▾
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.
03

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

Dynamic ProgrammingMedium
Save to ▾
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.
04

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

Arrays, Strings and HashingEasy
Save to ▾
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
05

How does quicksort work and why does pivot choice matter?

Sorting, Searching and BacktrackingMedium
Save to ▾
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.
06

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

Arrays, Strings and HashingEasy
Save to ▾
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.
07

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

Arrays, Strings and HashingMedium
Save to ▾
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.
08

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

Graphs and Graph AlgorithmsEasy
Save to ▾
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.
09

Generate all subsets of a list of distinct numbers.

Complexity Analysis and RecursionMedium
Save to ▾
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
10

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

Heaps, Priority Queues and GreedyMedium
Save to ▾
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.
11

What is a stable sort and why does stability matter?

Sorting, Searching and BacktrackingEasy
Save to ▾
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.
12

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

Trees and Binary Search TreesMedium
Save to ▾
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
13

What is time complexity and what does Big-O notation mean?

Complexity Analysis and RecursionEasy
Save to ▾
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.
14

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

Dynamic ProgrammingMedium
Save to ▾
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.
15

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

Linked Lists, Stacks and QueuesHard
Save to ▾
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.
16

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

Sorting, Searching and BacktrackingMedium
Save to ▾
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
17

What are prefix sums and what problems do they solve?

Arrays, Strings and HashingMedium
Save to ▾
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.
18

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?

Arrays, Strings and HashingMedium
Save to ▾
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.
19

How do you prove that a greedy algorithm is correct?

Heaps, Priority Queues and GreedyHard
Save to ▾
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.
20

Explain directed, undirected, weighted graphs and DAGs.

Graphs and Graph AlgorithmsEasy
Save to ▾
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.
21

What is quickselect and when is it better than sorting?

Sorting, Searching and BacktrackingHard
Save to ▾
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.
22

What is the difference between full, complete and perfect binary trees?

Trees and Binary Search TreesEasy
Save to ▾
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.
23

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

Complexity Analysis and RecursionMedium
Save to ▾
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.
24

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

Heaps, Priority Queues and GreedyMedium
Save to ▾
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.
25

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

Dynamic ProgrammingMedium
Save to ▾
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
26

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

Arrays, Strings and HashingEasy
Save to ▾
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.
27

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

Dynamic ProgrammingEasy
Save to ▾
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.
28

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

Linked Lists, Stacks and QueuesMedium
Save to ▾
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.
29

Write a function to validate a binary search tree.

Trees and Binary Search TreesMedium
Save to ▾
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.
30

What is a binary search tree and what is its time complexity?

Trees and Binary Search TreesEasy
Save to ▾
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.
31

What is a trie and where is it used?

Trees and Binary Search TreesMedium
Save to ▾
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.
32

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

Graphs and Graph AlgorithmsMedium
Save to ▾
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.
33

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
Save to ▾
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.
34

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

Arrays, Strings and HashingEasy
Save to ▾
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.
35

How can you reduce the space used by a DP solution?

Dynamic ProgrammingMedium
Save to ▾
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.
36

What is a dummy or sentinel node and why is it useful in linked list problems?

Linked Lists, Stacks and QueuesMedium
Save to ▾
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.

Frequently asked questions

Which companies hire Data Structures and Algorithms professionals in Kolkata?

Companies with large offices in Kolkata include many IT services and product firms. Use their company pages below to practise employer-specific sets.

Are Data Structures and Algorithms interviews in Kolkata different from other cities?

The questions depend more on the company than the city. Kolkata's mix of employers decides the style: Many openings are with service companies and their delivery centres, with a focus on strong fundamentals

How do I find Data Structures and Algorithms jobs in Kolkata?

Shortlist companies with Kolkata offices, keep your CV focused on Data Structures and Algorithms projects, apply on company career pages and job portals with the Kolkata filter, and practise the questions on this page before each interview.

Other cities

DelhiNoidaGurgaonBangaloreHyderabadPuneChennaiMumbaiAhmedabadJaipurLucknowChandigarhIndoreKochiCoimbatoreBhubaneswarNagpurVisakhapatnamThiruvananthapuram

More ways to practise

Company-wise Data Structures and Algorithms questionsExperience-wise Data Structures and Algorithms questionsRole-wise Data Structures and Algorithms questionsCity-wise Data Structures and Algorithms questionsMost asked Data Structures and Algorithms questionsScenario-based questionsPractical / hands-on questionsHR & behavioural questionsData Structures and Algorithms mock interviewOnline assessment questionsTechnical round questionsManagerial round questionsData Structures and Algorithms topic sheets