About the Software Engineer (Fresher / SDE-1) role
Freshers join product and service companies as software engineers or SDE-1 after clearing online coding tests and technical interviews focused on DSA. They build features, fix bugs and write tests under the guidance of senior engineers. Strong problem solving with arrays, strings, hashing, trees and basic graphs, explained clearly with complexity analysis, is the main hiring signal, along with one or two good projects.
Problem solving Complexity analysis Clean coding Hashing and arrays Tree traversals
Solved for this roleStart practicing
3 QUESTIONS FREESign up to unlock the full question bank and track your progress.Unlock every question and answer, then continue practising company-wise and package-wise.
✓ 3 questions free • Unlock the rest in seconds
01
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
02
What is a binary search tree and what is its time complexity?
In a BST every node's left subtree contains smaller keys and the right subtree larger keys. Search, insert and delete follow one path from the root, so they take O(h) time, where h is the height. A balanced tree has h about log n, giving O(log n). Inserting sorted data into a plain BST creates a skewed tree that behaves like a linked list with O(n) operations, which is why balanced variants exist.
03
What are prefix sums and what problems do they solve?
A prefix sum array stores pre[i] as the sum of the first i elements, built in O(n). The sum of any range from l to r is then pre[r+1] minus pre[l] in O(1). Combined with a hash map of prefix sums, it counts subarrays with sum k in O(n). 2D prefix sums answer rectangle sum queries on grids, and difference arrays apply many range updates efficiently.
04
Check whether a string is a palindrome, ignoring case and non-alphanumeric characters.
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.
It sorts an array of three distinct values, such as 0, 1 and 2, in one pass with O(1) space. It keeps three pointers: low, mid and high. If arr[mid] is 0, swap it with arr[low] and advance both; if 1, advance mid; if 2, swap it with arr[high] and decrease high without advancing mid. It runs in O(n) and is the basis of three-way partitioning in quicksort.
07
What are lower bound and upper bound, and what common bugs appear in binary search?
Lower bound returns the first index whose value is not less than the target, and upper bound the first index whose value is greater, so their difference counts occurrences. Common bugs are off-by-one errors in the loop condition, infinite loops when mid does not move, and integer overflow from (low plus high) divided by 2 in Java or C++; use low plus (high minus low) divided by 2. Python's bisect module provides both functions.
08
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.
09
How does Floyd's cycle detection algorithm work and why is it correct?
Floyd uses a slow pointer moving one step and a fast pointer moving two steps. If there is no cycle, fast reaches the end. If there is a cycle, fast gains one step per iteration on slow inside the loop, so they must meet. To find the cycle start, reset one pointer to the head and move both one step at a time; they meet at the start because the distances from head and from the meeting point are equal modulo the cycle length.
10
Solve two sum: return the indices of two numbers that add up to the target.
def two_sum(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
return []
# two_sum([2, 7, 11, 15], 9) -> [0, 1]
# O(n) time, O(n) space; sorting + two pointers gives O(1) space but loses indices
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.
12
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.
13
What is the difference between Big-O, Big-Omega and Big-Theta?
Big-O is an upper bound: the algorithm grows no faster than this. Big-Omega is a lower bound: it grows at least this fast. Big-Theta is a tight bound, when the upper and lower bounds match. Merge sort is Theta(n log n) because it always does that much work. In interviews people usually say Big-O to mean the tight worst-case bound, but you should know the formal difference.
14
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.
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 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.
17
Write an iterative inorder traversal of a binary tree.
def inorder(root):
result, stack = [], []
node = root
while node or stack:
while node: # go as far left as possible
stack.append(node)
node = node.left
node = stack.pop()
result.append(node.val) # visit
node = node.right # then the right subtree
return result
# O(n) time, O(h) space; no recursion limit issues
18
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.
19
What is the two pointer technique and when is it used?
Two pointers move through an array or string, often from both ends or at different speeds, to avoid nested loops. On a sorted array you can find a pair with a given sum in O(n) by moving left or right depending on the current sum. It is also used for reversing, removing duplicates in place, merging sorted arrays, palindrome checks and partitioning. It usually needs sorted data or a monotonic condition.
20
How do you approach a coding problem you have never seen before in an interview?
Situation: in a mock interview I got an unfamiliar graph problem. Task: solve it while keeping the interviewer involved. Action: I restated the problem, asked about constraints and edge cases, worked through a small example by hand, explained a brute-force idea with its complexity, then improved it step by step and coded only after agreement. I tested with edge cases aloud. Result: I reached an optimal solution and got positive feedback on communication.
21
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.
22
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.
23
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.
24
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)
25
A problem has n up to 100000. Which time complexities are acceptable for a 1-second limit?
A common rule is that judges run about 10 to the power 8 simple operations per second. With n equal to 10 to the power 5, O(n log n) is about 1.7 million operations and O(n) is trivial, both fine. O(n squared) is 10 to the power 10 operations, far too slow. So I would look for sorting, hashing, two pointers, binary search or prefix sums rather than nested loops over all pairs.
26
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
27
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.
28
What is recursion and why is a base case essential?
Recursion is when a function solves a problem by calling itself on smaller subproblems. Each call gets its own frame on the call stack holding parameters and local variables. The base case is the condition where the function returns directly without recursing, such as n equal to 0 for factorial. Without a correct base case, calls never stop and the program fails with a stack overflow.
import heapq
def merge_k_lists(lists):
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node)) # i breaks ties
dummy = tail = ListNode()
while heap:
val, i, node = heapq.heappop(heap)
tail.next = node
tail = node
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
# O(N log K) for N total nodes
30
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.
31
Describe a team project where one member was not contributing. What did you do?
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.
32
Write recursive Fibonacci and then optimise it with memoisation.
from functools import lru_cache
def fib_naive(n): # O(2^n) time
if n < 2:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
@lru_cache(maxsize=None)
def fib_memo(n): # O(n) time, O(n) space
if n < 2:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
def fib_iter(n): # O(n) time, O(1) space
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
Situation: I am starting my career with a strong interest in solving algorithmic and system problems. Task: grow into an engineer others rely on. Action: in the first years I want to master the codebase, deliver features reliably and deepen my skills in data structures, system design and the domain. Result: in five years I see myself as a senior engineer owning important components, mentoring juniors and contributing to design decisions in this team.
34
List common complexity classes from fastest to slowest with examples.
O(1): array index access or a hash lookup on average. O(log n): binary search. O(n): linear scan. O(n log n): merge sort and heap sort. O(n squared): nested loops over pairs, as in bubble sort. O(2 to the power n): generating all subsets. O(n factorial): generating all permutations. For n around one lakh, anything up to O(n log n) is comfortable, while O(n squared) usually times out.
def power(x, n):
if n < 0:
x, n = 1 / x, -n
result = 1
while n > 0:
if n & 1: # odd bit set: multiply current base in
result *= x
x *= x # square the base
n >>= 1 # move to next bit
return result
# power(2, 10) == 1024; use % mod after each multiply for modular power
37
An array of size 100000 must answer 100000 queries asking for the sum between two indices. What approach would you use?
Recomputing each sum is O(n) per query, about 10 to the power 10 operations in total, which is too slow. Since the array does not change, I would build a prefix sum array once in O(n) and answer each query in O(1) as pre[r+1] minus pre[l], giving O(n plus q) overall. If the array also receives updates, I would switch to a Fenwick tree or segment tree for O(log n) updates and queries.
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
39
How do you find the lowest common ancestor in a BST versus in a general binary tree?
In a BST, start at the root: if both values are smaller go left, if both are larger go right, otherwise the current node is the LCA, taking O(h). In a general binary tree, recurse: if the node is null or matches either target, return it; otherwise search both subtrees. If both sides return non-null, the current node is the LCA; else return the non-null side. That takes O(n).
40
Strings are immutable in Java and Python. How does that affect algorithm complexity?
Every modification creates a new string, so building a string by concatenation inside a loop can copy characters repeatedly and become O(n squared). Use StringBuilder in Java or collect parts in a list and call join in Python, which is O(n) overall. Immutability also makes strings safe as hash map keys and lets runtimes cache their hash codes, which is why they are good dictionary keys.
Frequently asked questions
What does a Software Engineer (Fresher / SDE-1) do?
Freshers join product and service companies as software engineers or SDE-1 after clearing online coding tests and technical interviews focused on DSA. They build features, fix bugs and write tests under the guidance of senior engineers. Strong problem solving with arrays, strings, hashing, trees and basic graphs, explained clearly with complexity analysis, is the main hiring signal, along with one or two good projects.
Which skills are tested in a Software Engineer (Fresher / SDE-1) interview?
Expect questions on Problem solving, Complexity analysis, Clean coding, Hashing and arrays, Tree traversals. Most rounds also ask you to explain a project and solve one practical problem live.
How do I prepare for a Software Engineer (Fresher / SDE-1) interview?
Revise Arrays, Strings and Hashing, Trees and Binary Search Trees, Complexity Analysis and Recursion first using the topic sheets, practise the questions on this page aloud, then do one full mock interview to practise timing.