从四月份下半月开始,陆陆续续面试了几家公司,都是golang的岗位。每一次面试,侧重点都会有不同,有的会直接给过来一道试题, 然后边解题,边讲述自己的思路,然后面试官根据你的思路和你交流沟通;有的呢,让讲述自己最近做过的项目,遇到的难点, 自己怎么解决的问题思路,而无独有偶的呢,这样的面试中,都要需要展示编码能力。这篇文章就把自己最近面试中遇到的每一个编程问题, 分三步阐述出来:问题描述,解题思路,实际编程。
1 交替打印数字和字母
1.1 问题描述
使用两个 goroutine
交替打印序列,一个 goroutinue
打印数字,
另外一个goroutine打印字母, 最终效果如下 12AB34CD56EF78GH910IJ 。
1.2 解题思路
问题很简单,使用 channel
来控制打印的进度。使用两个 channel
,来分别控制数字和字母的打印序列,
数字打印完成后通过 channel
通知字母打印, 字母打印完成后通知数字打印,然后周而复始的工作。
1.3 实际编码
1 | runtime.GOMAXPROCS(runtime.NumCPU()) |
代码执行结果:
12AB34CD56EF78GH910IJ
看完上面的代码,是不是会有些疑惑,为什么
chan_c
需要缓存,而chan_n
不需要呢?
当两个打印goroutine
无限交替运行时,没有缓存是OK的, 但很明显上面的示例不是,打印数字的goroutine
先退出,也就失去了goroutine
来读取chan_c
中的内容了, 而打印字母的goroutine就会阻塞在chan_c <- true
这里,这样就导致了死锁。
当然无缓存版也是可以,代码如下:
1 | runtime.GOMAXPROCS(runtime.NumCPU()) |
2 随机抽奖
2.1 问题描述
用户随机抽奖,数据结构如下所示:
1 | // map中,key代表名称,value代表成交单数 |
2.2 解决思路
从map中选取随机用户,拿到这个编码问题,有点懵逼,但仔细一想,只需把关注用户的区间,转变一下数据结构即解题。 把map转成array,思考起来就简单多了,原有问题变成了从0至n-1中选取一个数字,数字对应的用户即中奖用户。
2.3 实际编码
1 | package main |
代码执行结果:
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 | // map中,key代表名称,value代表成交单数 |
3.2 解决思路
这一题是上一题的延伸,加了订单数进去,做为权重来为用户抽奖。此题和上面的问题如此的相似,可把上面的问题, 理解成所有的用户权重都相同的抽奖,而此题是权重不同的抽奖。解决此问题,依旧是把map转为数组来思考, 把各用户的权重,从前到后依次拼接到数轴上,数轴的起点到终点即时中奖区间,而随机数落到的那个用户的区间,那个用户即为中奖用户。
3.3 实际编码
1 | package main |
代码执行结果:
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 | func GetAwardUserName(users map[string]int64) (name string) { |
由于一直以为Golang的map
for range
是可重入的,但现实是前后两轮遍历到的key
的顺序居然是被随机化的, 代码示例如下:
1 | n_map := make(map[int]bool) |
91257103468 46810325791
由于map的不可重入性, 以及 liguoqinjim 给出的 示例代码 和 运行结果 证明了map的
for range
的伪随机性, 代码修改如下(在Playground 中可查看完整代码):
1 | func GetAwardUserName(users map[string]int64) (name string) { |
上面代码,对于多次调用会有性能问题,每次都要重新计算
sum_num
和创建name_arr
, 使用闭包优化实现, 代码如下(在Playground 中可查看完整代码):
1 | func GetAwardGenerator(users map[string]int64) (generator func() string) { |
上面代码使用了闭包避免了多次抽奖时频繁的初始化, 但每次抽奖的复杂度O(n),很明显依旧有可优化的空间,可使用二分搜索来使复杂度降到
O(log n)
, 代码如下:
1 | func GetAwardGenerator(users map[string]int64) (generator func() string) { |
在已知长度的情况下,应使用
array[index]=num
而避免使用array=append(array, num)
, 代码和测试如下:
1 | package main |
132.123121ms 27.453897ms
4 总结
问题一来自一家公司 , 侧重于语言特性;问题二三来自另外一家公司 ,侧重于解决问题的思路;本人更喜欢第二种,很有启发性。 我之后会把其他自己认为比较有趣的编程任务,整理到此篇文章中,敬请期待。
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)