Common DSA Interview Questions
1. Array Manipulation
Explanation: Uses Kadane’s Algorithm.
def max_subarray_sum(nums):
max_sum = curr_sum = nums[0]
for num in nums[1:]:
curr_sum = max(num, curr_sum + num)
max_sum = max(max_sum, curr_sum)
return max_sum
def rotate_array(nums, k):
k %= len(nums)
nums[:] = nums[-k:] + nums[:-k]
2. String Manipulation
def is_permutation(s1, s2):
return sorted(s1) == sorted(s2)
def reverse_string(s):
return s[::-1]
3. Linked Lists
def reverse_list(head):
prev = None
curr = head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
4. Sorting & Searching
# Quick Sort
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr)//2]
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + mid + quicksort(right)
# Binary Search
def binary_search(arr, target):
l, r = 0, len(arr) - 1
while l <= r:
mid = (l + r) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
l = mid + 1
else:
r = mid - 1
return -1
5. Dynamic Programming
# Fibonacci (DP)
def fib(n):
dp = [0, 1]
for i in range(2, n+1):
dp.append(dp[i-1] + dp[i-2])
return dp[n]
# Coin Change
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
6. Miscellaneous
# Stack using list
stack = []
stack.append(1)
stack.pop()
# Check Prime
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
Comments (0)
No comments yet
Be the first to share your thoughts!
Leave a Comment