go面试算法系列记录
面试
最近从阿里离职，开始准备面试，刷了一个月左右的leetcode,然后实践出真知，去面试了几家公司。
shopee 算法一面 螺旋矩阵，反向螺旋矩阵
描述要求
给定一个n x n的，打印出一个螺旋矩阵，比如：
输入n= 3,
输出，则打印
9 8 7 2 1 6 3 4 5
思路和解决
其实考察的是对数组的理解，还有矩阵的理解，就是找到矩阵的上下左右边界，遍历即可。反向的话，无非是从高到低遍历，正向的话，是从低到高遍历。
代码
func main() {
matrix := generateMatrix(3)
printMatrix(matrix)
}
func printMatrix(matrix [][]int) {
if matrix == nil || len(matrix) == 0 {
return
}
n := len(matrix)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
fmt.Printf("%d ", matrix[i][j])
}
fmt.Println()
}
}
func generateMatrix(n int) [][]int {
upper_bound, left_bound := 0, 0
lower_bound, right_bound := n-1, n-1
// 反向的话，number是最大值
number := n*n
var matrix = make([][]int, n)
for k := range matrix {
matrix[k] = make([]int, n)
}
for number > 0 {
if upper_bound <= lower_bound {
for j := left_bound; j <= right_bound; j++ {
number--
matrix[upper_bound][j] = number
}
upper_bound++
}
if left_bound <= right_bound {
for j := upper_bound; j <= lower_bound; j++ {
number00
matrix[j][right_bound] = number
}
right_bound--
}
if upper_bound <= lower_bound {
for j := right_bound; j >= left_bound; j-- {
number--
matrix[lower_bound][j] = number
}
lower_bound--
}
if left_bound <= right_bound {
for j := lower_bound; j >= upper_bound; j-- {
number--
matrix[j][left_bound] = number
}
left_bound++
}
}
return matrix
}
shopee 算法二面 手写LRU
描述
LRU，即Least Recently Used，最近最少使用，是一种缓存算法，它的主要目的是为了防止缓存中的数据过期，过期后就不能再使用。
实现LRU算法,O(1)的时间复杂度
思路
LRU，数据结构组成，是双向链表+map，其中双向链表是用来记录LRU的，map是用来记录key和value的。
问题一：为啥需要双向链表？
因为需要记录LRU的顺序，所以需要双向链表，map是无序的。
问题二：为啥需要map？
双向链表，增删改查，查是O(n)的，但是map的查是O(1)的，所以需要map，这里用到了空间换时间。用一个map来存储所有的双向链表的节点，这样就可以O(1)的查找。查到双向链表的节点后，则删除和插入都是O(1)的。
问题三：map 存储的是双向链表的节点，还是双向链表的节点的value？
node 是key，value，prev，next 四个元素，map存储是key， value是 &node 指针。
//below generated by github copilot
type Node struct {
key int
value int
prev *Node
next *Node
}
type LRUCache struct {
map[int]*Node
head *Node
tail *Node
capacity int
size int
}
func Constructor(capacity int) LRUCache {
return LRUCache{
map[int]*Node{},
&Node{},
&Node{},
capacity,
0,
}
}
func (this *LRUCache) Get(key int) int {
if node, ok := this.map[key]; ok {
this.remove(node)
this.add(node)
return node.value
}
return -1
}
func (this *LRUCache) Put(key int, value int) {
if node, ok := this.map[key]; ok {
this.remove(node)
node.value = value
this.add(node)
} else {
if this.size == this.capacity {
delete(this.map, this.tail.key)
this.remove(this.tail)
}
node := &Node{
key: key,
value: value,
prev: nil,
next: nil,
}
this.add(node)
this.map[key] = node
this.size++
}
}
func (this *LRUCache) remove(node *Node) {
if node.prev != nil {
node.prev.next = node.next
}
if node.next != nil {
node.next.prev = node.prev
}
if node == this.head {
this.head = node.next
}
if node == this.tail {
this.tail = node.prev
}
}
func (this *LRUCache) add(node *Node) {
node.next = this.head
node.prev = nil
if this.head != nil {
this.head.prev = node
}
this.head = node
if this.tail == nil {
this.tail = node
}
}
不知名公司1 算法一面
描述
给了两个题目，二选一，一个是快速排序，一个是实现string的parseFloat
可以使用ide
我选了个parseFloat，因为当时快速排序的题目还没有刷到 :)，所以我选了parseFloat
思路
首先，我们需要实现一个parseFloat函数，这个函数的功能是将一个string转换成float，如果转换失败，返回0.0。
float 就是有小数的了，有可能还会丢失精度，所以我们需要实现一个精度的转换，这里我是把所有的先使用int存储，然后再统一转换成小数。
同时考虑float的最大值，最小值问题。
剩下的就是通用的十进制计算了，正负号了
自己写的版本，比较简单，但是没有考虑最大值和最小值的问题，所以还是不能用了。
func parseFloat(s string) float64 {
//negtive sign
neg := false
strconv.ParseFloat(s, 0)
havePoint := false
//a number res
var res float64
var resNeg float64
negBase := 1.0
//for loop to get sign and number
for _, v := range s {
n := v - '0'
if v == '.' {
if havePoint {
return 0
}
havePoint = true
continue
}
if v == '-' {
neg = true
continue
}
if !havePoint {
if v >= '0' && v <= '9' {
res = res*10 + float64(n)
}
} else if havePoint {
f := 0.1
negBase = negBase * f
if v >= '0' && v <= '9' {
resNeg = resNeg*10 + float64(n)
}
}
}
res = res + resNeg*negBase
if neg {
res = -res
}
return res
}
//below generated by github copilot，所以人还是打不过电脑
func parseFloat(s string) float64 {
if s == "" {
return 0.0
}
var sign int
if s[0] == '+' {
sign = 1
} else if s[0] == '-' {
sign = -1
} else {
sign = 1
}
var i int
if sign == -1 {
i = 1
} else {
i = 0
}
var res float64
for ; i < len(s); i++ {
if s[i] == '.' {
break
}
if s[i] < '0' || s[i] > '9' {
return 0.0
}
res = res*10 + float64(s[i]-'0')
}
if i == len(s) {
return float64(sign)*res
}
var j int
for ; i < len(s); i++ {
if s[i] < '0' || s[i] > '9' {
return 0.0
}
res = res + float64(s[i]-'0')*math.Pow(10, float64(-j))
j++
}
return float64(sign)*res
}
不知名公司2，算法一面
描述
时间关系，两个人面，仅要求给思路，不看具体代码实现
1 LRU的实现，why ？为啥使用这些数据结构，lru的使用场景？
不再赘述
2 单链表判断回文数，不能使用其他数据结构，只能使用单链表，不能新建一个单链表。
这里有两种办法，一种是使用栈，就是用函数调用，也就是函数递归栈来解决反转的判断。
paypal 二面（全程英文面试）
描述
给定一个string，判断是回文数？
思路
没有要求，回文数很简单
//below generated by github copilot
func isPalindrome(s string) bool {
if len(s) == 0 {
return true
}
var i int
var j int
for i = 0; i < len(s)/2; i++ {
j = len(s) - i - 1
if s[i] != s[j] {
return false
}
}
return true
}
众安保险，一面
描述
使用两个goroutine交替打印1-100之间的奇数和偶数, 输出时按照从小到大输出.
思路
使用go的channel即可，本身就是一个队列，同时a b goroutine使用channel来交替获得channel的使用权，并且打印
func print100() {
var ch = make(chan int, 1)
var i = 1
ch <- i
var doneC = make(chan struct{})
go func() {
for {
if len(ch) > 0 && i%2 == 0 {
if i >= 100 {
doneC <- struct{}{}
}
fmt.Println(<-ch)
i++
ch <- i
}
}
}()
go func() {
for {
if len(ch) > 0 && i%2 != 0 {
if i >= 100 {
doneC <- struct{}{}
}
fmt.Println(<-ch)
i++
ch <- i
}
}
}()
<-doneC
}
英语流利说 一面
描述
输入：{1, 1, 2, 3, 4, 5, 6, 7, 7}, 要求两个和是8的元素个数
输出：6
要求：O(n)时间复杂度,不能使用其他数据结构存储，不能增添额外的空间
思路
双指针，一个指针从前往后，一个指针从后往前，如果两个指针相等，则两个指针向中间移动，如果不相等，则两个指针向中间移动，
同时这里有个问题，对于重复元素的计数问题，这里面1，1 7,7 是4对，而不是1对，不需要去重元素。
func count(a []int, sum int) int {
left, right := 0, len(a)-1
count := 0
for left < right {
target := a[left] + a[right]
rightCount := 1
leftCount := 1
if target == sum {
r := a[right]
l := a[left]
var pre = right - 1
for left < pre && a[pre] == r {
rightCount++
pre--
}
pre++
right = pre
var next = left + 1
for next < right && a[next] == l {
next++
leftCount++
}
left = next
count += rightCount * leftCount
rightCount = 1
leftCount = 1
} else if target > sum {
right--
} else if target < sum {
left++
}
}
return count
}
某上海不知名web3 公司 一面
描述
1 15 threeSum https://leetcode.com/problems/3sum/
2 71 Simplify Path https://leetcode.com/problems/simplify-path/
思路
都是leetcode原题
threeSum的话，可以暴力解法，加一个map的key来去重，最后遍历map。或者使用递归，先twosum，再三sum，对于重复的元素，只计算一次，控制指针往前移并且忽略重复元素
//below generated by github copilot
func threeSum(nums []int) [][]int {
var res [][]int
if len(nums) < 3 {
return res
}
sort.Ints(nums)
var i int
for i = 0; i < len(nums)-2; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
var j int
for j = i + 1; j < len(nums)-1; j++ {
if j > i+1 && nums[j] == nums[j-1] {
continue
}
var k int
for k = j + 1; k < len(nums); k++
if k > j+1 && nums[k] == nums[k-1] {
continue
}
if nums[i]+nums[j]+nums[k] == 0 {
res = append(res, []int{nums[i], nums[j], nums[k]})
}
}
}
}
return res
}
simple path 的话，其实就是数据结构要用对，我自己用了队列，结果不对，实际要用栈。
//below generated by github copilot
func simplifyPath(path string) string {
var res string
var stack []string
var i int
for i = 0; i < len(path); i++ {
if path[i] == '/' {
continue
}
if path[i] == '.' {
if i+1 < len(path) && path[i+1] == '.' {
if len(stack) > 0 {
stack = stack[:len(stack)-1]
}
i++
} else if i+1 < len(path) && path[i+1] == '/' {
i++
} else {
continue
}
} else if path[i] == '/' {
if i+1 < len(path) && path[i+1] == '/' {
i++
}
} else {
var j int
for j = i; j < len(path); j++ {
if path[j] == '/' {
break
}
}
stack = append(stack, path[i:j])
i = j - 1
}
}
if len(stack) > 0 {
res = "/" + strings.Join(stack, "/")
}
return res
}
SAP accessments
描述
全是英文，题目比较简单，easy 水平，重要的是读懂问题，很长的描述
1 数组求和
2 路灯开关问题，8个路灯，有短路问题，如果前一天左右两个都开或者关，则自己今天是开，否则其他情况是关，开 1， 关0,边界条件是最边上的两盏灯，认为他们两侧的灯都是关即可。问n天后，路灯的开关情况。
思路
比较简单，不写了
重点是英文
重点是英文
重点是英文