10 common algorithms

Certainly! Here are 10 common algorithms that you should be familiar with before your Python coding interview, along with Python code examples for each:

1. 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

2. 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]

3. 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)

4. 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

5. 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)

6. 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')

7. 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

8. Factorial:
   Calculate the factorial of a non-negative integer.

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

9. 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

10. 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.