Algorithms & Design Patterns Guide

This is a collection of notes covering fundamental algorithms, data structures, and software design patterns.

Sorting Algorithms

Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they’re in the wrong order.

Time Complexity:

Best case: O(n)
Average case: O(n²)
Worst case: O(n²)

Space Complexity: O(1)

Algorithm Steps:

Iterate through each item in the list
Compare the item with its neighbor
Swap elements if they are in the wrong order
Repeat until no more swapping occurs

class BubbleSort
  def sort(items)
    return items if items.size <= 1

    swapped = false
    loop do
      items.size.times do |n|
        if (items[n] <=> items[n+1]) == 1
          items[n], items[n+1] = items[n+1], items[n]
          swapped = true
        end
      end
      break unless swapped
      swapped = false
    end
    items
  end
end

Quick Sort

Quick sort is a divide-and-conquer algorithm that works by selecting a ‘pivot’ element and partitioning the array around it.

Time Complexity:

Best case: O(n log n)
Average case: O(n log n)
Worst case: O(n²)

Algorithm Steps:

Choose a pivot element
Partition the array so elements smaller than pivot are on the left, larger on the right
Recursively apply quicksort to the sub-arrays

class QuickSort
  def sort(items)
    return items if items.size <= 1
    
    pivot = items.delete_at(rand(items.size))
    left = items.select { |x| x < pivot }
    right = items.select { |x| x >= pivot }
    
    sort(left) + [pivot] + sort(right)
  end
end

Merge Sort

Merge sort is a stable, divide-and-conquer algorithm that divides the array into halves, sorts them, and merges them back together.

Time Complexity:

Best case: O(n log n)
Average case: O(n log n)
Worst case: O(n log n)

Space Complexity: O(n)

class MergeSort
  def sort(items)
    return items if items.size <= 1
    
    mid = items.size / 2
    left = sort(items[0...mid])
    right = sort(items[mid..-1])
    
    merge(left, right)
  end
  
  private
  
  def merge(left, right)
    result = []
    
    while !left.empty? && !right.empty?
      if left.first <= right.first
        result << left.shift
      else
        result << right.shift
      end
    end
    
    result + left + right
  end
end

Insertion Sort

Insertion sort builds the final sorted array one item at a time, inserting each element into its correct position.

Time Complexity:

Best case: O(n)
Average case: O(n²)
Worst case: O(n²)

class InsertionSort
  def sort(items)
    (1...items.size).each do |i|
      key = items[i]
      j = i - 1
      
      while j >= 0 && items[j] > key
        items[j + 1] = items[j]
        j -= 1
      end
      
      items[j + 1] = key
    end
    items
  end
end

Data Structures

Stack

A Last-In-First-Out (LIFO) data structure.

class Stack
  def initialize
    @items = []
  end
  
  def push(item)
    @items.push(item)
  end
  
  def pop
    @items.pop
  end
  
  def peek
    @items.last
  end
  
  def empty?
    @items.empty?
  end
  
  def size
    @items.size
  end
end

Common Applications:

Function call management
Expression evaluation
Undo operations
Browser history

Queue

A First-In-First-Out (FIFO) data structure.

class Queue
  def initialize
    @items = []
  end
  
  def enqueue(item)
    @items.push(item)
  end
  
  def dequeue
    @items.shift
  end
  
  def front
    @items.first
  end
  
  def empty?
    @items.empty?
  end
  
  def size
    @items.size
  end
end

Common Applications:

Task scheduling
Breadth-first search
Print queues
Buffer for streaming data

Binary Tree

A tree data structure where each node has at most two children.

class TreeNode
  attr_accessor :value, :left, :right
  
  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end
end

class BinaryTree
  attr_accessor :root
  
  def initialize
    @root = nil
  end
  
  def insert(value)
    @root = insert_recursive(@root, value)
  end
  
  def search(value)
    search_recursive(@root, value)
  end
  
  def inorder_traversal
    result = []
    inorder_recursive(@root, result)
    result
  end
  
  private
  
  def insert_recursive(node, value)
    return TreeNode.new(value) if node.nil?
    
    if value < node.value
      node.left = insert_recursive(node.left, value)
    elsif value > node.value
      node.right = insert_recursive(node.right, value)
    end
    
    node
  end
  
  def search_recursive(node, value)
    return false if node.nil?
    return true if node.value == value
    
    if value < node.value
      search_recursive(node.left, value)
    else
      search_recursive(node.right, value)
    end
  end
  
  def inorder_recursive(node, result)
    return if node.nil?
    
    inorder_recursive(node.left, result)
    result << node.value
    inorder_recursive(node.right, result)
  end
end

Design Patterns

Strategy Pattern

“The Strategy Pattern defines a family of algorithms, encapsulates each one, and makes them interchangeable. Strategy lets the algorithm vary independently from clients that use it.” - Head First Design Patterns

The Strategy pattern allows you to switch algorithms at runtime, adhering to the open/closed principle.

// Strategy interface
public interface IWeapon
{
    void UseWeapon();
}

// Concrete strategies
public class Sword : IWeapon
{
    public void UseWeapon()
    {
        Console.WriteLine("Swinging sword!");
    }
}

public class Axe : IWeapon
{
    public void UseWeapon()
    {
        Console.WriteLine("Chopping with axe!");
    }
}

public class Bow : IWeapon
{
    public void UseWeapon()
    {
        Console.WriteLine("Shooting arrow!");
    }
}

// Context class
public class Character
{
    private IWeapon weapon;
    
    public Character(IWeapon weapon)
    {
        this.weapon = weapon;
    }
    
    public void SetWeapon(IWeapon weapon)
    {
        this.weapon = weapon;
    }
    
    public void Fight()
    {
        weapon.UseWeapon();
    }
}

// Usage
var king = new Character(new Sword());
king.Fight(); // "Swinging sword!"

king.SetWeapon(new Axe());
king.Fight(); // "Chopping with axe!"

Observer Pattern

The Observer pattern defines a one-to-many dependency between objects so that when one object changes state, all dependents are notified automatically.

// Subject interface
public interface ISubject
{
    void RegisterObserver(IObserver observer);
    void RemoveObserver(IObserver observer);
    void NotifyObservers();
}

// Observer interface
public interface IObserver
{
    void Update(float temperature, float humidity, float pressure);
}

// Concrete subject
public class WeatherData : ISubject
{
    private List<IObserver> observers;
    private float temperature;
    private float humidity;
    private float pressure;
    
    public WeatherData()
    {
        observers = new List<IObserver>();
    }
    
    public void RegisterObserver(IObserver observer)
    {
        observers.Add(observer);
    }
    
    public void RemoveObserver(IObserver observer)
    {
        observers.Remove(observer);
    }
    
    public void NotifyObservers()
    {
        foreach (var observer in observers)
        {
            observer.Update(temperature, humidity, pressure);
        }
    }
    
    public void MeasurementsChanged()
    {
        NotifyObservers();
    }
    
    public void SetMeasurements(float temperature, float humidity, float pressure)
    {
        this.temperature = temperature;
        this.humidity = humidity;
        this.pressure = pressure;
        MeasurementsChanged();
    }
}

// Concrete observer
public class CurrentConditionsDisplay : IObserver
{
    private float temperature;
    private float humidity;
    
    public void Update(float temperature, float humidity, float pressure)
    {
        this.temperature = temperature;
        this.humidity = humidity;
        Display();
    }
    
    public void Display()
    {
        Console.WriteLine($"Current conditions: {temperature}°F and {humidity}% humidity");
    }
}

Factory Pattern

The Factory pattern provides an interface for creating objects without specifying their exact classes.

// Product interface
public interface IPizza
{
    void Prepare();
    void Bake();
    void Cut();
    void Box();
}

// Concrete products
public class CheesePizza : IPizza
{
    public void Prepare() => Console.WriteLine("Preparing cheese pizza");
    public void Bake() => Console.WriteLine("Baking cheese pizza");
    public void Cut() => Console.WriteLine("Cutting cheese pizza");
    public void Box() => Console.WriteLine("Boxing cheese pizza");
}

public class PepperoniPizza : IPizza
{
    public void Prepare() => Console.WriteLine("Preparing pepperoni pizza");
    public void Bake() => Console.WriteLine("Baking pepperoni pizza");
    public void Cut() => Console.WriteLine("Cutting pepperoni pizza");
    public void Box() => Console.WriteLine("Boxing pepperoni pizza");
}

// Factory
public abstract class PizzaStore
{
    public IPizza OrderPizza(string type)
    {
        IPizza pizza = CreatePizza(type);
        
        pizza.Prepare();
        pizza.Bake();
        pizza.Cut();
        pizza.Box();
        
        return pizza;
    }
    
    protected abstract IPizza CreatePizza(string type);
}

// Concrete factory
public class NYPizzaStore : PizzaStore
{
    protected override IPizza CreatePizza(string type)
    {
        return type switch
        {
            "cheese" => new CheesePizza(),
            "pepperoni" => new PepperoniPizza(),
            _ => throw new ArgumentException("Unknown pizza type")
        };
    }
}

Adapter Pattern

The Adapter pattern allows incompatible interfaces to work together by wrapping an existing class with a new interface.

// Target interface (what the client expects)
public interface ITarget
{
    void Request();
}

// Adaptee (existing class with incompatible interface)
public class Adaptee
{
    public void SpecificRequest()
    {
        Console.WriteLine("Specific request");
    }
}

// Adapter
public class Adapter : ITarget
{
    private readonly Adaptee adaptee;
    
    public Adapter(Adaptee adaptee)
    {
        this.adaptee = adaptee;
    }
    
    public void Request()
    {
        adaptee.SpecificRequest();
    }
}

// Usage
var adaptee = new Adaptee();
var adapter = new Adapter(adaptee);
adapter.Request(); // Calls adaptee.SpecificRequest()

State Pattern

The State pattern allows an object to alter its behavior when its internal state changes, appearing as if the object changed its class.

// State interface
public interface IState
{
    void HandleRequest(Context context);
}

// Concrete states
public class ConcreteStateA : IState
{
    public void HandleRequest(Context context)
    {
        Console.WriteLine("Handling request in State A");
        context.SetState(new ConcreteStateB());
    }
}

public class ConcreteStateB : IState
{
    public void HandleRequest(Context context)
    {
        Console.WriteLine("Handling request in State B");
        context.SetState(new ConcreteStateA());
    }
}

// Context
public class Context
{
    private IState state;
    
    public Context(IState state)
    {
        this.state = state;
    }
    
    public void SetState(IState state)
    {
        this.state = state;
    }
    
    public void Request()
    {
        state.HandleRequest(this);
    }
}

Visitor Pattern

The Visitor pattern lets you define new operations without changing the classes of elements on which they operate.

// Visitor interface
public interface IVisitor
{
    void Visit(ConcreteElementA element);
    void Visit(ConcreteElementB element);
}

// Element interface
public interface IElement
{
    void Accept(IVisitor visitor);
}

// Concrete elements
public class ConcreteElementA : IElement
{
    public void Accept(IVisitor visitor)
    {
        visitor.Visit(this);
    }
    
    public string OperationA()
    {
        return "ConcreteElementA operation";
    }
}

public class ConcreteElementB : IElement
{
    public void Accept(IVisitor visitor)
    {
        visitor.Visit(this);
    }
    
    public string OperationB()
    {
        return "ConcreteElementB operation";
    }
}

// Concrete visitor
public class ConcreteVisitor : IVisitor
{
    public void Visit(ConcreteElementA element)
    {
        Console.WriteLine($"Visiting {element.OperationA()}");
    }
    
    public void Visit(ConcreteElementB element)
    {
        Console.WriteLine($"Visiting {element.OperationB()}");
    }
}

Dispose Pattern

The Dispose pattern provides a mechanism for releasing unmanaged resources deterministically.

public class ResourceHolder : IDisposable
{
    private bool disposed = false;
    private IntPtr unmanagedResource;
    private FileStream managedResource;
    
    public ResourceHolder()
    {
        // Allocate unmanaged and managed resources
        unmanagedResource = AllocateUnmanagedResource();
        managedResource = new FileStream("temp.txt", FileMode.Create);
    }
    
    // Public dispose method
    public void Dispose()
    {
        Dispose(true);
        GC.SuppressFinalize(this);
    }
    
    // Protected virtual dispose method
    protected virtual void Dispose(bool disposing)
    {
        if (!disposed)
        {
            if (disposing)
            {
                // Dispose managed resources
                managedResource?.Dispose();
            }
            
            // Dispose unmanaged resources
            if (unmanagedResource != IntPtr.Zero)
            {
                FreeUnmanagedResource(unmanagedResource);
                unmanagedResource = IntPtr.Zero;
            }
            
            disposed = true;
        }
    }
    
    // Finalizer
    ~ResourceHolder()
    {
        Dispose(false);
    }
    
    private IntPtr AllocateUnmanagedResource()
    {
        // Simulate unmanaged resource allocation
        return new IntPtr(1234);
    }
    
    private void FreeUnmanagedResource(IntPtr resource)
    {
        // Simulate unmanaged resource cleanup
    }
}

Algorithm Analysis

Big O Notation

Big O notation describes the upper bound of algorithm complexity.

Common Time Complexities:

O(1) - Constant time
O(log n) - Logarithmic time
O(n) - Linear time
O(n log n) - Log-linear time
O(n²) - Quadratic time
O(2ⁿ) - Exponential time
O(n!) - Factorial time

Examples:

O(1)     - Array access, hash table lookup
O(log n) - Binary search, balanced tree operations
O(n)     - Linear search, simple array traversal
O(n²)    - Nested loops, bubble sort
O(2ⁿ)    - Recursive Fibonacci, subset generation

Space Complexity

Space complexity measures the amount of memory an algorithm uses.

Types:

Auxiliary space: Extra space used by algorithm
Space complexity: Auxiliary space + input space

Best Practices

Choose appropriate data structures for your use case
Analyze time and space complexity before implementation
Consider trade-offs between time and space
Profile and measure actual performance
Optimize based on real usage patterns

This guide provides a solid foundation for understanding algorithms and design patterns, essential knowledge for software development and system design.