Mastering DSAs in Go - Data Structures [Part 2]

// Fixed-size array (size is part of the type)
fixed := [5]int{1, 2, 3, 4, 5}

// Dynamic slices with make
dynamicWithCapacity := make([]int, 0, 5) // Length 0, capacity 5
dynamicWithLength := make([]int, 5)      // Length 5, capacity 5

// ScoreTracker keeps track of a series of scores with unlimited capacity
type ScoreTracker struct {
    scores []int
}

// NewScoreTracker creates a new tracker with initial capacity
func NewScoreTracker(initialCapacity int) *ScoreTracker {
    return &ScoreTracker{
        scores: make([]int, 0, initialCapacity),
    }
}

// AddScore appends a new score to the collection - O(1) amortized
func (st *ScoreTracker) AddScore(score int) {
    st.scores = append(st.scores, score)
}

// AverageScore calculates the average of all scores - O(n)
func (st *ScoreTracker) AverageScore() float64 {
    if len(st.scores) == 0 {
        return 0
    }

    sum := 0
    for _, score := range st.scores {
        sum += score
    }

    return float64(sum) / float64(len(st.scores))
}

// Example usage:
func main() {
    tracker := NewScoreTracker(10) // Start with capacity for 10 scores

    // Add some scores (using O(1) amortized append operations)
    tracker.AddScore(85)
    tracker.AddScore(92)
    tracker.AddScore(78)
    tracker.AddScore(95)

    fmt.Printf("Average score: %.2f\n", tracker.AverageScore())
}

// O(1) amortized time complexity
func (st *ScoreTracker) AddScore(score int) {
    st.scores = append(st.scores, score)
}

// TopScores maintains a fixed-size sorted list of the highest scores
type TopScores struct {
    scores [5]int  // Fixed-size array of top 5 scores (highest first)
}

// Initialize with zeros
func NewTopScores() *TopScores {
    return &TopScores{}
}

// TryAddScore adds a score if it's high enough to make the top 5 - O(n)
func (ts *TopScores) TryAddScore(newScore int) bool {
    // Find position where this score belongs (if any)
    pos := -1
    for i, score := range ts.scores {
        if newScore > score {
            pos = i
            break
        }
    }

    // If not in top 5, we're done
    if pos == -1 {
        return false
    }

    // Shift lower scores down (this is an O(n) operation)
    for i := len(ts.scores) - 1; i > pos; i-- {
        ts.scores[i] = ts.scores[i-1]
    }

    // Insert the new score
    ts.scores[pos] = newScore
    return true
}

// Example usage:
func main() {
    topScores := NewTopScores()

    // Add some scores (each requires O(n) operations when shifting is needed)
    topScores.TryAddScore(85)
    topScores.TryAddScore(92)
    topScores.TryAddScore(78)
    topScores.TryAddScore(95)
    topScores.TryAddScore(88)

    // Try adding a score too low to make the cut
    wasAdded := topScores.TryAddScore(70)
    if !wasAdded {
        fmt.Println("Score 70 didn't make the top 5")
    }

    fmt.Println("Top scores:", topScores.scores)
}

type Node struct {
    Value int
    Next  *Node
}

type LinkedList struct {
    Head   *Node
    Length int
}

// Create a new linked list
func NewLinkedList() *LinkedList {
    return &LinkedList{
        Head:   nil,
        Length: 0,
    }
}

// Insert at beginning - O(1) time complexity
func (l *LinkedList) InsertAtBeginning(val int) {
    newNode := &Node{
        Value: val,
        Next:  l.Head,
    }
    l.Head = newNode
    l.Length++
}

// Insert at end - O(n) time complexity without tail pointer
func (l *LinkedList) InsertAtEnd(val int) {
    newNode := &Node{
        Value: val,
        Next:  nil,
    }

    // If list is empty, new node becomes the head
    if l.Head == nil {
        l.Head = newNode
    } else {
        // Traverse to the last node
        current := l.Head
        for current.Next != nil {
            current = current.Next
        }
        // Link the last node to the new node
        current.Next = newNode
    }
    l.Length++
}

// Search for a value - O(n) time complexity
func (l *LinkedList) Search(val int) bool {
    current := l.Head
    for current != nil {
        if current.Value == val {
            return true
        }
        current = current.Next
    }
    return false
}

// Delete a node with given value - O(n) time complexity
func (l *LinkedList) Delete(val int) bool {
    // If list is empty
    if l.Head == nil {
        return false
    }

    // If head is the target
    if l.Head.Value == val {
        l.Head = l.Head.Next
        l.Length--
        return true
    }

    // Search for the value in the rest of the list
    current := l.Head
    for current.Next != nil && current.Next.Value != val {
        current = current.Next
    }

    // If value was found
    if current.Next != nil {
        current.Next = current.Next.Next
        l.Length--
        return true
    }

    return false
}

// Example usage
func main() {
    list := NewLinkedList()

    // Add some values
    list.InsertAtBeginning(10)  // List: 10
    list.InsertAtBeginning(20)  // List: 20 -> 10
    list.InsertAtEnd(30)        // List: 20 -> 10 -> 30

    // Search for values
    fmt.Println("Contains 20:", list.Search(20))  // true
    fmt.Println("Contains 25:", list.Search(25))  // false

    // Delete a value
    list.Delete(10)             // List: 20 -> 30

    // Print the list
    current := list.Head
    for current != nil {
        fmt.Printf("%d -> ", current.Value)
        current = current.Next
    }
    fmt.Println("nil")
}

// Insert at beginning - O(1) time complexity
func (l *LinkedList) InsertAtBeginning(val int) {
    newNode := &Node{
        Value: val,
        Next:  l.Head,  // Point to current head
    }
    l.Head = newNode   // Update head to the new node
    l.Length++
}

// Transaction represents a single financial transaction
type Transaction struct {
    ID          string
    Amount      float64
    Description string
    Timestamp   time.Time
    Next        *Transaction  // Pointer to the next transaction
}

// TransactionHistory manages a linked list of transactions
type TransactionHistory struct {
    Head        *Transaction
    Size        int
}

// AddTransaction adds a new transaction to the beginning (most recent first) - O(1)
func (th *TransactionHistory) AddTransaction(amount float64, desc string) string {
    // Generate a transaction ID
    id := generateID()

    // Create a new transaction
    newTransaction := &Transaction{
        ID:          id,
        Amount:      amount,
        Description: desc,
        Timestamp:   time.Now(),
        Next:        th.Head,  // Point to current head (same pattern as our generic linked list)
    }

    // Update the head
    th.Head = newTransaction
    th.Size++

    return id
}

// Helper function (in a real implementation, this would be more sophisticated)
func generateID() string {
    return fmt.Sprintf("TX-%d", time.Now().UnixNano())
}

// Creating an empty map
ages := make(map[string]int)

// (Alternatively) Creating with initial values
ages := map[string]int{
	"Argo": 32,
	"Bumpkin": 28,
	"Cassandra": 45,
}

// Creating a map to store user ages
func NewUserAgeSystem() map[string]int {
    return make(map[string]int)
}

// Add or update a user's age
func AddUser(users map[string]int, name string, age int) {
    users[name] = age
}

// Get a user's age with error handling
func GetUserAge(users map[string]int, name string) (int, bool) {
    age, exists := users[name]
    return age, exists
}

// Example usage:
func main() {
    userAges := NewUserAgeSystem()

    // Add some users
    AddUser(userAges, "Argo", 32)
    AddUser(userAges, "Bumpkin", 28)
    AddUser(userAges, "Cassandra", 45)

    // Retrieve and display Argo's age
    if age, exists := GetUserAge(userAges, "Argo"); exists {
        fmt.Printf("Argo is %d years old\n", age)
    } else {
        fmt.Println("Argo not found in the system")
    }

    // Try to get a non-existent user
    if age, exists := GetUserAge(userAges, "Mahindra"); exists {
        fmt.Printf("Mahindra is %d years old\n", age)
    } else {
        fmt.Println("Mahindra not found in the system")
    }

    // Update Bumpkin's age
    AddUser(userAges, "Bumpkin", 29) // Bumpkin aged because of a birthday

    // Remove Cassandra from the system
    delete(userAges, "Cassandra")
}

// Insert or update - O(1) average case
userAges["Argo"] = 32

// Access with existence check - O(1) average case
age, exists := userAges["Bumpkin"]

// Delete - O(1) average case
delete(userAges, "Cassandra")

type TreeNode struct {
    Value int
    Left  *TreeNode
    Right *TreeNode
}

type BinarySearchTree struct {
    Root *TreeNode
}

// Create a new BST
func NewBinarySearchTree() *BinarySearchTree {
    return &BinarySearchTree{Root: nil}
}

// Insert a value into the BST
func (bst *BinarySearchTree) Insert(value int) {
    newNode := &TreeNode{Value: value}

    // If tree is empty, new node becomes root
    if bst.Root == nil {
        bst.Root = newNode
        return
    }

    // Otherwise, find the correct position
    insertNode(bst.Root, newNode)
}

// Helper function for insertion
func insertNode(node, newNode *TreeNode) {
    // Go left if new value is smaller
    if newNode.Value < node.Value {
        if node.Left == nil {
            node.Left = newNode
        } else {
            insertNode(node.Left, newNode)
        }
    } else {
        // Go right if new value is greater or equal
        if node.Right == nil {
            node.Right = newNode
        } else {
            insertNode(node.Right, newNode)
        }
    }
}

// Search for a value in the BST
func (bst *BinarySearchTree) Search(value int) *TreeNode {
    return searchNode(bst.Root, value)
}

// Helper function for searching (recursive approach)
func searchNode(node *TreeNode, value int) *TreeNode {
    // Base cases: not found or found
    if node == nil || node.Value == value {
        return node
    }

    // Recursive case: search in left or right subtree
    if value < node.Value {
        return searchNode(node.Left, value)
    }
    return searchNode(node.Right, value)
}

// Search iteratively (alternative implementation)
func (bst *BinarySearchTree) SearchIterative(value int) *TreeNode {
    current := bst.Root

    // Traverse down the tree
    for current != nil {
        // Value found
        if current.Value == value {
            return current
        }

        // Navigate left or right
        if value < current.Value {
            current = current.Left
        } else {
            current = current.Right
        }
    }

    // Value not found
    return nil
}

// In-order traversal (left, root, right)
func (bst *BinarySearchTree) InOrderTraversal() []int {
    result := []int{}
    inOrder(bst.Root, &result)
    return result
}

func inOrder(node *TreeNode, result *[]int) {
    if node != nil {
        inOrder(node.Left, result)
        *result = append(*result, node.Value)
        inOrder(node.Right, result)
    }
}

// Example usage
func main() {
    bst := NewBinarySearchTree()

    // Insert values
    values := []int{8, 3, 10, 1, 6, 9, 14}
    for _, v := range values {
        bst.Insert(v)
    }

    // Search for a value
    if node := bst.Search(6); node != nil {
        fmt.Println("Found value:", node.Value)
    } else {
        fmt.Println("Value not found")
    }

    // Print all values in order
    fmt.Println("In-order traversal:", bst.InOrderTraversal())
}

// Search iteratively
func (bst *BinarySearchTree) SearchIterative(value int) *TreeNode {
    current := bst.Root

    // Traverse down the tree
    for current != nil {
        // Value found
        if current.Value == value {
            return current
        }

        // Navigate left or right based on value comparison
        if value < current.Value {
            current = current.Left
        } else {
            current = current.Right
        }
    }

    // Value not found
    return nil
}

// A specialized tree for counting word occurrences
type WordCount struct {
    Word  string
    Count int
}

type WordCountTree struct {
    Value WordCount
    Left  *WordCountTree
    Right *WordCountTree
}

// Insert or increment word count
func (t *WordCountTree) Insert(word string) *WordCountTree {
    // If tree is empty, create a new node
    if t == nil {
        return &WordCountTree{
            Value: WordCount{Word: word, Count: 1},
        }
    }

    // Compare words lexicographically
    if word < t.Value.Word {
        // Insert into left subtree
        t.Left = t.Left.Insert(word)
    } else if word > t.Value.Word {
        // Insert into right subtree
        t.Right = t.Right.Insert(word)
    } else {
        // Word already exists, increment count
        t.Value.Count++
    }

    return t
}

// Process text and build a word frequency tree
func BuildWordFrequencyTree(text string) *WordCountTree {
    var root *WordCountTree

    // Split text into words and clean them
    words := strings.Fields(text)
    for _, word := range words {
        // Clean the word (remove punctuation, lowercase)
        word = strings.ToLower(strings.Trim(word, ",.!?:;\"'()"))
        if word != "" {
            root = root.Insert(word)
        }
    }

    return root
}

// Print the words in alphabetical order with their counts
func (t *WordCountTree) PrintSorted() {
    if t == nil {
        return
    }

    // In-order traversal: left, root, right
    t.Left.PrintSorted()
    fmt.Printf("%s: %d\n", t.Value.Word, t.Value.Count)
    t.Right.PrintSorted()
}

// Stack is a LIFO (Last In, First Out) data structure
type Stack struct {
    items []int
}

// NewStack creates a new stack
func NewStack() *Stack {
    return &Stack{
        items: make([]int, 0),
    }
}

// Push adds an item to the top of the stack
func (s *Stack) Push(item int) {
    s.items = append(s.items, item)
}

// Pop removes and returns the top item from the stack
func (s *Stack) Pop() (int, error) {
    if len(s.items) == 0 {
        return 0, errors.New("stack is empty")
    }

    lastIdx := len(s.items) - 1
    item := s.items[lastIdx]
    s.items = s.items[:lastIdx]
    return item, nil
}

// Peek returns the top item without removing it
func (s *Stack) Peek() (int, error) {
    if len(s.items) == 0 {
        return 0, errors.New("stack is empty")
    }

    return s.items[len(s.items)-1], nil
}

// IsEmpty returns true if the stack has no items
func (s *Stack) IsEmpty() bool {
    return len(s.items) == 0
}

// Size returns the number of items in the stack
func (s *Stack) Size() int {
    return len(s.items)
}

// Queue is a FIFO (First In, First Out) data structure
type Queue struct {
    items []int
}

// NewQueue creates a new queue
func NewQueue() *Queue {
    return &Queue{
        items: make([]int, 0),
    }
}

// Enqueue adds an item to the back of the queue
func (q *Queue) Enqueue(item int) {
    q.items = append(q.items, item)
}

// Dequeue removes and returns the front item from the queue
func (q *Queue) Dequeue() (int, error) {
    if len(q.items) == 0 {
        return 0, errors.New("queue is empty")
    }

    item := q.items[0]
    q.items = q.items[1:]
    return item, nil
}

// Front returns the front item without removing it
func (q *Queue) Front() (int, error) {
    if len(q.items) == 0 {
        return 0, errors.New("queue is empty")
    }

    return q.items[0], nil
}

// IsEmpty returns true if the queue has no items
func (q *Queue) IsEmpty() bool {
    return len(q.items) == 0
}

// Size returns the number of items in the queue
func (q *Queue) Size() int {
    return len(q.items)
}

// EvaluatePostfix evaluates a postfix expression like "3 4 + 5 *"
func EvaluatePostfix(expression string) (int, error) {
    stack := NewStack()
    tokens := strings.Fields(expression)

    for _, token := range tokens {
        switch token {
        case "+", "-", "*", "/":
            // Need at least two operands
            if stack.Size() < 2 {
                return 0, errors.New("invalid expression: not enough operands")
            }

            // Pop the two operands (remember: LIFO order)
            b, _ := stack.Pop()
            a, _ := stack.Pop()

            // Perform the operation and push result
            var result int
            switch token {
            case "+":
                result = a + b
            case "-":
                result = a - b
            case "*":
                result = a * b
            case "/":
                if b == 0 {
                    return 0, errors.New("division by zero")
                }
                result = a / b
            }

            stack.Push(result)

        default:
            // Must be a number, convert and push
            num, err := strconv.Atoi(token)
            if err != nil {
                return 0, fmt.Errorf("invalid token: %s", token)
            }
            stack.Push(num)
        }
    }

    // The result should be the only item on the stack
    if stack.Size() != 1 {
        return 0, errors.New("invalid expression: too many operands")
    }

    return stack.Pop()
}

// Example usage:
// result, _ := EvaluatePostfix("3 4 + 5 *") // (3 + 4) * 5 = 35

// Task represents a simple task with an ID and a function to execute
type Task struct {
    ID      string
    Execute func() error
}

// TaskQueue manages a queue of tasks to be executed in FIFO order
type TaskQueue struct {
    tasks []Task
}

// NewTaskQueue creates a new task queue
func NewTaskQueue() *TaskQueue {
    return &TaskQueue{
        tasks: make([]Task, 0),
    }
}

// AddTask adds a new task to the queue
func (tq *TaskQueue) AddTask(id string, execute func() error) {
    tq.tasks = append(tq.tasks, Task{
        ID:      id,
        Execute: execute,
    })
}

// ProcessAllTasks processes all tasks in the queue in FIFO order
func (tq *TaskQueue) ProcessAllTasks() []error {
    var errors []error

    for len(tq.tasks) > 0 {
        // Get the next task (from the front of the queue)
        task := tq.tasks[0]
        tq.tasks = tq.tasks[1:] // Dequeue operation

        // Execute the task
        if err := task.Execute(); err != nil {
            errors = append(errors, fmt.Errorf("task %s failed: %v", task.ID, err))
        }
    }

    return errors
}

// Example usage:
func main() {
    taskQueue := NewTaskQueue()

    // Add some tasks
    taskQueue.AddTask("task1", func() error {
        fmt.Println("Executing task 1")
        return nil
    })

    taskQueue.AddTask("task2", func() error {
        fmt.Println("Executing task 2")
        return errors.New("task 2 failed")
    })

    taskQueue.AddTask("task3", func() error {
        fmt.Println("Executing task 3")
        return nil
    })

    // Process all tasks
    errors := taskQueue.ProcessAllTasks()

    // Report any errors
    for _, err := range errors {
        fmt.Println("Error:", err)
    }
}

// CircularQueue implements a queue using a circular buffer
type CircularQueue struct {
    items []int
    head  int
    tail  int
    size  int
    cap   int
}

// NewCircularQueue creates a new circular queue with the given capacity
func NewCircularQueue(capacity int) *CircularQueue {
    return &CircularQueue{
        items: make([]int, capacity),
        head:  0,
        tail:  0,
        size:  0,
        cap:   capacity,
    }
}

// Enqueue adds an item to the queue - O(1)
func (q *CircularQueue) Enqueue(item int) error {
    if q.size == q.cap {
        return errors.New("queue is full")
    }

    q.items[q.tail] = item
    q.tail = (q.tail + 1) % q.cap
    q.size++
    return nil
}

// Dequeue removes and returns the front item - O(1)
func (q *CircularQueue) Dequeue() (int, error) {
    if q.size == 0 {
        return 0, errors.New("queue is empty")
    }

    item := q.items[q.head]
    q.head = (q.head + 1) % q.cap
    q.size--
    return item, nil
}