Gopher面试中的Coding
原文作者：brantou
从四月份下半月开始，陆陆续续面试了几家公司，都是golang的岗位。每一次面试，侧重点都会有不同，有的会直接给过来一道试题， 然后边解题，边讲述自己的思路，然后面试官根据你的思路和你交流沟通；有的呢，让讲述自己最近做过的项目，遇到的难点， 自己怎么解决的问题思路，而无独有偶的呢，这样的面试中，都要需要展示编码能力。这篇文章就把自己最近面试中遇到的每一个编程问题， 分三步阐述出来：问题描述，解题思路，实际编程。
交替打印数字和字母
问题描述
使用两个 goroutine 交替打印序列，一个 goroutinue 打印数字， 另外一个goroutine打印字母， 最终效果如下 12AB34CD56EF78GH910IJ 。
解题思路
问题很简单，使用 channel 来控制打印的进度。使用两个 channel ，来分别控制数字和字母的打印序列， 数字打印完成后通过 channel 通知字母打印, 字母打印完成后通知数字打印，然后周而复始的工作。
实际编码
1runtime.GOMAXPROCS(runtime.NumCPU())
2chan_n := make(chan bool)
3chan_c := make(chan bool, 1)
4done := make(chan struct{})
5
6go func() {
7 for i := 1; i < 11; i += 2 {
8 <-chan_c
9 fmt.Print(i)
10 fmt.Print(i + 1)
11 chan_n <- true
12 }
13}()
14
15go func() {
16 char_seq := []string{"A","B","C","D","E","F","G","H","I","J","K"}
17 for i := 0; i < 10; i += 2 {
18 <-chan_n
19 fmt.Print(char_seq[i])
20 fmt.Print(char_seq[i+1])
21 chan_c <- true
22 }
23 done <- struct{}{}
24}()
25
26chan_c <- true
27<-done代码执行结果:
112AB34CD56EF78GH910IJ看完上面的代码，是不是会有些疑惑，为什么
chan_c需要缓存，而chan_n不需要呢? 当两个打印goroutine无限交替运行时，没有缓存是OK的， 但很明显上面的示例不是，打印数字的goroutine先退出，也就没有了goroutine来读取chan_c中的内容了， 而打印字母的goroutine就会阻塞在chan_c <- true，这样就导致了死锁。
随机抽奖
问题描述
用户随机抽奖，数据结构如下所示：
1// map中，key代表名称，value代表成交单数
2var users map[string]int64 = map[string]int64{
3 "a": 10,
4 "b": 6,
5 "c": 3,
6 "d": 12,
7 "f": 1,
8}解决思路
从map中选取随机用户，拿到这个编码问题，有点懵逼,但仔细一想，只需把关注用户的区间，转变一下数据结构即解题。 把map转成array，思考起来就简单多了，原有问题变成了从0至n-1中选取一个数字，数字对应的用户即中奖用户。
实际编码
1package main
2
3import (
4 "fmt"
5 "math/rand"
6 "time"
7)
8
9func GetAwardUserName(users map[string]int64) (name string) {
10 sizeOfUsers := len(users)
11 award_index := rand.Intn(sizeOfUsers)
12
13 var index int
14 for u_name, _ := range users {
15 if index == award_index {
16 name = u_name
17 return
18 }
19 index += 1
20 }
21 return
22}
23
24func main() {
25 var users map[string]int64 = map[string]int64{
26 "a": 10,
27 "b": 6,
28 "c": 3,
29 "d": 12,
30 "e": 20,
31 "f": 1,
32 }
33
34 rand.Seed(time.Now().Unix())
35 award_stat := make(map[string]int64)
36 for i := 0; i < 1000; i += 1 {
37 name := GetAwardUserName(users)
38 if count, ok := award_stat[name]; ok {
39 award_stat[name] = count + 1
40 } else {
41 award_stat[name] = 1
42 }
43 }
44
45 for name, count := range award_stat {
46 fmt.Printf("user: %s, award count: %d\n", name, count)
47 }
48
49 return
50}代码执行结果：
1user: f, award count: 178
2user: d, award count: 152
3user: b, award count: 159
4user: e, award count: 182
5user: c, award count: 170
6user: a, award count: 159权重抽奖
问题描述
数据结构和上面一致，只是问题发生变化，需要更加用户的成单数来抽奖，用户成单越多，中奖概率越高，结构如下所示：
1// map中，key代表名称，value代表成交单数
2var users map[string]int64 = map[string]int64{
3 "a": 10,
4 "b": 6,
5 "c": 3,
6 "d": 12,
7 "f": 1,
8}解决思路
这一题是上一题的延伸，加了订单数进去，做为权重来为用户抽奖。此题和上面的问题如此的相似，可把上面的问题， 理解成所有的用户权重都相同的抽奖，而此题是权重不同的抽奖。解决此问题，依旧是把map转为数组来思考， 把各用户的权重，从前到后依次拼接到数轴上，数轴的起点到终点即时中奖区间，而随机数落到的那个用户的区间，那个用户即为中奖用户。
实际编码
1package main
2
3import (
4 "fmt"
5 "math/rand"
6 "time"
7)
8
9func GetAwardUserName(users map[string]int64) (name string) {
10 type A_user struct {
11 Name string
12 Offset int64
13 Num int64
14 }
15
16 a_user_arr := make([]*A_user, 0)
17 var sum_num int64
18 for name, num := range users {
19 a_user := &A_user{
20 Name: name,
21 Offset: sum_num,
22 Num: num,
23 }
24 a_user_arr = append(a_user_arr, a_user)
25 sum_num += num
26 }
27
28 award_num := rand.Int63n(sum_num)
29
30 for index, _ := range a_user_arr {
31 a_user := a_user_arr[index]
32 if a_user.Offset+a_user.Num > award_num {
33 name = a_user.Name
34 return
35 }
36 }
37 return
38}
39
40func main() {
41 var users map[string]int64 = map[string]int64{
42 "a": 10,
43 "b": 5,
44 "c": 15,
45 "d": 20,
46 "e": 10,
47 "f": 30,
48 }
49
50 rand.Seed(time.Now().Unix())
51 award_stat := make(map[string]int64)
52 for i := 0; i < 10000; i += 1 {
53 name := GetAwardUserName(users)
54 if count, ok := award_stat[name]; ok {
55 award_stat[name] = count + 1
56 } else {
57 award_stat[name] = 1
58 }
59 }
60
61 for name, count := range award_stat {
62 fmt.Printf("user: %s, award count: %d\n", name, count)
63 }
64
65 return
66}代码执行结果：
1user: c, award count: 1667
2user: f, award count: 3310
3user: e, award count: 1099
4user: d, award count: 2276
5user: b, award count: 549
6user: a, award count: 1099感谢各位的评论，让我受益匪浅，上面代码确实有太多的槽点，感谢吐槽，代码更正如下：
1func GetAwardUserName(users map[string]int64) (name string) {
2 var sum_num int64
3 for _, num := range users {
4 sum_num += num
5 }
6
7 award_num := rand.Int63n(sum_num)
8
9 var offset_num int64
10 for _name, num := range a_user_arr {
11 offset_num += num
12 if award_num < offset_num {
13 name = _name
14 return
15 }
16 }
17 return
18}由于一直以为Golang的map
for range是可重入的，但现实是前后两轮遍历到的key的顺序居然是被随机化的， 代码示例如下：
1n_map := make(map[int]bool)
2for i := 1; i <= 10; i++ {
3 n_map[i] = true
4}
5
6for num, _ := range n_map {
7 fmt.Print(num)
8}
9fmt.Print("\n")
10for num, _ := range n_map {
11 fmt.Print(num)
12}191257103468
246810325791由于map的不可重入性， 以及 liguoqinjim 给出的 示例代码 和 运行结果 证明了map的
for range的伪随机性， 代码修改如下(在Playground 中可查看完整代码):
1func GetAwardUserName(users map[string]int64) (name string) {
2 var sum_num int64
3 name_arr := make([]string, len(users))
4 for u_name, num := range users {
5 sum_num += num
6 name_arr = append(name_arr, u_name)
7 }
8
9 award_num := rand.Int63n(sum_num)
10
11 var offset_num int64
12 for _, u_name := range name_arr {
13 offset_num += users[u_name]
14 if award_num < offset_num {
15 name = u_name
16 return
17 }
18 }
19 return
20}上面代码，对于多次调用会有性能问题，每次都要重新计算
sum_num和创建name_arr, 使用闭包重新实现， 代码如下(在Playground 中可查看完整代码):
1func GetAwardGenerator(users map[string]int64) (generator func() string) {
2 var sum_num int64
3 name_arr := make([]string, len(users))
4 for u_name, num := range users {
5 sum_num += num
6 name_arr = append(name_arr, u_name)
7 }
8
9 generator = func() string {
10 award_num := rand.Int63n(sum_num)
11
12 var offset_num int64
13 for _, u_name := range name_arr {
14 offset_num += users[u_name]
15 if award_num < offset_num {
16 return u_name
17 }
18 }
19 // 缺省返回，正常情况下，不会运行到此处
20 return name_arr[0]
21 }
22 return
23}上面代码使用了闭包避免了多次抽奖时频繁的初始化， 但每次抽奖的复杂度O(n)，很明显依旧有可优化的空间，可使用二分搜索来使复杂度降到
O(log n), 代码如下：
1func GetAwardGenerator(users map[string]int64) (generator func() string) {
2 var sum_num int64
3 name_arr := make([]string, len(users))
4 offset_arr := make([]int64, len(users))
5 var index int
6 for u_name, num := range users {
7 name_arr[index] = u_name
8 offset_arr[index] = sum_num
9 sum_num += num
10 index += 1
11 }
12
13 generator = func() string {
14 award_num := rand.Int63n(sum_num)
15 return name_arr[binary_search(offset_arr, award_num)]
16 }
17 return
18}
19
20func binary_search(nums []int64, target int64) int {
21 start, end := 0, len(nums)-1
22 for start <= end {
23 mid := start + (end-start)/2
24 if nums[mid] > target {
25 end = mid - 1
26 } else if nums[mid] < target {
27 if mid+1 == len(nums) { // 最后一名中奖
28 return mid
29 }
30 if nums[mid+1] > target {
31 return mid
32 }
33 start = mid + 1
34 } else {
35 return mid
36 }
37 }
38
39 return -1
40}总结
问题一来自一家公司 , 侧重于语言特性；问题二三来自另外一家公司 ，侧重于解决问题的思路；本人更喜欢第二种，很有启发性。 我之后会把其他自己认为比较有趣的编程任务，整理到此篇文章中，敬请期待。
ps:原文底下评论有非常多针对解题的讨论，建议大家看看原文哦~