Top DSA Interview Questions for Freshers
Are you preparing for your first Data Structures and Algorithms interview and wondering what questions you might face?
Understanding the key Data Structures and Algorithms interview questions for freshers can give you more clarity.
With this guide, you’ll be well-prepared to tackle these Data Structures and Algorithms interview questions and answers for freshers and make a strong impression in your interview.
Practice Data Structures & Algorithms Interview Questions
Below are the Data Structures & Algorithms interview questions for freshers with answers:
1. How do you reverse a string in Python?
Answer:
You can reverse a string using Python slicing. The syntax is str[::-1], which iterates over the string in reverse.
def reverse_string(s):
return s[::-1]
2. How do you find the maximum element in an array?
Answer:
You can find the maximum element in an array using Python’s built-in max() function.
arr = [1, 4, 5, 2] max_element = max(arr)
3. How do you check if a string is a palindrome?
Answer:
A string is a palindrome if it reads the same forward and backward. You can check this by comparing the string with its reverse.
def is_palindrome(s):
return s == s[::-1]
4. How do you find the second largest element in an array?
Answer:
Sort the array in descending order and return the second element. Alternatively, iterate through the array to find the second largest element.
def second_largest(arr):
arr = list(set(arr)) # Remove duplicates
arr.sort(reverse=True)
return arr[1]
5. How do you find the sum of digits of a given number?
Answer:
To find the sum of digits, convert the number to a string and sum the individual digits using sum(map(int, str(n))).
def sum_of_digits(n):
return sum(int(digit) for digit in str(n))
6. How do you print the Fibonacci series up to n terms?
Answer:
You can calculate the Fibonacci series iteratively by adding the two previous numbers to get the next one.
def fibonacci(n):
a, b = 0, 1
for _ in range(n):
print(a, end=’ ‘)
a, b = b, a + b
7. How do you find the factorial of a given number n?
Answer:
The factorial of a number is the product of all positive integers less than or equal to n. This can be computed using recursion.
def factorial(n):
return 1 if n == 0 else n * factorial(n – 1)
8. How do you find the missing number in a sequence from 1 to n?
Answer:
The sum of numbers from 1 to n is n*(n+1)//2. Find the difference between this sum and the sum of elements in the array.
def find_missing(arr, n):
total = n * (n + 1) // 2
return total – sum(arr)
9. How do you check if two strings are anagrams?
Answer:
Two strings are anagrams if they contain the same characters in different orders. Sort both strings and compare them.
def are_anagrams(str1, str2):
return sorted(str1) == sorted(str2)
10. How do you find a duplicate element in an array?
Answer:
Use a set to keep track of elements. If an element already exists in the set, it’s a duplicate.
def find_duplicate(arr):
seen = set()
for num in arr:
if num in seen:
return num
seen.add(num)
11. How do you find the length of the longest substring without repeating characters?
Answer:
Use a sliding window approach to track the longest substring with unique characters.
def longest_unique_substring(s):
char_set = set()
l, res = 0, 0
for r in range(len(s)):
while s[r] in char_set:
char_set.remove(s[l])
l += 1
char_set.add(s[r])
res = max(res, r – l + 1)
return res
12. How do you find the intersection of two arrays?
Answer:
Convert both arrays to sets and use the & operator to find the intersection.
def intersection(arr1, arr2):
return list(set(arr1) & set(arr2))
13. How do you check if a binary tree is height-balanced?
Answer:
A binary tree is balanced if the height difference between the left and right subtree is not more than 1.
def is_balanced(root):
def height(node):
if not node:
return 0
left = height(node.left)
right = height(node.right)
if left == -1 or right == -1 or abs(left – right) > 1:
return -1
return 1 + max(left, right)
return height(root) != -1
14. How do you implement binary search in a sorted array?
Answer:
Binary search works by dividing the search space in half, checking the middle element, and deciding which half to search next.
def binary_search(arr, target):
low, high = 0, len(arr) – 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid – 1
return -1
15. How do you merge two sorted arrays into one sorted array?
Answer:
Use two pointers to iterate through both arrays and append the smaller element to the result.
def merge_sorted_arrays(arr1, arr2):
i, j = 0, 0
result = []
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
result.extend(arr1[i:])
result.extend(arr2[j:])
return result
16. How do you find the middle element of a linked list?
Answer:
Use two pointers, one moving twice as fast as the other. When the fast pointer reaches the end, the slow pointer will be at the middle.
def find_middle(head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
17. How do you check if a number is prime?
Answer:
A prime number has no divisors other than 1 and itself. Check divisibility up to the square root of the number.
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
18. How do you find the greatest common divisor (GCD) of two numbers?
Answer:
Use Euclid’s algorithm: repeatedly divide the larger number by the smaller until the remainder is zero.
def gcd(a, b):
while b:
a, b = b, a % b
return a
19. How do you merge overlapping intervals?
Answer:
Sort the intervals by the start time, then iterate through them and merge overlapping intervals.
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for curr in intervals[1:]:
if curr[0] <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], curr[1])
else:
merged.append(curr)
return merged
20. How do you find the Kth largest element in an array?
Answer:
Sort the array and return the Kth largest element. Alternatively, use a min-heap.
import heapq
def kth_largest(arr, k):
return heapq.nlargest(k, arr)[-1]
21. How do you find the longest palindromic substring in a given string?
Answer:
Expand around the center of the string and check for the longest palindrome in both even and odd-length substrings.
def longest_palindrome(s):
def expand_around_center(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right – left – 1
start, end = 0, 0
for i in range(len(s)):
len1 = expand_around_center(i, i)
len2 = expand_around_center(i, i + 1)
max_len = max(len1, len2)
if max_len > end – start:
start = i – (max_len – 1) // 2
end = i + max_len // 2
return s[start:end + 1]
22. How do you check if a string containing parentheses is balanced?
Answer:
Use a stack to keep track of open parentheses. For each closing parenthesis, pop the stack and check for a matching opening parenthesis.
def is_balanced(s):
stack = []
matching_parentheses = {‘)’: ‘(‘, ‘]’: ‘[‘, ‘}’: ‘{‘}
for char in s:
if char in matching_parentheses.values():
stack.append(char)
elif char in matching_parentheses:
if not stack or stack.pop() != matching_parentheses[char]:
return False
return not stack
23. How do you find a subarray with a given sum in a non-negative array?
Answer:
Use the sliding window technique to adjust the window size dynamically until the target sum is found.
def find_subarray_with_sum(arr, target):
start, current_sum = 0, 0
for end in range(len(arr)):
current_sum += arr[end]
while current_sum > target:
current_sum -= arr[start]
start += 1
if current_sum == target:
return arr[start:end + 1]
return []
24. How do you find the minimum element in a rotated sorted array?
Answer:
Use binary search to find the inflection point where the array is rotated.
def find_min_in_rotated_array(arr):
low, high = 0, len(arr) – 1
while low < high:
mid = (low + high) // 2
if arr[mid] > arr[high]:
low = mid + 1
else:
high = mid
return arr[low]
25. How do you find the median of two sorted arrays?
Answer:
Use binary search on the smaller array to partition both arrays into two halves, ensuring that the left half contains smaller elements than the right half.
def find_median_sorted_arrays(nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
x, y = len(nums1), len(nums2)
low, high = 0, x
while low <= high:
partitionX = (low + high) // 2
partitionY = (x + y + 1) // 2 – partitionX
maxX = float(‘-inf’) if partitionX == 0 else nums1[partitionX – 1] minX = float(‘inf’) if partitionX == x else nums1[partitionX]
maxY = float(‘-inf’) if partitionY == 0 else nums2[partitionY – 1] minY = float(‘inf’) if partitionY == y else nums2[partitionY]
if maxX <= minY and maxY <= minX:
if (x + y) % 2 == 0:
return (max(maxX, maxY) + min(minX, minY)) / 2
else:
return max(maxX, maxY)
elif maxX > minY:
high = partitionX – 1
else:
low = partitionX + 1
26. How do you implement a queue using two stacks?
Answer:
Use two stacks: one for enqueuing elements and another for dequeuing.
class QueueUsingStacks:
def __init__(self):
self.stack1 = []
self.stack2 = []
def enqueue(self, x):
self.stack1.append(x)
def dequeue(self):
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
27. How do you check if a binary tree is symmetric?
Answer:
A binary tree is symmetric if the left subtree is a mirror reflection of the right subtree.
def is_symmetric(root):
def is_mirror(t1, t2):
if not t1 and not t2:
return True
if not t1 or not t2:
return False
return t1.val == t2.val and is_mirror(t1.left, t2.right) and is_mirror(t1.right, t2.left)
return is_mirror(root, root)
28. How do you find the lowest common ancestor of two nodes in a binary tree?
Answer:
The LCA is the node that is the deepest common ancestor of both nodes. Traverse the tree recursively, and return the node where the paths to both nodes diverge.
def lowest_common_ancestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right:
return root
return left if left else right
29. How do you count the number of islands in a 2D grid?
Answer:
Perform a depth-first search (DFS) to mark all connected components of land (1) as visited.
def num_islands(grid):
if not grid:
return 0
def dfs(grid, i, j):
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == ‘0’:
return
grid[i][j] = ‘0’
dfs(grid, i + 1, j)
dfs(grid, i – 1, j)
dfs(grid, i, j + 1)
dfs(grid, i, j – 1)
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == ‘1’:
dfs(grid, i, j)
count += 1
return count
30. How do you find the maximum sum of a subarray using Kadane’s Algorithm?
Answer:
Kadane’s algorithm scans the array and computes the maximum subarray sum in linear time by updating the current maximum at each step.
def max_subarray_sum(arr):
max_so_far = max_ending_here = arr[0]
for i in range(1, len(arr)):
max_ending_here = max(arr[i], max_ending_here + arr[i])
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
31. How do you implement a stack using two queues?
Answer:
You can implement a stack by using two queues, one for pushing and the other for popping elements. When popping, the elements are dequeued until only one remains.
from collections import deque
class StackUsingQueues:
def __init__(self):
self.queue1 = deque()
self.queue2 = deque()
def push(self, x):
self.queue1.append(x)
def pop(self):
while len(self.queue1) > 1:
self.queue2.append(self.queue1.popleft())
popped = self.queue1.popleft()
self.queue1, self.queue2 = self.queue2, self.queue1
return popped
def top(self):
return self.queue1[-1]
def empty(self):
return not self.queue1
32. How do you find all permutations of a string?
Answer:
Use backtracking to generate all possible permutations of a string by swapping characters.
def permute(s):
def backtrack(start):
if start == len(s) – 1:
result.append(”.join(s))
for i in range(start, len(s)):
s[start], s[i] = s[i], s[start]
backtrack(start + 1)
s[start], s[i] = s[i], s[start]
result = []
s = list(s)
backtrack(0)
return result
33. How do you find the Kth smallest element in a Binary Search Tree (BST)?
Answer:
Inorder traversal of a BST gives the elements in sorted order. Perform an inorder traversal and stop at the Kth element.
def kth_smallest(root, k):
def inorder(node):
if node:
yield from inorder(node.left)
yield node.val
yield from inorder(node.right)
gen = inorder(root)
for _ in range(k):
result = next(gen)
return result
34. How do you find a peak element in an array where an element is greater than its neighbors?
Answer:
Use binary search to efficiently find a peak element.
def find_peak(arr):
low, high = 0, len(arr) – 1
while low < high:
mid = (low + high) // 2
if arr[mid] < arr[mid + 1]:
low = mid + 1
else:
high = mid
return arr[low]
35. How do you count the number of 1’s in the binary representation of an integer?
Answer:
Use bit manipulation by repeatedly clearing the least significant bit set to 1.
def count_ones(n):
count = 0
while n:
n &= n – 1
count += 1
return count
36. How do you convert a binary tree to a doubly linked list in-place?
Answer:
Perform an inorder traversal and adjust pointers as you visit each node to create a doubly linked list.
def convert_to_dll(root):
def inorder(node):
nonlocal prev
if not node:
return
inorder(node.left)
if prev:
prev.right = node
node.left = prev
prev = node
inorder(node.right)
if not root:
return None
prev = None
inorder(root)
while root.left:
root = root.left
return root
37. How do you find the longest increasing subsequence in an array?
Answer:
Use dynamic programming to store the length of the longest subsequence that ends at each element.
def longest_increasing_subsequence(arr):
dp = [1] * len(arr)
for i in range(1, len(arr)):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
38. How do you flatten a multilevel doubly linked list where each node can have a child pointing to another doubly linked list?
Answer:
Perform a depth-first traversal and adjust pointers to flatten the multilevel list.
def flatten(head):
if not head:
return head
dummy = Node(0)
prev = dummy
stack = [head]
while stack:
curr = stack.pop()
prev.next = curr
curr.prev = prev
if curr.next:
stack.append(curr.next)
if curr.child:
stack.append(curr.child)
curr.child = None
prev = curr
dummy.next.prev = None
return dummy.next
39. How do you find the maximum product of a contiguous subarray?
Answer:
Keep track of the current maximum and minimum products as you iterate through the array.
def max_product_subarray(nums):
max_prod, min_prod, result = nums[0], nums[0], nums[0]
for i in range(1, len(nums)):
candidates = (nums[i], nums[i] * max_prod, nums[i] * min_prod)
max_prod = max(candidates)
min_prod = min(candidates)
result = max(result, max_prod)
return result
40. How do you find the median of a data stream?
Answer:
Use two heaps: a max-heap for the lower half and a min-heap for the upper half of the data.
import heapq
class MedianFinder:
def __init__(self):
self.low = [] # Max-heap
self.high = [] # Min-heap
def add_num(self, num):
heapq.heappush(self.low, -num)
heapq.heappush(self.high, -heapq.heappop(self.low))
if len(self.low) < len(self.high):
heapq.heappush(self.low, -heapq.heappop(self.high))
def find_median(self):
if len(self.low) > len(self.high):
return -self.low[0]
return (-self.low[0] + self.high[0]) / 2
41. How do you find all unique triplets in an array that sum to zero?
Answer:
Sort the array and use two pointers to find pairs that sum to the negative of the current element.
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) – 2):
if i > 0 and nums[i] == nums[i – 1]:
continue
left, right = i + 1, len(nums) – 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right – 1]:
right -= 1
left += 1
right -= 1
return result
42. How do you find the minimum window substring in a string that contains all the characters of another string?
Answer:
Use a sliding window and a hash map to track the frequency of required characters.
from collections import Counter
def min_window(s, t):
if not s or not t:
return “”
dict_t = Counter(t)
required = len(dict_t)
left, right = 0, 0
formed = 0
window_counts = {}
ans = float(“inf”), None, None
while right < len(s):
char = s[right]
window_counts[char] = window_counts.get(char, 0) + 1
if char in dict_t and window_counts[char] == dict_t[char]:
formed += 1
while left <= right and formed == required:
char = s[left]
if right – left + 1 < ans[0]:
ans = (right – left + 1, left, right)
window_counts[char] -= 1
if char in dict_t and window_counts[char] < dict_t[char]:
formed -= 1
left += 1
right += 1
return “” if ans[0] == float(“inf”) else s[ans[1]:ans[2] + 1]
43. How do you serialize and deserialize a binary tree?
Answer:
Serialize the tree into a string using pre-order traversal and deserialize it back into a tree using a queue.
def serialize(root):
def helper(node):
if not node:
result.append(‘None’)
else:
result.append(str(node.val))
helper(node.left)
helper(node.right)
result = []
helper(root)
return ‘,’.join(result)
def deserialize(data):
def helper():
val = next(values)
if val == ‘None’:
return None
node = TreeNode(int(val))
node.left = helper()
node.right = helper()
return node
values = iter(data.split(‘,’))
return helper()
44. How do you implement an LRU (Least Recently Used) Cache?
Answer:
Use a combination of a dictionary and a doubly linked list to keep track of the least recently used elements.
class LRUCache:
def __init__(self, capacity):
self.cache = {}
self.capacity = capacity
self.head = ListNode(0)
self.tail = ListNode(0)
self.head.next = self.tail
self.tail.prev = self.head
def _add(self, node):
p = self.head.next
self.head.next = node
node.prev = self.head
node.next = p
p.prev = node
def _remove(self, node):
p = node.prev
n = node.next
p.next = n
n.prev = p
def get(self, key):
if key in self.cache:
node = self.cache[key]
self._remove(node)
self._add(node)
return node.val
return -1
def put(self, key, value):
if key in self.cache:
self._remove(self.cache[key])
node = ListNode(key, value)
self.cache[key] = node
self._add(node)
if len(self.cache) > self.capacity:
n = self.tail.prev
self._remove(n)
del self.cache[n.key]
45. How do you find the maximum path sum in a binary tree?
Answer:
Recursively calculate the maximum gain from each node and update the global maximum path sum.
def max_path_sum(root):
def helper(node):
nonlocal max_sum
if not node:
return 0
left_gain = max(helper(node.left), 0)
right_gain = max(helper(node.right), 0)
max_sum = max(max_sum, node.val + left_gain + right_gain)
return node.val + max(left_gain, right_gain)
max_sum = float(‘-inf’)
helper(root)
return max_sum
46. How do you find the longest common subsequence (LCS) between two strings?
Answer:
Use dynamic programming to store the LCS length at each substring.
def longest_common_subsequence(text1, text2):
dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
for i in range(1, len(text1) + 1):
for j in range(1, len(text2) + 1):
if text1[i – 1] == text2[j – 1]:
dp[i][j] = dp[i – 1][j – 1] + 1
else:
dp[i][j] = max(dp[i – 1][j], dp[i][j – 1])
return dp[-1][-1]
47. How do you find the shortest path in a graph using Dijkstra’s Algorithm?
Answer:
Use a priority queue to greedily select the node with the smallest distance, and update the distances of its neighbors.
import heapq
def dijkstra(graph, start):
distances = {node: float(‘infinity’) for node in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
current_distance, current_node = heapq.heappop(pq)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
48. How do you count the number of inversions in an array (where i < j and arr[i] > arr[j])?
Answer:
Use a modified merge sort algorithm to count the inversions while sorting the array.
def merge_sort_and_count(arr):
if len(arr) < 2:
return arr, 0
mid = len(arr) // 2
left, left_inv = merge_sort_and_count(arr[:mid])
right, right_inv = merge_sort_and_count(arr[mid:])
merged, split_inv = merge_and_count(left, right)
return merged, left_inv + right_inv + split_inv
def merge_and_count(left, right):
result = []
i = j = inv_count = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
inv_count += len(left) – i
result += left[i:]
result += right[j:]
return result, inv_count
49. How do you check if a given number is a power of two?
Answer:
A number is a power of two if it has only one bit set in its binary representation.
def is_power_of_two(n):
return n > 0 and (n & (n – 1)) == 0
50. How do you implement a Trie for storing words and their prefixes?
Answer:
A Trie is a tree-like data structure where each node represents a single character, and paths represent words.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
Final Words
Getting ready for an interview can feel overwhelming, but going through these Data Structures and Algorithms fresher interview questions can help you feel more confident.
With the right preparation, you’ll ace your Data Structures and Algorithms interview, but don’t forget to practice the fundamentals of data structures, algorithmic problem-solving, and time/space complexity-related interview questions too.
Frequently Asked Questions
1. What are the most common interview questions for data structures and algorithms?
Common DSA interview questions focus on fundamental data structures (arrays, linked lists, stacks, queues, trees, graphs) and algorithmic problems like sorting, searching, recursion, dynamic programming, and time complexity analysis.
2. What are the important DSA topics freshers should focus on for interviews?
Freshers should focus on arrays, linked lists, stacks, queues, binary trees, binary search trees, heaps, graphs, sorting algorithms, searching algorithms, recursion, dynamic programming, and Big-O time complexity.
3. How should freshers prepare for data structures and algorithms technical interviews?
Freshers should practice solving a variety of problems on platforms like LeetCode, Codeforces, or HackerRank, study different data structures and their use cases, and understand how to optimize solutions for time and space complexity.
4. What strategies can freshers use to solve DSA coding questions during interviews?
Freshers should first analyze the problem, identify the most suitable data structure, write pseudocode, and choose an algorithm that minimizes time and space complexity. Testing the solution with edge cases is also crucial during interviews.
5. Should freshers prepare for advanced DSA topics in interviews?
Yes, freshers should prepare for advanced topics like dynamic programming, graph algorithms (Dijkstra, BFS, DFS), and amortized analysis. While not always asked, these topics can give candidates an edge in technical interviews.
Explore More DSA Resources
- DSA Learning Websites
- DSA Practicing Websites
- DSA YouTube Channels
- DSA Project Ideas
- Data Structures & Algorithms MCQ
Explore More Interview Questions
Thirumoorthy serves as a teacher and coach. He obtained a 99 percentile on the CAT. He cleared numerous IT jobs and public sector job interviews, but he still decided to pursue a career in education. He desires to elevate the underprivileged sections of society through education
Thirumoorthy serves as a teacher and coach. He obtained a 99 percentile on the CAT. He cleared numerous IT jobs and public sector job interviews, but he still decided to pursue a career in education. He desires to elevate the underprivileged sections of society through education
Related Posts
Top Perl Interview Questions for Freshers
Are you preparing for your first Perl interview and wondering what questions you might face? Understanding the key Perl interview questions …
