Data Structures and Algorithms Interview Questions and Answers: 60 Questions from Easy to Hard
This guide is for students preparing for campus placement coding tests in India and for working developers facing the DSA rounds at product companies. It has 60 questions in three levels: the basics every fresher is expected to know, the patterns that decide most online assessments and live coding rounds, and the harder problems and follow-ups asked of experienced candidates. Each answer is written the way a strong candidate would say it aloud: the idea first, then why it works, its time and space complexity, and the mistake interviewers watch for. About half come with short Python code that has been run, with its real output in the answer. Try each question yourself before reading the answer, then take the mock test to practise under a timer.
- 60 questions, 3 levels
- Updated
- CoreHRx Jobs
- 17,463 open IT jobs
What DSA interview rounds cover
- Online assessments in campus drives: two or three problems in 60 to 90 minutes with hidden test cases, usually arrays, strings, hashing and one greedy or DP problem.
- Live coding rounds at product companies: one or two problems where the interviewer watches how you reach the solution, not only whether it passes.
- Core structures: arrays, strings, hash maps, linked lists, stacks, queues, trees, heaps and graphs, and the cost of each operation on them.
- Patterns: two pointers, sliding window, prefix sums, binary search on the answer, BFS and DFS, backtracking, dynamic programming and greedy.
- For experienced candidates: complexity trade-offs, follow-ups such as streaming input or data too big for memory, and clean, tested code under time pressure.
How to prepare (freshers and experienced)
- Learn one pattern at a time and solve 5 to 8 problems on it before moving on. Recognising the pattern is most of the work in an interview.
- Freshers: get fluent in one language and its built-ins, such as dict, set, deque, heapq and sorting with a key in Python, before chasing hard problems.
- Experienced developers: revise graphs and DP, which fade fastest, and practise explaining trade-offs out loud as you would to a teammate.
- Time yourself: about 20 to 25 minutes for a medium problem, including tests. Re-solve problems you got wrong a week later without looking at your old code.
- Keep a short list of your own mistakes, such as off-by-one errors, missed empty input and wrong loop bounds. They repeat far more often than unknown algorithms.
Interview-day tips and common mistakes
- Restate the problem and ask about input size, value ranges, duplicates and empty input before writing code. The constraints often tell you the expected complexity.
- Say the brute force first with its complexity, then improve it. A working simple answer beats an unfinished clever one.
- Do not code in silence. Explain what each block does, and name the data structure you chose and why.
- Test with a small example by hand, then edge cases: empty input, one element, all values equal, negative numbers and very large values.
- Do not claim a complexity you have not worked out. Count the loops and the cost of each operation inside them, including slicing and string building.
Data Structures and Algorithms interview questions: Easy questions (freshers)
20 questions1. What does Big-O notation tell you about an algorithm, and what does it not tell you?
Big-O describes how running time or memory grows as the input size n grows, ignoring constant factors and smaller terms. An algorithm doing 3n + 20 steps is O(n), and one doing n^2/2 steps is O(n^2), so for large n the second loses whatever the constants are. Big-O does not tell you the actual speed on small inputs: insertion sort, which is O(n^2), often beats an O(n log n) sort on 10 items. It usually describes the worst case unless you say average or amortised. Always say what n is, for example the number of nodes or of edges.
2. What is the time complexity of this nested loop, where the inner loop starts at i?
It is O(n^2). The inner loop runs n times when i is 0, n - 1 times when i is 1, and so on down to once, so the total is n + (n - 1) + ... + 1 = n(n + 1)/2. The program prints 55 5050: making n ten times bigger made the count about a hundred times bigger, which is the signature of quadratic growth. Starting the inner loop at i halves the work compared with a full n by n loop, but halving is a constant factor, so the complexity class does not change. Calling this O(n log n) is a common fresher mistake.
def count_steps(n):
steps = 0
for i in range(n):
for j in range(i, n):
steps += 1
return steps
print(count_steps(10), count_steps(100))3. What do common Python list operations cost, and which ones surprise people?
A Python list is a dynamic array. Indexing, len(), append() and pop() from the end are O(1), with append amortised O(1). Inserting or deleting at the front or in the middle, such as insert(0, x) or pop(0), is O(n) because every later element shifts. The in operator and index() scan the list, so they are O(n) too. Slicing nums[a:b] copies b - a elements, which is easy to miss inside a loop. Building a string with += in a loop can also turn quadratic, so collect the parts in a list and join them. For fast removal at both ends, use collections.deque.
4. How do you check whether a string is a palindrome, ignoring case, spaces and punctuation?
Use two pointers, one at each end, and move them towards each other. Skip characters that are not letters or digits, compare the rest in lower case, and stop at the first mismatch. The program prints True False: Top spot! reads the same both ways once the space and the ! are skipped, and Pune does not. This is O(n) time and O(1) extra space. Building a cleaned string and comparing it with its reverse is also O(n) and fine to mention, but it uses O(n) extra memory, and interviewers often ask for the in-place version.
def is_palindrome(s):
i, j = 0, len(s) - 1
while i < j:
if not s[i].isalnum():
i += 1
elif not s[j].isalnum():
j -= 1
elif s[i].lower() != s[j].lower():
return False
else:
i += 1
j -= 1
return True
print(is_palindrome("Top spot!"), is_palindrome("Pune"))5. In a sorted array, how do you find two numbers that add up to a target without a nested loop?
Put one pointer at the start and one at the end. If their sum is too small, move the left pointer right to get a bigger number; if it is too large, move the right pointer left. Each step rules out one value that cannot be part of any answer, so the scan is O(n) time and O(1) space instead of O(n^2) for checking every pair. For a target of 26 the pointers move from 2 and 20 to 11 and 15, and the program prints (11, 15). This only works because the array is sorted; on unsorted input use a hash map, or sort first for O(n log n).
def pair_with_sum(nums, target):
lo, hi = 0, len(nums) - 1
while lo < hi:
total = nums[lo] + nums[hi]
if total == target:
return nums[lo], nums[hi]
if total < target:
lo += 1
else:
hi -= 1
return None
print(pair_with_sum([2, 7, 11, 15, 20], 26))6. A shop in Indore records its daily sales. How do you find the best total over any 3 consecutive days efficiently?
Use a fixed-size sliding window. Compute the sum of the first k days once, then for each new day add the value entering the window and subtract the one leaving it. Each step is O(1), so the whole scan is O(n), compared with O(n * k) for adding up every window from scratch. Here the windows total 18, 17, 23, 12 and 18, so the program prints 23, for the days with 12, 3 and 8. A common mistake is an off-by-one in the element leaving the window, which is nums[i - k]. Also decide what to return when the list is shorter than k.
def max_window_sum(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
best = max(best, window)
return best
sales = [4, 2, 12, 3, 8, 1, 9]
print(max_window_sum(sales, 3))7. How do you solve two-sum in O(n) using a hash map?
Walk the array once and store each value with its index in a dictionary. For every element x, first check whether target - x is already in the dictionary; if it is, you have the pair. Dictionary lookups are O(1) on average, so the total is O(n) time and O(n) space, against O(n^2) for trying every pair. In the example the pair is 1 and 9, so the program prints [3, 4]. Checking before inserting matters: it stops an element from pairing with itself, for example using a single 5 twice when the target is 10.
def two_sum(nums, target):
seen = {}
for i, x in enumerate(nums):
if target - x in seen:
return [seen[target - x], i]
seen[x] = i
return []
print(two_sum([3, 8, 5, 1, 9], 10))8. How does a hash table give O(1) average lookups, and what happens on a collision?
A hash function turns the key into a number that maps to a slot in an internal array, so a lookup jumps straight to the right slot instead of scanning. Two keys can land in the same slot, which is a collision. Chaining keeps a small list per slot; open addressing, which CPython dicts use, probes other slots until it finds the key or an empty one. The table grows when it gets too full, so chains and probe sequences stay short. In the worst case, with many collisions, a lookup degrades to O(n). Keys must be hashable, which is why a list cannot be a dict key but a tuple can.
9. How do you check whether a string of brackets is balanced?
Use a stack. Push every opening bracket; on a closing bracket, the stack must not be empty and its top must be the matching opener, which you pop. At the end the stack must be empty. The program prints True False False: {[()]} closes in the right order, ([)] closes the round bracket while a square one is still open, and (( leaves two openers unmatched. It runs in O(n) time and O(n) space. The usual bugs are popping an empty stack, which raises IndexError in Python, and skipping the final empty check, which wrongly accepts input like ((.
def is_balanced(s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in "([{":
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
print(is_balanced("{[()]}"), is_balanced("([)]"), is_balanced("(("))10. What is the difference between a stack and a queue, and how do you implement each in Python?
A stack is last in, first out: the most recent item leaves first, like undo history or the function call stack. A queue is first in, first out: items leave in arrival order, like print jobs or the frontier in BFS. In Python a plain list is a good stack, with append() and pop() both O(1). Do not use a list as a queue, because pop(0) shifts every element and costs O(n). Use collections.deque with append() and popleft(), both O(1). For a queue shared between threads, use queue.Queue, which does the locking for you.
11. When would you choose a linked list over an array?
Choose a linked list when you insert or delete often at the front or in the middle and already hold a reference to the node there: relinking is O(1), while an array must shift elements, which is O(n). Arrays win at random access, O(1) by index against O(n) for walking a list, and they are far more cache-friendly because their elements sit next to each other in memory. Each list node also carries extra pointer memory. In practice dynamic arrays are the default, and linked lists appear inside other structures such as an LRU cache, or in interviews to test pointer handling.
12. How do you reverse a singly linked list in place?
Walk the list once and turn each next pointer around. You need three references: prev, the part already reversed; the current node; and nxt, saved before you overwrite current.next, or the rest of the list is lost. When the loop ends, prev is the new head, and the program prints [3, 2, 1]. It is O(n) time and O(1) extra space. A recursive version is shorter but uses O(n) stack space, so a long list can hit the recursion limit in Python. Check the empty list and the one-node list too; this loop handles both without special cases.
class Node:
def __init__(self, val, next=None):
self.val, self.next = val, next
def reverse(head):
prev = None
while head:
nxt = head.next
head.next = prev
prev = head
head = nxt
return prev
def to_list(node):
out = []
while node:
out.append(node.val)
node = node.next
return out
print(to_list(reverse(Node(1, Node(2, Node(3))))))13. How do you write a correct binary search, and why is it O(log n)?
Keep a range lo to hi that could still hold the target. Look at the middle: if it is the target, return it; if it is smaller, the target can only be to the right, so set lo = mid + 1; otherwise set hi = mid - 1. Stop when lo passes hi. The program prints 4 -1: 77 is at index 4 and 60 is missing. Each step halves the range, so a million sorted items need at most 20 probes. Classic bugs: while lo < hi with this inclusive range never checks the last candidate, and lo = mid can loop forever. In Java or C++, write mid = lo + (hi - lo) / 2 to avoid overflow.
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
marks = [35, 42, 58, 61, 77, 89, 94]
print(binary_search(marks, 77), binary_search(marks, 60))14. What are preorder, inorder and postorder traversals, and what does each give for this tree?
All three are depth-first, visit every node once and take O(n) time; they differ only in when the node itself is recorded. Preorder records it before its subtrees, inorder between the left and right subtree, and postorder after both. For this tree, with 1 at the root, 2 and 3 below it and 4 and 5 under 2, the program prints pre [1, 2, 4, 5, 3], in [4, 2, 5, 1, 3] and post [4, 5, 2, 3, 1]. Uses: preorder to copy or serialise a tree, inorder to read a BST in sorted order, postorder when children must be handled first, such as computing folder sizes.
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def walk(node, kind, out):
if node is None:
return out
if kind == "pre":
out.append(node.val)
walk(node.left, kind, out)
if kind == "in":
out.append(node.val)
walk(node.right, kind, out)
if kind == "post":
out.append(node.val)
return out
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
for kind in ("pre", "in", "post"):
print(kind, walk(root, kind, []))15. What is a binary search tree, and how fast are search and insert?
In a BST every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger, so a search goes left or right at each node and skips a whole subtree. Search, insert and delete cost O(h), where h is the height. In a balanced tree h is about log n, but inserting sorted data such as 1, 2, 3, 4 builds a chain where h equals n, so operations fall to O(n). That is why libraries use self-balancing trees, such as the red-black tree behind Java TreeMap. An inorder traversal of a BST returns its values in sorted order.
16. What makes a recursive function correct, and what is the risk of deep recursion in Python?
A recursive function needs a base case that returns without recursing, and every recursive call must move towards it, for example with a smaller n or a shorter list. Each call adds a frame to the call stack, holding its local variables until it returns, so recursion depth costs O(depth) memory. CPython stops at a recursion limit, 1000 by default, and raises RecursionError, so a recursive DFS down a 10,000-node chain fails. You can raise the limit with sys.setrecursionlimit, but the safer fix is an explicit stack. A missing base case, or input that does not shrink, is the most common bug.
17. Compare bubble, insertion, merge and quick sort on time, space and stability.
Bubble and insertion sort are O(n^2) in the worst case, sort in place with O(1) extra space and are stable; insertion sort is fast on small or nearly sorted input, close to O(n). Merge sort is O(n log n) in every case and stable, but the usual array version needs O(n) extra space. Quick sort averages O(n log n) and sorts in place, but bad pivots give O(n^2), and the usual versions are not stable. Stable means equal keys keep their original order, which matters when you sort records by one field after another. Python sorted() and list.sort() are stable and O(n log n).
18. How does Python heapq work, and how do you use it as a priority queue?
heapq keeps a plain list arranged as a binary min-heap, so the smallest item is always at index 0. heappush and heappop are O(log n), and reading the minimum is O(1). Tuples compare item by item, so pushing (priority, task) gives a priority queue, and the program prints the tasks in priority order 1, 2, 3. For a max-heap, push negated priorities. Two common mistakes: sorting the list after every push, which wastes time, and pushing tuples whose second item cannot be compared, which raises TypeError on a tie. Add a counter as a tie-breaker, as in (priority, count, task).
import heapq
tasks = []
heapq.heappush(tasks, (3, "send report"))
heapq.heappush(tasks, (1, "fix login bug"))
heapq.heappush(tasks, (2, "review PR"))
while tasks:
priority, name = heapq.heappop(tasks)
print(priority, name)19. What is the difference between BFS and DFS on a graph, and when do you use each?
BFS explores level by level with a queue, so it reaches nodes in order of their distance in edges from the start, which is why it finds shortest paths in an unweighted graph. DFS follows one path as deep as it can before backtracking, using recursion or a stack, and suits cycle detection, topological sort and exploring every path. Both are O(V + E) with an adjacency list. Here BFS visits A, B, C, D, E, F in that order. Mark a node as seen when you add it to the queue, not when you remove it, or the same node can be queued many times.
from collections import deque
def bfs(graph, start):
seen = {start}
order = []
queue = deque([start])
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
if nxt not in seen:
seen.add(nxt)
queue.append(nxt)
return order
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"],
"D": ["F"], "E": ["F"], "F": []}
print(bfs(graph, "A"))20. How should you talk through a coding problem in a campus placement interview?
Start by restating the problem and asking about input size, value ranges, duplicates and empty input. Work through one small example by hand. Then describe a brute-force approach and its complexity before writing anything, and improve it if the constraints need that, naming the data structure you will use and why. Write the code while explaining each part, then trace your example through it and check the edge cases. If you get stuck, say what you are trying, because an interviewer can only give a hint when they know where you are. Silence and rushing into code cost freshers the most.
Ready to check yourself? Take the free Data Structures and Algorithms mock test
Data Structures and Algorithms interview questions: Medium questions (1-3 years)
20 questions21. Why is appending to a Python list amortised O(1) when a resize copies the whole list?
The list keeps spare capacity. When it is full, it allocates a bigger array and copies everything, which is O(n) for that one append, but the capacity grows in proportion to the size, so resizes get rarer as the list grows. If capacity doubled each time, n appends would copy 1 + 2 + 4 + ... elements, fewer than 2n in total, so each append costs O(1) on average. CPython grows by a smaller factor, about 1.125, which still gives amortised O(1). Amortised is a guarantee over any sequence of operations, not an average over random inputs, and a single append can still be slow.
22. How do you find the length of the longest substring without repeating characters?
Use a variable-size sliding window and a dictionary holding the last index of each character. Extend the window one character at a time; if the character was already seen inside the window, move the start just past its previous position. Each character is handled once, so it is O(n). The program prints 8 2: bengalur is the longest run in bengaluru, and aabbcc allows only two. The classic bug is moving the start to last[ch] + 1 even when that old index is before the window, which moves the start backwards; on abba it returns 3 instead of 2. The check last[ch] >= start prevents that.
def longest_unique(s):
last = {}
start = best = 0
for i, ch in enumerate(s):
if ch in last and last[ch] >= start:
start = last[ch] + 1
last[ch] = i
best = max(best, i - start + 1)
return best
print(longest_unique("bengaluru"), longest_unique("aabbcc"))23. How do you count subarrays whose sum equals k when the array has negative numbers?
Use prefix sums with a hash map. If the running total at index j is S and some earlier prefix total was S - k, the elements between them sum to k. So count how often each prefix total has appeared, and at each step add the count of total - k. Seed the map with total 0 seen once, so subarrays that start at index 0 are counted. This is O(n) time and space, and the program prints 3. A sliding window does not work here: with negative numbers, adding an element can make the sum smaller, so there is no rule for when to shrink. Trying every pair is O(n^2).
from collections import defaultdict
def count_subarrays(nums, k):
seen = defaultdict(int)
seen[0] = 1
total = count = 0
for x in nums:
total += x
count += seen[total - k]
seen[total] += 1
return count
print(count_subarrays([3, 4, -7, 3, 1, 3, 1, -4], 7))24. How do you find all unique triplets that sum to zero, and how do you avoid duplicate triplets?
Sort the array, then fix each element in turn and run two pointers on the part to its right, looking for a pair that sums to minus the fixed value. The sort is O(n log n) and each fixed element costs an O(n) scan, so the total is O(n^2), against O(n^3) for three nested loops. Sorting also handles duplicates: skip a fixed element equal to the one before it, and after finding a triplet move both pointers past equal values. A set of tuples also removes duplicates but hides the logic and costs memory. Once the fixed element is positive you can stop, because everything after it is positive too.
25. How do you detect a cycle in a linked list and find the node where the cycle starts?
Use Floyd's method: a slow pointer moves one step at a time and a fast pointer two. Without a cycle, fast reaches the end; with one, they must meet inside it. To find the start, move one pointer back to the head and advance both one step at a time; they meet at the first node of the cycle. Why: when they meet, slow has walked k steps and fast 2k, so k is a multiple of the cycle length, and walking on from the meeting point by the distance from the head to the cycle start lands exactly on the start. The program prints 3. It is O(n) time and O(1) space, unlike a visited set.
class Node:
def __init__(self, val):
self.val, self.next = val, None
def cycle_start(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
slow = head
while slow is not fast:
slow, fast = slow.next, fast.next
return slow
return None
nodes = [Node(v) for v in range(1, 6)]
for a, b in zip(nodes, nodes[1:]):
a.next = b
nodes[-1].next = nodes[2] # 5 links back to 3
print(cycle_start(nodes[0]).val)26. For each day's share price, how do you find the next higher price in O(n)?
Use a monotonic stack holding the indexes of days whose next higher price is not known yet; their prices decrease from bottom to top. For each new price, pop every index with a lower price, because the new price is their answer, then push the new index. Each index is pushed and popped at most once, so the total is O(n), even with a loop inside a loop. The program prints [130, 130, 140, 140, 140, -1, -1]; the days still on the stack at the end never see a higher price and keep -1. The same pattern gives the previous smaller element and the largest rectangle in a histogram.
def next_higher(prices):
result = [-1] * len(prices)
stack = [] # indexes still waiting
for i, p in enumerate(prices):
while stack and prices[stack[-1]] < p:
result[stack.pop()] = p
stack.append(i)
return result
print(next_higher([120, 115, 130, 125, 118, 140, 135]))27. How do you print a binary tree level by level?
Run BFS with a queue and handle one level at a time: read len(queue) before the inner loop, because exactly that many nodes belong to the current level. Pop each of them, record its value and push its children, which form the next level. The program prints [[1], [2, 3], [4, 5, 6]]. It is O(n) time, and the queue holds at most one level plus part of the next, which is about n/2 nodes in a complete tree. The same skeleton gives the right-side view, the level with the largest sum and zigzag order. Using a list with pop(0) instead of deque makes each pop O(n).
from collections import deque
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def level_order(root):
if root is None:
return []
levels, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
levels.append(level)
return levels
T = TreeNode
root = T(1, T(2, T(4)), T(3, T(5), T(6)))
print(level_order(root))28. How do you check whether a binary tree is a valid BST, and what is the common wrong approach?
Checking only that each left child is smaller and each right child larger is not enough, because the rule covers whole subtrees. In this tree 6 is a fine left child of 15, but it sits in the right subtree of 10, so the tree is not a BST, and a child-only check wrongly accepts it. The fix is to pass down the allowed range: going left, the node value becomes the upper bound; going right, it becomes the lower bound. The program prints False. It is O(n) time and O(h) stack space. An inorder walk that checks the values strictly increase also works. Ask how duplicates are treated.
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def is_bst(node, low=float("-inf"), high=float("inf")):
if node is None:
return True
if not low < node.val < high:
return False
return (is_bst(node.left, low, node.val) and
is_bst(node.right, node.val, high))
# 10
# / \
# 5 15
# / \
# 6 20
root = T(10, T(5), T(15, T(6), T(20)))
print(is_bst(root))29. How do you find the lowest common ancestor of two nodes in a binary tree?
Recurse from the root. If the current node is empty or is one of the two targets, return it. Otherwise ask the left and right subtrees. If both return a node, the targets are on different sides, so the current node is the lowest common ancestor; if only one side returns a node, pass it up. Each node is visited once, so it is O(n) time and O(h) stack space. This assumes both nodes are in the tree; if one may be missing, track whether each was really found. In a BST it is simpler: walk down from the root while both values are on the same side, and the first split point is the answer, in O(h).
30. How do you get the top k scores from a large list without sorting all of it?
Keep a min-heap of size k. Push each score, and when the heap grows past k, pop the smallest, so the heap always holds the k largest seen so far and its top is the smallest of them. That is O(n log k) time and O(k) memory, better than an O(n log n) sort when k is small, and it works on a stream too large to hold in memory. The program prints [99, 94, 90]. In real code heapq.nlargest(k, scores) does the same job. A common mistake is heapifying all n scores as a max-heap and popping k times, which needs O(n) memory and cannot handle a stream.
import heapq
def k_largest(nums, k):
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap)
return sorted(heap, reverse=True)
scores = [71, 94, 58, 88, 99, 63, 90]
print(k_largest(scores, 3))31. How do you generate all subsets of a list with backtracking?
In each call, record the current path as one subset, then try adding each remaining item from the start index on, recurse with the next index, and remove the item again, which is the backtrack step. The start index means each combination is built only once, in one order, so b, a never appears next to a, b. For three items the program prints all 8 subsets, from the empty one to a, b, c. There are 2^n subsets and copying each costs up to n, so it is O(n * 2^n) time. The classic bug is appending path instead of path[:]: every entry is then the same list, which is empty at the end.
def subsets(items):
result, path = [], []
def backtrack(start):
result.append(path[:])
for i in range(start, len(items)):
path.append(items[i])
backtrack(i + 1)
path.pop()
backtrack(0)
return result
print(subsets(["a", "b", "c"]))32. How does sorting with a key work in Python, and why does stability matter in real code?
sorted() and list.sort() take a key function, call it once per element and compare the keys instead of the items. To sort candidates by score descending and then by name, use key=lambda c: (-c.score, c.name). Python sorting is stable, so you can also sort in two passes: first by the secondary key, then by the primary key, and ties keep the earlier order. CPython uses an adaptive merge sort, Timsort, which is O(n log n) in the worst case and close to O(n) on nearly sorted data. Negating a string for descending order raises TypeError; use reverse=True or two stable passes instead.
33. A courier in Pune must deliver parcels in a fixed order within D days. How do you find the smallest van capacity that works?
Binary search on the answer. The capacity lies between the heaviest parcel and the total weight, and the check is monotonic: if a capacity works, every larger one works too. So search that range, and for each candidate count the days needed greedily, starting a new day when the next parcel does not fit. Keep the smallest that fits; for 3 days the program prints 14. It costs O(n log S) for total weight S. Use this pattern when asked for the smallest or largest value that passes a yes or no test. Starting lo at 1 is a bug: a capacity below the heaviest parcel can look feasible.
def min_capacity(parcels, days):
def days_needed(cap):
used, load = 1, 0
for w in parcels:
if load + w > cap:
used, load = used + 1, 0
load += w
return used
lo, hi = max(parcels), sum(parcels)
while lo < hi:
mid = (lo + hi) // 2
if days_needed(mid) <= days:
hi = mid
else:
lo = mid + 1
return lo
print(min_capacity([8, 3, 5, 9, 4, 6, 2], 3))34. How do you count separate islands of land in a grid?
Treat each land cell as a node joined to its four neighbours and count connected components. Scan the grid; each time you find land that is not yet visited, add one to the count and flood-fill that whole island with DFS or BFS, marking cells as visited. Each cell is handled a constant number of times, so it is O(rows * cols) time and space. The program prints 3. It uses an explicit stack, not recursion, because a large island can exceed the recursion limit in Python. A common bug is checking bounds after indexing: a negative index in Python silently wraps around.
def count_islands(grid):
rows, cols = len(grid), len(grid[0])
seen = set()
def flood(r, c):
stack = [(r, c)]
seen.add((r, c))
while stack:
x, y = stack.pop()
for nx, ny in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
if (0 <= nx < rows and 0 <= ny < cols and
grid[nx][ny] == "1" and (nx, ny) not in seen):
seen.add((nx, ny))
stack.append((nx, ny))
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1" and (r, c) not in seen:
flood(r, c)
count += 1
return count
grid = ["11000",
"11010",
"00011",
"10000"]
print(count_islands(grid))35. How do you find a valid build order for services that depend on each other?
Model each dependency, a before b, as a directed edge from a to b and run a topological sort. Kahn's algorithm counts the incoming edges of each node, starts with nodes that have none, and each time it removes a node it lowers the count of its neighbours, queueing any that reach zero. It is O(V + E). The program prints db, auth, api, ui, tests in that order. If fewer nodes come out than went in, the rest form a cycle and no order exists, so the second call, where tests must come before db, prints None. The order is not unique when several nodes are ready at once.
from collections import deque
def build_order(tasks, deps):
indeg = {t: 0 for t in tasks}
nxt = {t: [] for t in tasks}
for before, after in deps:
nxt[before].append(after)
indeg[after] += 1
queue = deque(t for t in tasks if indeg[t] == 0)
order = []
while queue:
t = queue.popleft()
order.append(t)
for u in nxt[t]:
indeg[u] -= 1
if indeg[u] == 0:
queue.append(u)
return order if len(order) == len(tasks) else None
tasks = ["db", "auth", "api", "ui", "tests"]
deps = [("db", "auth"), ("db", "api"), ("auth", "api"),
("api", "ui"), ("ui", "tests"), ("api", "tests")]
print(build_order(tasks, deps))
print(build_order(tasks, deps + [("tests", "db")]))36. When is BFS enough for shortest paths, and when do you need Dijkstra?
BFS gives shortest paths when every edge costs the same, such as moves on a grid or hops in a network, because it reaches nodes in order of their number of edges. Once edges have different non-negative weights, such as road lengths or travel times, a path with fewer edges can be longer, so you need Dijkstra, which always expands the closest unfinished node from a priority queue, in O((V + E) log V) with a binary heap. If weights are only 0 or 1, a deque-based 0-1 BFS gives O(V + E). With negative weights neither works, and you need Bellman-Ford. Name the weight type first.
37. Why does greedy fail for minimum coins, and how does DP solve it?
Greedy takes the largest coin that fits. That happens to be optimal for Indian denominations such as 1, 2, 5, 10, 20, 50, 100, 200 and 500, but not for every set: with coins 1, 3 and 4 and amount 6, greedy picks 4, 1 and 1, while 3 and 3 needs only two coins. DP builds the answer for every amount from 0 up: dp[a] is 1 plus the minimum of dp[a - c] over the coins c that fit. The program prints 2 -1, since 3 cannot be made from 5 and 10. It is O(amount * number of coins) time and O(amount) space. Start unreachable amounts at infinity, not 0.
def min_coins(coins, amount):
INF = float("inf")
dp = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a and dp[a - c] + 1 < dp[a]:
dp[a] = dp[a - c] + 1
return dp[amount] if dp[amount] != INF else -1
print(min_coins([1, 3, 4], 6), min_coins([5, 10], 3))38. How do you recognise a DP problem, and what is the difference between memoization and tabulation?
Look for two signs: the answer can be built from answers to smaller versions of the same problem, and plain recursion would solve the same subproblems again and again. Words like minimum cost, number of ways or longest are hints. Memoization is top-down: write the recursion and cache each result, for example with functools.lru_cache, so each state is computed once. Tabulation is bottom-up: fill a table from the smallest states in a fixed order, which avoids recursion depth limits and often lets you keep only the last row. Define the state and the transition before coding.
39. How do you fit the most meetings into one conference room?
Sort the meetings by end time and take each one that starts no earlier than the last chosen one ends. Finishing early leaves the most room for the rest; an exchange argument proves it, since any best schedule can swap its first meeting for the earliest-ending one. The program prints 3, and the sort makes it O(n log n). Sorting by start time fails: with (8, 17), (9, 10) and (11, 12) it takes only the long meeting, while two fit. Sorting by length also fails: with (1, 5), (4, 7) and (6, 10) the shortest meeting blocks both others. Ask whether back-to-back meetings are allowed.
def max_meetings(meetings):
count, free_at = 0, float("-inf")
for start, end in sorted(meetings, key=lambda m: m[1]):
if start >= free_at:
count += 1
free_at = end
return count
slots = [(9, 12), (10, 11), (11, 13), (12, 14), (13, 15), (14, 16)]
print(max_meetings(slots))40. Your solution passes the sample tests but gets Time Limit Exceeded on the hidden ones. What do you do?
Reread the constraints and estimate: with n up to 100,000, an O(n^2) solution is about 10^10 steps and cannot pass, so you need O(n log n) or better. Then look for hidden costs inside loops: the in operator on a list, list.pop(0), slicing, string concatenation or sorting inside a loop. Replace them with a set or dict lookup, a deque, index arithmetic or a single sort. If the algorithm is already right, check input reading: in Python, calling input() for many lines is slow, and reading from sys.stdin is much faster. Finally, test locally with a generated worst-case input before resubmitting.
Ready to check yourself? Take the free Data Structures and Algorithms mock test
Data Structures and Algorithms interview questions: Hard questions (experienced)
20 questions41. How do you solve 0/1 knapsack in O(capacity) memory, and why must the inner loop run backwards?
dp[c] holds the best value for capacity c using the items seen so far. For each item, set dp[c] = max(dp[c], dp[c - w] + v). Running c from high to low means dp[c - w] still holds the value from before this item, so each item is used at most once. If you loop upwards, dp[c - w] may already include the same item, which solves unbounded knapsack instead. For capacity 8 the program prints 130 (weights 3 and 5); the upward loop returns 160 by taking the 2 kg item four times. Time is O(n * capacity), which is pseudo-polynomial and useless for a capacity like 10^9.
def knapsack(weights, values, cap):
dp = [0] * (cap + 1)
for w, v in zip(weights, values):
for c in range(cap, w - 1, -1): # high to low
dp[c] = max(dp[c], dp[c - w] + v)
return dp[cap]
print(knapsack([2, 3, 4, 5], [40, 50, 65, 80], 8))42. How does edit distance work, and how would you use it to match misspelt city names?
Edit distance is the fewest single-character inserts, deletes and replacements that 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 the last characters match, it equals dp[i - 1][j - 1]; otherwise 1 plus the best of delete, insert and replace. The program prints 3 for bangalore and bengaluru. Each row needs only the previous one, so it is O(m * n) time and O(n) space. For city search, lowercase first, rank names by distance, and skip names whose length differs by more than your limit, since the distance is at least that gap.
def edit_distance(a, b):
prev = list(range(len(b) + 1))
for i in range(1, len(a) + 1):
cur = [i] + [0] * len(b)
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
prev = cur
return prev[-1]
print(edit_distance("bangalore", "bengaluru"))43. How do you find the length of the longest increasing subsequence in O(n log n)?
Keep a list tails where tails[i] is the smallest possible last value of an increasing subsequence of length i + 1. For each number, binary search for the first tail that is not smaller: if there is none, append the number, which extends the longest subsequence; otherwise replace that tail with the smaller number. tails stays sorted, so each step is O(log n). The program prints 4, for example 2, 3, 6, 9. Explain the O(n^2) DP first. Two traps: tails itself is not always a real subsequence, so rebuilding one needs parent indexes, and non-decreasing runs need bisect_right.
from bisect import bisect_left
def lis_length(nums):
tails = []
for x in nums:
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x
return len(tails)
print(lis_length([5, 2, 8, 6, 3, 6, 9, 7]))44. Implement Dijkstra with a heap. Why does it skip stale entries, and why does it fail with negative edges?
Python heapq has no decrease-key, so when a shorter distance is found the code pushes a new entry and leaves the old one in the heap. When the old one is popped later, its distance is larger than the recorded one, so it is skipped. This lazy deletion keeps the cost at O((V + E) log V). With these made-up road lengths, Satara gets 95 via Lonavala, not 110 direct, and Kolhapur 215. Dijkstra assumes that once the closest node is popped its distance is final, which holds only when no edge is negative. With negative weights, use Bellman-Ford.
import heapq
def dijkstra(graph, src):
dist = {src: 0}
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry
for v, w in graph[u]:
nd = d + w
if nd < dist.get(v, float("inf")):
dist[v] = nd
heapq.heappush(heap, (nd, v))
return dist
roads = {"Pune": [("Lonavala", 65), ("Satara", 110)],
"Lonavala": [("Mumbai", 85), ("Satara", 30)],
"Satara": [("Kolhapur", 120)],
"Mumbai": [("Kolhapur", 380)],
"Kolhapur": []}
print(dijkstra(roads, "Pune"))45. When would you use Bellman-Ford or Floyd-Warshall instead of Dijkstra?
Bellman-Ford relaxes every edge V - 1 times, which is O(V * E), slower than Dijkstra but correct with negative edge weights. If one more round still improves a distance, there is a negative cycle reachable from the source, so shortest paths are undefined; currency arbitrage problems use this check. Floyd-Warshall finds shortest paths between all pairs in O(V^3) time and O(V^2) memory, a good fit for a few hundred nodes when you need every pair. For all pairs on a large sparse graph with non-negative weights, running Dijkstra from every node is usually faster. Let the weights decide.
46. How does Union-Find work, and how does it make Kruskal's minimum spanning tree efficient?
Union-Find keeps each group as a tree of parent links: find walks to the root, and union joins two roots. Two tricks make it fast: path compression, here path halving, which points nodes nearer the root during find, and union by size, which hangs the smaller tree under the larger. Together they give O(alpha(n)) amortised per operation, effectively constant. Kruskal sorts the edges by weight and keeps each edge whose ends are in different groups; union returning False means the edge would close a cycle. For cabling five offices the program prints 14. The sort dominates: O(E log E).
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
def mst_cost(n, edges):
dsu, total = DSU(n), 0
for w, a, b in sorted(edges):
if dsu.union(a, b):
total += w
return total
cables = [(4, 0, 1), (8, 0, 2), (2, 1, 2), (6, 1, 3),
(3, 2, 3), (9, 3, 4), (5, 2, 4)]
print(mst_cost(5, cables))47. Several servers in a data centre grid fail at once, and each minute the failure spreads to their neighbours. How do you find when the last server fails?
Use multi-source BFS: put every failed server in the queue at time 0 and run one BFS. Because all sources start in the same layer, each healthy server is reached from its nearest failed one, and the last layer reached gives the time. This is O(rows * cols), whereas a separate BFS from each of k failed servers costs O(k * rows * cols). Afterwards, check whether any healthy server was never reached and return -1 if so. Common bugs are marking cells when popped instead of when pushed, which queues them twice, and counting an extra minute at the end.
48. How do you keep the running median of delivery times as each order completes?
Keep two heaps: a max-heap with the smaller half and a min-heap with the larger half, letting the smaller half hold one extra value. Python has only a min-heap, so the smaller half stores negated values. Each new value goes into the smaller half, its largest moves across, and if the larger half becomes bigger one value moves back. The median is the top of the smaller half, or the average of both tops. Each add is O(log n) and median() is O(1). The program prints [42, 30.0, 42, 33.5, 42]. Keeping a sorted list with bisect.insort avoids a full sort but still shifts O(n) elements per insert.
import heapq
class RunningMedian:
def __init__(self):
self.low = [] # max-heap of the smaller half (negated)
self.high = [] # min-heap of the larger half
def add(self, x):
heapq.heappush(self.low, -x)
heapq.heappush(self.high, -heapq.heappop(self.low))
if len(self.high) > len(self.low):
heapq.heappush(self.low, -heapq.heappop(self.high))
def median(self):
if len(self.low) > len(self.high):
return -self.low[0]
return (-self.low[0] + self.high[0]) / 2
rm, out = RunningMedian(), []
for minutes in [42, 18, 77, 25, 60]:
rm.add(minutes)
out.append(rm.median())
print(out)49. Why is building a heap from n items O(n) and not O(n log n)?
heapify works bottom-up: it sifts down each non-leaf node, from the last parent back to the root. A sift-down costs at most the node's height, and most nodes are near the bottom: about half are leaves with height 0, a quarter have height 1, and so on. The total is the sum over heights h of about h * n / 2^(h + 1), which adds up to about n, so heapify is O(n). Pushing the items one by one is O(n log n) in the worst case, because each push can sift up the full height. That is why heapq.heapify beats n heappush calls, and why heap sort is still O(n log n): the n pops cost log n each.
50. Hash map operations are called O(1). When is that not true, and how does Python protect against attacks on it?
O(1) is the average with a good hash and a bounded load factor. If many keys collide, each lookup compares against all of them, and n inserts can cost O(n^2) in total. Attackers have exploited this with web requests carrying thousands of colliding keys, a hash-flooding denial of service. Since Python 3.3, hashes of str and bytes are randomised per process, controlled by PYTHONHASHSEED, so collisions cannot be planned. Integers are not randomised: hash(n) equals n for small non-negative integers. Resizing also makes an occasional insert O(n), fine amortised but visible in latency.
51. Design an LRU cache with O(1) get and put.
You need fast lookup by key, plus a fast way to move an entry to the most-recent end and to evict from the least-recent end. A hash map from key to a node in a doubly linked list does both in O(1): the map finds the node, and the list unlinks and relinks it in constant time. Python OrderedDict is that pair, with move_to_end and popitem(last=False). After reading u1 and adding u3, the program shows u1 and u3 cached and prints -1 for the evicted u2. If asked to build the list by hand, use dummy head and tail nodes to avoid null checks; add a lock if threads share it.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.data = OrderedDict()
def get(self, key):
if key not in self.data:
return -1
self.data.move_to_end(key)
return self.data[key]
def put(self, key, value):
if key in self.data:
self.data.move_to_end(key)
self.data[key] = value
if len(self.data) > self.capacity:
self.data.popitem(last=False)
cache = LRUCache(2)
cache.put("u1", "Asha")
cache.put("u2", "Ravi")
cache.get("u1")
cache.put("u3", "Meena")
print(list(cache.data), cache.get("u2"))52. How would you build autocomplete for place names with a trie, and what does it cost?
A trie stores strings character by character, so words that share a prefix share a path from the root. Insert and prefix lookup cost O(L) for a string of length L, however many words are stored; listing the suggestions then costs the size of the subtree under the prefix. Here each node is a dict, and the $ key marks the end of a word. The program prints pune, punjab and puri for pu, and an empty list for x. Real autocomplete also stores a popularity score and keeps only the top few suggestions at each node. Tries use a lot of memory; for a fixed list, bisect on a sorted list is simpler.
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {})
node["$"] = True # end of a word
def starts_with(self, prefix):
node = self.root
for ch in prefix:
if ch not in node:
return []
node = node[ch]
out, stack = [], [(node, prefix)]
while stack:
node, word = stack.pop()
for ch, child in node.items():
if ch == "$":
out.append(word)
else:
stack.append((child, word + ch))
return sorted(out)
t = Trie()
for place in ["pune", "punjab", "puri", "patna", "pondicherry"]:
t.insert(place)
print(t.starts_with("pu"), t.starts_with("x"))53. How do you count N-Queens solutions, and how does pruning keep backtracking practical?
Place one queen per row, so rows never clash, and in each row try only columns that are not attacked. Three sets record the used columns and both diagonals: cells on one diagonal share r - c, and on the other they share r + c, so the safety check is O(1) instead of a scan of the board. After the recursive call, remove the queen so the next column starts clean. The program prints [1, 0, 0, 2, 10, 4, 40, 92] for n = 1 to 8. Pruning cuts a branch the moment a placement is unsafe: for n = 8 the search makes 2,057 calls, instead of trying all 8^8, about 16.8 million, placements.
def count_queens(n):
cols, diag, anti = set(), set(), set()
def place(r):
if r == n:
return 1
total = 0
for c in range(n):
if c in cols or r - c in diag or r + c in anti:
continue
cols.add(c)
diag.add(r - c)
anti.add(r + c)
total += place(r + 1)
cols.remove(c)
diag.remove(r - c)
anti.remove(r + c)
return total
return place(0)
print([count_queens(n) for n in range(1, 9)])54. How do you find the maximum of every window of size k in O(n)?
Keep a deque of indexes whose values decrease from front to back. For each new element, pop from the back every index whose value is less than or equal to it, since those can never be a window maximum again, then append the new index. Pop from the front if that index has slid out of the window. The front then always holds the current maximum. Every index enters and leaves the deque at most once, so the total is O(n), against O(n * k) for scanning each window. The program prints [9, 9, 7, 7, 7, 8]. Store indexes, not values, or you cannot tell when the front has left the window.
from collections import deque
def window_max(nums, k):
dq, out = deque(), [] # indexes, values decreasing
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
out.append(nums[dq[0]])
return out
print(window_max([3, 9, 4, 2, 7, 1, 5, 8], 3))55. How do you search a rotated sorted array, and what changes when it has duplicates?
In a sorted array rotated at an unknown point, such as 40, 50, 60, 10, 20, 30, at least one half around mid is always sorted. Compare nums[lo] with nums[mid] to see which half is sorted, check whether the target lies inside that half, and discard the other half if it does; otherwise discard the sorted half. That keeps O(log n). With duplicates, nums[lo], nums[mid] and nums[hi] can all be equal, as in 2, 2, 2, 3, 2, and you cannot tell which side is sorted. The usual fix is to move lo up and hi down by one, which is correct but makes the worst case O(n). Say this trade-off out loud.
56. Python has no tail-call optimisation. How do you handle recursion that may go 100,000 levels deep?
CPython keeps every frame until the call returns and stops at a recursion limit, 1000 by default. A tail-recursive rewrite does not help, because CPython never reuses the frame. Raising the limit with sys.setrecursionlimit is fragile: frames still cost memory, and before Python 3.11 deep recursion could crash on a C stack overflow. The reliable fix is a loop with an explicit stack: push the start, pop, process, push the children. For post-order work such as subtree sizes, push each node twice with a visited flag, or reverse the visit order. C++ and Java hit the same wall as a stack overflow.
57. Why is quicksort O(n^2) in the worst case, and how does quickselect find the kth largest in O(n) on average?
Quicksort partitions the array around a pivot. If the pivot is always the smallest or largest element, as with a first-element pivot on sorted input, each partition removes just one element, so the work is n + (n - 1) + ... + 1, which is O(n^2), with recursion n deep. A random pivot makes this very unlikely and gives O(n log n) expected time. Quickselect partitions the same way but recurses only into the side that holds the kth position, so the expected work is n + n/2 + n/4 + ..., which is O(n). Its worst case is still O(n^2); median of medians guarantees O(n) but is slower in practice.
58. How do you convince an interviewer that a greedy algorithm is correct?
Give an exchange argument: take any optimal solution, show it can be changed step by step to agree with the greedy choice without getting worse, and conclude that greedy is optimal too. For meeting scheduling, the first meeting of an optimal schedule can be swapped for the one that ends earliest, because that leaves at least as much time for the rest. Or show greedy stays ahead at every step. Before arguing, try to break your greedy on small cases; a brute-force checker on random inputs finds holes fastest. If you find a counterexample, such as coins 1, 3 and 4 for amount 6, switch to DP.
59. The input can have 200,000 items and the time limit is 1 second. How do you choose the target complexity?
Use the rough rule that compiled code does about 10^8 simple operations per second, and Python nearer 10^7. With n = 200,000, O(n^2) is 4 * 10^10 operations, far too slow, while n log n is about 3.5 million, which fits easily, so aim for O(n log n) or O(n). For compiled code it works backwards too: n up to about 20 hints at exponential backtracking or bitmask DP, a few hundred allows O(n^3), and a few thousand allows O(n^2). In Python, lean on built-ins such as sorted, sum and set operations, which run in C. Check memory too: 200,000 integers is fine, but an n by n table is not.
60. As an experienced candidate, how do you handle a follow-up such as "what if the data does not fit in memory?"
Say what changes first: the algorithm must stream the data or work in chunks. For sorting, use an external merge sort: sort chunks that fit in memory, write them to disk, then merge them with a heap whose size is the number of chunks. For the top k items, keep a heap of size k while streaming. For approximate distinct counts or frequent items, mention HyperLogLog or a count-min sketch, which trade exactness for memory. For data spread over machines, partition by a hash of the key so each machine handles its share. Each time, state the trade-off: memory, accuracy or passes over the data.
Practice questions for November 2026
New every month3 questions from the Data Structures and Algorithms mock test, the way they appear in it. A new set comes on the 1st of every month. Pick your answer, then open it.
-
How much extra memory (auxiliary space) does squares(a) use for a list of n numbers?
def squares(a): return [x * x for x in a]- O(n), for the new list it returns
- O(n^2)
- O(log n)
- O(1), because there is no explicit loop
Show the answer
Answer: O(n), for the new list it returns. The list comprehension builds a brand-new list with one entry per input item, so memory grows linearly with n. A comprehension is still a loop; O(1) extra space needs overwriting a in place or yielding the values one at a time.
-
Keys 50, 30, 70, 60, 80, 65 are inserted into an empty BST. Then 50 is deleted by replacing it with its inorder successor. What is the preorder traversal afterwards?
- 60, 30, 70, 65, 80
- 65, 30, 70, 60, 80
- 50, 30, 70, 60, 65, 80
- 30, 70, 60, 65, 80
Show the answer
Answer: 60, 30, 70, 65, 80. The inorder successor of 50 is the smallest key in its right subtree, 60. 60 moves up to the root and its right child 65 takes 60's old place under 70. The tree stays a valid BST: 60, then 30, then 70 with children 65 and 80.
-
A linked list 1 -> 2 -> ... -> 8 is reversed in groups of 3 nodes, and a final group with fewer than 3 nodes is left as it is. What is the resulting order?
- [2, 1, 4, 3, 6, 5, 8, 7]
- [3, 2, 1, 6, 5, 4, 8, 7]
- [8, 7, 6, 5, 4, 3, 2, 1]
- [3, 2, 1, 6, 5, 4, 7, 8]
Show the answer
Answer: [3, 2, 1, 6, 5, 4, 7, 8]. The groups are (1, 2, 3), (4, 5, 6) and the short group (7, 8). The two full groups are reversed and linked to each other, giving 3 2 1 6 5 4, and 7 8 keeps its order. The whole job is O(n) time with O(1) extra space.
Ready to apply?
There are 17,463 open IT jobs on CoreHRx right now. Create a free profile once and apply with it.