go面试算法系列记录
面试
最近从阿里离职,开始准备面试,刷了一个月左右的leetcode,然后实践出真知,去面试了几家公司。
shopee 算法一面 螺旋矩阵,反向螺旋矩阵
描述要求
给定一个n x n的,打印出一个螺旋矩阵,比如:
输入n= 3,
输出,则打印
9 8 7 2 1 6 3 4 5
思路和解决
其实考察的是对数组的理解,还有矩阵的理解,就是找到矩阵的上下左右边界,遍历即可。反向的话,无非是从高到低遍历,正向的话,是从低到高遍历。
代码
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 指针。
不知名公司1 算法一面
描述
给了两个题目,二选一,一个是快速排序,一个是实现string的parseFloat
可以使用ide
我选了个parseFloat,因为当时快速排序的题目还没有刷到 :),所以我选了parseFloat
思路
首先,我们需要实现一个parseFloat函数,这个函数的功能是将一个string转换成float,如果转换失败,返回0.0。
float 就是有小数的了,有可能还会丢失精度,所以我们需要实现一个精度的转换,这里我是把所有的先使用int存储,然后再统一转换成小数。
同时考虑float的最大值,最小值问题。
剩下的就是通用的十进制计算了,正负号了
自己写的版本,比较简单,但是没有考虑最大值和最小值的问题,所以还是不能用了。
不知名公司2,算法一面
描述
时间关系,两个人面,仅要求给思路,不看具体代码实现
1 LRU的实现,why ?为啥使用这些数据结构,lru的使用场景?
不再赘述
2 单链表判断回文数,不能使用其他数据结构,只能使用单链表,不能新建一个单链表。
这里有两种办法,一种是使用栈,就是用函数调用,也就是函数递归栈来解决反转的判断。
paypal 二面(全程英文面试)
描述
给定一个string,判断是回文数?
思路
没有要求,回文数很简单
众安保险,一面
描述
使用两个goroutine交替打印1-100之间的奇数和偶数, 输出时按照从小到大输出.
思路
使用go的channel即可,本身就是一个队列,同时a b goroutine使用channel来交替获得channel的使用权,并且打印
英语流利说 一面
描述
输入:{1, 1, 2, 3, 4, 5, 6, 7, 7}, 要求两个和是8的元素个数
输出:6
要求:O(n)时间复杂度,不能使用其他数据结构存储,不能增添额外的空间
思路
双指针,一个指针从前往后,一个指针从后往前,如果两个指针相等,则两个指针向中间移动,如果不相等,则两个指针向中间移动,
同时这里有个问题,对于重复元素的计数问题,这里面1,1 7,7 是4对,而不是1对,不需要去重元素。
某上海不知名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,对于重复的元素,只计算一次,控制指针往前移并且忽略重复元素
simple path 的话,其实就是数据结构要用对,我自己用了队列,结果不对,实际要用栈。
SAP accessments
描述
全是英文,题目比较简单,easy 水平,重要的是读懂问题,很长的描述
1 数组求和
2 路灯开关问题,8个路灯,有短路问题,如果前一天左右两个都开或者关,则自己今天是开,否则其他情况是关,开 1, 关0,边界条件是最边上的两盏灯,认为他们两侧的灯都是关即可。问n天后,路灯的开关情况。
思路
比较简单,不写了
重点是英文
重点是英文
重点是英文