面试记录

面试

快仓算法岗面试

• 中午将近12点接到电话面试，直接问了项目，照着前一天晚上写的CUDA项目的文档，直接念了一遍，结果被面试官多次要求说重点，把数据传输优化的细节说了一下，然后没了；
• 午睡被HR电话叫醒，约了下午五点面试，一直以为快仓的非视觉方向算法岗是做运筹学方向的优化，下午一直在纠结数学，结果面试官扫了一眼简历，不感兴趣，全部问的传统数据结构和算法；
• 一上来问了快排和冒泡，聊了复杂度，排序算法的稳定性，然后问为什么快排会（比冒泡）快，然后面试官自己直接说了答案，因为排序算法的快慢本质上就是看比较和交换的次数，冒泡的话每次比较和交换都是在相邻的两个元素之间进行，而快排的一次交换可以减少多个逆序对（逆序对为0就是期望的有序数组），然后我自己加戏说了针对快排的优化（尾递归，选择主元的策略），结果被面试官打断，进入下一题；
• 这题是一套连击，给一个1000万大小的数组，找出最大的前100个；给一个1亿大小的数组，内存一次只能放1000万个，找出最大的前100个；第一小问之前看过（准确地说，那题是找数组中第k大的数），两种策略，一是维护一个大小为k的小顶堆（注意不是大顶堆），然后扫一遍数组，复杂度为 $O(nlogk)$ ，第二种策略是直接 $O(n)$ 建堆，然后pop $k$ 次，但是面试官强行说建堆的复杂度为 $O(nlogk)$ ，稍微说了几句，就没和他争了；然后第二小问，我本来以为是外部排序，不太会，刚说了把数组分成10组，做排序，面试官就问我，是全部排序吗，这真是一个巨大的提示，说明这题和外排没有关系了，我说只要找出