What is Binary Search and what is its time complexity? Write the implementation in Python.
Show ▼
Hide ▲
Binary Search finds a target in a sorted array by repeatedly halving the search space.
Time: O(log n) | Space: O(1)
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
What is Bubble Sort and what is its time complexity? Write the implementation in Python.
Show ▼
Hide ▲
Bubble Sort repeatedly swaps adjacent elements if they are in the wrong order.
Time: O(n²) | Space: O(1)
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr
What is Merge Sort and what is its time complexity? Write the implementation in Python.
Show ▼
Hide ▲
Merge Sort is a divide-and-conquer algorithm that splits the array in half, recursively sorts each half, then merges them.
Time: O(n log n) | Space: O(n)
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 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
result.extend(left[i:])
result.extend(right[j:])
return result
What is Quick Sort and what is its time complexity? Write the implementation in Python.
Show ▼
Hide ▲
Quick Sort picks a pivot, partitions elements around it, then recursively sorts each partition.
Time: O(n log n) avg, O(n²) worst | Space: O(log n)
def quick_sort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo < hi:
pivot_idx = partition(arr, lo, hi)
quick_sort(arr, lo, pivot_idx - 1)
quick_sort(arr, pivot_idx + 1, hi)
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
return i + 1
What is BFS (Breadth-First Search) and what is its time complexity? Write the implementation in Python.
Show ▼
Hide ▲
BFS explores a graph level by level using a queue. Used for shortest path in unweighted graphs.
Time: O(V + E) | Space: O(V)
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
What is DFS (Depth-First Search) and what is its time complexity? Write the implementation in Python (iterative and recursive).
Show ▼
Hide ▲
DFS explores a graph by going as deep as possible before backtracking.
Time: O(V + E) | Space: O(V)
Iterative:
def dfs_iterative(graph, start):
visited = set()
stack = [start]
result = []
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
result.append(node)
for neighbor in graph[node]:
stack.append(neighbor)
return result
Recursive:
def dfs_recursive(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
return visited
What is Dijkstra's Algorithm and what is its time complexity? Write the implementation in Python.
Show ▼
Hide ▲
Dijkstra's finds the shortest path from a source to all vertices in a weighted graph with non-negative weights.
Time: O((V + E) log V) with min-heap | Space: O(V)
import heapq
def dijkstra(graph, start):
dist = {node: float('inf') for node in graph}
dist[start] = 0
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, weight in graph[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heapq.heappush(heap, (dist[v], v))
return dist
What is the Two Pointers technique? Write a Python example: find a pair in a sorted array that sums to a target.
Show ▼
Hide ▲
Two Pointers uses two indices moving toward each other (or in the same direction) to solve problems on sorted arrays or linked lists in O(n).
Time: O(n) | Space: O(1)
def two_sum_sorted(arr, target):
lo, hi = 0, len(arr) - 1
while lo < hi:
s = arr[lo] + arr[hi]
if s == target:
return (lo, hi)
elif s < target:
lo += 1
else:
hi -= 1
return None
What is the Sliding Window technique? Write a Python example: find the max sum of a subarray of size k.
Show ▼
Hide ▲
Sliding Window maintains a window of elements and slides it across the array, adding/removing one element at a time.
Time: O(n) | Space: O(1)
def max_sum_subarray(arr, k):
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
What is Dynamic Programming (Fibonacci)? Write top-down (memoization) and bottom-up (tabulation) in Python.
Show ▼
Hide ▲
DP solves problems by breaking them into overlapping subproblems and storing results to avoid recomputation.
Top-down (Memoization): O(n) time, O(n) space
def fib_memo(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n]
Bottom-up (Tabulation): O(n) time, O(1) space
def fib_tab(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
What is Kadane's Algorithm? Write the implementation in Python.
Show ▼
Hide ▲
Kadane's Algorithm finds the maximum sum contiguous subarray in O(n) time.
Time: O(n) | Space: O(1)
def max_subarray(arr):
max_ending_here = arr[0]
max_so_far = arr[0]
for num in arr[1:]:
max_ending_here = max(num, max_ending_here + num)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
What is the 0/1 Knapsack problem? Write the DP solution in Python.
Show ▼
Hide ▲
Given items with weights and values and a capacity W, find the maximum value without exceeding W. Each item is used at most once.
Time: O(n * W) | Space: O(n * W)
def knapsack(weights, values, W):
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(W + 1):
dp[i][w] = dp[i-1][w]
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1])
return dp[n][W]