Data Structures and Algorithms Interview Questions in Bhubaneswar
36 practice questions with answers for Data Structures and Algorithms interviews in Bhubaneswar.
Data Structures and Algorithms jobs in Bhubaneswar
Bhubaneswar is eastern India's emerging IT hub, with campuses of large IT-services companies in Infocity and Info Valley. Freshers make up a big share of hiring, so fundamentals and aptitude rounds matter most.
Below are 36 questions that match the mix of service, product and domain employers hiring software engineer (fresher / sde-1)s in Bhubaneswar.
Solved for BhubaneswarStart 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
A metro app must find the route with the fewest stations between two stops. Which algorithm would you use?
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.
02
How does quicksort work and why does pivot choice matter?
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.
03
How is the longest common subsequence computed with DP?
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.
04
How did you prepare for data structures and algorithms rounds?
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.
05
What is tail recursion and do Java and Python optimise it?
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.
06
How does a hash table work, and how are collisions handled?
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.
07
What are the trade-offs between recursion and iteration?
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.
08
What is the load factor of a hash table and why does it matter?
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.
09
Explain best, average and worst case complexity using quicksort.
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.
10
An interviewer asks you to reduce your solution's extra space from O(n) to O(1). How do you approach it?
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.
11
Write recursive Fibonacci and then optimise it with memoisation.
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
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.
13
A trading application needs a stack that also returns the current minimum in O(1). How would you design it?
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.
14
An array of size 100000 must answer 100000 queries asking for the sum between two indices. What approach would you use?
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.
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.
16
How does merge sort work and what are its properties?
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.
17
Find the minimum number of railway platforms needed given arrival and departure times.
// 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.
18
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?
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.
19
Packages with given weights must be shipped in order within D days. How do you find the minimum ship capacity?
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).
20
Tell me about a time you used the right data structure to solve a real problem in a project or job.
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.
21
You are building undo and redo for a text editor. Which data structures would you use?
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.
22
Find the minimum number of coins needed to make an amount.
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
23
A cashier system uses the greedy rule of always giving the largest coin first. When can this fail?
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).
24
What are lower bound and upper bound, and what common bugs appear in binary search?
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.
25
Count the number of islands in a grid of 1s and 0s.
// 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
26
Explain the sliding window technique with fixed and variable windows.
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).
27
Tell me about a time you received critical feedback on your code.
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.
28
A hospital emergency system must treat patients by severity, and patients with equal severity in arrival order. How would you implement it?
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.
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.
30
A sorted array has been rotated at an unknown point. How can you still search it in O(log n)?
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).
31
What is the difference between a subarray, a subsequence and a substring?
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.
32
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?
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.
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.
34
Check whether a string is a palindrome, ignoring case and non-alphanumeric characters.
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).
36
Implement topological sort using Kahn's algorithm.
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
Few big employers listed in Bhubaneswar?
Many Bhubaneswar candidates also apply to teams in Kolkata and to remote or hybrid roles. Practise the Kolkata set as well.
Which companies hire Data Structures and Algorithms professionals in Bhubaneswar?
Companies with large offices in Bhubaneswar include many IT services and product firms. Use their company pages below to practise employer-specific sets.
Are Data Structures and Algorithms interviews in Bhubaneswar different from other cities?
The questions depend more on the company than the city. Bhubaneswar's mix of employers decides the style: Freshers make up a big share of hiring, so fundamentals and aptitude rounds matter most
How do I find Data Structures and Algorithms jobs in Bhubaneswar?
Shortlist companies with Bhubaneswar offices, keep your CV focused on Data Structures and Algorithms projects, apply on company career pages and job portals with the Bhubaneswar filter, and practise the questions on this page before each interview.