Introduction
As we step into 2025, Data Structures and Algorithms (DSA) remain the cornerstone of coding interviews at top tech companies like Google, Amazon, and Microsoft. For BCA students, mastering these concepts isn’t just about acing exams—it’s about landing that dream job. Whether you’re prepping for campus placements or LeetCode marathons, solving medium-level problems builds problem-solving skills and confidence. In this post, we’ve curated the top 10 medium DSA questions across key topics like arrays, strings, linked lists, trees, and more. Each includes a clear explanation, problem statement, and Python solution. Dive in, code along, and level up your DSA game today!
(Word count so far: 98)
Why Focus on These DSA Questions in 2025?
Before jumping into the problems, a quick note: Based on recent trends from GeeksforGeeks and LeetCode discussions, arrays and strings dominate 60% of interviews, while trees and graphs are rising due to AI/ML roles. These questions are handpicked for their frequency in MAANG interviews and relevance to BCA syllabi. Practice them on platforms like GeeksforGeeks or LeetCode for timed challenges. Let’s get started!
Array Questions
Arrays are foundational in DSA, testing your ability to manipulate contiguous memory efficiently. Expect questions on subarrays, sums, and optimizations—perfect for BCA’s core curriculum.
Question 1: Pair with the Given Sum
Difficulty: Medium Why Important: This tests hashing for O(n) solutions, a staple in interview whiteboarding. Problem Statement: Given an array of integers nums and an integer target, return True if there exists a pair of elements that sum to target. Assume no duplicates for simplicity.
Approach: Use a hash set to store seen elements while iterating. For each num, check if (target – num) exists in the set.
Python Solution:
python
def has_pair_sum(nums, target):
seen = set()
for num in nums:
complement = target - num
if complement in seen:
return True
seen.add(num)
return False
# Example
nums = [2, 7, 11, 15]
target = 9
print(has_pair_sum(nums, target)) # Output: TrueTime Complexity: O(n) | Space Complexity: O(n) Try variations: What if pairs must be unique indices?
Question 2: Best Time to Buy and Sell Stock
Difficulty: Medium Why Important: Dynamic programming lite—optimizes profit calculation, common in algorithmic trading problems. Problem Statement: Given an array prices where prices[i] is the stock price on day i, find the maximum profit from one buy and one sell. If no profit, return 0.
Approach: Track the minimum price seen so far and update max profit as (current – min_price).
Python Solution:
python
def max_profit(prices):
if not prices:
return 0
min_price = prices[0]
max_profit = 0
for price in prices[1:]:
profit = price - min_price
max_profit = max(max_profit, profit)
min_price = min(min_price, price)
return max_profit
# Example
prices = [7, 1, 5, 3, 6, 4]
print(max_profit(prices)) # Output: 5 (buy at 1, sell at 6)Time Complexity: O(n) | Space Complexity: O(1) Pro Tip: Extend to multiple transactions for advanced practice.
Question 3: Maximum Subarray
Difficulty: Medium Why Important: Kadane’s algorithm is a must-know for contiguous sum problems in exams. Problem Statement: Given an integer array nums, find the subarray with the largest sum and return that sum.
Approach: Use Kadane’s: Track current sum, reset if negative, update global max.
Python Solution:
python
def max_subarray_sum(nums):
if not nums:
return 0
max_current = max_global = nums[0]
for num in nums[1:]:
max_current = max(num, max_current + num)
if max_current > max_global:
max_global = max_current
return max_global
# Example
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(nums)) # Output: 6 ([4, -1, 2, 1])Time Complexity: O(n) | Space Complexity: O(1) BCA Twist: Visualize with a diagram of the array peaks.
Question 4: Trapping Rain Water
Difficulty: Medium Why Important: Two-pointer technique shines here, testing space optimization. Problem Statement: Given an array height of bar heights, compute trapped rainwater units.
Approach: Use two pointers from ends, moving the shorter one inward, calculating water per step.
Python Solution:
python
def trap_rain_water(height):
if not height:
return 0
left, right = 0, len(height) - 1
left_max, right_max = 0, 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
water += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
water += right_max - height[right]
right -= 1
return water
# Example
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trap_rain_water(height)) # Output: 6Time Complexity: O(n) | Space Complexity: O(1) Image Idea: Include a bar chart screenshot showing water levels (compress via TinyPNG).
String Questions
Strings demand pattern recognition and sliding windows—crucial for text processing in web dev projects.
Question 5: Longest Substring Without Repeating Characters
Difficulty: Medium Why Important: Sliding window with hash set; frequent in string manipulation interviews. Problem Statement: Given a string s, find the length of the longest substring without repeating characters.
Approach: Expand window with a set; shrink from left on duplicate.
Python Solution:
python
def length_of_longest_substring(s):
char_set = set()
left = 0
max_length = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_length = max(max_length, right - left + 1)
return max_length
# Example
s = "abcabcbb"
print(length_of_longest_substring(s)) # Output: 3 ("abc")Time Complexity: O(n) | Space Complexity: O(min(m,n)) where m is charset size Link Internally: Check our Next.js String Utils Guide for real-world apps.
Question 6: Longest Palindromic Substring
Difficulty: Medium Why Important: Expand-around-center method; useful for validation in AI tools. Problem Statement: Given a string s, return the longest palindromic substring.
Approach: For each center (char or between), expand while palindrome holds.
Python Solution:
python
def longest_palindrome(s):
if not s:
return ""
start, max_len = 0, 1
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
for i in range(len(s)):
len1 = expand_around_center(i, i)
len2 = expand_around_center(i, i + 1)
current_len = max(len1, len2)
if current_len > max_len:
max_len = current_len
start = i - (current_len - 1) // 2
return s[start:start + max_len]
# Example
s = "babad"
print(longest_palindrome(s)) # Output: "bab" or "aba"Time Complexity: O(n²) | Space Complexity: O(1) Alt Text for Image: “Palindrome expansion diagram for string ‘babad'”.
Linked List Questions
Linked lists build pointer manipulation skills, essential for memory-efficient data handling.
Question 7: Reverse a Linked List
Difficulty: Medium Why Important: Iterative reversal; base for advanced list ops in BCA projects. Problem Statement: Reverse a singly linked list and return the new head. (Assume ListNode class defined.)
Approach: Use three pointers: prev, curr, next.
Python Solution:
python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev = None
curr = head
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev
# Example usage (build list: 1->2->3->4)
# head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
# reversed_head = reverse_list(head) # Becomes 4->3->2->1Time Complexity: O(n) | Space Complexity: O(1) Recursive version? Try it!
Question 8: Detect Cycle in a Linked List
Difficulty: Medium (Easy-Medium) Why Important: Floyd’s tortoise-hare; detects loops in graphs too. Problem Statement: Given head, return True if the list has a cycle.
Approach: Slow (1 step) and fast (2 steps) pointers; meet if cycle.
Python Solution:
python
def has_cycle(head):
if not head or not head.next:
return False
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# Example: List with cycle at node 2Time Complexity: O(n) | Space Complexity: O(1) External Link: Floyd’s Algorithm on Wikipedia
Tree Questions
Trees model hierarchies; binary trees are hot for 2025’s AI data structures.
Question 9: Maximum Depth of Binary Tree
Difficulty: Medium Why Important: Recursion basics; extends to balanced trees. Problem Statement: Given root, return max depth (root=1). (Assume TreeNode class.)
Approach: Recursive: 1 + max(left, right depths).
Python Solution:
python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
# Example: Balanced tree of depth 3Time Complexity: O(n) | Space Complexity: O(h) (height) Diagram Suggestion: Binary tree visualization.
Question 10: Validate Binary Search Tree
Difficulty: Medium Why Important: Inorder traversal; key for sorted data validation. Problem Statement: Return True if the tree is a valid BST (left < root < right).
Approach: Recursive check with min/max bounds.
Python Solution:
python
def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
if not root:
return True
if root.val <= min_val or root.val >= max_val:
return False
return (is_valid_bst(root.left, min_val, root.val) and
is_valid_bst(root.right, root.val, max_val))
# Example: Valid BST root=2, left=1, right=3Time Complexity: O(n) | Space Complexity: O(h) Internal Link: Our BCA Tree Projects Series Part 1
Conclusion
There you have it—the top 10 medium DSA questions every BCA student should tackle in 2025. From array sums to BST validation, these problems sharpen your edge for interviews and projects. Remember, consistency beats cramming: Solve one daily, debug errors, and track progress. What’s your favorite? Share your solutions or doubts in the comments below—let’s build a community! For more, subscribe to Nexus Coder and check our Free AI Tools for Developers.