Mastering Data Structures with 50 Coding Challenges: Trees, Graphs, Stacks, and Queues - Part 2

In computer science, understanding and effectively utilizing data structures is crucial for designing efficient algorithms and solving complex problems. Among the fundamental data structures are trees, graphs, stacks, and queues. Each of these structures serves unique purposes and has distinct characteristics that make them suitable for different types of applications and scenarios.

This guide delves into these essential data structures, providing clear definitions, characteristics, and practical examples in Go (Golang). By exploring trees, graphs, stacks, and queues, you'll gain a comprehensive understanding of their functionalities and how to implement them. Additionally, we've included 50 coding challenges designed to test and enhance your knowledge of these data structures. These challenges will enable you to improve your problem-solving skills and tackle a wide range of computational problems with confidence.

26. Graph BFS

Explanation: Implement Breadth-First Search (BFS) for a graph.

Source Code:

package main

import (
	"fmt"
)

type Graph struct {
	vertices int
	edges    map[int][]int
}

func NewGraph(vertices int) *Graph {
	return &Graph{
		vertices: vertices,
		edges:    make(map[int][]int),
	}
}

func (g *Graph) AddEdge(v, w int) {
	g.edges[v] = append(g.edges[v], w)
}

func (g *Graph) BFS(start int) []int {
	visited := make([]bool, g.vertices)
	queue := []int{start}
	visited[start] = true
	result := []int{}

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

		for _, neighbor := range g.edges[vertex] {
			if !visited[neighbor] {
				queue = append(queue, neighbor)
				visited[neighbor] = true
			}
		}
	}
	return result
}

func main() {
	g := NewGraph(6)
	g.AddEdge(0, 1)
	g.AddEdge(0, 2)
	g.AddEdge(1, 3)
	g.AddEdge(1, 4)
	g.AddEdge(2, 5)

	fmt.Println(g.BFS(0)) // Output: [0 1 2 3 4 5]
}

27. Graph DFS

Explanation: Implement Depth-First Search (DFS) for a graph.

Source Code:

package main

import (
	"fmt"
)

type Graph struct {
	vertices int
	edges    map[int][]int
}

func NewGraph(vertices int) *Graph {
	return &Graph{
		vertices: vertices,
		edges:    make(map[int][]int),
	}
}

func (g *Graph) AddEdge(v, w int) {
	g.edges[v] = append(g.edges[v], w)
}

func (g *Graph) DFS(start int) []int {
	visited := make([]bool, g.vertices)
	result := []int{}
	var dfs func(v int)
	dfs = func(v int) {
		visited[v] = true
		result = append(result, v)
		for _, neighbor := range g.edges[v] {
			if !visited[neighbor] {
				dfs(neighbor)
			}
		}
	}
	dfs(start)
	return result
}

func main() {
	g := NewGraph(6)
	g.AddEdge(0, 1)
	g.AddEdge(0, 2)
	g.AddEdge(1, 3)
	g.AddEdge(1, 4)
	g.AddEdge(2, 5)

	fmt.Println(g.DFS(0)) // Output: [0 1 3 4 2 5]
}

28. Detect Cycle in Graph

Explanation: Write a function to detect if a graph contains a cycle.

Source Code:

package main

import (
	"fmt"
)

type Graph struct {
	vertices int
	edges    map[int][]int
}

func NewGraph(vertices int) *Graph {
	return &Graph{
		vertices: vertices,
		edges:    make(map[int][]int),
	}
}

func (g *Graph) AddEdge(v, w int) {
	g.edges[v] = append(g.edges[v], w)
}

func (g *Graph) isCyclicUtil(v int, visited []bool, recStack []bool) bool {
	if visited[v] == false {
		visited[v] = true
		recStack[v] = true

		for _, neighbor := range g.edges[v] {
			if !visited[neighbor] && g.isCyclicUtil(neighbor, visited, recStack) {
				return true
			} else if recStack[neighbor] {
				return true
			}
		}
	}
	recStack[v] = false
	return false
}

func (g *Graph) isCyclic() bool {
	visited := make([]bool, g.vertices)
	recStack := make([]bool, g.vertices)

	for i := 0; i < g.vertices; i++ {
		if g.isCyclicUtil(i, visited, recStack) {
			return true
		}
	}
	return false
}

func main() {
	g := NewGraph(4)
	g.AddEdge(0, 1)
	g.AddEdge(1, 2)
	g.AddEdge(2, 0)
	g.AddEdge(2, 3)

	fmt.Println(g.isCyclic()) // Output: true
}

Heaps and Priority Queues

29. Implement Min-Heap

Explanation: Implement a min-heap data structure.

Source Code:

package main

import (
	"fmt"
)

type MinHeap struct {
	array []int
}

func (h *MinHeap) insert(key int) {
	h.array = append(h.array, key)
	h.heapifyUp(len(h.array) - 1)
}

func (h *MinHeap) extractMin() int {
	if len(h.array) == 0 {
		return -1 // or some indication that the heap is empty
	}
	root := h.array[0]
	lastIndex := len(h.array) - 1
	h.array[0] = h.array[lastIndex]
	h.array = h.array[:lastIndex]
	h.heapifyDown(0)
	return root
}

func (h *MinHeap) heapifyUp(index int) {
	for h.array[parent(index)] > h.array[index] {
		h.swap(parent(index), index)
		index = parent(index)
	}
}

func (h *MinHeap) heapifyDown(index int) {
	lastIndex := len(h.array) - 1
	l, r := left(index), right(index)
	childToCompare := 0

	for l <= lastIndex {
		if l == lastIndex {
			childToCompare = l
		} else if h.array[l] < h.array[r] {
			childToCompare = l
		} else {
			childToCompare = r
		}

		if h.array[index] > h.array[childToCompare] {
			h.swap(index, childToCompare)
			index = childToCompare
			l, r = left(index), right(index)
		} else {
			return
		}
	}
}

func parent(i int) int {
	return (i - 1) / 2
}

func left(i int) int {
	return 2*i + 1
}

func right(i int) int {
	return 2*i + 2
}

func (h *MinHeap) swap(i1, i2 int) {
	h.array[i1], h.array[i2] = h.array[i2], h.array[i1]
}

func main() {
	h := &MinHeap{}
	h.insert(3)
	h.insert(1)
	h.insert(6)
	h.insert(5)
	h.insert(2)
	h.insert(4)

	fmt.Println(h.extractMin()) // Output: 1
	fmt.Println(h.extractMin()) // Output: 2
	fmt.Println(h.extractMin()) // Output: 3
}

30. Kth Largest Element

Explanation: Write a function to find the Kth largest element in an array using a min-heap.

Source Code:

package main

import (
	"container/heap"
	"fmt"
)

type MinHeap []int

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

func findKthLargest(nums []int, k int) int {
	h := &MinHeap{}
	heap.Init(h)
	for _, num := range nums {
		heap.Push(h, num)
		if h.Len() > k {
			heap.Pop(h)
		}
	}
	return heap.Pop(h).(int)
}

func main() {
	nums := []int{3, 2, 1, 5, 6, 4}
	k := 2
	fmt.Println(findKthLargest(nums, k)) // Output: 5
}

31. Merge K Sorted Lists

Explanation: Write a function to merge K sorted linked lists using a priority queue.

Source Code:

package main

import (
	"container/heap"
	"fmt"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

type MinHeap []*ListNode

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i].Val < h[j].Val }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(*ListNode)) }
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func mergeKLists(lists []*ListNode) *ListNode {
	h := &MinHeap{}
	heap.Init(h)
	for _, list := range lists {
		if list != nil {
			heap.Push(h, list)
		}
	}

	dummy := &ListNode{}
	current := dummy
	for h.Len() > 0 {
		minNode := heap.Pop(h).(*ListNode)
		current.Next = minNode
		current = current.Next
		if minNode.Next != nil {
			heap.Push(h, minNode.Next)
		}
	}
	return dummy.Next
}

func printList(head *ListNode) {
	for head != nil {
		fmt.Printf("%d ", head.Val)
		head = head.Next
	}
	fmt.Println()
}

func main() {
	list1 := &ListNode{Val: 1, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5}}}
	list2 := &ListNode{Val: 1, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4}}}
	list3 := &ListNode{Val: 2, Next: &ListNode{Val: 6}}
	lists := []*ListNode{list1, list2, list3}
	mergedList := mergeKLists(lists)
	printList(mergedList) // Output: 1 1 2 3 4 4 5 6
}

32. Top K Frequent Elements

Explanation: Write a function to find the top K frequent elements in an array using a heap.

Source Code:

package main

import (
	"container/heap"
	"fmt"
)

type Element struct {
	val   int
	count int
}

type MaxHeap []Element

func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i].count > h[j].count }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(Element)) }
func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func topKFrequent(nums []int, k int) []int {
	frequency := make(map[int]int)
	for _, num := range nums {
		frequency[num]++
	}

	h := &MaxHeap{}
	heap.Init(h)
	for val, count := range frequency {
		heap.Push(h, Element{val, count})
	}

	result := []int{}
	for i := 0; i < k; i++ {
		result = append(result, heap.Pop(h).(Element).val)
	}
	return result
}

func main() {
	nums := []int{1, 1, 1, 2, 2, 3}
	k := 2
	fmt.Println(topKFrequent(nums, k)) // Output: [1 2]
}

33. Median Finder

Explanation: Implement a data structure that supports the insertion of numbers and returns the median of the current numbers.

Source Code:

package main

import (
	"container/heap"
	"fmt"
)

type MaxHeap []int
type MinHeap []int

func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

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

type MedianFinder struct {
	maxHeap *MaxHeap
	minHeap *MinHeap
}

func Constructor() MedianFinder {
	maxHeap := &MaxHeap{}
	minHeap := &MinHeap{}
	heap.Init(maxHeap)
	heap.Init(minHeap)
	return MedianFinder{maxHeap, minHeap}
}

func (mf *MedianFinder) AddNum(num int) {
	heap.Push(mf.maxHeap, num)
	heap.Push(mf.minHeap, heap.Pop(mf.maxHeap))

	if mf.maxHeap.Len() < mf.minHeap.Len() {
		heap.Push(mf.maxHeap, heap.Pop(mf.minHeap))
	}
}

func (mf *MedianFinder) FindMedian() float64 {
	if mf.maxHeap.Len() > mf.minHeap.Len() {
		return float64((*mf.maxHeap)[0])
	}
	return float64((*mf.maxHeap)[0]+(*mf.minHeap)[0]) / 2.0
}

func main() {
	mf := Constructor()
	mf.AddNum(1)
	mf.AddNum(2)
	fmt.Println(mf.FindMedian()) // Output: 1.5
	mf.AddNum(3)
	fmt.Println(mf.FindMedian()) // Output: 2
}

Hash Tables

34. Two Sum

Explanation: Write a function to find two numbers in an array that add up to a target value using a hash map.

Source Code:

package main

import (
	"fmt"
)

func twoSum(nums []int, target int) []int {
	m := make(map[int]int)
	for i, num := range nums {
		if idx, ok := m[target-num]; ok {
			return []int{idx, i}
		}
		m[num] = i
	}
	return nil
}

func main() {
	nums := []int{2, 7, 11, 15}
	target := 9
	fmt.Println(twoSum(nums, target)) // Output: [0 1]
}

35. Group Anagrams

Explanation: Write a function to group anagrams from a list of strings.

Source Code:

package main

import (
	"fmt"
	"sort"
	"strings"
)

func groupAnagrams(strs []string) [][]string {
	m := make(map[string][]string)
	for _, str := range strs {
		sortedStr := sortString(str)
		m[sortedStr] = append(m[sortedStr], str)
	}

	result := [][]string{}
	for _, v := range m {
		result = append(result, v)
	}
	return result
}

func sortString(s string) string {
	sortedStr := strings.Split(s, "")
	sort.Strings(sortedStr)
	return strings.Join(sortedStr, "")
}

func main() {
	strs := []string{"eat", "tea", "tan", "ate", "nat", "bat"}
	fmt.Println(groupAnagrams(strs)) // Output: [[eat tea ate] [tan nat] [bat]]
}

36. Longest Substring Without Repeating Characters

Explanation: Write a function to find the length of the longest substring without repeating characters.

Source Code:

package main

import (
	"fmt"
)

func lengthOfLongestSubstring(s string) int {
	m := make(map[byte]int)
	maxLen, start := 0, 0

	for i := 0; i < len(s); i++ {
		if idx, ok := m[s[i]]; ok && idx >= start {
			start = idx + 1
		}
		m[s[i]] = i
		if i-start+1 > maxLen {
			maxLen = i - start + 1
		}
	}
	return maxLen
}

func main() {
	s := "abcabcbb"
	fmt.Println(lengthOfLongestSubstring(s)) // Output: 3
}

37. Subarray Sum Equals K

Explanation: Write a function to find the number of subarrays that sum to a given value using a hash map.

Source Code:

package main

import (
	"fmt"
)

func subarraySum(nums []int, k int) int {
	count, sum := 0, 0
	m := make(map[int]int)
	m[0] = 1

	for _, num := range nums {
		sum += num
		if _, ok := m[sum-k]; ok {
			count += m[sum-k]
		}
		m[sum]++
	}
	return count
}

func main() {
	nums := []int{1, 1, 1}
	k := 2
	fmt.Println(subarraySum(nums, k)) // Output: 2
}

38. Find All Duplicates

Explanation: Write a function to find all duplicate elements in an array using a hash map.

Source Code:

package main

import (
	"fmt"
)

func findDuplicates(nums []int) []int {
	m := make(map[int]int)
	duplicates := []int{}
	for _, num := range nums {
		m[num]++
		if m[num] == 2 {
			duplicates = append(duplicates, num)
		}
	}
	return duplicates
}

func main() {
	nums := []int{4, 3, 2, 7, 8, 2, 3, 1}
	fmt.Println(findDuplicates(nums)) // Output: [2 3]
}

Strings

39. Longest Palindromic Substring

Explanation: Write a function to find the longest palindromic substring in a given string.

Source Code:

package main

import (
	"fmt"
)

func longestPalindrome(s string) string {
	if len(s) < 2 {
		return s
	}

	start, maxLen := 0, 1
	for i := 0; i < len(s); i++ {
		expandAroundCenter(s, i, i, &start, &maxLen)
		expandAroundCenter(s, i, i+1, &start, &maxLen)
	}
	return s[start : start+maxLen]
}

func expandAroundCenter(s string, left, right int, start, maxLen *int) {
	for left >= 0 && right < len(s) && s[left] == s[right] {
		left--
		right++
	}
	if right-left-1 > *maxLen {
		*start = left + 1
		*maxLen = right - left - 1
	}
}

func main() {
	s := "babad"
	fmt.Println(longestPalindrome(s)) // Output: "bab" or "aba"
}

40. String Compression

Explanation: Write a function to perform basic string compression using the counts of repeated characters.

Source Code:

package main

import (
	"fmt"
	"strconv"
)

func compressString(s string) string {
	if len(s) == 0 {
		return ""
	}

	compressed := ""
	count := 1
	for i := 1; i < len(s); i++ {
		if s[i] == s[i-1] {
			count++
		} else {
			compressed += string(s[i-1]) + strconv.Itoa(count)
			count = 1
		}
	}
	compressed += string(s[len(s)-1]) + strconv.Itoa(count)

	if len(compressed) >= len(s) {
		return s
	}
	return compressed
}

func main() {
	s := "aabcccccaaa"
	fmt.Println(compressString(s)) // Output: "a2b1c5a3"
}

41. Isomorphic Strings

Explanation: Write a function to determine if two strings are isomorphic.

Source Code:

package main

import (
	"fmt"
)

func isIsomorphic(s string, t string) bool {
	if len(s) != len(t) {
		return false
	}

	mappingS := make(map[byte]byte)
	mappingT := make(map[byte]byte)

	for i := 0; i < len(s); i++ {
		charS, charT := s[i], t[i]
		if mappingS[charS] > 0 && mappingS[charS] != charT {
			return false
		}
		if mappingT[charT] > 0 && mappingT[charT] != charS {
			return false
		}
		mappingS[charS] = charT
		mappingT[charT] = charS
	}

	return true
}

func main() {
	s := "egg"
	t := "add"
	fmt.Println(isIsomorphic(s, t)) // Output: true
}

42. Word Ladder

Explanation: Write a function to find the shortest transformation sequence from one word to another.

Source Code:

package main

import (
	"fmt"
)

func ladderLength(beginWord string, endWord string, wordList []string) int {
	wordSet := make(map[string]bool)
	for _, word := range wordList {
		wordSet[word] = true
	}
	if !wordSet[endWord] {
		return 0
	}

	queue := []string{beginWord}
	steps := 1

	for len(queue) > 0 {
		for i := len(queue); i > 0; i-- {
			word := queue[0]
			queue = queue[1:]
			if word == endWord {
				return steps
			}
			for j := 0; j < len(word); j++ {
				for k := 'a'; k <= 'z'; k++ {
					newWord := word[:j] + string(k) + word[j+1:]
					if wordSet[newWord] {
						queue = append(queue, newWord)
						delete(wordSet, newWord)
					}
				}
			}
		}
		steps++
	}
	return 0
}

func main() {
	beginWord := "hit"
	endWord := "cog"
	wordList := []string{"hot", "dot", "dog", "lot", "log", "cog"}
	fmt.Println(ladderLength(beginWord, endWord, wordList)) // Output: 5
}

43. Valid Anagram

Explanation: Write a function to determine if two strings are anagrams of each other.

Source Code:

package main

import (
	"fmt"
)

func isAnagram(s string, t string) bool {
	if len(s) != len(t) {
		return false
	}

	count := make(map[rune]int)
	for _, char := range s {
		count[char]++
	}
	for _, char := range t {
		count[char]--
		if count[char] < 0 {
			return false
		}
	}
	return true
}

func main() {
	s := "anagram"
	t := "nagaram"
	fmt.Println(isAnagram(s, t)) // Output: true
}

Miscellaneous

44. LRU Cache

Explanation: Implement an LRU (Least Recently Used) cache.

Source Code:

package main

import (
	"container/list"
	"fmt"
)

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

type Pair struct {
	key, value int
}

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

func (c *LRUCache) Get(key int) int {
	if node, ok := c.cache[key]; ok {
		c.list.MoveToFront(node)
		return node.Value.(Pair).value
	}
	return -1
}

func (c *LRUCache) Put(key, value int) {
	if node, ok := c.cache[key]; ok {
		c.list.MoveToFront(node)
		node.Value = Pair{key, value}
	} else {
		if c.list.Len() == c.capacity {
			node := c.list.Back()
			c.list.Remove(node)
			delete(c.cache, node.Value.(Pair).key)
		}
		node := c.list.PushFront(Pair{key, value})
		c.cache[key] = node
	}
}

func main() {
	cache := Constructor(2)
	cache.Put(1, 1)
	cache.Put(2, 2)
	fmt.Println(cache.Get(1)) // Output: 1
	cache.Put(3, 3)
	fmt.Println(cache.Get(2)) // Output: -1
	cache.Put(4, 4)
	fmt.Println(cache.Get(1)) // Output: -1
	fmt.Println(cache.Get(3)) // Output: 3
	fmt.Println(cache.Get(4)) // Output: 4
}

45. Design a Hit Counter

Explanation: Design a hit counter that counts the number of hits received in the past 5 minutes.

Source Code:

package main

import (
	"fmt"
	"time"
)

type HitCounter struct {
	timestamps []int
}

func Constructor() HitCounter {
	return HitCounter{}
}

func (c *HitCounter) Hit(timestamp int) {
	c.timestamps = append(c.timestamps, timestamp)
}

func (c *HitCounter) GetHits(timestamp int) int {
	startTime := timestamp - 300
	for len(c.timestamps) > 0 && c.timestamps[0] <= startTime {
		c.timestamps = c.timestamps[1:]
	}
	return len(c.timestamps)
}

func main() {
	counter := Constructor()
	now := int(time.Now().Unix())
	counter.Hit(now)
	counter.Hit(now + 1)
	counter.Hit(now + 300)
	counter.Hit(now + 301)
	fmt.Println(counter.GetHits(now + 301)) // Output: 3
}

46. Implement Trie (Prefix Tree)

Explanation: Implement a trie for storing and searching a set of strings.

Source Code:

package main

import (
	"fmt"
)

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

type Trie struct {
	root *TrieNode
}

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

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

func (t *Trie) Search(word string) bool {
	node := t.root
	for _, char := range word {
		if _, ok := node.children[char]; !ok {
			return false
		}
		node = node.children[char]
	}
	return node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
	node := t.root
	for _, char := range prefix {
		if _, ok := node.children[char]; !ok {
			return false
		}
		node = node.children[char]
	}
	return true
}

func main() {
	trie := Constructor()
	trie.Insert("apple")
	fmt.Println(trie.Search("apple"))   // Output: true
	fmt.Println(trie.Search("app"))     // Output: false
	fmt.Println(trie.StartsWith("app")) // Output: true
	trie.Insert("app")
	fmt.Println(trie.Search("app")) // Output: true
}

47. Design Tic-Tac-Toe

Explanation: Design a Tic-Tac-Toe game that is played between two players on a 3x3 grid.

Source Code:

package main

import (
	"fmt"
)

type TicTacToe struct {
	board [][]int
}

func Constructor(n int) TicTacToe {
	board := make([][]int, n)
	for i := range board {
		board[i] = make([]int, n)
	}
	return TicTacToe{board: board}
}

func (this *TicTacToe) Move(row int, col int, player int) int {
	this.board[row][col] = player
	if this.checkWin(row, col, player) {
		return player
	}
	return 0
}

func (this *TicTacToe) checkWin(row int, col int, player int) bool {
	n := len(this.board)
	rowWin, colWin, diagWin, antiDiagWin := true, true, true, true

	for i := 0; i < n; i++ {
		if this.board[row][i] != player {
			rowWin = false
		}
		if this.board[i][col] != player {
			colWin = false
		}
		if this.board[i][i] != player {
			diagWin = false
		}
		if this.board[i][n-i-1] != player {
			antiDiagWin = false
		}
	}

	return rowWin || colWin || diagWin || antiDiagWin
}

func main() {
	game := Constructor(3)
	fmt.Println(game.Move(0, 0, 1)) // Output: 0
	fmt.Println(game.Move(0, 2, 2)) // Output: 0
	fmt.Println(game.Move(2, 2, 1)) // Output: 0
	fmt.Println(game.Move(1, 1, 2)) // Output: 0
	fmt.Println(game.Move(2, 0, 1)) // Output: 0
	fmt.Println(game.Move(1, 0, 2)) // Output: 0
	fmt.Println(game.Move(2, 1, 1)) // Output: 1 (player 1 wins)
}

48. Implement Skiplist

Explanation: Implement a skiplist for efficient searching.

Source Code:

package main

import (
	"fmt"
	"math/rand"
)

const MaxLevel = 16

type SkiplistNode struct {
	val  int
	next []*SkiplistNode
}

type Skiplist struct {
	head  *SkiplistNode
	level int
}

func Constructor() Skiplist {
	return Skiplist{head: &SkiplistNode{next: make([]*SkiplistNode, MaxLevel)}, level: 1}
}

func (s *Skiplist) Search(target int) bool {
	curr := s.head
	for i := s.level - 1; i >= 0; i-- {
		for curr.next[i] != nil && curr.next[i].val < target {
			curr = curr.next[i]
		}
	}
	curr = curr.next[0]
	return curr != nil && curr.val == target
}

func (s *Skiplist) Add(num int) {
	update := make([]*SkiplistNode, MaxLevel)
	curr := s.head
	for i := s.level - 1; i >= 0; i-- {
		for curr.next[i] != nil && curr.next[i].val < num {
			curr = curr.next[i]
		}
		update[i] = curr
	}
	level := randomLevel()
	if level > s.level {
		for i := s.level; i < level; i++ {
			update[i] = s.head
		}
		s.level = level
	}
	newNode := &SkiplistNode{val: num, next: make([]*SkiplistNode, level)}
	for i := 0; i < level; i++ {
		newNode.next[i] = update[i].next[i]
		update[i].next[i] = newNode
	}
}

func (s *Skiplist) Erase(num int) bool {
	update := make([]*SkiplistNode, MaxLevel)
	curr := s.head
	for i := s.level - 1; i >= 0; i-- {
		for curr.next[i] != nil && curr.next[i].val < num {
			curr = curr.next[i]
		}
		update[i] = curr
	}
	curr = curr.next[0]
	if curr == nil || curr.val != num {
		return false
	}
	for i := 0; i < s.level; i++ {
		if update[i].next[i] != curr {
			break
		}
		update[i].next[i] = curr.next[i]
	}
	for s.level > 1 && s.head.next[s.level-1] == nil {
		s.level--
	}
	return true
}

func randomLevel() int {
	level := 1
	for rand.Float32() < 0.5 && level < MaxLevel {
		level++
	}
	return level
}

func main() {
	skiplist := Constructor()
	skiplist.Add(1)
	skiplist.Add(2)
	skiplist.Add(3)
	fmt.Println(skiplist.Search(0)) // Output: false
	skiplist.Add(4)
	fmt.Println(skiplist.Search(1)) // Output: true
	fmt.Println(skiplist.Erase(0))  // Output: false
	fmt.Println(skiplist.Erase(1))  // Output: true
	fmt.Println(skiplist.Search(1)) // Output: false
}

49. LFU Cache

Explanation: Implement an LFU (Least Frequently Used) cache.

Source Code:

package main

import (
	"container/heap"
	"fmt"
)

type LFUCache struct {
	capacity int
	lookup   map[int]*Node
	freqHeap *FrequencyHeap
}

type Node struct {
	key      int
	value    int
	frequency int
	index    int
}

type FrequencyHeap []*Node

func (h FrequencyHeap) Len() int           { return len(h) }
func (h FrequencyHeap) Less(i, j int) bool { return h[i].frequency < h[j].frequency }
func (h FrequencyHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
	h[i].index, h[j].index = i, j
}

func (h *FrequencyHeap) Push(x interface{}) {
	n := len(*h)
	node := x.(*Node)
	node.index = n
	*h = append(*h, node)
}

func (h *FrequencyHeap) Pop() interface{} {
	old := *h
	n := len(old)
	node := old[n-1]
	node.index = -1
	*h = old[0 : n-1]
	return node
}

func (h *FrequencyHeap) update(node *Node) {
	heap.Fix(h, node.index)
}

func Constructor(capacity int) LFUCache {
	h := &FrequencyHeap{}
	heap.Init(h)
	return LFUCache{
		capacity: capacity,
		lookup:   make(map[int]*Node),
		freqHeap: h,
	}
}

func (c *LFUCache) Get(key int) int {
	if node, ok := c.lookup[key]; ok {
		node.frequency++
		c.freqHeap.update(node)
		return node.value
	}
	return -1
}

func (c *LFUCache) Put(key, value int) {
	if c.capacity == 0 {
		return
	}

	if node, ok := c.lookup[key]; ok {
		node.value = value
		node.frequency++
		c.freqHeap.update(node)
		return
	}

	if len(c.lookup) == c.capacity {
		node := heap.Pop(c.freqHeap).(*Node)
		delete(c.lookup, node.key)
	}

	node := &Node{key: key, value: value, frequency: 1}
	c.lookup[key] = node
	heap.Push(c.freqHeap, node)
}

func main() {
	cache := Constructor(2)
	cache.Put(1, 1)
	cache.Put(2, 2)
	fmt.Println(cache.Get(1)) // Output: 1
	cache.Put(3, 3)
	fmt.Println(cache.Get(2)) // Output: -1
	fmt.Println(cache.Get(3)) // Output: 3
	cache.Put(4, 4)
	fmt.Println(cache.Get(1)) // Output: -1
	fmt.Println(cache.Get(3)) // Output: 3
	fmt.Println(cache.Get(4)) // Output: 4
}

50. Maximal Square

Explanation: Write a function to find the largest square containing only 1's in a binary matrix.

Source Code:

package main

import (
	"fmt"
)

func maximalSquare(matrix [][]byte) int {
	if len(matrix) == 0 {
		return 0
	}

	rows, cols := len(matrix), len(matrix[0])
	maxSide := 0
	dp := make([][]int, rows)
	for i := range dp {
		dp[i] = make([]int, cols)
	}

	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			if matrix[i][j] == '1' {
				if i == 0 || j == 0 {
					dp[i][j] = 1
				} else {
					dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
				}
				if dp[i][j] > maxSide {
					maxSide = dp[i][j]
				}
			}
		}
	}

	return maxSide * maxSide
}

func min(a, b, c int) int {
	if a < b && a < c {
		return a
	} else if b < c {
		return b
	}
	return c
}

func main() {
	matrix := [][]byte{
		{'1', '0', '1', '0', '0'},
		{'1', '0', '1', '1', '1'},
		{'1', '1', '1', '1', '1'},
		{'1', '0', '0', '1', '0'},
	}
	fmt.Println(maximalSquare(matrix)) // Output: 4
}

These exercises provide a comprehensive set of challenges to help practice and improve your skills in data structures and algorithms using Go.