Data Structures and Algorithms Interview Questions in Lucknow
36 practice questions with answers for Data Structures and Algorithms interviews in Lucknow.
Data Structures and Algorithms jobs in Lucknow
Lucknow's tech job market is smaller but growing, led by IT-services delivery centres, government-tech projects and start-ups. Many Lucknow candidates target Noida and Gurgaon roles or remote jobs, so interviews follow the NCR pattern.
Below are 36 questions that match the mix of service, product and domain employers hiring software engineer (fresher / sde-1)s in Lucknow.
Solved for LucknowStart 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.
A binary heap is a complete binary tree where every parent is smaller than its children in a min-heap or larger in a max-heap, so the root is the minimum or maximum. Because the tree is complete, it is stored in an array without pointers: for index i, children are at 2i plus 1 and 2i plus 2 and the parent at (i minus 1) divided by 2. This layout is compact and cache friendly.
02
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.
03
Design a simple scheduler that gives each job a fixed time slice in turn.
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.
04
What is the Union-Find data structure and what optimisations make it fast?
Union-Find, or disjoint set union, tracks which elements belong to the same group with find, returning a representative, and union, merging two groups. Path compression makes every node on a find path point directly to the root, and union by rank or size attaches the smaller tree under the larger. Together they give nearly constant amortised time, the inverse Ackermann function. It is used in Kruskal and dynamic connectivity.
05
What is the difference between memoisation and tabulation?
Memoisation is top-down: write the natural recursion and cache results in a map or array, so only needed states are computed, but recursion depth can be a problem. Tabulation is bottom-up: fill a table iteratively from base cases in an order where dependencies are ready, avoiding recursion overhead and making space optimisation easier. Both usually have the same time complexity; choose whichever is clearer for the problem.
06
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.
07
Implement fast exponentiation to compute x to the power n in O(log n).
def power(x, n):
if n < 0:
x, n = 1 / x, -n
result = 1
while n > 0:
if n & 1: # odd bit set: multiply current base in
result *= x
x *= x # square the base
n >>= 1 # move to next bit
return result
# power(2, 10) == 1024; use % mod after each multiply for modular power
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
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.
10
What is the difference between a linked list and an array?
An array stores elements contiguously, giving O(1) index access and good cache performance, but inserting or deleting in the middle costs O(n) because elements shift. A linked list stores nodes with pointers to the next node, so insertion and deletion at a known node are O(1), but finding the i-th element takes O(n) and each node has pointer overhead. Arrays suit read-heavy work, lists suit frequent splicing.
11
What are prefix sums and what problems do they solve?
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.
12
What is recursion and why is a base case essential?
Recursion is when a function solves a problem by calling itself on smaller subproblems. Each call gets its own frame on the call stack holding parameters and local variables. The base case is the condition where the function returns directly without recursing, such as n equal to 0 for factorial. Without a correct base case, calls never stop and the program fails with a stack overflow.
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
14
Why is naive recursive Fibonacci exponential, and how do you fix it?
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.
15
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
16
A recursive tree traversal crashes on a skewed tree with one million nodes. How do you fix it?
A skewed tree has height about n, so recursion needs a million stack frames and overflows. Rewrite the traversal iteratively with an explicit stack stored on the heap, or use Morris traversal, which threads temporary links through the tree to achieve O(1) extra space. If the tree is built by our code, also consider why it is skewed and switch to a self-balancing tree so height stays O(log n).
17
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.
18
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).
19
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.
20
How do you use a priority queue in Java and Python?
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).
def hanoi(n, src, dst, aux, moves):
if n == 0:
return
hanoi(n - 1, src, aux, dst, moves) # move n-1 disks out of the way
moves.append((src, dst)) # move the largest disk
hanoi(n - 1, aux, dst, src, moves) # move n-1 disks on top of it
moves = []
hanoi(3, 'A', 'C', 'B', moves)
print(len(moves)) # 7, since the count is 2^n - 1
22
What is a greedy algorithm and when does it give the optimal answer?
A greedy algorithm builds a solution step by step, always taking the choice that looks best right now and never revisiting it. It is optimal only when the problem has the greedy choice property, meaning a locally best choice is part of some optimal solution, and optimal substructure. Examples where greedy works are activity selection, Huffman coding, Dijkstra and Kruskal. For many problems, such as 0/1 knapsack, it fails.
23
How do DFS and BFS differ in memory use on a tree?
DFS uses a stack, either the call stack or an explicit one, holding at most the height of the tree, so O(h) memory: about log n for balanced trees but n for skewed ones. BFS uses a queue holding an entire level, up to about n over 2 nodes in the last level of a complete tree. So DFS is lighter for wide balanced trees, while BFS is natural for shortest paths and level-wise processing.
24
What is the diameter of a binary tree and how do you compute it efficiently?
The diameter is the number of edges on the longest path between any two nodes, which may not pass through the root. Compute it in one postorder traversal: for each node, get the heights of the left and right subtrees, update a global best with left plus right, and return 1 plus the larger height to the parent. This visits each node once, giving O(n) time instead of O(n squared) from recomputing heights.
25
How do you find the lowest common ancestor in a BST versus in a general binary tree?
In a BST, start at the root: if both values are smaller go left, if both are larger go right, otherwise the current node is the LCA, taking O(h). In a general binary tree, recurse: if the node is null or matches either target, return it; otherwise search both subtrees. If both sides return non-null, the current node is the LCA; else return the non-null side. That takes O(n).
26
Find the first and last position of a target in a sorted array.
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)
27
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.
28
What are the complexities of heap operations, and why does building a heap take O(n)?
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.
29
What is a bipartite graph and how do you check for one?
A graph is bipartite if its vertices can be split into two groups so every edge connects vertices from different groups, which is equivalent to having no odd-length cycle. To check, colour vertices with BFS or DFS: give the start vertex colour 0, its neighbours colour 1 and so on; if any edge connects two vertices of the same colour, it is not bipartite. Run it on each component, O(V plus E).
30
How do you handle pressure during a timed online coding test?
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.
It sorts an array of three distinct values, such as 0, 1 and 2, in one pass with O(1) space. It keeps three pointers: low, mid and high. If arr[mid] is 0, swap it with arr[low] and advance both; if 1, advance mid; if 2, swap it with arr[high] and decrease high without advancing mid. It runs in O(n) and is the basis of three-way partitioning in quicksort.
32
A recursive DFS in Python crashes with RecursionError on a deep input. How do you fix it?
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.
33
Find the length of the longest substring without repeating characters.
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
34
A Sudoku solver using plain backtracking is too slow on hard puzzles. How would you speed it up?
Add stronger pruning and better choice ordering. Keep bitmasks of used digits for each row, column and box, so validity checks are O(1). Always fill the empty cell with the fewest candidates first, the minimum remaining values heuristic, which shrinks the search tree dramatically. Apply constraint propagation, filling cells with a single candidate before guessing. For the hardest cases, exact cover with Dancing Links is very fast.
35
Two linked lists merge at some node and share the rest. How do you find the merge point efficiently?
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.
36
How would you implement browser back and forward navigation?
Use two stacks plus the current page. Visiting a new page pushes the current page onto the back stack, sets the new page as current and clears the forward stack. Back pushes current onto the forward stack and pops the back stack into current. Forward does the reverse. Each operation is O(1). A doubly linked list with a cursor is an alternative that makes it easy to show the full history.
Few big employers listed in Lucknow?
Many Lucknow candidates also apply to teams in Noida and to remote or hybrid roles. Practise the Noida set as well.
Which companies hire Data Structures and Algorithms professionals in Lucknow?
Companies with large offices in Lucknow include many IT services and product firms. Use their company pages below to practise employer-specific sets.
Are Data Structures and Algorithms interviews in Lucknow different from other cities?
The questions depend more on the company than the city. Lucknow's mix of employers decides the style: Many Lucknow candidates target Noida and Gurgaon roles or remote jobs, so interviews follow the NCR pattern
How do I find Data Structures and Algorithms jobs in Lucknow?
Shortlist companies with Lucknow offices, keep your CV focused on Data Structures and Algorithms projects, apply on company career pages and job portals with the Lucknow filter, and practise the questions on this page before each interview.