微软的面试分为三轮,一个下午完成,正常情况都可以面到第三面。
第一面聊了10分钟左右的学习经历和比赛经历,因为我机缘巧合之下拿到一个比赛的第三名,因此主要和面试官扯了扯这个比赛。但是,我之前很少使用DNN,面试官还是建议学一下DNN。
聊完项目,就开始做算法题:最小的K个数:这道题LeetCode和剑指Offer里都有,可惜之前没有刷到过。话说,我真的是不幸,刷了300道题,都没有碰到。这道题我当时想出来用最小堆的做法,时间复杂度为O(log(n)),空间复杂度为O(K)。
最优的做法是快速选择,时间复杂度为O(log(n)),空间复杂度为O(1)。Java里的ArrayList的插入时间复杂度:因为,ArrayList的储存是固定数组。因此,超过数组大小,需要重新申请数组,然后复制。但是,平均时间复杂度还是O(n)。
第二面求中位数:我一开始以为是LeetCode那道Hard题,我就请求换了个题。后来想想,实在是不应该。多个有序数组合并:一开始,我想到了类似的归并的方法,但是时间复杂度较高。后来,我又想到了优先队列的方法,但是没有写出完美的代码。之后,面试官又问了能不能复现优先队列,没有实现成功。
第三面将字符串中的连续空格变为1个:实际是道Easy题,用两个指针就可以完成。但是,当时脑子瓦特,没有想到,后悔啊。系统题:忘了。
...查看更多