Certainly! Here are 10 common algorithms that you should be familiar with before your Python coding interview, along with Python code examples for each:
- Binary Search:
Binary search is used to efficiently find a target element in a sorted list or array.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1- Bubble Sort:
Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]- Quick Sort:
Quick sort is a divide-and-conquer sorting algorithm that uses a pivot element to partition the array into smaller subarrays.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)- Merge Sort:
Merge sort is another divide-and-conquer sorting algorithm that divides the input array into two halves, sorts them, and then merges them.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
def merge(left, right):
result = []
while left and right:
if left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
if left:
result.extend(left)
if right:
result.extend(right)
return result- Depth-First Search (DFS):
DFS is used to traverse or search a tree or graph data structure deeply.
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
def dfs(graph, node, visited):
if node not in visited:
print(node)
visited.add(node)
for neighbor in graph[node]:
dfs(graph, neighbor, visited)
visited = set()
dfs(graph, 'A', visited)- Breadth-First Search (BFS):
BFS is used to traverse or search a tree or graph data structure breadth-first.
from collections import deque
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
print(node)
visited.add(node)
queue.extend(graph[node])
bfs(graph, 'A')- Fibonacci Sequence:
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones.
def fibonacci(n):
if n <= 0:
return []
elif n == 1:
return [0]
elif n == 2:
return [0, 1]
else:
fib = [0, 1]
for i in range(2, n):
fib.append(fib[i - 1] + fib[i - 2])
return fib- Factorial:
Calculate the factorial of a non-negative integer.
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)- Dijkstra’s Algorithm:
Dijkstra’s algorithm is used to find the shortest path between nodes in a graph with weighted edges.
import heapq
def dijkstra(graph, start):
distances = {node: float('infinity') for node in graph}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances- Knapsack Problem:
The knapsack problem is a classic optimization problem where you must maximize the total value of items included in a knapsack without exceeding its weight capacity.
def knapsack(items, capacity):
n = len(items)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
weight, value = items[i - 1]
for w in range(capacity + 1):
if weight <= w:
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight] + value)
else:
dp[i][w] = dp[i - 1][w]
return dp[n][capacity]These are just a few common algorithms you might encounter in a coding interview. Understanding these algorithms and being able to implement them in Python can be valuable during technical interviews.