Gopher面试中的Coding

从四月份下半月开始,陆陆续续面试了几家公司,都是golang的岗位。每一次面试,侧重点都会有不同,有的会直接给过来一道试题, 然后边解题,边讲述自己的思路,然后面试官根据你的思路和你交流沟通;有的呢,让讲述自己最近做过的项目,遇到的难点, 自己怎么解决的问题思路,而无独有偶的呢,这样的面试中,都要需要展示编码能力。这篇文章就把自己最近面试中遇到的每一个编程问题, 分三步阐述出来:问题描述,解题思路,实际编程。

1 交替打印数字和字母

1.1 问题描述

使用两个 goroutine 交替打印序列,一个 goroutinue 打印数字, 另外一个goroutine打印字母, 最终效果如下 12AB34CD56EF78GH910IJ

1.2 解题思路

问题很简单,使用 channel 来控制打印的进度。使用两个 channel ,来分别控制数字和字母的打印序列, 数字打印完成后通过 channel 通知字母打印, 字母打印完成后通知数字打印,然后周而复始的工作。

1.3 实际编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
runtime.GOMAXPROCS(runtime.NumCPU())
chan_n := make(chan bool)
chan_c := make(chan bool, 1)
done := make(chan struct{})

go func() {
for i := 1; i < 11; i += 2 {
<-chan_c
fmt.Print(i)
fmt.Print(i + 1)
chan_n <- true
}
}()

go func() {
char_seq := []string{"A","B","C","D","E","F","G","H","I","J","K"}
for i := 0; i < 10; i += 2 {
<-chan_n
fmt.Print(char_seq[i])
fmt.Print(char_seq[i+1])
chan_c <- true
}
done <- struct{}{}
}()

chan_c <- true
<-done

代码执行结果:

12AB34CD56EF78GH910IJ

看完上面的代码,是不是会有些疑惑,为什么 chan_c 需要缓存,而 chan_n 不需要呢?
当两个打印 goroutine 无限交替运行时,没有缓存是OK的, 但很明显上面的示例不是,打印数字的 goroutine 先退出,也就失去了 goroutine 来读取 chan_c 中的内容了, 而打印字母的goroutine就会阻塞在 chan_c <- true 这里,这样就导致了死锁。

当然无缓存版也是可以,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
runtime.GOMAXPROCS(runtime.NumCPU())
chan_n := make(chan bool)
chan_c := make(chan bool)
done := make(chan struct{})

go func() {
for i := 1; i < 11; i += 2 {
fmt.Print(i)
fmt.Print(i + 1)
chan_n <- true
<-chan_c
}

done <- struct{}{}
}()

go func() {
char_seq := []string{"A","B","C","D","E","F","G","H","I","J","K"}
for i := 0; i < 10; i += 2 {
<-chan_n
fmt.Print(char_seq[i])
fmt.Print(char_seq[i+1])
chan_c <- true
}

done <- struct{}{}
}()

<-done
<-done

2 随机抽奖

2.1 问题描述

用户随机抽奖,数据结构如下所示:

1
2
3
4
5
6
7
8
// map中,key代表名称,value代表成交单数
var users map[string]int64 = map[string]int64{
"a": 10,
"b": 6,
"c": 3,
"d": 12,
"f": 1,
}

2.2 解决思路

从map中选取随机用户,拿到这个编码问题,有点懵逼,但仔细一想,只需把关注用户的区间,转变一下数据结构即解题。 把map转成array,思考起来就简单多了,原有问题变成了从0至n-1中选取一个数字,数字对应的用户即中奖用户。

2.3 实际编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package main

import (
"fmt"
"math/rand"
"time"
)

func GetAwardUserName(users map[string]int64) (name string) {
sizeOfUsers := len(users)
award_index := rand.Intn(sizeOfUsers)

var index int
for u_name, _ := range users {
if index == award_index {
name = u_name
return
}
index += 1
}
return
}

func main() {
var users map[string]int64 = map[string]int64{
"a": 10,
"b": 6,
"c": 3,
"d": 12,
"e": 20,
"f": 1,
}

rand.Seed(time.Now().Unix())
award_stat := make(map[string]int64)
for i := 0; i < 1000; i += 1 {
name := GetAwardUserName(users)
if count, ok := award_stat[name]; ok {
award_stat[name] = count + 1
} else {
award_stat[name] = 1
}
}

for name, count := range award_stat {
fmt.Printf("user: %s, award count: %d\n", name, count)
}

return
}

代码执行结果:

user: f, award count: 178
user: d, award count: 152
user: b, award count: 159
user: e, award count: 182
user: c, award count: 170
user: a, award count: 159

3 权重抽奖

3.1 问题描述

数据结构和上面一致,只是问题发生变化,需要更加用户的成单数来抽奖,用户成单越多,中奖概率越高,结构如下所示:

1
2
3
4
5
6
7
8
// map中,key代表名称,value代表成交单数
var users map[string]int64 = map[string]int64{
"a": 10,
"b": 6,
"c": 3,
"d": 12,
"f": 1,
}

3.2 解决思路

这一题是上一题的延伸,加了订单数进去,做为权重来为用户抽奖。此题和上面的问题如此的相似,可把上面的问题, 理解成所有的用户权重都相同的抽奖,而此题是权重不同的抽奖。解决此问题,依旧是把map转为数组来思考, 把各用户的权重,从前到后依次拼接到数轴上,数轴的起点到终点即时中奖区间,而随机数落到的那个用户的区间,那个用户即为中奖用户。

3.3 实际编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package main

import (
"fmt"
"math/rand"
"time"
)

func GetAwardUserName(users map[string]int64) (name string) {
type A_user struct {
Name string
Offset int64
Num int64
}

a_user_arr := make([]*A_user, 0)
var sum_num int64
for name, num := range users {
a_user := &A_user{
Name: name,
Offset: sum_num,
Num: num,
}
a_user_arr = append(a_user_arr, a_user)
sum_num += num
}

award_num := rand.Int63n(sum_num)

for index, _ := range a_user_arr {
a_user := a_user_arr[index]
if a_user.Offset+a_user.Num > award_num {
name = a_user.Name
return
}
}
return
}

func main() {
var users map[string]int64 = map[string]int64{
"a": 10,
"b": 5,
"c": 15,
"d": 20,
"e": 10,
"f": 30,
}

rand.Seed(time.Now().Unix())
award_stat := make(map[string]int64)
for i := 0; i < 10000; i += 1 {
name := GetAwardUserName(users)
if count, ok := award_stat[name]; ok {
award_stat[name] = count + 1
} else {
award_stat[name] = 1
}
}

for name, count := range award_stat {
fmt.Printf("user: %s, award count: %d\n", name, count)
}

return
}

代码执行结果:

user: c, award count: 1667
user: f, award count: 3310
user: e, award count: 1099
user: d, award count: 2276
user: b, award count: 549
user: a, award count: 1099

感谢各位的评论,让我受益匪浅,上面代码确实有太多的槽点,感谢吐槽,代码更正如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func GetAwardUserName(users map[string]int64) (name string) {
var sum_num int64
for _, num := range users {
sum_num += num
}

award_num := rand.Int63n(sum_num)

var offset_num int64
for _name, num := range a_user_arr {
offset_num += num
if award_num < offset_num {
name = _name
return
}
}
return
}

由于一直以为Golang的map for range 是可重入的,但现实是前后两轮遍历到的 key 的顺序居然是被随机化的, 代码示例如下:

1
2
3
4
5
6
7
8
9
10
11
12
n_map := make(map[int]bool)
for i := 1; i <= 10; i++ {
n_map[i] = true
}

for num, _ := range n_map {
fmt.Print(num)
}
fmt.Print("\n")
for num, _ := range n_map {
fmt.Print(num)
}
91257103468
46810325791

由于map的不可重入性, 以及 liguoqinjim 给出的 示例代码运行结果 证明了map的 for range 的伪随机性, 代码修改如下(在Playground 中可查看完整代码):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func GetAwardUserName(users map[string]int64) (name string) {
var sum_num int64
name_arr := make([]string, len(users))
for u_name, num := range users {
sum_num += num
name_arr = append(name_arr, u_name)
}

award_num := rand.Int63n(sum_num)

var offset_num int64
for _, u_name := range name_arr {
offset_num += users[u_name]
if award_num < offset_num {
name = u_name
return
}
}
return
}

上面代码,对于多次调用会有性能问题,每次都要重新计算 sum_num 和创建 name_arr, 使用闭包优化实现, 代码如下(在Playground 中可查看完整代码):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func GetAwardGenerator(users map[string]int64) (generator func() string) {
var sum_num int64
name_arr := make([]string, len(users))
for u_name, num := range users {
sum_num += num
name_arr = append(name_arr, u_name)
}

generator = func() string {
award_num := rand.Int63n(sum_num)

var offset_num int64
for _, u_name := range name_arr {
offset_num += users[u_name]
if award_num < offset_num {
return u_name
}
}
// 缺省返回,正常情况下,不会运行到此处
return name_arr[0]
}
return
}

上面代码使用了闭包避免了多次抽奖时频繁的初始化, 但每次抽奖的复杂度O(n),很明显依旧有可优化的空间,可使用二分搜索来使复杂度降到 O(log n), 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func GetAwardGenerator(users map[string]int64) (generator func() string) {
var sum_num int64
name_arr := make([]string, len(users))
offset_arr := make([]int64, len(users))
var index int
for u_name, num := range users {
name_arr[index] = u_name
offset_arr[index] = sum_num
sum_num += num
index += 1
}

generator = func() string {
award_num := rand.Int63n(sum_num)
return name_arr[binary_search(offset_arr, award_num)]
}
return
}

func binary_search(nums []int64, target int64) int {
start, end := 0, len(nums)-1
for start <= end {
mid := start + (end-start)/2
if nums[mid] > target {
end = mid - 1
} else if nums[mid] < target {
if mid+1 == len(nums) { // 最后一名中奖
return mid
}
if nums[mid+1] > target {
return mid
}
start = mid + 1
} else {
return mid
}
}

return -1
}

在已知长度的情况下,应使用 array[index]=num 而避免使用 array=append(array, num), 代码和测试如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package main

import (
"fmt"
"time"
)

func main() {
test_len := 10000000
start := time.Now()
s := make([]int, test_len, test_len)
for i := 0; i < test_len; i++ {
s = append(s, i)
}
fmt.Println(time.Now().Sub(start).String())

start = time.Now()
s1 := make([]int, test_len)
for i := 0; i < test_len; i++ {
s1[i] = i
}
fmt.Println(time.Now().Sub(start).String())
}
132.123121ms
27.453897ms

4 总结

问题一来自一家公司 , 侧重于语言特性;问题二三来自另外一家公司 ,侧重于解决问题的思路;本人更喜欢第二种,很有启发性。 我之后会把其他自己认为比较有趣的编程任务,整理到此篇文章中,敬请期待。

Last Updated 2017-10-18 Wed 14:50.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)