DSA Interview Problems – Python Solutions with
Explanation
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)
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
1
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)
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])
2
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]:
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)
3
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)
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
4
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]
[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]
5
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:
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
6
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 👍