Quick reference implementations of Go data structures and algos for interviews

dsa.go

// Queue
// using a slice
package main

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

type Queue struct {
	items []int
}

// operations: Enqueue, Dequeue, Peek, IsEmpty, IsFull, Front, Rear

func (q *Queue) Enqueue(item int) {
	q.items = append(q.items, item)
}

func (q *Queue) Dequeue() int {
	item := q.items[0]
	q.items = q.items[1:]
	return item
}

func (q *Queue) Peek() int {
	return q.items[0]
}

func (q *Queue) IsEmpty() bool {
	return len(q.items) == 0
}

func (q *Queue) IsFull() bool {
	return len(q.items) == cap(q.items)
}

func (q *Queue) Front() int {
	return q.items[0]
}

func (q *Queue) Rear() int {
	return q.items[len(q.items)-1]
}

// Stack
// using a slice

type Stack struct {
	items []int
}

// operations: Push, Pop, Peek, IsEmpty, IsFull, Top, Bottom

func (s *Stack) Push(item int) {
	s.items = append(s.items, item)
}

func (s *Stack) Pop() int {
	item := s.items[len(s.items)-1]
	s.items = s.items[:len(s.items)-1]
	return item
}

func (s *Stack) Peek() int {
	return s.items[len(s.items)-1]
}

func (s *Stack) IsEmpty() bool {
	return len(s.items) == 0
}

func (s *Stack) IsFull() bool {
	return len(s.items) == cap(s.items)
}

func (s *Stack) Top() int {
	return s.items[len(s.items)-1]
}

func (s *Stack) Bottom() int {
	return s.items[0]
}

// Linked List

type ListNode struct {
	Val  int
	Next *ListNode
}

// operations: Insert, Delete, Search, Traverse

func (l *ListNode) New(value int) *ListNode {
	return &ListNode{Val: value, Next: nil}
}

func (l *ListNode) Insert(value int) {
	newNode := &ListNode{Val: value, Next: l.Next}
	l.Next = newNode
}

func (l *ListNode) Delete(value int) {
	if l == nil {
		return
	}
	l.Next = l.Next.Next
}

func (l *ListNode) Search(value int) *ListNode {
	for l != nil {
		if l.Val == value {
			return l
		}
		l = l.Next
	}
	return nil
}

func (l *ListNode) Traverse() {
	for l != nil {
		fmt.Println(l.Val)
		l = l.Next
	}
}

// Circular Queue (Fixed Size)

type CircularQueue struct {
	items []int
	size  int
	front int
	rear  int
}

// operations: Enqueue, Dequeue, Peek, IsEmpty, IsFull, Front, Rear

func (c *CircularQueue) New(size int) *CircularQueue {
	return &CircularQueue{items: make([]int, size), size: size, front: 0, rear: -1}
}

func (c *CircularQueue) Enqueue(item int) {
	if c.IsFull() {
		return
	}
	c.rear = (c.rear + 1) % c.size
	c.items[c.rear] = item
}

func (c *CircularQueue) Dequeue() int {
	if c.IsEmpty() {
		return -1
	}
	item := c.items[c.front]
	c.front = (c.front + 1) % c.size
	return item
}

func (c *CircularQueue) Peek() int {
	return c.items[c.front]
}

func (c *CircularQueue) IsEmpty() bool {
	return c.front == c.rear+1 || (c.front == 0 && c.rear == c.size-1)
}

func (c *CircularQueue) IsFull() bool {
	return c.front == (c.rear+2)%c.size
}

// Graph representation for BFS/DFS/Dijkstra's
type Graph struct {
	adj map[int][]Edge
}

type Edge struct {
	to     int
	weight int
}

// BFS - Breadth First Search
// Time Complexity: O(V + E) where V is vertices and E is edges
// Space Complexity: O(V)
func BFS(graph Graph, start int) []int {
	visited := make(map[int]bool)
	queue := []int{start}
	result := []int{}

	for len(queue) > 0 {
		vertex := queue[0]
		queue = queue[1:]

		if !visited[vertex] {
			visited[vertex] = true
			result = append(result, vertex)

			for _, edge := range graph.adj[vertex] {
				if !visited[edge.to] {
					queue = append(queue, edge.to)
				}
			}
		}
	}
	return result
}

// DFS - Depth First Search
// Time Complexity: O(V + E)
// Space Complexity: O(V)
func DFS(graph Graph, start int) []int {
	visited := make(map[int]bool)
	result := []int{}

	var dfsUtil func(vertex int)
	dfsUtil = func(vertex int) {
		visited[vertex] = true
		result = append(result, vertex)

		for _, edge := range graph.adj[vertex] {
			if !visited[edge.to] {
				dfsUtil(edge.to)
			}
		}
	}

	dfsUtil(start)
	return result
}

// Dijkstra's Algorithm
// Time Complexity: O((V + E) * log V) with binary heap
// Space Complexity: O(V)
func Dijkstra(graph Graph, start int) map[int]int {
	distances := make(map[int]int)
	for vertex := range graph.adj {
		distances[vertex] = math.MaxInt32
	}
	distances[start] = 0

	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, &Item{vertex: start, priority: 0})

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

		if current.priority > distances[vertex] {
			continue
		}

		for _, edge := range graph.adj[vertex] {
			distance := distances[vertex] + edge.weight
			if distance < distances[edge.to] {
				distances[edge.to] = distance
				heap.Push(pq, &Item{vertex: edge.to, priority: distance})
			}
		}
	}
	return distances
}

// Priority Queue implementation for Dijkstra's
type Item struct {
	vertex   int
	priority 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].priority < pq[j].priority }
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]
	old[n-1] = nil
	item.index = -1
	*pq = old[0 : n-1]
	return item
}

// QuickSort
// Time Complexity: Average O(n log n), Worst O(n²)
// Space Complexity: O(log n)
func QuickSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	pivot := arr[len(arr)-1]
	left := []int{}
	right := []int{}

	for i := 0; i < len(arr)-1; i++ {
		if arr[i] < pivot {
			left = append(left, arr[i])
		} else {
			right = append(right, arr[i])
		}
	}

	left = QuickSort(left)
	right = QuickSort(right)

	return append(append(left, pivot), right...)
}

// BinarySearch
// Time Complexity: O(log n)
// Space Complexity: O(1)
func BinarySearch(arr []int, target int) int {
	left, right := 0, len(arr)-1

	for left <= right {
		mid := left + (right-left)/2
		if arr[mid] == target {
			return mid
		} else if arr[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}

// MergeSort
// Time Complexity: O(n log n)
// Space Complexity: O(n)
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 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
}

// TODO: Two Pointers

// TODO: Sliding Window