Data Structures and Algorithms Interview Questions for 1 Year Experience
40 questions with answers for candidates with 1 year of experience — 18 easy, 22 medium.
What interviewers expect: 1 year experience
With one year of experience, interviews still lean heavily on DSA with medium problems, plus questions about your work. Expect trees, heaps, sliding window, binary search and basic graphs, along with how you applied data structures in real code, handled bugs and wrote tests. Clear communication and clean code matter as much as reaching the optimal solution.
This set is weighted towards Linked Lists, Stacks and Queues (7), Trees and Binary Search Trees (6), Graphs and Graph Algorithms (6), Heaps, Priority Queues and Greedy (6).
Medium DSA problems Heaps and binary search Basic graphs Real project examples
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.
✓ 3 questions free • Unlock the rest in seconds
01
What is space complexity and how is auxiliary space different?
Space complexity is the total memory an algorithm uses relative to input size, including the input itself. Auxiliary space counts only the extra memory beyond the input, such as temporary arrays, hash maps and the recursion stack. Merge sort needs O(n) auxiliary space for merging, while heap sort needs O(1). Interviewers usually mean auxiliary space when they ask you to reduce space usage.
02
What are inorder, preorder, postorder and level order traversals?
Inorder visits left subtree, node, then right subtree, and gives sorted order for a BST. Preorder visits node, left, then right, which is useful for copying or serialising a tree. Postorder visits left, right, then node, used for deleting trees or computing subtree results. Level order visits nodes level by level using a queue. All take O(n) time; recursive versions use O(h) stack space.
03
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.
04
A learning platform has courses with prerequisites. How do you find a valid order, and what if none exists?
Model courses as vertices with an edge from each prerequisite to the course that needs it, then run topological sort with Kahn's algorithm. Courses with no pending prerequisites enter a queue first, and taking one reduces the in-degree of dependent courses. If the output has fewer courses than the total, there is a cycle, so no valid order exists, and I would report the courses involved so the content team can fix them.
05
Explain best, average and worst case complexity using quicksort.
Best case is the minimum work over inputs of size n, worst case the maximum and average case the expected work over typical inputs. Quicksort averages O(n log n) because random pivots split arrays reasonably evenly. Its worst case is O(n squared) when the pivot is always the smallest or largest element, such as sorted input with a first-element pivot. Random pivots or median-of-three make the worst case very unlikely.
06
How do you decide between a greedy approach and dynamic programming?
Try to find a simple counterexample to the greedy rule on small inputs; if one exists, greedy is wrong and you likely need DP, which explores all choices of overlapping subproblems. If you can argue with an exchange argument that the greedy choice is always safe, greedy is simpler and faster. Coin change with arbitrary coins needs DP, while interval scheduling by earliest end time is safely greedy.
07
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.
08
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.
09
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.
10
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.
11
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.
12
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.
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
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.
15
What is the diameter of a binary tree and how do you compute it efficiently?
The diameter is the number of edges on the longest path between any two nodes, which may not pass through the root. Compute it in one postorder traversal: for each node, get the heights of the left and right subtrees, update a global best with left plus right, and return 1 plus the larger height to the parent. This visits each node once, giving O(n) time instead of O(n squared) from recomputing heights.
16
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.
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.
18
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.
19
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
Kadane's algorithm finds the maximum sum contiguous subarray in O(n) time and O(1) space. At each element it decides whether to extend the current subarray or start fresh: current = max(x, current + x), and best = max(best, current). The insight is that a negative running sum never helps a future subarray. For an all-negative array it correctly returns the largest single element when initialised with the first value.
21
How would you implement browser back and forward navigation?
Use two stacks plus the current page. Visiting a new page pushes the current page onto the back stack, sets the new page as current and clears the forward stack. Back pushes current onto the forward stack and pops the back stack into current. Forward does the reverse. Each operation is O(1). A doubly linked list with a cursor is an alternative that makes it easy to show the full history.
22
How do DFS and BFS differ in memory use on a tree?
DFS uses a stack, either the call stack or an explicit one, holding at most the height of the tree, so O(h) memory: about log n for balanced trees but n for skewed ones. BFS uses a queue holding an entire level, up to about n over 2 nodes in the last level of a complete tree. So DFS is lighter for wide balanced trees, while BFS is natural for shortest paths and level-wise processing.
23
A cashier system uses the greedy rule of always giving the largest coin first. When can this fail?
Greedy coin change is optimal for canonical systems such as Indian rupee denominations, but fails for arbitrary coin sets. With coins 1, 3 and 4 and amount 6, greedy gives 4 plus 1 plus 1, three coins, while 3 plus 3 uses only two. For arbitrary denominations, use dynamic programming where dp of x is the minimum coins for amount x, computed in O(amount times number of coins).
24
How is the longest common subsequence computed with DP?
Let dp[i][j] be the LCS length of the first i characters of A and the first j characters of B. If A[i-1] equals B[j-1], dp[i][j] is dp[i-1][j-1] plus 1; otherwise it is the maximum of dp[i-1][j] and dp[i][j-1]. Fill the table row by row in O(m times n) time. Backtracking from dp[m][n] recovers the actual subsequence. LCS underlies diff tools and DNA sequence comparison.
25
Print the level order traversal of a binary tree, one list per level.
from collections import deque
def level_order(root):
if not root:
return []
out, q = [], deque([root])
while q:
level = []
for _ in range(len(q)): # process exactly one level
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
out.append(level)
return out
26
An interviewer asks you to reduce your solution's extra space from O(n) to O(1). How do you approach it?
I check what the extra structure stores and whether the input itself can hold that information. Common techniques: use two pointers instead of a hash set on sorted data, keep only the last few DP values instead of a full table, modify the input in place, such as marking visited indices by negating values, or use bit manipulation like XOR to find a missing number. I state any trade-offs, such as mutating input.
27
Implement Dijkstra's algorithm with a priority queue.
Situation: a reviewer wanted me to replace my BFS solution with a more complex bidirectional search. Task: reach the best decision for the code, not win the argument. Action: I asked about their concern, which was latency on large graphs, then shared measurements showing our graphs were small and the simpler code was faster to maintain, and agreed to add a benchmark that would alert us if size grew. Result: the reviewer approved and we documented the trade-off.
29
What is the difference between a subarray, a subsequence and a substring?
A subarray is a contiguous part of an array, and an array of n elements has n times n plus 1 over 2 of them. A substring is the same idea for strings. A subsequence keeps the original order but may skip elements, so there are 2 to the power n of them. This matters for choosing techniques: sliding window and prefix sums suit subarrays, while subsequence problems often need dynamic programming.
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.
31
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.
32
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)
33
Your recursive solution passes with memoisation, but the interviewer asks for a bottom-up version. How do you convert it?
I identify the recursion parameters, which become the table dimensions, and the base cases, which become the initial cells. Then I look at which states each call depends on, for example index plus 1, and fill the table in the opposite order, so dependencies are computed first. The recursive transition becomes the loop body. Finally I check whether only the last row is used, so I can reduce space, and walk through a small example.
34
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.
35
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).
36
Implement Kadane's algorithm for the maximum subarray sum.
def max_subarray(nums):
best = current = nums[0]
for x in nums[1:]:
current = max(x, current + x) # extend or start fresh
best = max(best, current)
return best
# max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) -> 6 (subarray 4, -1, 2, 1)
37
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.
38
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.
39
Design a simple scheduler that gives each job a fixed time slice in turn.
Round-robin scheduling fits a queue. Put all jobs in a FIFO queue. Repeatedly dequeue a job, run it for one time slice, and if it is not finished, enqueue it at the back with its remaining time. Each step is O(1). For priorities, keep one queue per priority level or use a priority queue. A circular buffer works well if the number of jobs is bounded, avoiding allocations.
40
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).
Frequently asked questions
What is asked in Data Structures and Algorithms interviews for 1 year of experience?
With one year of experience, interviews still lean heavily on DSA with medium problems, plus questions about your work. Expect trees, heaps, sliding window, binary search and basic graphs, along with how you applied data structures in real code, handled bugs and wrote tests. Clear communication and clean code matter as much as reaching the optimal solution.
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 1 year of experience?
Focus first on Medium DSA problems, Heaps and binary search, Basic graphs, Real project examples.