Exploring the World of Katas: Algorithms, Data Structures, and Problem Solving

Katas

Katas

Algorithms

A simple example of a search algorithm:

def linear_search(arr, target):
    for i, element in enumerate(arr):
        if element == target:
            return i
    return -1

# Example usage
print(linear_search([1, 3, 5, 7, 9], 5))  # Output: 2
print(linear_search([1, 3, 5, 7, 9], 6))  # Output: -1

Arrays

An example of array manipulation:

def reverse_array(arr):
    return arr[::-1]

# Example usage
original = [1, 2, 3, 4, 5]
reversed_arr = reverse_array(original)
print(reversed_arr)  # Output: [5, 4, 3, 2, 1]

BFS (Breadth-First Search)

A simple BFS implementation for a graph:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Example usage
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs(graph, 'A')  # Output: A B C D E F

Backtracking

A simple backtracking example to generate all possible subsets:

def generate_subsets(nums):
    def backtrack(start, current):
        result.append(current[:])
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    result = []
    backtrack(0, [])
    return result

# Example usage
print(generate_subsets([1, 2, 3]))
# Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Binary Search

An implementation of binary search:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Example usage
sorted_array = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(sorted_array, 7))  # Output: 3
print(binary_search(sorted_array, 6))  # Output: -1