面试

最近从阿里离职，开始准备面试，刷了一个月左右的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，最近最少使用，是一种缓存算法，它的主要目的是为了防止缓存中的数据过期，过期后就不能再使用。