從四月份下半月開始，陸陸續(xù)續(xù)面試了幾家公司，都是golang的崗位左驾。每一次面試，側(cè)重點都會有不同魂那，有的會直接給過來一道試題， 然后邊解題稠项，邊講述自己的思路涯雅，然后面試官根據(jù)你的思路和你交流溝通；有的呢展运，讓講述自己最近做過的項目活逆，遇到的難點精刷， 自己怎么解決的問題思路，而無獨有偶的呢划乖，這樣的面試中贬养，都要需要展示編碼能力。這篇文章就把自己最近面試中遇到的每一個編程問題琴庵， 分三步闡述出來：問題描述误算，解題思路，實際編程迷殿。
交替打印數(shù)字和字母
問題描述
使用兩個 goroutine 交替打印序列儿礼，一個 goroutinue 打印數(shù)字， 另外一個goroutine打印字母庆寺， 最終效果如下 12AB34CD56EF78GH910IJ 蚊夫。
解題思路
問題很簡單，使用 channel 來控制打印的進(jìn)度懦尝。使用兩個 channel 知纷，來分別控制數(shù)字和字母的打印序列， 數(shù)字打印完成后通過 channel 通知字母打印, 字母打印完成后通知數(shù)字打印陵霉，然后周而復(fù)始的工作琅轧。
實際編碼
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
代碼執(zhí)行結(jié)果:
12AB34CD56EF78GH910IJ
看完上面的代碼，是不是會有些疑惑踊挠，為什么
chan_c需要緩存乍桂，而chan_n不需要呢?
當(dāng)兩個打印goroutine無限交替運行時，沒有緩存是OK的效床， 但很明顯上面的示例不是睹酌，打印數(shù)字的goroutine先退出，也就沒有了goroutine來讀取chan_c中的內(nèi)容了剩檀， 而打印字母的goroutine就會阻塞在chan_c <- true憋沿，這樣就導(dǎo)致了死鎖。
隨機抽獎
問題描述
用戶隨機抽獎谨朝，數(shù)據(jù)結(jié)構(gòu)如下所示：
// map中卤妒，key代表名稱，value代表成交單數(shù)
var users map[string]int64 = map[string]int64{
"a": 10,
"b": 6,
"c": 3,
"d": 12,
"f": 1,
}
解決思路
從map中選取隨機用戶字币，拿到這個編碼問題，有點懵逼,但仔細(xì)一想共缕，只需把關(guān)注用戶的區(qū)間洗出，轉(zhuǎn)變一下數(shù)據(jù)結(jié)構(gòu)即解題。 把map轉(zhuǎn)成array图谷，思考起來就簡單多了翩活，原有問題變成了從0至n-1中選取一個數(shù)字阱洪，數(shù)字對應(yīng)的用戶即中獎用戶。
實際編碼
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
}
代碼執(zhí)行結(jié)果：
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
權(quán)重抽獎
問題描述
數(shù)據(jù)結(jié)構(gòu)和上面一致菠镇，只是問題發(fā)生變化冗荸，需要更加用戶的成單數(shù)來抽獎，用戶成單越多利耍，中獎概率越高蚌本，結(jié)構(gòu)如下所示：
// map中，key代表名稱隘梨，value代表成交單數(shù)
var users map[string]int64 = map[string]int64{
"a": 10,
"b": 6,
"c": 3,
"d": 12,
"f": 1,
}
解決思路
這一題是上一題的延伸程癌，加了訂單數(shù)進(jìn)去，做為權(quán)重來為用戶抽獎轴猎。此題和上面的問題如此的相似嵌莉，可把上面的問題， 理解成所有的用戶權(quán)重都相同的抽獎捻脖，而此題是權(quán)重不同的抽獎锐峭。解決此問題，依舊是把map轉(zhuǎn)為數(shù)組來思考可婶， 把各用戶的權(quán)重沿癞，從前到后依次拼接到數(shù)軸上，數(shù)軸的起點到終點即時中獎區(qū)間扰肌，而隨機數(shù)落到的那個用戶的區(qū)間抛寝，那個用戶即為中獎用戶。
實際編碼
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
}
代碼執(zhí)行結(jié)果：
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是可重入的钻趋，但現(xiàn)實是前后兩輪遍歷到的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 給出的 示例代碼 和 運行結(jié)果 證明了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
}
上面代碼，對于多次調(diào)用會有性能問題鳞绕，每次都要重新計算
sum_num和創(chuàng)建name_arr, 使用閉包重新實現(xiàn)失仁， 代碼如下(在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
}
上面代碼使用了閉包避免了多次抽獎時頻繁的初始化萄焦， 但每次抽獎的復(fù)雜度O(n)，很明顯依舊有可優(yōu)化的空間，可使用二分搜索來使復(fù)雜度降到
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
}
總結(jié)
問題一來自一家公司 , 側(cè)重于語言特性拂封；問題二三來自另外一家公司 茬射，側(cè)重于解決問題的思路；本人更喜歡第二種冒签，很有啟發(fā)性在抛。 我之后會把其他自己認(rèn)為比較有趣的編程任務(wù)，整理到此篇文章中萧恕，敬請期待刚梭。
