Gopher面试中的Coding

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

交替打印数字和字母

问题描述

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

解题思路

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

实际编码

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 ，这样就导致了死锁。

随机抽奖

问题描述

用户随机抽奖，数据结构如下所示：

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

解决思路

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

实际编码

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

权重抽奖

问题描述

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

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

解决思路

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

实际编码

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

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

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 的顺序居然是被随机化的，代码示例如下：

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 中可查看完整代码):

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 中可查看完整代码):

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), 代码如下：

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
}

总结

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

最后编辑于：2017.12.10 04:28:15

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,456评论 5赞 477
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,370评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,337评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,583评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,596评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,572评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,936评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,595评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,850评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,601评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,685评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,371评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,951评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,934评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,167评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 43,636评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,411评论 2赞 342

Gopher面试中的Coding

交替打印数字和字母

问题描述

解题思路

实际编码

随机抽奖

问题描述

解决思路

实际编码

权重抽奖

问题描述

解决思路

实际编码

总结

推荐阅读更多精彩内容