Go 算法与面试题项目

项目简介

这是一个 Go 语言算法练习项目，包含常见排序算法、数据结构、网络编程示例以及面试常见问题。

---

文件说明

排序算法

文件	功能描述	时间复杂度
quickSort.go	快速排序实现，采用分治策略，选择最后一个元素作为基准	O(n log n) 平均
mergeSort.go	归并排序实现，递归分割数组然后合并有序子数组	O(n log n)
bubbleSort.go	冒泡排序实现，相邻元素比较交换，优化版添加交换标志	O(n²)
insertSort.go	插入排序实现，将元素插入已排序部分的正确位置	O(n²)
selectSort.go	选择排序实现，每次选择最小元素放到当前位置	O(n²)
shellSort.go	希尔排序实现，改进的插入排序，使用增量序列	O(n log n) ~ O(n²)
heapsort.go	最大堆实现，解决滑动窗口最大值问题	O(n log k)

查找算法

文件	功能描述
binarysearch.go	二分查找实现，在有序数组中查找目标值，时间复杂度 O(log n)

数据结构

文件	功能描述
link.go	单链表实现，包含追加节点、打印链表、删除节点操作
reverse3.go	链表反转实现，使用迭代方式翻转链表
datastructure/queue.go	队列数据结构实现，包含入队和展示功能
datastructure/chessmap.go	稀疏数组应用，将二维棋盘压缩存储，节省空间

动态规划

文件	功能描述
最小路径和.go	最小路径和问题，使用动态规划计算从左上角到右下角的最小路径和
sanjiao.go	杨辉三角生成，打印前 N 行杨辉三角

网络编程

文件	功能描述
main.go	HTTP 服务器基础示例，演示 http.HandleFunc 路由注册
file.go	文件服务器，使用 http.FileServer 提供静态文件服务
windows.go	自定义文件系统，隐藏点文件（隐藏以 . 开头的文件）
get.go	HTTP GET 请求示例，获取远程资源并读取响应体
handelfunc.go	HTTP 处理函数示例，演示多个路由端点
client.go	JSON 解析和字符串过滤示例，过滤包含特定关键词的链接

系统与底层

文件	功能描述
ctx.go	Context 使用示例，演示 context.WithValue 传递键值对
pointer.go	指针大小演示，展示各类型占用的字节数和字符串 Unicode 长度
system/intlength.go	整数类型长度和字符串头大小，使用 unsafe.Sizeof
system/stringsheaders.go	字符串底层结构，使用 unsafe 访问字符串的 Data 指针

面试题（mianshiya 目录）

文件	功能描述	考点
mianshiya/err.go	error 接口 nil 判断陷阱	error 类型底层原理、nil 判断
mianshiya/mutex.go	互斥锁并发计数器	并发安全、sync.Mutex、sync.WaitGroup
mianshiya/dangling.go	Channel 关闭与 nil 指针处理	Channel 生命周期、指针安全

调试示例（debug 目录）

文件	功能描述
debug/defertest.go	defer 语句执行测试

---

Go 语言面试知识点

一、基础语法

1. 变量与常量

• var 声明变量，:= 短变量声明（只能在函数内使用）
• const 声明常量
• 值类型：int、float、bool、string、array、struct
• 引用类型：slice、map、channel、pointer、func、interface

2. 指针

• Go 没有指针运算
• & 取地址，* 解引用
• 指针零值为 nil

3. 数组与切片

• 数组是值类型，长度固定
• 切片是引用类型，长度可变
• 切片底层结构：指针、长度、容量
• append 可能导致扩容（容量翻倍）

4. Map

• 无序的键值对集合
• nil map 不能写入
• 并发读写需要加锁或使用 sync.Map

5. 结构体与方法

• 结构体是值类型
• 方法有值接收者和指针接收者
• 指针接收者可以修改结构体，值接收者不能

6. 接口

• 接口是抽象类型，定义行为契约
• 空接口 interface{} 可表示任意类型
• 接口值由两部分组成：类型和值
• 类型断言和类型开关

二、并发编程

1. Goroutine

• 轻量级线程，由 Go 运行时管理
• 使用 go 关键字启动
• 主 Goroutine 退出时，所有 Goroutine 都会退出

2. Channel

• 用于 Goroutine 间通信（CSP 模型）
• 有缓冲和无缓冲 Channel
• close 关闭 Channel，发送方负责关闭
• 使用 range 遍历 Channel
• select 多路复用

3. 并发原语

原语	用途
sync.Mutex	互斥锁，保证同一时间只有一个 Goroutine 访问
sync.RWMutex	读写锁，多读单写
sync.WaitGroup	等待一组 Goroutine 完成
sync.Once	确保函数只执行一次
sync.Atomic	原子操作
context.Context	跨 Goroutine 传递取消信号、超时、值

4. 并发模式

• Worker Pool 模式
• Pipeline 模式
• Fan-in / Fan-out 模式

三、错误处理

1. Error 接口

type error interface {
    Error() string
}

2. 错误处理模式

• 显式返回错误
• errors.New() 创建错误
• fmt.Errorf() 格式化错误
• 自定义错误类型

3. 常见陷阱

• nil error 与非 nil 接口：var err error = (*MyError)(nil) 不是 nil
• 总是检查返回的错误

4. Go 1.13+ 错误处理

• errors.Is() 判断错误类型
• errors.As() 类型转换
• %w 包装错误

四、内存管理

1. 堆与栈

• 栈：存储局部变量、函数参数，自动管理
• 堆：动态分配，由 GC 管理
• 逃逸分析决定变量分配位置

2. 垃圾回收（GC）

• 三色标记清除算法
• 写屏障
• GC 触发条件：内存分配量、定时、手动触发

3. 内存泄漏场景

• Goroutine 泄漏（永不退出的 Goroutine）
• Channel 阻塞
• 定时器未停止
• 长生命周期的对象持有短生命周期对象

五、常见面试题

1. defer 执行顺序

• defer 按后进先出（LIFO）顺序执行
• defer 在 return 之后、函数返回之前执行
• defer 可以修改返回值（命名返回值）

2. 切片扩容机制

• 容量小于 1024 时，翻倍
• 容量大于等于 1024 时，增长 25%
• 实际扩容算法可能调整

3. 接口值的比较

• 两个接口值相等需要类型和值都相等
• nil 接口值的类型和值都为 nil
• 包含 nil 指针的接口值不是 nil

4. Channel 的零值

• nil Channel 的操作：
  • 发送：永久阻塞
  • 接收：永久阻塞
  • 关闭：panic

5. Context 使用场景

• 请求超时控制
• 取消操作
• 跨 Goroutine 传递请求作用域的值
• 优雅关闭

6. GC 如何判断对象可回收

• 根对象（全局变量、栈变量）
• 从根对象开始遍历，标记可达对象
• 未标记的对象可回收

7. 如何防止循环引用导致的内存泄漏

• 使用弱引用（Go 原生不支持，需用 unsafe）
• 手动打破循环
• 使用指针时注意生命周期

8. Mutex 和 RWMutex 的选择

• 读多写少：RWMutex
• 读写都多：Mutex（RWMutex 在写多场景下性能可能更差）

9. 如何实现单例模式

var (
    instance *Singleton
    once     sync.Once
)

func GetInstance() *Singleton {
    once.Do(func() {
        instance = &Singleton{}
    })
    return instance
}

10. struct{}{} 的用途

• 用于 Channel 信号传递（不关心数据）
• 用于 Set 实现（map[T]struct{}）
• 占用 0 字节内存

六、性能优化

1. 减少内存分配

• 预分配切片容量
• 复用对象（对象池 sync.Pool）
• 避免字符串到字节数组的频繁转换

2. 减少 GC 压力

• 减少小对象分配
• 使用栈分配（避免逃逸）
• 及时释放大对象

3. 并发优化

• 使用合适的并发原语
• 避免 Goroutine 泄漏
• 控制 Goroutine 数量（Worker Pool）

4. 性能分析工具

• pprof：CPU 和内存分析
• trace：执行追踪
• benchstat：基准测试结果对比

---

测试文件（未在说明中列出）

文件	功能
test*.go	各算法的测试入口文件

---

运行方式

# 运行单个文件
go run 文件名.go

# 编译
go build 文件名.go

# 运行测试
go test

---

项目结构

.
├── main.go                    # HTTP 服务器示例
├── file.go                    # 文件服务器
├── get.go                     # HTTP GET 示例
├── quickSort.go               # 快速排序
├── link.go                    # 链表
├── shellSort.go               # 希尔排序
├── selectSort.go              # 选择排序
├── binarysearch.go            # 二分查找
├── handelfunc.go              # HTTP 处理函数
├── insertSort.go              # 插入排序
├── ctx.go                     # Context 示例
├── heapsort.go                # 堆排序/最大堆
├── mergeSort.go               # 归并排序
├── bubblesort.go              # 冒泡排序
├── windows.go                 # 自定义文件系统
├── client.go                  # JSON 解析
├── reverse3.go                # 链表反转
├── sanjiao.go                 # 杨辉三角
├── 最小路径和.go              # 动态规划
├── pointer.go                 # 指针示例
├── system/                    # 系统底层
│   ├── intlength.go
│   └── stringsheaders.go
├── mianshiya/                 # 面试题
│   ├── err.go
│   ├── mutex.go
│   └── dangling.go
├── debug/                     # 调试示例
│   └── defertest.go
└── datastructure/             # 数据结构
    ├── chessmap.go
    └── queue.go