Golang 面试题搜集

Golang 常见面试题目解析

Golang 理论

Redis基础

MySQL相关

面试必备算法

排序算法

Owner

Minho

一个纯粹的PHPer

https://github.com/lifei6671/interview-go

Comments

第七题的第七小题解答不够到位
https://github.com/lifei6671/interview-go/blob/master/question/q007.md#7%E4%B8%8B%E9%9D%A2%E7%9A%84%E7%A8%8B%E5%BA%8F%E8%BF%90%E8%A1%8C%E5%90%8E%E4%B8%BA%E4%BB%80%E4%B9%88%E4%BC%9A%E7%88%86%E5%BC%82%E5%B8%B8

func (p *Project) run(msgchan chan interface{}) { for { defer p.deferError() go p.exec(msgchan) time.Sleep(time.Second * 2) } }

这一段错误不仅是 defer p.deferError() 没有出现在协程内部，而是无节制地在创建协程。虽然通过 time.Sleep(time.Second * 2) 限制了频率，但如果以 Main 内 time.Sleep(time.Second * 100000000000000) 如此久的等待，迟早也会因为内存占用过大而报错。
实现阻塞读的并发安全Map
package main

import ( "fmt" "time" "sync" )

type sp interface { Out(key string, val interface{}) //存入key /val，如果该key读取的goroutine挂起，则唤醒。此方法不会阻塞，时刻都可以立即执行并返回 Rd(key string, timeout time.Duration) interface{} //读取一个key，如果key不存在阻塞，等待key存在或者超时 }

type Item2 struct { value interface{} ch chan struct{} exist bool } type ConcurrentMap struct { mapval map[string]*Item2 rwmutex *sync.RWMutex }

func NewConcurrentMap() *ConcurrentMap { return &ConcurrentMap{ mapval: make(map[string]*Item2, 0), rwmutex: new(sync.RWMutex), } }

func (c *ConcurrentMap) Out(key string, val interface{}) { c.rwmutex.Lock() defer c.rwmutex.Unlock()

item, ok := c.mapval[key] if !ok { c.mapval[key] = &Item2{ value: val, exist: true, } return } item.value = val if !item.exist { if item.ch != nil { close(item.ch) item.ch = nil } } return

}

func (c *ConcurrentMap) Rd(key string, timeout time.Duration) interface{} { c.rwmutex.Lock() defer c.rwmutex.Unlock()

item, ok := c.mapval[key] if !ok { item = &Item2{ exist: false, ch: make(chan struct{}, 1), } c.mapval[key] = item } if item.exist { return item.value } select { case <-time.After(timeout): return nil case <-item.ch: } item, _ = c.mapval[key] return item.value

}

q001.md

看到前面已经有一个关于这个问题的讨论，我还是选择了开了一个新的issue谈谈我的想法。

除了使用加锁的方法，还可以使用channel来实现goroutine调度，这是一个典型的 pingpong的问题，加上一个channel接受完成通知就好。

package main

import (
	"fmt"
)

func main() {
	ping := make(chan struct{}, 1)
	pong := make(chan struct{}, 1)
	done := make(chan struct{})

	ping <- struct{}{}
	go func() {
		for i := 0; i < 10; i++ {
			<-ping
			fmt.Print(i)
			pong <- struct{}{}
		}
	}()

	go func() {
		for i := 0; i < 10; i++ {
			<-pong
			fmt.Printf("%c", 'A'+i)
			ping <- struct{}{}
		}
		done <- struct{}{}
	}()

	<-done
	close(ping)
	close(pong)
}

question/q001.md 优化

number, letter := make(chan struct{}), make(chan struct{}) letter <- struct{}{} 这种使用方式比 number, letter := make(chan bool), make(chan bool) letter <- true 更好些吧

最接近的三数之和，代码有误

` func threeSumClosest(nums []int, target int) int { if len(nums) == 3 { return nums[0] + nums[1] + nums[2] } sort.Ints(nums) sum := nums[0] + nums[1] + nums[2]

  for i := 0; i < len(nums); i++ {
	  l := i+1
	  r := len(nums) - 1
	  for l < r {
		  current := nums[i] + nums[l] + nums[r]
		  if math.Abs(float64(sum - target)) > math.Abs(float64(target - current)) {
			  sum = current
		  }
		  if current < target {
			  l++
		  } else if current == target {
			  return target
		  } else {
			  r--
		  }
	  }
  }
  return sum

}

`

读阻塞且并发安全的 Map，答案是否有问题？

https://github.com/lifei6671/interview-go/blob/63a7d02b52c3dc7c3d9fa1e8cb2b3559f8b1caad/src/q010.go#L57 https://github.com/lifei6671/interview-go/blob/63a7d02b52c3dc7c3d9fa1e8cb2b3559f8b1caad/src/q010.go#L58

这两行代码中的解锁和加锁操作并不是原子的，在 57 行解锁后，锁可能会被其他协程拿到。如果锁被一个写操作的协程拿到，就会出现刚写入的键值对又被覆盖成空的情况。

实现 Sunday 匹配 needle在最末尾的时候返回结果异常

s := "hello world abc is a test chars in program develop comm" index := strStrSunday(s, "common") fmt.Println("common index is", index) 正常应该返回-1，实际会返回54 什么的

附上根据原链接java 版本实现的一个方法：

` func strStrSunday(haystack string, needle string) int { if len(haystack) < len(needle) { return -1 }

  if haystack == needle {
	  return 0
  }

  originIndex := 0
  aimIndex := 0
  nextIndex := 0

  for aimIndex < len(needle) {
	  if originIndex > len(haystack)-1 {
		  return -1
	  }

	  if haystack[originIndex] == needle[aimIndex] {
		  originIndex++
		  aimIndex++
	  } else {
		  nextIndex = originIndex - aimIndex + len(needle)
		  if nextIndex < len(haystack) {
			  offset := strings.LastIndex(needle, string(haystack[nextIndex]))
			  if offset == -1 {
				  originIndex = nextIndex + 1
			  } else {
				  originIndex = nextIndex - offset
			  }

			  aimIndex = 0
		  } else {
			  return -1
		  }
	  }
  }

  return originIndex - aimIndex

} `

“实现阻塞读且并发安全的map”答案补充

我注意到https://github.com/lifei6671/interview-go/blob/master/question/q010.md中缺少了Rdfunc的实现，我完成了，并且经过了简单的测试。

func (m *Map) Rd(key string, timeout time.Duration) interface{} {
	e, ok := m.c[key]
	if !ok {
		// create channel
		m.c[key] = &entry{
			isExist: false,
			ch:      make(chan struct{}),
		}
	}
	// 阻塞
	e, _ = m.c[key]
	if e.ch != nil {
		select {
		case <-e.ch:
		case <-time.After(timeout):
		}
	}
	return m.c[key].value
}

冒泡排序完全是错的

冒泡排序是通过数去找位置，这里的冒泡排序写成选择排序了，附代码

func bubbleSort(arr []int) []int {
	if len(arr) == 0 {
		return arr
	}
	n := len(arr)
	for i := 0; i < n-1; i++ {
		for j := 0; j < n-1-i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
	return arr
}

第六题机器人坐标计算有问题

第六题机器人坐标计算如果命令字符串包含嵌套的命令，那么题中的代码就会有问题。举个例子，输入的命令为2(F3(B)),正确的答案是(0,-4)。然而给出的代码输出是(0,0) 正确的代码可以参考如下：

const (
	NORTH = iota
	EAST
	SOUTH
	WEST
)

type Offset struct {
	x int
	y int
}

var dirlist []Offset
var dirname []string

func init() {
	dirname = []string{"NORTH", "EAST", "SOUTH", "WEST"}
	dirlist = []Offset{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
}

func getOffset(offset Offset, sign int, x int, y int) (int, int) {
	return x + offset.x*sign, y + offset.y*sign
}

func rmove(dir int, x int, y int, start int, s string) (int, int, int, int) {

	times := 0

	i := start
	//fmt.Printf("start:%d\n", start)
	for ; i < len(s); i++ {
		ch := s[i]
		//fmt.Printf("ch:%d,", ch)
		if ch >= '0' && ch <= '9' {
			times = times*10 + int(ch-'0')
		} else if ch == '(' {
			next := 0
			for j := 0; j < times; j++ {
				x, y, dir, next = rmove(dir, x, y, i+1, s)
			}
			i = next
		} else if ch == ')' {
			break
		} else if ch == 'R' {
			dir = (dir + 1) % 4
		} else if ch == 'L' {
			dir = (dir + 3) % 4

		} else if ch == 'F' {
			x, y = getOffset(dirlist[dir], 1, x, y)

		} else if ch == 'B' {
			x, y = getOffset(dirlist[dir], -1, x, y)
		}
	}
	//fmt.Printf("s:%s,x:%d,y:%d,dir:%d,i:%d\n", s, x, y, dir, i)
	return x, y, dir, i
}

// @返回参数1: 作标
// @返回参数2：方向
func move(s string) ([]int, int) {

	dir := NORTH
	x, y, dir, _ := rmove(dir, 0, 0, 0, s)
	//fmt.Printf("dir:%s\n", dirname[dir])
	return []int{x, y}, dir
}

golang面试题集合