Go面试题精讲:数据结构与算法10道经典题

摘要: 本篇精讲Go数据结构与算法面试10道经典题，涵盖slice扩容机制、map哈希冲突处理、ring buffer实现、LRU缓存实现、跳表实现、堆排序实现、二叉树遍历、图BFS/DFS、动态规划、字符串匹配，每道题配代码示例和复杂度分析，分享面试中slice扩容预估错误导致OOM的踩坑经验，对比Go与Java算法面试侧重点。

开篇故事

去年面试一个三年经验的Go后端，让他手写LRU缓存。他用了map + list.List的组合，逻辑写对了但忘了淘汰时要从map里删key，双向链表和map的删除操作没保持同步。追问slice扩容规则，他说"翻倍"，实际Go 1.18后扩容规则变了，小切片翻倍但大切片按1.25倍增长，还有256的阈值分界。

算法面试不是背模板就行的，理解底层数据结构的内存布局和扩容策略才是关键。这篇把高频出现的10道题写清楚，每道题都是最小可运行版本。

一、slice扩容机制

考点: Go 1.18后扩容规则分两段，小切片翻倍，大切片1.25倍。

package main

import "fmt"

func main() {
	var s []int
	// append触发扩容, 追踪cap变化
	// 阶段一: cap<256时直接翻倍
	// 阶段二: cap>=256时按1.25倍增长(Go 1.18+)
	for i := 0; i < 1000; i++ {
		s = append(s, i)
		// 当len超过cap时触发growslice
		// growslice先算新cap, 再mallocgc分配新数组
	}
	fmt.Printf("len=%d cap=%d\n", len(s), cap(s))
	// 输出: len=1000 cap=1280(1.25倍增长的结果)

	// 手动预分配可避免多次扩容拷贝
	// make(T, len, cap) 指定初始容量
	pre := make([]int, 0, 1000) // 一次分配到位
	for i := 0; i < 1000; i++ {
		pre = append(pre, i) // 不触发扩容
	}
	fmt.Printf("pre: len=%d cap=%d\n", len(pre), cap(pre))
}

考点解析: 扩容核心是计算新cap再分配新数组，旧数据memmove到新数组。小切片(<256)翻倍减少扩容次数，大切片1.25倍控制内存浪费。每次扩容都有拷贝开销，已知长度时预分配。

二、map哈希冲突处理

考点: Go map用链地址法，每个bucket存8个KV，溢出bucket用链表串联。

package main

import "fmt"

// map底层是runtime.hmap结构(简化)
// type hmap struct {
//     count    int        // 元素数量
//     buckets  []bmap     // bucket数组, 长度是2的幂
//     oldbuckets []bmap   // 扩容时旧bucket
//     ...
// }
// type bmap struct {
//     tophash [8]uint8  // 8个KV的哈希高字节
//     // 后面紧跟着8个key, 8个value, 1个overflow指针
// }

func main() {
	m := make(map[string]int)
	// 哈希计算: hash := alg.Hash(key)
	// 定位bucket: bucket := hash & (bucketCount-1)
	// 冲突处理: 同一bucket内线性探测8个槽位
	// 8个槽满后分配overflow bucket, 链表串联
	m["go"] = 1
	m["rust"] = 2

	// map扩容: 装载因子超过6.5(count/buckets)触发
	// 或overflow bucket过多触发等量扩容
	for i := 0; i < 100; i++ {
		m[fmt.Sprintf("key%d", i)] = i
	}
	fmt.Println(len(m)) // 102
}

考点解析: 每个bucket固定8个槽位，用tophash快速比较。哈希冲突时先在bucket内线性探测，满了挂overflow bucket。扩容时新建双倍bucket数组，渐进式搬迁数据。

三、ring buffer实现

考点: 固定大小环形缓冲区，用取模实现首尾循环。

package main

import "fmt"

// RingBuffer 固定容量环形缓冲区
type RingBuffer struct {
	data  []int  // 底层数组
	size  int    // 容量
	head  int    // 读位置
	tail  int    // 写位置
	count int    // 当前元素数
}

func NewRingBuffer(n int) *RingBuffer {
	return &RingBuffer{
		data: make([]int, n),
		size: n,
	}
}

// Push 写入元素, 满了覆盖最旧的
func (r *RingBuffer) Push(v int) {
	// tail取模实现环形写入
	r.data[r.tail] = v
	r.tail = (r.tail + 1) % r.size
	if r.count == r.size {
		// 缓冲区满, head跟着前进(覆盖旧数据)
		r.head = (r.head + 1) % r.size
	} else {
		r.count++
	}
}

// Pop 读取并移除最旧元素
func (r *RingBuffer) Pop() (int, bool) {
	if r.count == 0 {
		return 0, false // 空缓冲区
	}
	v := r.data[r.head]
	r.head = (r.head + 1) % r.size
	r.count--
	return v, true
}

func main() {
	rb := NewRingBuffer(3)
	rb.Push(1)
	rb.Push(2)
	rb.Push(3)
	rb.Push(4) // 覆盖1
	fmt.Println(rb.Pop()) // 2
}

考点解析: 环形缓冲区用head/tail两个指针加取模运算实现。固定容量避免扩容，适合生产者消费者场景。Go标准库没有ring buffer，需手写或用第三方库。

四、LRU缓存实现

考点: map提供O(1)查找，双向链表维护访问顺序。

package main

import (
	"container/list"
	"fmt"
)

// LRU Least Recently Used缓存
type LRU struct {
	capacity int                   // 最大容量
	cache    map[int]*list.Element // key到链表节点的映射
	ll       *list.List            // 双向链表, 头部最近使用
}

// entry 缓存条目, 存key和value
type entry struct {
	key   int
	value int
}

func NewLRU(cap int) *LRU {
	return &LRU{
		capacity: cap,
		cache:    make(map[int]*list.Element),
		ll:       list.New(),
	}
}

// Get 查找, 命中则移到链表头部
func (l *LRU) Get(key int) (int, bool) {
	if elem, ok := l.cache[key]; ok {
		// 移到链表头部表示最近使用
		l.ll.MoveToFront(elem)
		return elem.Value.(*entry).value, true
	}
	return 0, false
}

// Put 写入, 超容量淘汰链表尾部(最久未使用)
func (l *LRU) Put(key, value int) {
	if elem, ok := l.cache[key]; ok {
		// 已存在, 更新值并移到头部
		l.ll.MoveToFront(elem)
		elem.Value.(*entry).value = value
		return
	}
	// 新增, 放到链表头部
	elem := l.ll.PushFront(&entry{key: key, value: value})
	l.cache[key] = elem
	// 超容量, 淘汰尾部(最久未使用)
	if l.ll.Len() > l.capacity {
		// 取尾部元素
		oldest := l.ll.Back()
		if oldest != nil {
			// 从链表移除
			l.ll.Remove(oldest)
			// 从map删除, 这步容易漏!
			delete(l.cache, oldest.Value.(*entry).key)
		}
	}
}

func main() {
	lru := NewLRU(2)
	lru.Put(1, 10)
	lru.Put(2, 20)
	lru.Get(1)       // 1变最近使用
	lru.Put(3, 30)   // 淘汰2(key=2)
	v, ok := lru.Get(2)
	fmt.Println(v, ok) // 0 false
}

考点解析: LRU核心是map加双向链表双指针。Get时MoveToFront更新访问顺序，Put超容量时Back()取尾部淘汰。最容易漏的步骤是淘汰时同步从map删除key，导致map和链表不一致。

五、跳表实现

考点: 多层链表实现O(logN)查找，概率性平衡。

package main

import (
	"fmt"
	"math/rand"
)

const maxLevel = 16 // 最大层数

// Node 跳表节点
type Node struct {
	key   int     // 键
	value int     // 值
	next  []*Node // 每层的后继指针
}

// SkipList 跳表
type SkipList struct {
	head *Node // 头节点(哨兵)
}

func NewSkipList() *SkipList {
	return &SkipList{
		head: &Node{next: make([]*Node, maxLevel)},
	}
}

// randomLevel 随机生成层数, p=0.5
func randomLevel() int {
	level := 1
	// 每次50%概率增加一层
	for rand.Float64() < 0.5 && level < maxLevel {
		level++
	}
	return level
}

// Insert 插入元素
func (s *SkipList) Insert(key, value int) {
	// update[i]记录每层插入位置的前驱节点
	update := make([]*Node, maxLevel)
	curr := s.head
	// 从最高层往右找, 找到每层最后一个小于key的节点
	for i := maxLevel - 1; i >= 0; i-- {
		for curr.next[i] != nil && curr.next[i].key < key {
			curr = curr.next[i]
		}
		update[i] = curr // 记录前驱
	}
	// 生成随机层数
	level := randomLevel()
	node := &Node{
		key:   key,
		value: value,
		next:  make([]*Node, level),
	}
	// 在每层插入新节点, 更新前驱的next
	for i := 0; i < level; i++ {
		node.next[i] = update[i].next[i]
		update[i].next[i] = node
	}
}

// Search 查找, O(logN)
func (s *SkipList) Search(key int) (int, bool) {
	curr := s.head
	// 从最高层开始找, 缩小范围后下钻
	for i := maxLevel - 1; i >= 0; i-- {
		for curr.next[i] != nil && curr.next[i].key < key {
			curr = curr.next[i]
		}
	}
	// 最底层检查是否命中
	curr = curr.next[0]
	if curr != nil && curr.key == key {
		return curr.value, true
	}
	return 0, false
}

func main() {
	sl := NewSkipList()
	sl.Insert(1, 10)
	sl.Insert(5, 50)
	sl.Insert(3, 30)
	v, ok := sl.Search(3)
	fmt.Println(v, ok) // 30 true
}

考点解析: 跳表用多层索引实现二分查找的效果，插入时随机层数保持概率平衡。比红黑树实现简单，Redis的zset底层用跳表。每层节点数约为下层的1/2。

六、堆排序实现

考点: 利用最大堆性质，每次把堆顶放到末尾。

package main

import "fmt"

// heapify 调整以i为根的子树为最大堆
func heapify(arr []int, n, i int) {
	largest := i        // 假设当前节点最大
	left := 2*i + 1    // 左子节点索引
	right := 2*i + 2   // 右子节点索引

	// 左子比根大, 更新largest
	if left < n && arr[left] > arr[largest] {
		largest = left
	}
	// 右子比当前最大大, 更新largest
	if right < n && arr[right] > arr[largest] {
		largest = right
	}
	// 根不是最大, 交换并递归调整
	if largest != i {
		arr[i], arr[largest] = arr[largest], arr[i]
		heapify(arr, n, largest)
	}
}

// HeapSort 堆排序
func HeapSort(arr []int) {
	n := len(arr)
	// 建堆: 从最后一个非叶子节点开始自底向上
	for i := n/2 - 1; i >= 0; i-- {
		heapify(arr, n, i)
	}
	// 排序: 每次把堆顶(最大)换到末尾
	for i := n - 1; i > 0; i-- {
		arr[0], arr[i] = arr[i], arr[0] // 堆顶移到末尾
		heapify(arr, i, 0)              // 对剩余部分调堆
	}
}

func main() {
	arr := []int{4, 10, 3, 5, 1}
	HeapSort(arr)
	fmt.Println(arr) // [1 3 4 5 10]
}

考点解析: 堆排序时间O(NlogN)，空间O(1)。建堆O(N)，每次调堆O(logN)执行N次。Go标准库container/heap是泛型最小堆实现，优先队列可以直接用。

七、二叉树遍历

考点: 前中后序递归与迭代写法，层序遍历用队列。

package main

import (
	"container/list"
	"fmt"
)

// TreeNode 二叉树节点
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// PreOrder 前序遍历(根左右), 递归
func PreOrder(root *TreeNode) {
	if root == nil {
		return
	}
	fmt.Print(root.Val, " ") // 先访问根
	PreOrder(root.Left)     // 再左子树
	PreOrder(root.Right)    // 再右子树
}

// InOrder 中序遍历(左根右), 递归
// BST中序遍历结果是升序序列
func InOrder(root *TreeNode) {
	if root == nil {
		return
	}
	InOrder(root.Left)      // 先左子树
	fmt.Print(root.Val, " ") // 再根
	InOrder(root.Right)     // 再右子树
}

// LevelOrder 层序遍历, 用队列
func LevelOrder(root *TreeNode) {
	if root == nil {
		return
	}
	queue := list.New()
	queue.PushBack(root) // 根入队
	for queue.Len() > 0 {
		// 出队一个节点
		node := queue.Remove(queue.Front()).(*TreeNode)
		fmt.Print(node.Val, " ")
		// 左右子入队
		if node.Left != nil {
			queue.PushBack(node.Left)
		}
		if node.Right != nil {
			queue.PushBack(node.Right)
		}
	}
}

func main() {
	//       1
	//      / \
	//     2   3
	//    / \
	//   4   5
	root := &TreeNode{1,
		&TreeNode{2, &TreeNode{4, nil, nil}, &TreeNode{5, nil, nil}},
		&TreeNode{3, nil, nil},
	}
	PreOrder(root)    // 1 2 4 5 3
	fmt.Println()
	InOrder(root)     // 4 2 5 1 3
	fmt.Println()
	LevelOrder(root)  // 1 2 3 4 5
}

考点解析: 前序根左右，中序左根右(BST中序即升序)，后序左右根。层序遍历用队列BFS。递归改迭代时前中序用栈，后序用栈加prev指针。

八、图BFS与DFS

考点: BFS用队列找最短路径，DFS用递归或栈遍历。

package main

import "fmt"

// Graph 邻接表表示的图
type Graph struct {
	V     int       // 顶点数
	Edges [][]int   // 邻接表
}

func NewGraph(v int) *Graph {
	return &Graph{V: v, Edges: make([][]int, v)}
}

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

// BFS 广度优先, 用队列, 找最短路径
func (g *Graph) BFS(start int) []int {
	visited := make([]bool, g.V)
	queue := []int{start}
	visited[start] = true
	result := []int{}

	for len(queue) > 0 {
		// 出队
		node := queue[0]
		queue = queue[1:]
		result = append(result, node)
		// 遍历邻接点
		for _, neighbor := range g.Edges[node] {
			if !visited[neighbor] {
				visited[neighbor] = true
				queue = append(queue, neighbor)
			}
		}
	}
	return result
}

// DFS 深度优先, 递归
func (g *Graph) DFS(start int) []int {
	visited := make([]bool, g.V)
	result := []int{}
	g.dfsHelper(start, visited, &result)
	return result
}

func (g *Graph) dfsHelper(node int, visited []bool, result *[]int) {
	visited[node] = true
	*result = append(*result, node)
	for _, neighbor := range g.Edges[node] {
		if !visited[neighbor] {
			g.dfsHelper(neighbor, visited, result)
		}
	}
}

func main() {
	g := NewGraph(5)
	g.AddEdge(0, 1)
	g.AddEdge(0, 2)
	g.AddEdge(1, 3)
	g.AddEdge(2, 4)
	fmt.Println("BFS:", g.BFS(0))   // [0 1 2 3 4]
	fmt.Println("DFS:", g.DFS(0))   // [0 1 3 2 4]
}

考点解析: BFS用队列保证层序，适合最短路径。DFS用递归(栈)深入到底，适合连通性判断。两者都用visited数组防止重复访问。Go用切片模拟队列，没有标准队列类型。

九、动态规划(背包问题)

考点: 0-1背包状态转移方程，二维dp压缩到一维。

package main

import "fmt"

// Knapsack 0-1背包, 每件物品取或不取
// dp[j] = max(dp[j], dp[j-w[i]] + v[i])
func Knapsack(weights, values []int, capacity int) int {
	// dp[j] 表示容量j时的最大价值
	dp := make([]int, capacity+1)
	for i := 0; i < len(weights); i++ {
		// 逆序遍历, 防止同一物品取多次
		for j := capacity; j >= weights[i]; j-- {
			// 取: dp[j-w[i]] + values[i]
			// 不取: dp[j]
			if dp[j-weights[i]]+values[i] > dp[j] {
				dp[j] = dp[j-weights[i]] + values[i]
			}
		}
	}
	return dp[capacity]
}

func main() {
	weights := []int{2, 3, 4, 5}
	values := []int{3, 4, 5, 6}
	capacity := 8
	// 最优: 取物品1和3(重量2+5=7, 价值3+6=9)
	fmt.Println(Knapsack(weights, values, capacity)) // 9
}

考点解析: 0-1背包一维dp必须逆序遍历，保证每个物品只取一次。如果正序遍历退化成完全背包(物品可重复取)。状态转移方程的核心是"取或不取"两种选择的max。

十、字符串匹配(KMP)

考点: KMP用next数组跳过重复比较，O(N+M)。

package main

import "fmt"

// buildNext 构建next数组(最长公共前后缀长度)
func buildNext(pattern string) []int {
	n := len(pattern)
	next := make([]int, n)
	next[0] = -1 // next[0]固定-1, 表示无前缀
	k := -1      // k指向前缀末尾
	j := 0       // j指向后缀末尾
	for j < n-1 {
		if k == -1 || pattern[k] == pattern[j] {
			k++
			j++
			next[j] = k // 匹配则前缀长度+1
		} else {
			k = next[k] // 失配, k回退到next[k]
		}
	}
	return next
}

// KMP 字符串匹配
func KMP(text, pattern string) int {
	next := buildNext(pattern)
	i, j := 0, 0 // i遍历text, j遍历pattern
	for i < len(text) && j < len(pattern) {
		if j == -1 || text[i] == pattern[j] {
			i++
			j++ // 匹配, 双指针前进
		} else {
			j = next[j] // 失配, pattern指针跳转
		}
	}
	if j == len(pattern) {
		return i - j // 匹配位置
	}
	return -1 // 未匹配
}

func main() {
	fmt.Println(KMP("ABABDABACDABABC", "ABABC")) // 10
}

考点解析: KMP核心是next数组预处理最长公共前后缀，失配时pattern指针跳到next[j]而非回到开头。预处理O(M)，匹配O(N)，总O(N+M)。暴力匹配O(NM)。

踩坑经验

坑1: slice扩容预估错误导致OOM

线上服务处理批量任务，把结果收集到一个切片里。预估每个任务产生约500条结果，总任务量10万。开发时按"500 * 10万 = 5000万"预估内存，每条结果约200字节，算下来10GB。觉得切片扩容最多多一倍，应该15GB够了。

实际部署后内存直接涨到40GB被OOM Kill。问题出在两点。第一，Go 1.18后大切片扩容按1.25倍增长，不是翻倍，中间多次扩容每次都分配新数组，峰值内存远超预期。第二，append扩容时旧数组暂时不被GC回收，新旧数组同时存在，内存翻倍。

// Bad: 不预分配, 频繁扩容, 峰值内存翻倍
results := []Result{}
for i := 0; i < 50000000; i++ {
	results = append(results, compute(i))
}

// Good: 预分配cap, 一次到位, 无扩容拷贝
results := make([]Result, 0, 50000000)
for i := 0; i < 50000000; i++ {
	results = append(results, compute(i))
}

教训是已知或可预估数据量时必须预分配cap。面试中被问到slice扩容规则时，要能说出Go 1.18后的两段式增长规则，以及扩容期间新旧数组同时存在的内存峰值问题。

对比分析

维度	Go算法面试	Java算法面试
数据结构库	container/list和container/heap较少	Collections框架丰富完整
手写要求	多用手写(swap, ring buffer等)	可用标准库(HashMap, PriorityQueue)
内存意识	侧重slice扩容和内存布局	侧重对象创建和GC压力
泛型支持	1.18+泛型简化容器实现	泛型成熟, 类型擦除细节
典型题目	slice/map底层, LRU, worker pool	红黑树, 并发容器, JVM相关

Go面试更侧重底层内存布局和标准库匮乏下的手写能力，Java面试更侧重标准库原理和JVM层面理解。Go面试官喜欢问slice和map的底层结构，Java面试官喜欢问HashMap和ConcurrentHashMap原理。

总结

数据结构与算法面试10道题从底层原理到经典实现全覆盖。slice扩容和map哈希冲突是Go特色考点，LRU和跳表是手写高频题。堆排序、KMP、动态规划是算法基本功。Go标准库数据结构较少(container包只有list、heap、ring)，大量场景需要手写，面试时注意用切片模拟栈和队列，用map加链表实现缓存。预分配slice容量是生产环境的硬性要求。