南京|小米|外包|云服务工程师|二面

一面的面经在这里

算法

• 输出给定字符串的全排列，不考虑重复字符。输入：abc，输出：[abc, acb, bca, bac, cab, cba]

  点击查看答案

  思路一：使用递归，求给定字符串的全排列，就是求除了第一个字符以外其他字符串的全排列，然后把第一个字符依次插在其他全排列的每一个可能的位置。

  main.go

  package main
  
  import (
  	"fmt"
  )
  
  // 输出字符串的全排列
  func FullPermutation(input string) []string {
  	// 支持任意字符，不止是 ASCII
  	chars := []rune(input)
  	n := len(chars)
  	if n == 0 {
  		return []string{}
  	}
  	if n == 1 {
  		return []string{input}
  	}
  
  	var result []string
  	for _, f := range FullPermutation(string(chars[1:])) {
  		charsF := []rune(f)
  		// 对于每一个 f，有 len(charsF)+1 种不同的插入位置
  		for i := 0; i <= len(charsF); i++ {
  			var temp []rune
  			temp = append(temp, charsF[:i]...)
  			temp = append(temp, chars[0])
  			temp = append(temp, charsF[i:]...)
  			result = append(result, string(temp))
  		}
  	}
  
  	return result
  }
  
  func main() {
  	input := "abc"
  	fmt.Println(FullPermutation(input))
  	input = "我爱你"
  	fmt.Println(FullPermutation(input))
  }

  思路二：使用回溯法，用一个布尔数组标记字符是否已被使用，通过回溯生成所有排列。

  main.go

  package main
  
  import "fmt"
  
  func FullPermutation(input string) []string {
  	chars := []rune(input)
  	n := len(chars)
  	used := make([]bool, n)
  	var result []string
  	var path []rune
  	var backtrack func([]bool, []rune)
  	backtrack = func(used []bool, path []rune) {
  		if len(path) == n {
  			tmp := make([]rune, n)
  			copy(tmp, path)
  			result = append(result, string(tmp))
  			return
  		}
  		for i := 0; i < n; i++ {
  			if used[i] {
  				continue
  			}
  			used[i] = true
  			path = append(path, chars[i])
  			backtrack(used, path)
  			path = path[:len(path)-1]
  			used[i] = false
  		}
  	}
  
  	backtrack(used, path)
  	return result
  }
  
  func main() {
  	input := "abc"
  	fmt.Println(FullPermutation(input))
  	input = "我爱你"
  	fmt.Println(FullPermutation(input))
  }

• 以 S 形（之字形）打印二叉树，二叉树类型可以自己定义，其中的值为 int 类型

  点击查看答案

  main.go

  // 输入：
  //         3
  //      1     4
  //    3 nil  1  5
  
  // 输出：3, 4, 1, 3, 1, 5
  package main
  
  import "fmt"
  
  type TreeNode struct {
  	Val   int
  	Left  *TreeNode
  	Right *TreeNode
  }
  
  func SPrintTree(root *TreeNode) [][]int {
  	if root == nil {
  		return [][]int{}
  	}
  
  	var result [][]int
  	currentStack := []*TreeNode{root} // 当前层栈
  	nextStack := []*TreeNode{}        // 下一层栈
  	leftToRight := true               // 当前层方向，初始为从左到右
  
  	for len(currentStack) > 0 {
  		levelVals := make([]int, 0, len(currentStack))
  
  		// 遍历当前栈中的所有节点
  		for len(currentStack) > 0 {
  			node := currentStack[len(currentStack)-1]
  			currentStack = currentStack[:len(currentStack)-1]
  			levelVals = append(levelVals, node.Val)
  			// 根据方向决定子节点的入栈顺序是什么
  			if leftToRight {
  				if node.Left != nil {
  					nextStack = append(nextStack, node.Left)
  				}
  				if node.Right != nil {
  					nextStack = append(nextStack, node.Right)
  				}
  			} else {
  				if node.Right != nil {
  					nextStack = append(nextStack, node.Right)
  				}
  				if node.Left != nil {
  					nextStack = append(nextStack, node.Left)
  				}
  			}
  		}
  
  		result = append(result, levelVals)
  		// 交换当前层和下一层栈
  		currentStack, nextStack = nextStack, currentStack
  		// 反转方向
  		leftToRight = !leftToRight
  	}
  	return result
  }
  
  func PrintSTree(root *TreeNode) {
  	levels := SPrintTree(root)
  	for i, level := range levels {
  		fmt.Printf("第 %d 层: %v\n", i+1, level)
  	}
  }
  
  func main() {
  	// 输入：
  	//         3
  	//      1     4
  	//    3 nil  1  5
  	root := &TreeNode{Val: 3}
  	root.Left = &TreeNode{Val: 1}
  	root.Right = &TreeNode{Val: 4}
  	root.Left.Left = &TreeNode{Val: 3}
  	root.Right.Left = &TreeNode{Val: 1}
  	root.Right.Right = &TreeNode{Val: 5}
  	PrintSTree(root)
  }

Golang

• 线上出现 goroutine 的泄漏问题一般是怎么排查的？

• Golang 是怎么实现高并发的？

• Golang 是怎么管理内存的？怎么做垃圾回收的？

K8s

简单介绍一下 K8s 由哪些部分组成？分别是什么作用？

AI 相关

工作中有没有用过 AI 相关的工具？

Redis

Redis 大 key 问题是什么，怎么解决？

网络

https 协议是怎么保证安全性的？

项目

挑简历上的一个项目讲一讲，然后面试官会针对项目中的一些具体细节进行提问，因人而异，但主要都是针对数据库、缓存、高并发、高可用等情况进行提问。

其他

离职原因