Со второй половины апреля я последовательно проходил собеседования в нескольких компаниях, все из которых являются позициями в голанге. Фокус каждого интервью будет разным.Некоторые зададут вам вопрос напрямую, а затем объяснят ваши идеи при решении проблемы, а затем интервьюер будет общаться с вами в соответствии с вашими идеями.Проекты, которые вы сделали, трудности, с которыми вы столкнулись. столкнулись, собственные представления о том, как решать проблемы, и, кстати, на таком собеседовании нужно продемонстрировать свои навыки кодирования. В этой статье каждая проблема программирования, с которой я столкнулся во время моего недавнего интервью, рассматривается в три этапа: описание проблемы, идеи решения проблемы и собственно программирование.
Поочередно печатать цифры и буквы
описание проблемы
использовать дваgoroutineчередующиеся последовательности печати,goroutinueПечатайте числа, другая горутина печатает буквы, окончательный эффект выглядит следующим образом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При бесконечном чередовании без кэширования все в порядке, но, очевидно, приведенный выше пример не работает, печатая числа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,
}
Решения
Выбор случайных пользователей на карте для решения этой проблемы с кодированием немного сбивает с толку, но после тщательного размышления вам нужно только изменить структуру данных, чтобы решить проблему. О преобразовании карты в массив думать намного проще.Первоначальная задача состоит в том, чтобы выбрать число от 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,
}
Решения
Этот вопрос является продолжением предыдущего вопроса.Количество заказов добавляется в качестве веса для розыгрыша призов для пользователей. Этот вопрос настолько похож на вопрос выше, что этот вопрос можно понимать как лотерею, в которой все пользователи имеют одинаковый вес, а этот вопрос — лотерею с разным весом. Чтобы решить эту проблему, карта по-прежнему рассматривается как массив, а веса каждого пользователя сращиваются с числовой линией спереди назад, Начальная точка и конечная точка числовой строки - это интервал мгновенного выигрыша, а интервал пользователя, на который попадает случайное число, и есть этот пользователь, то есть выигравший пользователь.
фактическое кодирование
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
}
Потому что я всегда думал, что карта Голанга
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
Из-за неповторяемости карт иliguoqinjimданообразец кодаа такжерезультат операциидоказывает
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
}
Суммировать
Вопрос 1 от одной компании и фокусируется на особенностях языка; вопросы 2 и 3 от другой компании и сосредоточены на идеях решения проблем; я предпочитаю второй, который очень информативен. Я буду организовывать другие задачи по программированию, которые я считаю более интересными в этой статье в будущем, так что следите за обновлениями.