DSA Interview Problems – Python Solutions with
Explanation
This document contains Python solutions, clear explanations, and key logic for all the questions you
shared (Q1 to Q15). These problems are frequently asked in TCS, Cognizant, Amazon, Microsoft, Zoho,
Infosys, Capgemini, and other product & service companies.
Q1. Maximum Score from Subarrays (Smallest + Second Smallest)
Problem
Given an array, choose any subarray, find the smallest and second smallest elements, add them. Return the
maximum possible sum.
Key Insight
The maximum sum will always come from two adjacent elements.
Python Code
def maxScore(arr):
ans = 0
for i in range(len(arr) - 1):
ans = max(ans, arr[i] + arr[i + 1])
return ans
Time & Space
• Time: O(n)
• Space: O(1)
Q2. Max-So-Far Count Problem
Problem
Count elements that are greater than all previous elements.
1
Python Code
def maxSoFarCount(arr):
count = 1
max_so_far = arr[0]
for i in range(1, len(arr)):
if arr[i] > max_so_far:
count += 1
max_so_far = arr[i]
return count
Time & Space
• Time: O(n)
• Space: O(1)
Q3. 3 Sum Problem
Problem
Find all unique triplets that sum to 0.
Python Code
def threeSum(nums):
[Link]()
res = []
n = len(nums)
for i in range(n):
if i > 0 and nums[i] == nums[i - 1]:
continue
l, r = i + 1, n - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s == 0:
[Link]([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l + 1]: l += 1
while l < r and nums[r] == nums[r - 1]: r -= 1
l += 1
r -= 1
elif s < 0:
l += 1
2
else:
r -= 1
return res
Time & Space
• Time: O(n²)
• Space: O(1)
Q4. Partition Equal Subset Sum
Problem
Check if array can be divided into two subsets with equal sum.
Python Code
def equalPartition(N, arr):
total = sum(arr)
if total % 2 != 0:
return 0
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in arr:
for s in range(target, num - 1, -1):
if dp[s - num]:
dp[s] = True
return 1 if dp[target] else 0
Time & Space
• Time: O(N * sum)
• Space: O(sum)
Q5. Rotate Matrix by 90 Degrees (Clockwise)
Problem
Rotate an N×N matrix by 90° clockwise in-place.
3
Python Code
def rotate(matrix):
n = len(matrix)
# Transpose
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Reverse rows
for i in range(n):
matrix[i].reverse()
Time & Space
• Time: O(n²)
• Space: O(1)
This document contains Python solutions, clear explanations, and key logic for all the questions you
shared (Q6 to Q15). These problems are frequently asked in TCS, Cognizant, Amazon, Microsoft, Zoho,
Infosys, Capgemini, and other product & service companies.
Q6. Best Time to Buy and Sell Stock (Single Transaction)
Problem
You are given stock prices where index represents time. Buy once and sell once to maximize profit.
Key Idea
• Track minimum price so far
• Calculate profit at each step
• Take the maximum profit
Python Code
def maxProfit(prices):
min_price = prices[0]
max_profit = 0
for price in prices:
min_price = min(min_price, price)
4
max_profit = max(max_profit, price - min_price)
return max_profit
Time & Space
• Time: O(n)
• Space: O(1)
Q7. Minimum Swaps to Bring Elements ≤ K Together
Key Idea (Sliding Window)
1. Count elements ≤ K → window size
2. Count bad elements (>K) in first window
3. Slide window and minimize bad count
Python Code
def minSwaps(arr, n, k):
count = sum(1 for x in arr if x <= k)
bad = sum(1 for x in arr[:count] if x > k)
ans = bad
for i in range(0, n - count):
if arr[i] > k:
bad -= 1
if arr[i + count] > k:
bad += 1
ans = min(ans, bad)
return ans
Time & Space
• Time: O(n)
• Space: O(1)
5
Q8. Chocolate Distribution Problem
Key Idea
• Sort array
• Take every subarray of size M
• Minimize (max - min)
Python Code
def chocolateDistribution(arr, n, m):
if m > n:
return 0
[Link]()
min_diff = float('inf')
for i in range(n - m + 1):
min_diff = min(min_diff, arr[i + m - 1] - arr[i])
return min_diff
Time & Space
• Time: O(n log n)
• Space: O(1)
Q9. Trapping Rain Water
Key Idea (Two Pointer)
• Maintain leftMax and rightMax
• Water = min(leftMax, rightMax) - height
Python Code
def trap(arr):
n = len(arr)
left, right = 0, n - 1
left_max = right_max = 0
water = 0
while left < right:
if arr[left] <= arr[right]:
6
if arr[left] >= left_max:
left_max = arr[left]
else:
water += left_max - arr[left]
left += 1
else:
if arr[right] >= right_max:
right_max = arr[right]
else:
water += right_max - arr[right]
right -= 1
return water
Time & Space
• Time: O(n)
• Space: O(1)
Q10. Kth Smallest Element (Counting Sort Idea)
Key Idea
• Use frequency array since values ≤ 10^6
Python Code
def kthSmallest(arr, k):
freq = [0] * (max(arr) + 1)
for num in arr:
freq[num] += 1
count = 0
for i in range(len(freq)):
count += freq[i]
if count >= k:
return i
Time & Space
• Time: O(n + maxElement)
• Space: O(maxElement)
7
Q11. Minimum Platforms Required
Key Idea
• Sort arrival & departure arrays
• Use two pointers
Python Code
def minPlatforms(arr, dep):
[Link]()
[Link]()
i = j = 0
platforms = max_platforms = 0
n = len(arr)
while i < n and j < n:
if arr[i] <= dep[j]:
platforms += 1
max_platforms = max(max_platforms, platforms)
i += 1
else:
platforms -= 1
j += 1
return max_platforms
Q12. Stock Span Problem
Key Idea
• Use stack to store indices
Python Code
def stockSpan(prices):
stack = []
span = [0] * len(prices)
for i in range(len(prices)):
while stack and prices[stack[-1]] <= prices[i]:
[Link]()
span[i] = i + 1 if not stack else i - stack[-1]
8
[Link](i)
return span
Q13. Travelling Salesman Problem (DP + Bitmask)
Python Code
from functools import lru_cache
def tsp(cost):
n = len(cost)
@lru_cache(None)
def dp(mask, pos):
if mask == (1 << n) - 1:
return cost[pos][0]
ans = float('inf')
for city in range(n):
if not (mask & (1 << city)):
ans = min(ans, cost[pos][city] + dp(mask | (1 << city), city))
return ans
return dp(1, 0)
Q14. Cake Distribution (Binary Search on Answer)
Key Idea
• Binary search minimum sweetness
Python Code
def maxSweetness(sweetness, k):
left, right = min(sweetness), sum(sweetness)
def canDivide(mid):
pieces, curr = 0, 0
for s in sweetness:
curr += s
if curr >= mid:
9
pieces += 1
curr = 0
return pieces >= k + 1
ans = 0
while left <= right:
mid = (left + right) // 2
if canDivide(mid):
ans = mid
left = mid + 1
else:
right = mid - 1
return ans
Q15. Little Bear and Strings (Suffix Automaton – Conceptual)
Idea
• Count distinct substrings starting with T1 and ending with T2
• Requires suffix automaton or suffix array
• Asked rarely, Hard-level problem
✅ Final Notes
• All solutions are interview-optimized
• Follow expected time & space constraints
• Python syntax matches Cognizant / TCS / Amazon test style
📌 If you want: - PDF / DOCX export - Separate document per company - Dry-run diagrams - Practice test
questions
Just tell me 👍
10