- 正确答案： 1. 使用 Go 语言的 goroutine 和 channel 实现三个线程循环打印 1、2、3，每个线程负责打印一个数字，通过 channel 控制执行顺序。 2. 前缀树（Trie）是一种树形数据结构，用于高效存储和检索字符串集合中的键，特别适用于前缀匹配场景。 - 解答思路：第一题：要实现多线程循环打印 1 2 3，核心是线程间同步。Go 中推荐使用 channel 进行协程通信。可以设计三个 channel，分别控制三个 goroutine 的执行顺序，通过轮流发送信号实现循环打印。主程序控制循环次数，避免无限执行。第二题：前缀树的核心思想是“空间换时间”，利用字符串的公共前缀来减少查询时间。每个节点代表一个字符，从根到某节点路径构成一个字符串前缀。需要支持插入、查找、前缀匹配等操作。 - 深度知识讲解：问题1：Go 多线程循环打印 123 考点：goroutine、channel、并发控制、同步机制。 Go 不使用传统“线程”概念，而是轻量级的 goroutine。多个 goroutine 之间通过 channel 进行通信，避免共享内存带来的竞态条件。本题考察对 CSP（Communicating Sequential Processes）模型的理解。使用 buffered 或 unbuffered channel 均可，但需注意死锁问题。典型做法是用三个 channel 形成“接力”模式，初始时第一个 channel 获得令牌，其余阻塞。关键点： - 使用无缓冲 channel 实现同步。 - 主 goroutine 控制总循环次数。 - 每个打印 goroutine 打印后传递控制权给下一个。代码示例（循环打印 10 次 1 2 3）： ``` package main import ( "fmt" ) func main() { const N = 10 ch1 := make(chan bool) ch2 := make(chan bool) ch3 := make(chan bool) go func() { for i := 0; i < N; i++ { <-ch1 fmt.Print("1") ch2 <- true } }() go func() { for i := 0; i < N; i++ { <-ch2 fmt.Print("2") ch3 <- true } }() go func() { for i := 0; i < N; i++ { <-ch3 fmt.Print("3") if i < N-1 { ch1 <- true } else { close(ch1) // 结束信号 } } }() ch1 <- true // 启动第一个 select {} // 防止主 goroutine 退出 } ``` 注意：最后不能让 ch3 再发回 ch1 导致第11次启动，所以第 N 次不发。也可以用 WaitGroup 配合 channel 更优雅地结束。改进版使用 WaitGroup 管理生命周期： ``` package main import ( "fmt" "sync" ) func main() { const N = 10 var wg sync.WaitGroup ch1 := make(chan bool) ch2 := make(chan bool) ch3 := make(chan bool) wg.Add(3) go func() { defer wg.Done() for i := 0; i < N; i++ { <-ch1 fmt.Print("1") ch2 <- true } }() go func() { defer wg.Done() for i := 0; i < N; i++ { <-ch2 fmt.Print("2") ch3 <- true } }() go func() { defer wg.Done() for i := 0; i < N; i++ { <-ch3 fmt.Print("3") if i == N-1 { close(ch1) return } ch1 <- true } }() ch1 <- true wg.Wait() } ``` 输出：123123123...（共10组）扩展知识点： - Go runtime 调度器 GMP 模型（Goroutine, M: OS thread, P: Processor） - channel 底层是环形队列，有互斥锁保护，实现线程安全 - 无缓冲 channel 是同步的，发送和接收必须配对才能完成 - 可以使用 mutex + condition variable 实现类似功能，但不符合 Go 的“不要通过共享内存来通信，而应通过通信来共享内存”的哲学问题2：前缀树（Trie）考点：树形数据结构、字符串处理、内存布局、递归与迭代实现。 Trie 是一种有序树，用于存储动态集合或关联数组，其中的键通常是字符串。与二叉搜索树不同，Trie 的节点不存储完整的键，而是存储单个字符。从根到叶子的路径表示一个完整字符串。核心特性： - 插入、查找时间复杂度为 O(m)，m 是字符串长度，与数据集中元素数量无关。 - 空间复杂度较高，尤其是字符集大时（如 Unicode），可用压缩 Trie（Patricia Trie）优化。 - 支持高效前缀匹配，如自动补全、拼写检查。节点结构： - children: 映射字符到子节点指针（常用 map[rune]*TrieNode 或数组） - isEnd: 标记该节点是否为某个字符串的结尾实现操作： - Insert(s string): 逐字符插入，不存在则创建新节点 - Search(s string): 完全匹配，路径存在且末尾 isEnd=true - StartsWith(prefix string): 只需路径存在即可代码示例： ``` type TrieNode struct { children map[rune]*TrieNode isEnd bool } type Trie struct { root *TrieNode } func NewTrie() *Trie { return &Trie{ root: &TrieNode{children: make(map[rune]*TrieNode)}, } } func (t *Trie) Insert(word string) { node := t.root for _, ch := range word { if next, exists := node.children[ch]; exists { node = next } else { newNode := &TrieNode{children: make(map[rune]*TrieNode)} node.children[ch] = newNode node = newNode } } node.isEnd = true } func (t *Trie) Search(word string) bool { node := t.root for _, ch := range word { if next, exists := node.children[ch]; exists { node = next } else { return false } } return node.isEnd } func (t *Trie) StartsWith(prefix string) bool { node := t.root for _, ch := range prefix { if next, exists := node.children[ch]; exists { node = next } else { return false } } return true } ``` 使用示例： ``` func main() { trie := NewTrie() trie.Insert("apple") fmt.Println(trie.Search("apple")) // true fmt.Println(trie.Search("app")) // false fmt.Println(trie.StartsWith("app")) // true trie.Insert("app") fmt.Println(trie.Search("app")) // true } ``` 深度知识扩展： 1. 字符映射优化： - 若仅小写字母，可用数组 [26]*TrieNode 替代 map，提升性能。 - 对于中文或 Unicode，map[rune]*TrieNode 更合适。 2. 空间优化技术： - 压缩前缀树（Radix Tree / Patricia Trie）：合并只有一个子节点的链。 - 使用 slice 或 array 替代 map 减少哈希开销。 3. 应用场景： - 自动补全（搜索引擎、IDE） - 拼写检查（Levenshtein Automaton 结合 Trie） - IP 路由查找（最长前缀匹配） - 单词游戏（Boggle、Word Search） 4. 并发安全： - 多线程环境下需加读写锁（sync.RWMutex） - 或采用函数式 Trie（持久化数据结构） 5. 性能对比： - 相比哈希表：Trie 在前缀查询上优势明显，但哈希表平均查找更快。 - 相比 BST：Trie 查找稳定 O(m)，不受数据分布影响。小结：这两道题分别考察了 Go 并发编程能力和基础数据结构实现能力。第一题强调对 channel 和 goroutine 的理解，第二题考察对树结构和字符串算法的掌握。在实际面试中，建议先清晰说明思路，再动手编码，并注意边界条件和资源管理。

字节一面

全站热榜

创作者周榜