面试

最近从阿里离职,开始准备面试,刷了一个月左右的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天后,路灯的开关情况。

思路

比较简单,不写了

重点是英文

重点是英文

重点是英文