Advanced Data Structures: A Coffee Shop Guide

package main

import "fmt"

type OrderQueue struct {
    orders []string
}

func (q *OrderQueue) Enqueue(order string) {
    q.orders = append(q.orders, order)
    fmt.Printf("📝 Added order: %s (Queue size: %d)\n", order, len(q.orders))
}

func (q *OrderQueue) Dequeue() string {
    if len(q.orders) == 0 {
        return ""
    }
    order := q.orders[0]
    q.orders = q.orders[1:]
    fmt.Printf("✅ Serving order: %s (Remaining: %d)\n", order, len(q.orders))
    return order
}

func (q *OrderQueue) IsEmpty() bool {
    return len(q.orders) == 0
}

func main() {
    queue := &OrderQueue{}

    // Morning rush
    queue.Enqueue("Latte")
    queue.Enqueue("Cappuccino")
    queue.Enqueue("Espresso")

    // Serve customers
    queue.Dequeue() // Latte
    queue.Dequeue() // Cappuccino

    queue.Enqueue("Mocha")
    queue.Dequeue() // Espresso
}

package main

import "fmt"

type CupStack struct {
    cups []string
}

func (s *CupStack) Push(cup string) {
    s.cups = append(s.cups, cup)
    fmt.Printf("➕ Stacked cup: %s (Height: %d)\n", cup, len(s.cups))
}

func (s *CupStack) Pop() string {
    if len(s.cups) == 0 {
        return ""
    }
    cup := s.cups[len(s.cups)-1]
    s.cups = s.cups[:len(s.cups)-1]
    fmt.Printf("➖ Took cup: %s (Remaining: %d)\n", cup, len(s.cups))
    return cup
}

func (s *CupStack) Peek() string {
    if len(s.cups) == 0 {
        return ""
    }
    return s.cups[len(s.cups)-1]
}

func main() {
    stack := &CupStack{}

    // Stack cups
    stack.Push("Small Cup #1")
    stack.Push("Medium Cup #2")
    stack.Push("Large Cup #3")

    // Use cups (LIFO order)
    fmt.Println("Top cup:", stack.Peek())
    stack.Pop() // Large Cup #3
    stack.Pop() // Medium Cup #2
}

package main

import "fmt"

type Customer struct {
    Name   string
    Points int
    Next   *Customer
}

type LoyaltyChain struct {
    Head *Customer
}

func (l *LoyaltyChain) AddCustomer(name string, points int) {
    newCustomer := &Customer{
        Name:   name,
        Points: points,
    }

    if l.Head == nil {
        l.Head = newCustomer
        return
    }

    current := l.Head
    for current.Next != nil {
        current = current.Next
    }
    current.Next = newCustomer
    fmt.Printf("🎁 Added %s to loyalty program (%d points)\n", name, points)
}

func (l *LoyaltyChain) Display() {
    current := l.Head
    fmt.Println("\n📋 Loyalty Chain:")
    for current != nil {
        fmt.Printf("  → %s (%d points)\n", current.Name, current.Points)
        current = current.Next
    }
}

func main() {
    chain := &LoyaltyChain{}

    chain.AddCustomer("Alice", 50)
    chain.AddCustomer("Bob", 30)
    chain.AddCustomer("Carol", 80)

    chain.Display()
}

package main

import "fmt"

type OrderMap struct {
    orders map[string]string
}

func NewOrderMap() *OrderMap {
    return &OrderMap{
        orders: make(map[string]string),
    }
}

func (m *OrderMap) PlaceOrder(name, drink string) {
    m.orders[name] = drink
    fmt.Printf("☕ Order placed: %s → %s\n", name, drink)
}

func (m *OrderMap) GetOrder(name string) (string, bool) {
    drink, exists := m.orders[name]
    return drink, exists
}

func (m *OrderMap) CompleteOrder(name string) {
    if drink, exists := m.orders[name]; exists {
        fmt.Printf("✅ Completed: %s's %s\n", name, drink)
        delete(m.orders, name)
    }
}

func main() {
    orders := NewOrderMap()

    // Take orders
    orders.PlaceOrder("Alice", "Latte")
    orders.PlaceOrder("Bob", "Espresso")
    orders.PlaceOrder("Carol", "Mocha")

    // Barista calls: "Order for Alice!"
    if drink, found := orders.GetOrder("Alice"); found {
        fmt.Printf("📢 %s is ready!\n", drink)
        orders.CompleteOrder("Alice")
    }
}

package main

import "fmt"

type Order struct {
    Name  string
    Drink string
    Next  *Order
}

type HashTableWithChaining struct {
    buckets []*Order
    size    int
}

func NewHashTable(size int) *HashTableWithChaining {
    return &HashTableWithChaining{
        buckets: make([]*Order, size),
        size:    size,
    }
}

func (ht *HashTableWithChaining) hash(name string) int {
    hash := 0
    for _, ch := range name {
        hash += int(ch)
    }
    return hash % ht.size
}

func (ht *HashTableWithChaining) Insert(name, drink string) {
    index := ht.hash(name)
    newOrder := &Order{Name: name, Drink: drink}

    if ht.buckets[index] == nil {
        ht.buckets[index] = newOrder
        fmt.Printf("☕ Order: %s → %s (bucket %d)\n", name, drink, index)
    } else {
        // Collision! Add to chain
        fmt.Printf("⚠️  Collision at bucket %d! Adding %s to chain\n", index, name)
        current := ht.buckets[index]
        for current.Next != nil {
            current = current.Next
        }
        current.Next = newOrder
    }
}

func (ht *HashTableWithChaining) Get(name string) string {
    index := ht.hash(name)
    current := ht.buckets[index]

    for current != nil {
        if current.Name == name {
            return current.Drink
        }
        current = current.Next
    }
    return ""
}

func main() {
    ht := NewHashTable(5)

    // These might collide depending on hash function
    ht.Insert("Bob", "Latte")
    ht.Insert("Bobby", "Espresso")
    ht.Insert("Robert", "Mocha")

    fmt.Println("\n🔍 Finding Bob's order:", ht.Get("Bob"))
}

package main

import "fmt"

type MenuItem struct {
    Name  string
    Price int
    Left  *MenuItem
    Right *MenuItem
}

type MenuBST struct {
    Root *MenuItem
}

func (m *MenuBST) Insert(name string, price int) {
    newItem := &MenuItem{Name: name, Price: price}

    if m.Root == nil {
        m.Root = newItem
        return
    }

    m.insertNode(m.Root, newItem)
}

func (m *MenuBST) insertNode(current, newItem *MenuItem) {
    if newItem.Price < current.Price {
        if current.Left == nil {
            current.Left = newItem
        } else {
            m.insertNode(current.Left, newItem)
        }
    } else {
        if current.Right == nil {
            current.Right = newItem
        } else {
            m.insertNode(current.Right, newItem)
        }
    }
}

func (m *MenuBST) FindInRange(min, max int) {
    fmt.Printf("\n☕ Items between $%d and $%d:\n", min, max)
    m.inRangeSearch(m.Root, min, max)
}

func (m *MenuBST) inRangeSearch(node *MenuItem, min, max int) {
    if node == nil {
        return
    }

    if node.Price > min {
        m.inRangeSearch(node.Left, min, max)
    }

    if node.Price >= min && node.Price <= max {
        fmt.Printf("  - %s: $%d\n", node.Name, node.Price)
    }

    if node.Price < max {
        m.inRangeSearch(node.Right, min, max)
    }
}

func main() {
    menu := &MenuBST{}

    menu.Insert("Latte", 5)
    menu.Insert("Americano", 3)
    menu.Insert("Macchiato", 8)
    menu.Insert("Cold Brew", 4)
    menu.Insert("Frappuccino", 6)

    menu.FindInRange(4, 6) // Find drinks $4-$6
}

package main

import (
    "fmt"
    "math"
)

type AVLNode struct {
    Name   string
    Price  int
    Height int
    Left   *AVLNode
    Right  *AVLNode
}

func height(node *AVLNode) int {
    if node == nil {
        return 0
    }
    return node.Height
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func getBalance(node *AVLNode) int {
    if node == nil {
        return 0
    }
    return height(node.Left) - height(node.Right)
}

func rightRotate(y *AVLNode) *AVLNode {
    x := y.Left
    T2 := x.Right

    x.Right = y
    y.Left = T2

    y.Height = max(height(y.Left), height(y.Right)) + 1
    x.Height = max(height(x.Left), height(x.Right)) + 1

    return x
}

func leftRotate(x *AVLNode) *AVLNode {
    y := x.Right
    T2 := y.Left

    y.Left = x
    x.Right = T2

    x.Height = max(height(x.Left), height(x.Right)) + 1
    y.Height = max(height(y.Left), height(y.Right)) + 1

    return y
}

func insert(node *AVLNode, name string, price int) *AVLNode {
    if node == nil {
        return &AVLNode{Name: name, Price: price, Height: 1}
    }

    if price < node.Price {
        node.Left = insert(node.Left, name, price)
    } else if price > node.Price {
        node.Right = insert(node.Right, name, price)
    } else {
        return node
    }

    node.Height = 1 + max(height(node.Left), height(node.Right))

    balance := getBalance(node)

    // Left-Left Case
    if balance > 1 && price < node.Left.Price {
        return rightRotate(node)
    }

    // Right-Right Case
    if balance < -1 && price > node.Right.Price {
        return leftRotate(node)
    }

    // Left-Right Case
    if balance > 1 && price > node.Left.Price {
        node.Left = leftRotate(node.Left)
        return rightRotate(node)
    }

    // Right-Left Case
    if balance < -1 && price < node.Right.Price {
        node.Right = rightRotate(node.Right)
        return leftRotate(node)
    }

    return node
}

func main() {
    var root *AVLNode

    items := []struct {
        name  string
        price int
    }{
        {"Espresso", 3},
        {"Latte", 5},
        {"Cappuccino", 4},
        {"Mocha", 6},
        {"Americano", 3},
    }

    for _, item := range items {
        root = insert(root, item.name, item.price)
        fmt.Printf("✅ Added %s ($%d) - Tree height: %d\n", item.name, item.price, height(root))
    }
}

package main

import (
    "container/heap"
    "fmt"
)

type Customer struct {
    Name     string
    Priority int
    Index    int
}

type PriorityQueue []*Customer

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].Priority > pq[j].Priority // Max heap
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].Index = i
    pq[j].Index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    customer := x.(*Customer)
    customer.Index = n
    *pq = append(*pq, customer)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    customer := old[n-1]
    customer.Index = -1
    *pq = old[0 : n-1]
    return customer
}

func main() {
    pq := make(PriorityQueue, 0)
    heap.Init(&pq)

    customers := []*Customer{
        {Name: "Alice (Regular)", Priority: 5},
        {Name: "Bob (VIP)", Priority: 10},
        {Name: "Carol (New)", Priority: 3},
        {Name: "Dave (Member)", Priority: 7},
    }

    // Add customers
    for _, customer := range customers {
        heap.Push(&pq, customer)
        fmt.Printf("➕ Added: %s (Priority: %d)\n", customer.Name, customer.Priority)
    }

    // Serve in priority order
    fmt.Println("\n🎯 Serving order:")
    for pq.Len() > 0 {
        customer := heap.Pop(&pq).(*Customer)
        fmt.Printf("  → %s (Priority: %d)\n", customer.Name, customer.Priority)
    }
}

package main

import "fmt"

type TrieNode struct {
    children map[rune]*TrieNode
    isEnd    bool
    word     string
}

type Trie struct {
    root *TrieNode
}

func NewTrie() *Trie {
    return &Trie{
        root: &TrieNode{
            children: make(map[rune]*TrieNode),
        },
    }
}

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{
                children: make(map[rune]*TrieNode),
            }
        }
        node = node.children[ch]
    }
    node.isEnd = true
    node.word = word
}

func (t *Trie) AutoComplete(prefix string) []string {
    node := t.root

    // Navigate to prefix
    for _, ch := range prefix {
        if node.children[ch] == nil {
            return []string{}
        }
        node = node.children[ch]
    }

    // Collect all words with this prefix
    results := []string{}
    t.collectWords(node, &results)
    return results
}

func (t *Trie) collectWords(node *TrieNode, results *[]string) {
    if node.isEnd {
        *results = append(*results, node.word)
    }

    for _, child := range node.children {
        t.collectWords(child, results)
    }
}

func main() {
    trie := NewTrie()

    drinks := []string{
        "latte",
        "latté",
        "latte macchiato",
        "espresso",
        "espresso macchiato",
        "cappuccino",
        "coffee",
    }

    for _, drink := range drinks {
        trie.Insert(drink)
    }

    // Autocomplete
    prefixes := []string{"lat", "esp", "cof"}
    for _, prefix := range prefixes {
        suggestions := trie.AutoComplete(prefix)
        fmt.Printf("🔍 '%s' → %v\n", prefix, suggestions)
    }
}

package main

import "fmt"

type SegmentTree struct {
    tree []int
    n    int
}

func NewSegmentTree(sales []int) *SegmentTree {
    n := len(sales)
    st := &SegmentTree{
        tree: make([]int, 4*n),
        n:    n,
    }
    st.build(sales, 0, 0, n-1)
    return st
}

func (st *SegmentTree) build(sales []int, node, start, end int) {
    if start == end {
        st.tree[node] = sales[start]
        return
    }

    mid := (start + end) / 2
    leftChild := 2*node + 1
    rightChild := 2*node + 2

    st.build(sales, leftChild, start, mid)
    st.build(sales, rightChild, mid+1, end)

    st.tree[node] = st.tree[leftChild] + st.tree[rightChild]
}

func (st *SegmentTree) Query(left, right int) int {
    return st.query(0, 0, st.n-1, left, right)
}

func (st *SegmentTree) query(node, start, end, left, right int) int {
    if right < start || end < left {
        return 0
    }

    if left <= start && end <= right {
        return st.tree[node]
    }

    mid := (start + end) / 2
    leftChild := 2*node + 1
    rightChild := 2*node + 2

    leftSum := st.query(leftChild, start, mid, left, right)
    rightSum := st.query(rightChild, mid+1, end, left, right)

    return leftSum + rightSum
}

func main() {
    // Hourly sales from 8am to 4pm
    hourlySales := []int{50, 80, 100, 50, 60, 40, 70, 50}
    hours := []string{"8am", "9am", "10am", "11am", "12pm", "1pm", "2pm", "3pm"}

    st := NewSegmentTree(hourlySales)

    // Query: Total sales between 9am (index 1) and 11am (index 3)
    total := st.Query(1, 3)
    fmt.Printf("💰 Sales from %s to %s: $%d\n", hours[1], hours[3], total)

    // Query: Morning sales (8am-12pm)
    morning := st.Query(0, 4)
    fmt.Printf("🌅 Morning sales (8am-12pm): $%d\n", morning)
}

package main

import "fmt"

type Graph struct {
    adjList map[string][]string
}

func NewGraph() *Graph {
    return &Graph{
        adjList: make(map[string][]string),
    }
}

func (g *Graph) AddEdge(from, to string) {
    g.adjList[from] = append(g.adjList[from], to)
}

func (g *Graph) GetDependencies(ingredient string) {
    visited := make(map[string]bool)
    fmt.Printf("📋 Dependencies for %s:\n", ingredient)
    g.dfs(ingredient, visited, 0)
}

func (g *Graph) dfs(node string, visited map[string]bool, level int) {
    if visited[node] {
        return
    }

    visited[node] = true
    indent := ""
    for i := 0; i < level; i++ {
        indent += "  "
    }
    fmt.Printf("%s→ %s\n", indent, node)

    for _, neighbor := range g.adjList[node] {
        g.dfs(neighbor, visited, level+1)
    }
}

func main() {
    g := NewGraph()

    // Build latte dependency graph
    g.AddEdge("Latte", "Espresso Shot")
    g.AddEdge("Latte", "Steamed Milk")
    g.AddEdge("Espresso Shot", "Ground Coffee")
    g.AddEdge("Ground Coffee", "Coffee Beans")
    g.AddEdge("Steamed Milk", "Milk")

    g.GetDependencies("Latte")
}

package main

import (
    "container/heap"
    "fmt"
    "math"
)

type Edge struct {
    to     string
    weight int
}

type Item struct {
    node     string
    distance int
    index    int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].distance < pq[j].distance
}
func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    item.index = -1
    *pq = old[0 : n-1]
    return item
}

type WeightedGraph struct {
    adjList map[string][]Edge
}

func NewWeightedGraph() *WeightedGraph {
    return &WeightedGraph{
        adjList: make(map[string][]Edge),
    }
}

func (g *WeightedGraph) AddEdge(from, to string, weight int) {
    g.adjList[from] = append(g.adjList[from], Edge{to: to, weight: weight})
    g.adjList[to] = append(g.adjList[to], Edge{to: from, weight: weight})
}

func (g *WeightedGraph) Dijkstra(start, end string) (int, []string) {
    distances := make(map[string]int)
    previous := make(map[string]string)

    for node := range g.adjList {
        distances[node] = math.MaxInt32
    }
    distances[start] = 0

    pq := make(PriorityQueue, 0)
    heap.Init(&pq)
    heap.Push(&pq, &Item{node: start, distance: 0})

    for pq.Len() > 0 {
        current := heap.Pop(&pq).(*Item)

        if current.node == end {
            break
        }

        if current.distance > distances[current.node] {
            continue
        }

        for _, edge := range g.adjList[current.node] {
            distance := distances[current.node] + edge.weight

            if distance < distances[edge.to] {
                distances[edge.to] = distance
                previous[edge.to] = current.node
                heap.Push(&pq, &Item{node: edge.to, distance: distance})
            }
        }
    }

    // Reconstruct path
    path := []string{}
    for at := end; at != ""; at = previous[at] {
        path = append([]string{at}, path...)
        if at == start {
            break
        }
    }

    return distances[end], path
}

func main() {
    g := NewWeightedGraph()

    g.AddEdge("Shop A", "Shop B", 2)
    g.AddEdge("Shop A", "Shop C", 4)
    g.AddEdge("Shop B", "Shop C", 1)
    g.AddEdge("Shop B", "Shop D", 7)
    g.AddEdge("Shop C", "Shop D", 3)

    distance, path := g.Dijkstra("Shop A", "Shop D")
    fmt.Printf("🚗 Shortest route: %v\n", path)
    fmt.Printf("📏 Total distance: %d km\n", distance)
}

package main

import "fmt"

type UnionFind struct {
    parent map[string]string
    rank   map[string]int
}

func NewUnionFind() *UnionFind {
    return &UnionFind{
        parent: make(map[string]string),
        rank:   make(map[string]int),
    }
}

func (uf *UnionFind) MakeSet(customer string) {
    if _, exists := uf.parent[customer]; !exists {
        uf.parent[customer] = customer
        uf.rank[customer] = 0
    }
}

func (uf *UnionFind) Find(customer string) string {
    if uf.parent[customer] != customer {
        uf.parent[customer] = uf.Find(uf.parent[customer]) // Path compression
    }
    return uf.parent[customer]
}

func (uf *UnionFind) Union(customer1, customer2 string) {
    root1 := uf.Find(customer1)
    root2 := uf.Find(customer2)

    if root1 == root2 {
        return
    }

    // Union by rank
    if uf.rank[root1] < uf.rank[root2] {
        uf.parent[root1] = root2
    } else if uf.rank[root1] > uf.rank[root2] {
        uf.parent[root2] = root1
    } else {
        uf.parent[root2] = root1
        uf.rank[root1]++
    }

    fmt.Printf("🔗 Joined %s and %s at same table\n", customer1, customer2)
}

func (uf *UnionFind) AreTogether(customer1, customer2 string) bool {
    return uf.Find(customer1) == uf.Find(customer2)
}

func main() {
    uf := NewUnionFind()

    customers := []string{"Alice", "Bob", "Carol", "Dave", "Eve", "Frank"}
    for _, customer := range customers {
        uf.MakeSet(customer)
    }

    // Group customers
    uf.Union("Alice", "Bob")
    uf.Union("Bob", "Carol")
    uf.Union("Dave", "Eve")

    // Check if customers are together
    fmt.Println("\n🔍 Checking groups:")
    fmt.Printf("Alice and Carol together? %v\n", uf.AreTogether("Alice", "Carol"))
    fmt.Printf("Alice and Dave together? %v\n", uf.AreTogether("Alice", "Dave"))
    fmt.Printf("Dave and Eve together? %v\n", uf.AreTogether("Dave", "Eve"))
}

package main

import "fmt"

type Task struct {
    name         string
    dependencies []string
}

func TopologicalSort(tasks []Task) []string {
    // Build adjacency list and in-degree map
    adjList := make(map[string][]string)
    inDegree := make(map[string]int)

    for _, task := range tasks {
        if _, exists := inDegree[task.name]; !exists {
            inDegree[task.name] = 0
        }

        for _, dep := range task.dependencies {
            adjList[dep] = append(adjList[dep], task.name)
            inDegree[task.name]++
        }
    }

    // Find tasks with no dependencies
    queue := []string{}
    for task, degree := range inDegree {
        if degree == 0 {
            queue = append(queue, task)
        }
    }

    result := []string{}

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        result = append(result, current)

        for _, neighbor := range adjList[current] {
            inDegree[neighbor]--
            if inDegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }

    return result
}

func main() {
    tasks := []Task{
        {name: "Grind Beans", dependencies: []string{}},
        {name: "Heat Milk", dependencies: []string{}},
        {name: "Pull Espresso", dependencies: []string{"Grind Beans"}},
        {name: "Froth Milk", dependencies: []string{"Heat Milk"}},
        {name: "Combine", dependencies: []string{"Pull Espresso", "Froth Milk"}},
        {name: "Add Foam", dependencies: []string{"Combine"}},
        {name: "Serve", dependencies: []string{"Add Foam"}},
    }

    order := TopologicalSort(tasks)
    fmt.Println("📋 Recipe steps in order:")
    for i, step := range order {
        fmt.Printf("  %d. %s\n", i+1, step)
    }
}

package main

import (
    "fmt"
    "hash/fnv"
)

type BloomFilter struct {
    bits []bool
    size int
    k    int // Number of hash functions
}

func NewBloomFilter(size, k int) *BloomFilter {
    return &BloomFilter{
        bits: make([]bool, size),
        size: size,
        k:    k,
    }
}

func (bf *BloomFilter) hash(s string, seed int) int {
    h := fnv.New32a()
    h.Write([]byte(fmt.Sprintf("%s%d", s, seed)))
    return int(h.Sum32()) % bf.size
}

func (bf *BloomFilter) Add(customer string) {
    for i := 0; i < bf.k; i++ {
        index := bf.hash(customer, i)
        bf.bits[index] = true
    }
    fmt.Printf("✅ Added %s to bloom filter\n", customer)
}

func (bf *BloomFilter) MightContain(customer string) bool {
    for i := 0; i < bf.k; i++ {
        index := bf.hash(customer, i)
        if !bf.bits[index] {
            return false
        }
    }
    return true
}

func main() {
    bf := NewBloomFilter(100, 3)

    // Regular customers
    regulars := []string{"Alice", "Bob", "Carol"}
    for _, customer := range regulars {
        bf.Add(customer)
    }

    // Check customers
    checks := []string{"Alice", "Dave", "Bob", "Eve"}
    fmt.Println("\n🔍 Checking customers:")
    for _, customer := range checks {
        if bf.MightContain(customer) {
            fmt.Printf("  %s: Probably a regular ✓\n", customer)
        } else {
            fmt.Printf("  %s: Definitely new ✗\n", customer)
        }
    }
}

package main

import (
    "container/list"
    "fmt"
)

type LRUCache struct {
    capacity int
    cache    map[string]*list.Element
    lru      *list.List
}

type cacheEntry struct {
    key   string
    value string
}

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        capacity: capacity,
        cache:    make(map[string]*list.Element),
        lru:      list.New(),
    }
}

func (c *LRUCache) Get(key string) (string, bool) {
    if elem, found := c.cache[key]; found {
        c.lru.MoveToFront(elem)
        return elem.Value.(*cacheEntry).value, true
    }
    return "", false
}

func (c *LRUCache) Put(key, value string) {
    if elem, found := c.cache[key]; found {
        c.lru.MoveToFront(elem)
        elem.Value.(*cacheEntry).value = value
        fmt.Printf("🔄 Updated cache: %s = %s\n", key, value)
        return
    }

    if c.lru.Len() >= c.capacity {
        oldest := c.lru.Back()
        if oldest != nil {
            c.lru.Remove(oldest)
            delete(c.cache, oldest.Value.(*cacheEntry).key)
            fmt.Printf("🗑️  Evicted: %s\n", oldest.Value.(*cacheEntry).key)
        }
    }

    entry := &cacheEntry{key: key, value: value}
    elem := c.lru.PushFront(entry)
    c.cache[key] = elem
    fmt.Printf("➕ Cached: %s = %s\n", key, value)
}

func main() {
    cache := NewLRUCache(3)

    cache.Put("drink1", "Latte")
    cache.Put("drink2", "Cappuccino")
    cache.Put("drink3", "Espresso")

    fmt.Println()

    // Access drink1 (moves to front)
    if drink, found := cache.Get("drink1"); found {
        fmt.Printf("🔍 Found: %s\n", drink)
    }

    fmt.Println()

    // Add new drink (should evict drink2)
    cache.Put("drink4", "Mocha")

    fmt.Println("\n📋 Checking what's in cache:")
    for _, key := range []string{"drink1", "drink2", "drink3", "drink4"} {
        if drink, found := cache.Get(key); found {
            fmt.Printf("  ✓ %s: %s\n", key, drink)
        } else {
            fmt.Printf("  ✗ %s: not in cache\n", key)
        }
    }
}

package main

import (
    "fmt"
    "math/rand"
)

const MaxLevel = 4
const Probability = 0.5

type SkipNode struct {
    value   int
    forward []*SkipNode
}

type SkipList struct {
    header *SkipNode
    level  int
}

func NewSkipList() *SkipList {
    return &SkipList{
        header: &SkipNode{forward: make([]*SkipNode, MaxLevel)},
        level:  0,
    }
}

func (sl *SkipList) randomLevel() int {
    level := 0
    for rand.Float64() < Probability && level < MaxLevel-1 {
        level++
    }
    return level
}

func (sl *SkipList) Insert(value int) {
    update := make([]*SkipNode, MaxLevel)
    current := sl.header

    for i := sl.level; i >= 0; i-- {
        for current.forward[i] != nil && current.forward[i].value < value {
            current = current.forward[i]
        }
        update[i] = current
    }

    level := sl.randomLevel()
    if level > sl.level {
        for i := sl.level + 1; i <= level; i++ {
            update[i] = sl.header
        }
        sl.level = level
    }

    newNode := &SkipNode{
        value:   value,
        forward: make([]*SkipNode, level+1),
    }

    for i := 0; i <= level; i++ {
        newNode.forward[i] = update[i].forward[i]
        update[i].forward[i] = newNode
    }

    fmt.Printf("➕ Inserted $%d at level %d\n", value, level)
}

func (sl *SkipList) Search(value int) bool {
    current := sl.header

    for i := sl.level; i >= 0; i-- {
        for current.forward[i] != nil && current.forward[i].value < value {
            current = current.forward[i]
        }
    }

    current = current.forward[0]
    return current != nil && current.value == value
}

func main() {
    sl := NewSkipList()

    prices := []int{3, 5, 7, 4, 6}
    for _, price := range prices {
        sl.Insert(price)
    }

    fmt.Println("\n🔍 Searching:")
    for _, price := range []int{5, 8} {
        if sl.Search(price) {
            fmt.Printf("  $%d: Found ✓\n", price)
        } else {
            fmt.Printf("  $%d: Not found ✗\n", price)
        }
    }
}

package main

import (
    "fmt"
    "hash/fnv"
    "math"
    "math/bits"
)

type HyperLogLog struct {
    registers []uint8
    m         int
}

func NewHyperLogLog(precision int) *HyperLogLog {
    m := 1 << precision
    return &HyperLogLog{
        registers: make([]uint8, m),
        m:         m,
    }
}

func (hll *HyperLogLog) hash(s string) uint64 {
    h := fnv.New64a()
    h.Write([]byte(s))
    return h.Sum64()
}

func (hll *HyperLogLog) Add(customer string) {
    hash := hll.hash(customer)
    index := hash & uint64(hll.m-1)

    // Count leading zeros in remaining bits
    w := hash >> uint(math.Log2(float64(hll.m)))
    leadingZeros := uint8(bits.LeadingZeros64(w)) + 1

    if leadingZeros > hll.registers[index] {
        hll.registers[index] = leadingZeros
    }
}

func (hll *HyperLogLog) Count() int {
    sum := 0.0
    for _, val := range hll.registers {
        sum += 1.0 / math.Pow(2, float64(val))
    }

    alpha := 0.7213 / (1 + 1.079/float64(hll.m))
    estimate := alpha * float64(hll.m*hll.m) / sum

    return int(estimate)
}

func main() {
    hll := NewHyperLogLog(10)

    // Simulate customer visits
    customers := []string{
        "Alice", "Bob", "Carol", "Alice", "Dave",
        "Bob", "Eve", "Frank", "Alice", "Grace",
    }

    for _, customer := range customers {
        hll.Add(customer)
    }

    actualUnique := 7 // Alice, Bob, Carol, Dave, Eve, Frank, Grace
    estimated := hll.Count()

    fmt.Printf("👥 Actual unique customers: %d\n", actualUnique)
    fmt.Printf("📊 HyperLogLog estimate: %d\n", estimated)
    fmt.Printf("📉 Error: %.1f%%\n", math.Abs(float64(estimated-actualUnique))/float64(actualUnique)*100)
}

package main

import "fmt"

type Order struct {
    drink       string
    milk        string
    size        string
    previousVer *Order
    version     int
}

type OrderHistory struct {
    versions []*Order
}

func NewOrderHistory(drink, milk, size string) *OrderHistory {
    initial := &Order{
        drink:   drink,
        milk:    milk,
        size:    size,
        version: 1,
    }
    return &OrderHistory{
        versions: []*Order{initial},
    }
}

func (oh *OrderHistory) Modify(field, newValue string) *Order {
    current := oh.versions[len(oh.versions)-1]
    newOrder := &Order{
        drink:       current.drink,
        milk:        current.milk,
        size:        current.size,
        previousVer: current,
        version:     current.version + 1,
    }

    switch field {
    case "milk":
        newOrder.milk = newValue
    case "size":
        newOrder.size = newValue
    }

    oh.versions = append(oh.versions, newOrder)
    fmt.Printf("🔄 Modified order (v%d → v%d): Changed %s to %s\n",
        current.version, newOrder.version, field, newValue)

    return newOrder
}

func (oh *OrderHistory) GetVersion(version int) *Order {
    if version > 0 && version <= len(oh.versions) {
        return oh.versions[version-1]
    }
    return nil
}

func (oh *OrderHistory) PrintHistory() {
    fmt.Println("\n📜 Order History:")
    for _, order := range oh.versions {
        fmt.Printf("  v%d: %s %s with %s\n",
            order.version, order.size, order.drink, order.milk)
    }
}

func main() {
    order := NewOrderHistory("Latte", "Whole Milk", "Grande")

    order.Modify("milk", "Oat Milk")
    order.Modify("size", "Venti")

    order.PrintHistory()

    // Access old version
    fmt.Println("\n🔙 Going back to version 1:")
    v1 := order.GetVersion(1)
    fmt.Printf("  %s %s with %s\n", v1.size, v1.drink, v1.milk)
}

package main

import (
    "fmt"
    "time"
)

type Order struct {
    id        int
    timestamp time.Time
}

type SlidingWindow struct {
    orders     []Order
    windowSize time.Duration
}

func NewSlidingWindow(windowSize time.Duration) *SlidingWindow {
    return &SlidingWindow{
        orders:     []Order{},
        windowSize: windowSize,
    }
}

func (sw *SlidingWindow) AddOrder(id int) {
    order := Order{
        id:        id,
        timestamp: time.Now(),
    }
    sw.orders = append(sw.orders, order)
    sw.cleanup()
    fmt.Printf("➕ Order #%d added (Window size: %d)\n", id, len(sw.orders))
}

func (sw *SlidingWindow) cleanup() {
    cutoff := time.Now().Add(-sw.windowSize)
    validStart := 0

    for i, order := range sw.orders {
        if order.timestamp.After(cutoff) {
            validStart = i
            break
        }
    }

    sw.orders = sw.orders[validStart:]
}

func (sw *SlidingWindow) Count() int {
    sw.cleanup()
    return len(sw.orders)
}

func (sw *SlidingWindow) GetOrders() []int {
    sw.cleanup()
    ids := make([]int, len(sw.orders))
    for i, order := range sw.orders {
        ids[i] = order.id
    }
    return ids
}

func main() {
    window := NewSlidingWindow(3 * time.Second)

    window.AddOrder(1)
    window.AddOrder(2)

    time.Sleep(2 * time.Second)
    window.AddOrder(3)

    fmt.Printf("\n📊 Orders in window: %v\n", window.GetOrders())

    time.Sleep(2 * time.Second)
    fmt.Printf("📊 Orders in window after 4s: %v\n", window.GetOrders())
}

package main

import (
    "fmt"
    "math"
)

type Point struct {
    x, y float64
    name string
}

type KDNode struct {
    point Point
    left  *KDNode
    right *KDNode
}

func buildKDTree(points []Point, depth int) *KDNode {
    if len(points) == 0 {
        return nil
    }

    axis := depth % 2

    // Sort points by current axis
    if axis == 0 {
        // Sort by x
        for i := 0; i < len(points)-1; i++ {
            for j := i + 1; j < len(points); j++ {
                if points[i].x > points[j].x {
                    points[i], points[j] = points[j], points[i]
                }
            }
        }
    } else {
        // Sort by y
        for i := 0; i < len(points)-1; i++ {
            for j := i + 1; j < len(points); j++ {
                if points[i].y > points[j].y {
                    points[i], points[j] = points[j], points[i]
                }
            }
        }
    }

    median := len(points) / 2

    return &KDNode{
        point: points[median],
        left:  buildKDTree(points[:median], depth+1),
        right: buildKDTree(points[median+1:], depth+1),
    }
}

func distance(p1, p2 Point) float64 {
    dx := p1.x - p2.x
    dy := p1.y - p2.y
    return math.Sqrt(dx*dx + dy*dy)
}

func findWithinRadius(node *KDNode, target Point, radius float64, depth int, results *[]Point) {
    if node == nil {
        return
    }

    dist := distance(node.point, target)
    if dist <= radius {
        *results = append(*results, node.point)
    }

    axis := depth % 2
    var axisValue, targetValue float64

    if axis == 0 {
        axisValue = node.point.x
        targetValue = target.x
    } else {
        axisValue = node.point.y
        targetValue = target.y
    }

    if targetValue-radius <= axisValue {
        findWithinRadius(node.left, target, radius, depth+1, results)
    }
    if targetValue+radius >= axisValue {
        findWithinRadius(node.right, target, radius, depth+1, results)
    }
}

func main() {
    shops := []Point{
        {x: 2, y: 3, name: "Shop A"},
        {x: 5, y: 4, name: "Shop B"},
        {x: 9, y: 6, name: "Shop C"},
        {x: 4, y: 7, name: "Shop D"},
        {x: 8, y: 1, name: "Shop E"},
    }

    tree := buildKDTree(shops, 0)

    myLocation := Point{x: 5, y: 5, name: "My Location"}
    radius := 3.0

    results := []Point{}
    findWithinRadius(tree, myLocation, radius, 0, &results)

    fmt.Printf("🗺️  Shops within %.1fkm of %s:\n", radius, myLocation.name)
    for _, shop := range results {
        dist := distance(myLocation, shop)
        fmt.Printf("  - %s (%.2fkm away)\n", shop.name, dist)
    }
}

package main

import "fmt"

type Shift struct {
    employee string
    start    int
    end      int
}

type IntervalNode struct {
    shift Shift
    max   int
    left  *IntervalNode
    right *IntervalNode
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func insert(node *IntervalNode, shift Shift) *IntervalNode {
    if node == nil {
        return &IntervalNode{
            shift: shift,
            max:   shift.end,
        }
    }

    if shift.start < node.shift.start {
        node.left = insert(node.left, shift)
    } else {
        node.right = insert(node.right, shift)
    }

    node.max = max(node.max, shift.end)
    if node.left != nil {
        node.max = max(node.max, node.left.max)
    }
    if node.right != nil {
        node.max = max(node.max, node.right.max)
    }

    return node
}

func findOverlapping(node *IntervalNode, time int, results *[]string) {
    if node == nil {
        return
    }

    if node.shift.start <= time && time <= node.shift.end {
        *results = append(*results, node.shift.employee)
    }

    if node.left != nil && node.left.max >= time {
        findOverlapping(node.left, time, results)
    }

    findOverlapping(node.right, time, results)
}

func main() {
    var root *IntervalNode

    shifts := []Shift{
        {employee: "Alice", start: 9, end: 13},   // 9am-1pm
        {employee: "Bob", start: 14, end: 18},    // 2pm-6pm
        {employee: "Carol", start: 9, end: 11},   // 9am-11am
        {employee: "Dave", start: 16, end: 20},   // 4pm-8pm
        {employee: "Eve", start: 12, end: 16},    // 12pm-4pm
    }

    for _, shift := range shifts {
        root = insert(root, shift)
        fmt.Printf("➕ Scheduled: %s (%d:00-%d:00)\n",
            shift.employee, shift.start, shift.end)
    }

    checkTimes := []int{10, 15, 19}
    for _, time := range checkTimes {
        results := []string{}
        findOverlapping(root, time, &results)

        fmt.Printf("\n🕐 At %d:00, working: %v\n", time, results)
    }
}