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天后,路灯的开关情况。
思路
比较简单,不写了
重点是英文
重点是英文
重点是英文