What are Data Structures? — Optimize the Code¶

func contains(items []int, target int) bool {
    for _, item := range items {
        if item == target {
            return true
        }
    }
    return false
}

// Called in a loop: O(n) * O(m) = O(n*m)
func main() {
    allowList := []int{1, 5, 10, 15, 20, 25, 30}
    requests := []int{3, 5, 10, 99, 20}
    for _, r := range requests {
        if contains(allowList, r) {
            fmt.Println(r, "allowed")
        }
    }
}

func main() {
    allowSet := map[int]struct{}{
        1: {}, 5: {}, 10: {}, 15: {}, 20: {}, 25: {}, 30: {},
    }
    requests := []int{3, 5, 10, 99, 20}
    for _, r := range requests {
        if _, ok := allowSet[r]; ok { // O(1) lookup
            fmt.Println(r, "allowed")
        }
    }
}

func hasDuplicate(arr []int) bool {
    for i := 0; i < len(arr); i++ {
        for j := i + 1; j < len(arr); j++ {
            if arr[i] == arr[j] {
                return true
            }
        }
    }
    return false
}

func hasDuplicate(arr []int) bool {
    seen := make(map[int]struct{})
    for _, val := range arr {
        if _, exists := seen[val]; exists {
            return true
        }
        seen[val] = struct{}{}
    }
    return false
}

func buildString(words []string) string {
    result := ""
    for _, word := range words {
        result += word + " " // Creates a new string each time
    }
    return result
}

import "strings"

func buildString(words []string) string {
    var sb strings.Builder
    for _, word := range words {
        sb.WriteString(word)
        sb.WriteString(" ")
    }
    return sb.String()
}

func main() {
    events := []string{}
    for i := 0; i < 100000; i++ {
        event := fmt.Sprintf("event-%d", i)
        events = append([]string{event}, events...) // O(n) shift every time
    }
}

import "container/list"

func main() {
    events := list.New()
    for i := 0; i < 100000; i++ {
        events.PushFront(fmt.Sprintf("event-%d", i)) // O(1)
    }
}

import "sort"

func minMax(arr []int) (int, int) {
    sorted := make([]int, len(arr))
    copy(sorted, arr)
    sort.Ints(sorted)
    return sorted[0], sorted[len(sorted)-1]
}

func minMax(arr []int) (int, int) {
    if len(arr) == 0 {
        panic("empty array")
    }
    min, max := arr[0], arr[0]
    for _, val := range arr[1:] {
        if val < min {
            min = val
        }
        if val > max {
            max = val
        }
    }
    return min, max
}

func frequency(arr []int) map[int]int {
    result := map[int]int{}
    for _, val := range arr {
        if _, exists := result[val]; exists {
            continue // Already counted
        }
        count := 0
        for _, v := range arr {
            if v == val {
                count++
            }
        }
        result[val] = count
    }
    return result
}

func frequency(arr []int) map[int]int {
    result := map[int]int{}
    for _, val := range arr {
        result[val]++ // O(1) hash map increment
    }
    return result
}

type SlowQueue struct {
    data []int
}

func (q *SlowQueue) Enqueue(val int) {
    q.data = append(q.data, val)
}

func (q *SlowQueue) Dequeue() int {
    val := q.data[0]
    q.data = q.data[1:] // Looks O(1) in Go due to slice header, but...
    // Actually, this leaks memory — the underlying array never shrinks.
    // In other languages, this is a full O(n) shift.
    return val
}

import "container/list"

queue := list.New()
queue.PushBack(val)                    // enqueue: O(1)
front := queue.Front()
queue.Remove(front)                    // dequeue: O(1)

import "sort"

func isSorted(arr []int) bool {
    sorted := make([]int, len(arr))
    copy(sorted, arr)
    sort.Ints(sorted)
    for i := range arr {
        if arr[i] != sorted[i] {
            return false
        }
    }
    return true
}

func isSorted(arr []int) bool {
    for i := 1; i < len(arr); i++ {
        if arr[i] < arr[i-1] {
            return false
        }
    }
    return true
}

// Adjacency matrix: 10000 x 10000 = 100,000,000 entries
// Each int = 8 bytes → 800 MB of memory!
matrix := make([][]int, 10000)
for i := range matrix {
    matrix[i] = make([]int, 10000)
}

// Add edge
matrix[u][v] = 1
matrix[v][u] = 1

// Get neighbors: must scan entire row O(V)
func neighbors(matrix [][]int, u int) []int {
    result := []int{}
    for v := 0; v < len(matrix[u]); v++ {
        if matrix[u][v] != 0 {
            result = append(result, v)
        }
    }
    return result
}

// Adjacency list: only stores actual edges
adj := make(map[int][]int)

func addEdge(adj map[int][]int, u, v int) {
    adj[u] = append(adj[u], v)
    adj[v] = append(adj[v], u)
}

// Get neighbors: O(degree) — typically much less than V
func neighbors(adj map[int][]int, u int) []int {
    return adj[u]
}

func fib(n int) int {
    if n <= 1 {
        return n
    }
    return fib(n-1) + fib(n-2) // Exponential: each call branches into two
}
// fib(50) takes minutes. fib(100) never finishes.

func fib(n int) int {
    if n <= 1 {
        return n
    }
    a, b := 0, 1
    for i := 2; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}
// fib(50) is instant. fib(1000000) completes in milliseconds (with big int).

func twoSum(nums []int, target int) (int, int) {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i]+nums[j] == target {
                return i, j
            }
        }
    }
    return -1, -1
}

func twoSum(nums []int, target int) (int, int) {
    seen := make(map[int]int) // value -> index
    for i, num := range nums {
        complement := target - num
        if j, exists := seen[complement]; exists {
            return j, i
        }
        seen[num] = i
    }
    return -1, -1
}