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:原文底下评论有非常多针对解题的讨论,建议大家看看原文哦~

原文发布于微信公众号 - Golang语言社区(Golangweb)

原文发表时间:2018-09-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

Gopher面试中的Coding

从四月份下半月开始,陆陆续续面试了几家公司,都是golang的岗位。每一次面试,侧重点都会有不同,有的会直接给过来一道试题, 然后边解题,边讲述自己的思路,然后...

4847
来自专栏CDA数据分析师

优秀程序员写代码一定会用的 11 条经验!

我已经写了20年代码了,在此期间曾与17个团队共事过,使用不同的语言做过数百个项目。

892
来自专栏ml

C++ 与设计模式学习(其一)

       记得曾经一年前,听到同学再说设计模式,当时觉得不怎么重要,所以就没有去系统的学习,这一放,就是一年,直到前段时间,面试了一个阿里巴巴的职位,要我谈...

4237
来自专栏编程

邪恶的编码魔咒,你中招没?

关键时刻,第一时间送达! 自从我观看了Gary Bernhardt所推崇的视频以后,就对某些编程语言的怪异表现着迷了。一些编程语言比其他语言有更多令人感到意外的...

1857
来自专栏游戏杂谈

两道函数式编程题

Winter出的题,有些我也答不上来,题目难度并不是很高,但还考的比较深入。例如:

1142
来自专栏Java Web

Java 8——行为参数化

前言 《Java8实战》不得不说是一本好书,捧起来看起来就兴奋得不想放下,其中介绍的函数式编程实在是太令人兴奋了,不仅仅大大提高了代码的可读性,而且提高了代码的...

4527
来自专栏大数据挖掘DT机器学习

新手学python 如何求职拿offer?

从八月底开始找工作,短短的一星期多一些,面试了9家公司,拿到5份Offer,可能是因为我所面试的公司都是些创业性的公司吧,不过还是感触良多,因为学习Python...

5006
来自专栏Java技术栈

告别狗屎代码,请记住这 11 条编码秘诀!

我已经写了20年代码了,在此期间曾与17个团队共事过,使用不同的语言做过数百个项目。

1491
来自专栏PPV课数据科学社区

是学习Java还是Python?一张图告诉你!

Java 和 Python 一直都是两种很火很强大的编程语言,对于刚开始起步学习编程的同学来说,会迷惑且最经常问的问题是,我该学 Java 还是 Python,...

3637
来自专栏CDA数据分析师

如何拿到半数面试公司Offer——我的Python求职之路

从八月底开始找工作,短短的一星期多一些,面试了9家公司,拿到5份Offer,可能是因为我所面试的公司都是些创业性的公司吧,不过还是感触良多,因为学习Python...

2748

扫码关注云+社区

领取腾讯云代金券