Youssef Ameachaq's Blog

Youssef Ameachaq

3️⃣ Data Structures & Algorithms

1. Trees

A tree is a hierarchical structure with a collection of nodes. Each node has a value and links to child nodes. A binary tree is a type where each node has at most two children (left and right).

Example: Binary Tree in Go

package main

import "fmt"

// Define a node
type Node struct {
    value int
    left  *Node
    right *Node
}

// Function to insert a new node
func insert(root *Node, value int) *Node {
    if root == nil {
        return &Node{value: value}
    }
    if value < root.value {
        root.left = insert(root.left, value)
    } else {
        root.right = insert(root.right, value)
    }
    return root
}

// Function to print tree (in-order traversal)
func inOrder(root *Node) {
    if root != nil {
        inOrder(root.left)
        fmt.Print(root.value, " ")
        inOrder(root.right)
    }
}

func main() {
    root := &Node{value: 10}
    insert(root, 5)
    insert(root, 15)
    insert(root, 3)

    fmt.Println("In-order traversal:")
    inOrder(root) // Output: 3 5 10 15
}

2. Graphs

A graph is a collection of nodes (also called vertices) and edges connecting pairs of nodes. It can be directed or undirected. A directed graph has edges pointing in a specific direction.

Example: Graph in Go (Adjacency List)

package main

import "fmt"

// Define the graph structure using a map
type Graph struct {
    adjList map[int][]int
}

// Function to add a new edge to the graph
func (g *Graph) addEdge(u, v int) {
    g.adjList[u] = append(g.adjList[u], v)
}

// Function to print the graph
func (g *Graph) printGraph() {
    for node, neighbors := range g.adjList {
        fmt.Printf("%d -> %v\n", node, neighbors)
    }
}

func main() {
    g := Graph{adjList: make(map[int][]int)}

    g.addEdge(1, 2)
    g.addEdge(1, 3)
    g.addEdge(2, 4)

    g.printGraph()
}

3. Hash Maps (Hash Tables)

A hash map is a collection of key-value pairs. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Example: Hash Map in Go

package main

import "fmt"

func main() {
    // Create a hash map
    myMap := make(map[string]int)

    // Add key-value pairs
    myMap["apple"] = 5
    myMap["banana"] = 3
    myMap["cherry"] = 8

    // Access a value by key
    fmt.Println("Value for 'banana':", myMap["banana"]) // Output: 3

    // Delete a key
    delete(myMap, "apple")

    // Check if a key exists
    value, exists := myMap["apple"]
    if exists {
        fmt.Println("Apple exists:", value)
    } else {
        fmt.Println("Apple doesn't exist")
    }
}

4. Queues

A queue is a linear data structure that follows the FIFO (First In, First Out) principle. You add elements at the back and remove them from the front.

Example: Queue in Go (Using slice)

package main

import "fmt"

// Define the Queue structure
type Queue struct {
    elements []int
}

// Function to add an element to the queue
func (q *Queue) enqueue(value int) {
    q.elements = append(q.elements, value)
}

// Function to remove an element from the queue
func (q *Queue) dequeue() (int, bool) {
    if len(q.elements) == 0 {
        return 0, false
    }
    value := q.elements[0]
    q.elements = q.elements[1:]
    return value, true
}

func main() {
    q := Queue{}

    q.enqueue(10)
    q.enqueue(20)

    value, _ := q.dequeue()
    fmt.Println("Dequeued:", value) // Output: 10
}

5. Stacks

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. You add elements on top and remove them from the top.

Example: Stack in Go (Using slice)

package main

import "fmt"

// Define the Stack structure
type Stack struct {
    elements []int
}

// Function to push an element onto the stack
func (s *Stack) push(value int) {
    s.elements = append(s.elements, value)
}

// Function to pop an element from the stack
func (s *Stack) pop() (int, bool) {
    if len(s.elements) == 0 {
        return 0, false
    }
    value := s.elements[len(s.elements)-1]
    s.elements = s.elements[:len(s.elements)-1]
    return value, true
}

func main() {
    s := Stack{}

    s.push(10)
    s.push(20)

    value, _ := s.pop()
    fmt.Println("Popped:", value) // Output: 20
}

6. Sorting & Searching Algorithms

Sorting (Bubble Sort Example)

Bubble Sort compares adjacent elements and swaps them if they are in the wrong order. It repeats this until the entire array is sorted.

package main

import "fmt"

// Bubble sort function
func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j] // Swap
            }
        }
    }
}

func main() {
    arr := []int{5, 2, 9, 1, 5, 6}
    bubbleSort(arr)
    fmt.Println("Sorted array:", arr) // Output: [1 2 5 5 6 9]
}

Searching (Binary Search Example)

Binary Search works on sorted arrays. It repeatedly divides the search interval in half. If the value is less than the item in the middle, it narrows the search to the left half; otherwise, it narrows it to the right half.

package main

import "fmt"

// Binary search function
func binarySearch(arr []int, target int) int {
    low, high := 0, len(arr)-1
    for low <= high {
        mid := (low + high) / 2
        if arr[mid] == target {
            return mid // Target found
        } else if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return -1 // Target not found
}

func main() {
    arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
    target := 5
    result := binarySearch(arr, target)
    fmt.Println("Index of target:", result) // Output: 4
}

7. Big-O Notation & Complexity Analysis

Big-O is used to describe the performance or complexity of an algorithm. It focuses on how the runtime or space requirements grow as the input size increases.

Example Analysis:

Problem-solving techniques

1. Brute Force

Brute force is a straightforward approach where you try all possible solutions until you find the correct one. It’s not always the most efficient, but it’s simple and works for smaller problems.

Example: Finding a pair that adds up to a target sum

package main

import "fmt"

// Brute force approach to find two numbers that sum up to the target
func findPair(nums []int, target int) (int, int, bool) {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i]+nums[j] == target {
                return nums[i], nums[j], true
            }
        }
    }
    return 0, 0, false
}

func main() {
    nums := []int{10, 15, 3, 7}
    target := 17
    num1, num2, found := findPair(nums, target)
    if found {
        fmt.Println("Pair found:", num1, num2) // Output: Pair found: 10 7
    } else {
        fmt.Println("No pair found")
    }
}

2. Two Pointers

The two-pointer technique uses two pointers to solve problems by iterating through the data in a way that eliminates unnecessary checks, often improving efficiency compared to brute force.

Example: Finding a pair that adds up to a target sum (Optimized)

package main

import "fmt"

// Two-pointer technique for sorted array
func findPair(nums []int, target int) (int, int, bool) {
    left, right := 0, len(nums)-1
    for left < right {
        sum := nums[left] + nums[right]
        if sum == target {
            return nums[left], nums[right], true
        } else if sum < target {
            left++
        } else {
            right--
        }
    }
    return 0, 0, false
}

func main() {
    nums := []int{3, 7, 10, 15}
    target := 17
    num1, num2, found := findPair(nums, target)
    if found {
        fmt.Println("Pair found:", num1, num2) // Output: Pair found: 3 14
    } else {
        fmt.Println("No pair found")
    }
}

3. Divide and Conquer

Divide and conquer splits a problem into smaller sub-problems, solves them individually, and then combines the results. This is efficient for problems like sorting or searching.

Example: Merge Sort (Divide and Conquer)

package main

import "fmt"

// Merge function to combine two sorted slices
func merge(left, right []int) []int {
    result := []int{}
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] < right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}

// MergeSort function
func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}

func main() {
    arr := []int{3, 1, 4, 1, 5, 9, 2, 6}
    sortedArr := mergeSort(arr)
    fmt.Println("Sorted array:", sortedArr) // Output: Sorted array: [1 1 2 3 4 5 6 9]
}

4. Dynamic Programming (DP)

Dynamic programming is used to solve problems by breaking them down into smaller sub-problems and storing the results of sub-problems to avoid redundant calculations.

Example: Fibonacci Sequence (DP)

package main

import "fmt"

// Fibonacci function with dynamic programming
func fibonacci(n int) int {
    dp := make([]int, n+1)
    dp[0] = 0
    dp[1] = 1
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

func main() {
    n := 10
    fmt.Println("Fibonacci of", n, "is", fibonacci(n)) // Output: Fibonacci of 10 is 55
}

5. Backtracking

Backtracking is a technique for solving problems by trying out all possible solutions and “backtracking” when you reach a solution that doesn’t work.

Example: Solving N-Queens Problem

package main

import "fmt"

// Function to check if it's safe to place a queen
func isSafe(board [][]int, row, col int) bool {
    for i := 0; i < row; i++ {
        if board[i][col] == 1 {
            return false
        }
        if col-(row-i) >= 0 && board[i][col-(row-i)] == 1 {
            return false
        }
        if col+(row-i) < len(board) && board[i][col+(row-i)] == 1 {
            return false
        }
    }
    return true
}

// Function to solve the N-Queens problem
func solveNQueens(board [][]int, row int) bool {
    if row == len(board) {
        return true
    }
    for col := 0; col < len(board); col++ {
        if isSafe(board, row, col) {
            board[row][col] = 1
            if solveNQueens(board, row+1) {
                return true
            }
            board[row][col] = 0 // Backtrack
        }
    }
    return false
}

func printBoard(board [][]int) {
    for _, row := range board {
        for _, val := range row {
            if val == 1 {
                fmt.Print("Q ")
            } else {
                fmt.Print(". ")
            }
        }
        fmt.Println()
    }
}

func main() {
    n := 4
    board := make([][]int, n)
    for i := 0; i < n; i++ {
        board[i] = make([]int, n)
    }

    if solveNQueens(board, 0) {
        printBoard(board)
    } else {
        fmt.Println("No solution")
    }
}

6. Greedy Algorithm

A greedy algorithm makes the locally optimal choice at each step, aiming for a global optimum. It doesn’t always work, but it’s effective for certain problems.

Example: Coin Change Problem (Greedy Approach)

package main

import "fmt"

// Function to find the minimum number of coins
func coinChange(coins []int, amount int) int {
    count := 0
    for _, coin := range coins {
        for amount >= coin {
            amount -= coin
            count++
        }
    }
    if amount > 0 {
        return -1 // No solution
    }
    return count
}

func main() {
    coins := []int{1, 5, 10, 25}
    amount := 30
    result := coinChange(coins, amount)
    fmt.Println("Minimum number of coins:", result) // Output: Minimum number of coins: 2
}

7. Divide and Conquer vs. Dynamic Programming

Both techniques solve problems by breaking them down into sub-problems, but the difference lies in how they handle overlapping sub-problems: