Backend developers build APIs, services and data pipelines in Java, Python, Go or Node.js. DSA knowledge helps them pick the right data structures for caching, queues, rate limiting, search and scheduling, and to keep services fast as data grows. Interviews combine medium DSA problems with practical questions on hash maps, heaps, graphs for dependencies and complexity of database operations, plus basic system design.
API development Caching strategies Queues and heaps Complexity trade-offs Basic system design
Solved for this roleStart 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
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
02
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).
03
Strings are immutable in Java and Python. How does that affect algorithm complexity?
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.
04
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.
05
Find the shortest path length from the top-left to the bottom-right of a grid where 1 is a wall.
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)
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 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.
08
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.
09
Find the next greater element for every element of an array.
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)
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.
11
Explain directed, undirected, weighted graphs and DAGs.
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.
12
How does a monotonic deque find the maximum of every sliding window in O(n)?
Keep a deque of indices whose values are in decreasing order. For each new element, pop from the back while the back value is smaller, since those elements can never be the maximum again, then push the new index. Pop from the front if its index has left the window. The front is always the maximum of the current window. Every index enters and leaves once, so the total time is O(n) instead of O(n times k).
13
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?
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.
14
Why are you looking for a change from your current job?
Situation: in my current role I have learned a lot maintaining internal tools for two years. Task: I want to grow into harder engineering problems. Action: I have been strengthening my data structures, system design and backend skills through projects and by taking ownership of performance work in my team. Result: I am now ready for a role with larger scale and more technical depth, which is why this position appeals to me.
15
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.
16
A build system hangs because some services depend on each other in a loop. How would you detect and report the cycle?
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.
17
Your brute-force solution for the longest substring without repeating characters is O(n cubed). How would you improve it?
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.
18
Solve jump game: can you reach the last index if nums[i] is the maximum jump from i?
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
19
Tell me about an interview or exam you failed and what you learned.
Situation: I was rejected after a coding round because I could not solve a tree problem in time. Task: understand the gap honestly. Action: I wrote down the question, realised I memorised solutions instead of patterns, and reorganised my practice by patterns such as postorder aggregation and BFS by level, explaining each solution aloud. Result: three months later I cleared a similar round comfortably, and I now review every mistake within a day.
20
How can you implement a queue using two stacks, and what is its complexity?
Use an in-stack for enqueue and an out-stack for dequeue. Enqueue pushes onto the in-stack in O(1). For dequeue, if the out-stack is empty, pop everything from the in-stack and push it onto the out-stack, which reverses the order, then pop from the out-stack. Each element moves at most once between stacks, so dequeue is O(1) amortised even though a single transfer can be O(n).
def rotate(nums, k):
n = len(nums)
k %= n
def reverse(l, r):
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
reverse(0, n - 1) # reverse all
reverse(0, k - 1) # reverse first k
reverse(k, n - 1) # reverse the rest
# [1,2,3,4,5,6,7], k=3 -> [5,6,7,1,2,3,4]; O(n) time, O(1) space
22
How does Floyd's cycle detection algorithm work and why is it correct?
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.
23
In activity selection, why do we sort by end time rather than start time or duration?
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.
24
You need to merge K sorted log files from different servers into one sorted output. How would you do it efficiently?
Use a min-heap of size K holding the current smallest line from each file, keyed by timestamp. Pop the smallest, write it out, and push the next line from the same file. Each line is pushed and popped once, so total time is O(N log K) for N lines, and memory is O(K) plus buffers, which works even when files are larger than RAM. Buffered reading and writing keeps I/O efficient.
25
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.
26
Why does greedy work for fractional knapsack but fail for 0/1 knapsack?
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).
27
What is a dummy or sentinel node and why is it useful in linked list problems?
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.
28
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
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.
30
What is a monotonic stack and which problems does it solve?
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.
31
How does cycle detection differ in directed and undirected graphs?
In an undirected graph, DFS finds a cycle when it reaches an already visited vertex that is not the parent of the current vertex; Union-Find also works by checking whether an edge joins vertices already in the same set. In a directed graph you need three states, unvisited, in the current recursion stack and finished, and a cycle exists when DFS reaches a vertex still on the stack. Kahn's algorithm also detects directed cycles.
32
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.
33
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.
34
How does Dijkstra's algorithm work and why does it fail with negative edge weights?
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.
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
36
Find the cheapest flight from one city to another using at most K stops. Why does plain Dijkstra not work directly?
Plain Dijkstra finalises the cheapest path to a city, but that path may use too many stops, while a costlier path with fewer stops could still lead to a valid answer. One fix is Bellman-Ford limited to K plus 1 rounds, copying distances each round, O(K times E). Another is Dijkstra on states of city and stops used, or a BFS by levels that tracks cost, pruning states that are worse in both cost and stops.
37
How do you prioritise when several tasks have deadlines at the same time?
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.
38
How would you generate friend suggestions as friends of friends in a social network?
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.
39
Given meeting start and end times for a day, how do you find the minimum number of rooms needed?
Sort meetings by start time and keep a min-heap of end times for rooms in use. For each meeting, if the earliest ending room is free by its start time, pop it; then push this meeting's end time. The heap size at the end, or its maximum, is the answer. This is O(n log n). An alternative sorts start and end times separately and sweeps with two pointers, counting overlaps.
40
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.
Frequently asked questions
What does a Backend Developer do?
Backend developers build APIs, services and data pipelines in Java, Python, Go or Node.js. DSA knowledge helps them pick the right data structures for caching, queues, rate limiting, search and scheduling, and to keep services fast as data grows. Interviews combine medium DSA problems with practical questions on hash maps, heaps, graphs for dependencies and complexity of database operations, plus basic system design.
Which skills are tested in a Backend Developer interview?
Expect questions on API development, Caching strategies, Queues and heaps, Complexity trade-offs, Basic system design. Most rounds also ask you to explain a project and solve one practical problem live.
How do I prepare for a Backend Developer interview?
Revise Heaps, Priority Queues and Greedy, Linked Lists, Stacks and Queues, Graphs and Graph Algorithms, Arrays, Strings and Hashing first using the topic sheets, practise the questions on this page aloud, then do one full mock interview to practise timing.