Data Structures and Algorithms Interview Questions for Freshers
40 questions with answers for candidates with Freshers — 29 easy, 11 medium.
What interviewers expect: freshers
Freshers face an online assessment with two to four coding problems of easy to medium difficulty, often with aptitude questions, followed by one or two technical interviews. Expect arrays, strings, hashing, linked lists, trees and basic recursion, plus questions on complexity. Interviewers value clear thinking, a working brute-force solution improved step by step and well-explained college projects.
This set is weighted towards Linked Lists, Stacks and Queues (9), Sorting, Searching and Backtracking (7), Arrays, Strings and Hashing (5), Heaps, Priority Queues and Greedy (5).
Arrays, strings and hashing Linked lists and stacks Tree traversals Complexity analysis
Solved at this levelStart 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.
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
02
Write an iterative binary search that returns the index of a target or -1.
// Java
static int binarySearch(int[] a, int target) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // avoids overflow
if (a[mid] == target) return mid;
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// O(log n) time, O(1) space
03
What are the ways to represent a graph and when would you use each?
An adjacency list stores, for each vertex, a list of neighbours, using O(V plus E) memory; it is best for sparse graphs such as road or social networks and makes iterating neighbours fast. An adjacency matrix uses a V by V grid, O(V squared) memory, with O(1) edge checks; it suits dense or small graphs and Floyd-Warshall. An edge list is a simple list of pairs, convenient for Kruskal's algorithm.
A queue is first-in, first-out with enqueue at the back and dequeue at the front, used in BFS, task scheduling and buffering. A deque allows insertion and removal at both ends in O(1), as in Python collections.deque or Java ArrayDeque. A circular queue uses a fixed array with head and tail indices that wrap around modulo capacity, avoiding shifting and wasted space, common in ring buffers and OS schedulers.
05
What is dynamic programming, and what are overlapping subproblems and optimal substructure?
Dynamic programming solves a problem by combining solutions of smaller subproblems and storing them so each is computed only once. It applies when a problem has overlapping subproblems, meaning the same smaller problems repeat, as in Fibonacci, and optimal substructure, meaning the best answer can be built from best answers to subproblems, as in shortest paths. DP often turns exponential brute force into polynomial time.
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
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.
Situation: in my final-year project a teammate missed several deadlines. Task: complete the project without conflict. Action: I spoke to him privately and learned he struggled with the graph algorithms part. We swapped tasks so he took the UI, and I paired with him for an hour on the core logic. I also set up a weekly checklist for everyone. Result: we submitted on time and he presented the UI section confidently.
10
What is the difference between a static array and a dynamic array?
A static array has a fixed size set at creation, such as int[] in Java, and offers O(1) index access with contiguous memory. A dynamic array such as Java ArrayList or Python list grows automatically by allocating a larger block and copying elements, giving amortised O(1) append. Both have O(n) insertion or deletion in the middle because elements must shift. Dynamic arrays trade a little memory for flexibility.
11
Merge two sorted linked lists into one sorted list.
class ListNode:
def __init__(self, val=0, nxt=None):
self.val = val
self.next = nxt
def merge(a, b):
dummy = tail = ListNode()
while a and b:
if a.val <= b.val:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b
return dummy.next
# O(m + n) time, O(1) extra space
Backtracking builds a solution step by step and abandons a partial solution as soon as it cannot lead to a valid answer, then undoes the last choice and tries the next. It is a DFS over the space of choices. It solves permutations, combinations, subsets, N-Queens, Sudoku and word search. The worst case is often exponential, so good pruning, such as checking constraints early, is what makes it practical.
A singly linked list node points only to the next node, using less memory but allowing traversal in one direction. A doubly linked list node also points to the previous node, enabling backward traversal and O(1) deletion of a given node, which LRU caches need. A circular list connects the last node back to the first, useful for round-robin scheduling and buffers. Each extra pointer adds memory and update complexity.
14
Explain the sliding window technique with fixed and variable windows.
A sliding window keeps a contiguous range and updates its result incrementally instead of recomputing. A fixed window of size k, such as the maximum sum of k consecutive elements, adds the new element and removes the old one each step in O(n). A variable window grows the right end and shrinks the left end while a condition is violated, as in the longest substring without repeating characters. Both turn O(n squared) into O(n).
15
Why do you want to work at a product company as a software engineer?
Situation: during my internship I worked on a feature used by thousands of people and saw how algorithm choices changed response times. Task: I want a role where engineering quality directly affects users. Action: I have practised data structures, system basics and clean coding, and built projects end to end. Result: I believe a product company will let me own features, learn from strong engineers and see the real impact of my work.
16
How does binary search work and what does it require?
Binary search works on sorted data or any monotonic condition. Compare the middle element with the target; if equal, return it, if the target is smaller search the left half, otherwise the right half. Each step halves the search space, giving O(log n) time, so a million elements need about 20 comparisons. It requires random access, so it suits arrays but not linked lists.
17
Compute the integer square root of a number using binary search.
def int_sqrt(x):
lo, hi = 0, x
ans = 0
while lo <= hi:
mid = (lo + hi) // 2
if mid * mid <= x:
ans = mid # mid is a valid candidate
lo = mid + 1
else:
hi = mid - 1
return ans
# int_sqrt(8) -> 2, int_sqrt(16) -> 4; O(log x)
18
In a company org chart stored as a tree, how would you find the closest common manager of two employees?
This is the lowest common ancestor problem. If each employee stores a parent pointer, collect the ancestors of the first employee in a set and walk up from the second until a match is found, O(h). Without parent pointers, use the recursive LCA on the tree from the CEO, O(n). For many repeated queries on a large chart, preprocess with binary lifting to answer each query in O(log n).
19
What is the difference between full, complete and perfect binary trees?
In a full binary tree every node has zero or two children. In a complete binary tree every level except possibly the last is completely filled, and the last level is filled from the left, which is exactly the shape of a binary heap and allows array storage. A perfect binary tree has all internal nodes with two children and all leaves at the same level, containing 2 to the power h plus 1, minus 1 nodes.
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
21
Tell me about a time you had to make a decision with incomplete information.
Situation: during a release, a performance test showed occasional slow responses but the logs were incomplete. Task: decide whether to ship on schedule. Action: I listed what we knew, estimated the impact using the available percentiles, proposed shipping behind a feature flag with extra monitoring, and prepared a rollback plan. Result: we shipped on time, the extra metrics revealed a slow cache warm-up that we fixed in the next patch with no user complaints.
22
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).
23
Check whether a string is a palindrome, ignoring case and non-alphanumeric characters.
BFS explores level by level with a queue and finds shortest paths in unweighted graphs, such as minimum moves on a board. DFS goes as deep as possible with recursion or a stack and suits cycle detection, topological sorting, connected components, path existence and backtracking. Both run in O(V plus E). BFS can use more memory on wide graphs, while DFS can hit recursion limits on deep ones.
25
A satellite image is a grid of land and water cells. How do you count the islands?
Treat each land cell as a vertex connected to its four neighbours that are also land. Scan the grid; when you find unvisited land, increase the island count and run DFS or BFS to mark the whole connected island as visited. Each cell is visited once, so the time is O(rows times columns). Use BFS or an explicit stack for very large grids to avoid recursion limits, or Union-Find if cells arrive over time.
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.
27
A warehouse robot moves only right or down on a grid with some blocked cells. How do you count the number of paths?
Use DP where dp[r][c] is the number of ways to reach cell r, c. A blocked cell has 0 ways; the start has 1; every other cell is dp[r-1][c] plus dp[r][c-1]. Fill row by row in O(rows times columns), and keep a single row array to use O(columns) space. Counts can become huge, so problems often ask for the result modulo 10 to the power 9 plus 7.
28
How can you reduce the space used by a DP solution?
If each row of the table depends only on the previous row, keep two rows or even a single array, reducing O(n times m) space to O(m). Fibonacci-like problems need only the last two values, so O(1). For 0/1 knapsack in one array, iterate capacity from high to low so each item is used once; for unbounded knapsack iterate low to high. The trade-off is that reconstructing the actual solution becomes harder.
29
Users enter formulas with brackets in a spreadsheet tool. How do you validate that the brackets are balanced?
Scan the formula once with a stack. Push every opening bracket; on a closing bracket, check that the stack is not empty and its top is the matching opening type, then pop. Ignore other characters. At the end the stack must be empty. This is O(n) time and handles nested mixes such as parentheses inside square brackets. To show useful errors, record the position of the first mismatch or unclosed bracket.
30
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).
31
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.
32
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.
33
Find the kth largest element in an array using a heap.
import heapq
def kth_largest(nums, k):
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap) # drop the smallest
return heap[0] # smallest of the k largest
# kth_largest([3, 2, 1, 5, 6, 4], 2) -> 5
# O(n log k) time, O(k) space; quickselect gives O(n) average
34
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.
35
What is time complexity and what does Big-O notation mean?
Time complexity describes how the number of steps an algorithm performs grows as the input size n grows, ignoring machine speed. Big-O gives an upper bound on that growth for large n and drops constants and lower terms, so 3n squared plus 5n becomes O(n squared). It lets you compare approaches before coding; for example binary search at O(log n) beats linear search at O(n) on large sorted data.
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.
37
Solve house robber: maximise money robbed from houses in a row without robbing two adjacent houses.
def rob(nums):
take, skip = 0, 0 # best if the previous house is taken or skipped
for x in nums:
take, skip = skip + x, max(take, skip)
return max(take, skip)
# rob([2, 7, 9, 3, 1]) -> 12 (2 + 9 + 1)
# dp[i] = max(dp[i-1], dp[i-2] + nums[i]); O(n) time, O(1) space
38
A bug appeared somewhere in the last 1000 commits. How would you find the commit that introduced it quickly?
Commits form an ordered sequence where everything after the bad commit fails and everything before passes, which is a monotonic condition, so binary search applies. Test the middle commit; if it fails, search the earlier half, otherwise the later half. About 10 tests find the culprit among 1000 commits. git bisect automates this, and git bisect run can execute a test script at each step.
39
A teammate's BST validation only checks that each node is greater than its left child and smaller than its right child. Why is that wrong?
The BST property applies to entire subtrees, not just direct children. A node deep in the left subtree could be larger than the root and still pass the local check. The correct approach passes a valid range down the recursion: the left child must lie between the lower bound and the node value, the right child between the node value and the upper bound. Alternatively, check that an inorder traversal is strictly increasing.
40
Describe a time you got stuck during a coding interview or contest. How did you recover?
Situation: in an online round I could not find an efficient approach for a subarray problem. Task: still score well under time pressure. Action: I first submitted a correct brute-force solution for partial marks, then wrote out small examples and noticed the prefix sums pattern, which led to an O(n) solution with a hash map. Result: I solved it with ten minutes left and learned to secure a working solution before optimising.
Frequently asked questions
What is asked in Data Structures and Algorithms interviews for Freshers?
Freshers face an online assessment with two to four coding problems of easy to medium difficulty, often with aptitude questions, followed by one or two technical interviews. Expect arrays, strings, hashing, linked lists, trees and basic recursion, plus questions on complexity. Interviewers value clear thinking, a working brute-force solution improved step by step and well-explained college projects.
How many questions should I practise before a Data Structures and Algorithms interview?
Work through all 40 questions here, then the company-wise sets for the employers you are targeting. Quality matters more than count: be able to explain why each answer is right.
Which topics matter most for Freshers?
Focus first on Arrays, strings and hashing, Linked lists and stacks, Tree traversals, Complexity analysis.