Golang 面试题·卷四

线上测试地址：https://play.studygolang.com/

1、右图的程序的预期输出结果是10M，但结果远比其小。修改程序使其达到预期输出。（20分）

package main

import (
	"log"
	"sync/atomic"
	"time"
)

var loop = 100000
var counter int32 = 0
var complete = make(chan int, 100)

func run(k int) {
	for i := 0; i < loop; i++ {
        counter++
	}
	complete <- k
}

func main() {
	for i := 0; i < 100; i++ {
		go run(i)
	}

	for {
		if len(complete) == 100 {
			log.Printf("%v", counter)
		}
		time.Sleep(100)
	}
}

参考答案

结果：

counter++
替换为 atomic.AddInt32(&counter, 1)

2、为什么第二种方式比第一种快那么多？

package main

import (
	"fmt"
	"time"
)

func main() {
	size := 20000
	matrix1 := make([][]int, size)
	for i := 0; i < size; i++ {
		matrix1[i] = make([]int, size)
	}

	start1 := time.Now()
	// 方法1
	for i := 0; i < size; i++ {
		for j := 0; j < size; j++ {
			matrix1[i][j] = i + j
		}
	}

	fmt.Println(time.Since(start1))

	matrix2 := make([][]int, size)
	for i := 0; i < size; i++ {
		matrix2[i] = make([]int, size)
	}

	// 方法2
	start2 := time.Now()
	for i := 0; i < size; i++ {
		for j := 0; j < size; j++ {
			matrix2[j][i] = i + j
		}
	}
	fmt.Println(time.Since(start2))
}

// 1.1769527s
// 8.5584257s

参考答案

结果：

因为cpu cache 具有时间局部性和空间局部性，在方法一中访问的数据是相近的，会在cpu 缓存当中，因此会更快一点。

参考文档：

* https://www.cnblogs.com/jokerjason/p/10711022.html
* https://en.m.wikipedia.org/wiki/Cache_prefetching
* https://mp.weixin.qq.com/s/viQp36FeMZSqUoFy3VrBNw

3、给一个二叉树，实现函数判断其叶节点数值从左到右是否为等差数列。如右图所示的二叉树，其叶节点[1,3,5,7]为等差数列，返回True。

答案：

package main

import "fmt"

type Node struct {
	Val   int
	Left  *Node
	Right *Node
}

func main() {
	node9 := &Node{Val: 9, Left: &Node{Val: 3}, Right: &Node{Val: 5}}
	node6 := &Node{Val: 6, Left: &Node{Val: 1}, Right: node9}
	root := &Node{Val: 4, Left: node6, Right: &Node{Val: 7}}
	fmt.Println(isLeafAP(root))
}

func isLeafAP(root *Node) bool {
	var firstNumber, lastNumber, dValue int
	c := make(chan int)
	go RangeLeaf(root, c)
	i := 1
	for {
		v, ok := <-c
		if !ok {
			return true
		}
		if i == 1 {
			firstNumber = v
		} else if i == 2 {
			dValue = v - firstNumber
			lastNumber = v
		} else if v-lastNumber != dValue {
			return false
		}
		lastNumber = v
		i++
	}
}

func RangeLeaf(node *Node, c chan int) {
	defer close(c)
	preorderTraverse(node, c)
}

func preorderTraverse(node *Node, c chan int) {
	if node == nil {
		return
	}

	if node.Left == nil && node.Right == nil {
		c <- node.Val
		return
	}

	preorderTraverse(node.Left, c)
	preorderTraverse(node.Right, c)
}

4、以下代码输出什么？

package main

import (
	"fmt"
)

type Animal interface {
	PrintName() string
}

type Cat struct {
	Name string
}

func (a *Cat) PrintName() string {
	return ""
}

func main() {
	var c = Cat{Name: "tom"}
	var i Animal
	i = c
	fmt.Println(i.PrintName())
}

参考答案

结果：cannot use c (type Cat) as type Animal in assignment:
Cat does not implement Animal (PrintName method has pointer receiver)

原因：接口 Animal 定义 PrintName() string 方法

但是 Cat 类型没有实现 PrintName() string方法，*Cat实现了，所以 Cat并没有实现Animal。

总结：如果想继承接口，实现的方法绑定的对象一定不能是指针。
```