3.15 一面(50min)
自我介绍+概念题
英文介绍(对着稿子说着说着发现截图掉了最后两段,草草收尾,逐渐紧张。。。)
介绍一下你的一个项目吧
面试官:我更希望听你从设计模式方面来讲你的项目,但你更多的是讲的算法相关的是吧,不过没关系
设计模式还有了解?
介绍一下死锁吧
C++的虚函数了解吗?virtual?多态了解吗?
【此时心想,咋这么多概念题,,我以为上来微软就算法呢。。】
那问道数学题吧,小学时候我们学过,能被三整除的数字有一个性质,就是各位的和加起来能被三整除,为什么?能证明一下吗?(讲得比较好吧,面试官说很好,然后就发链接写代码了)
算法题(给了一个在线编辑的网页链接写代码)
1. 给一个字符串,仅由空格和单词组成,只要不是空格就是单词的一部分,把单词的顺序全部反转,并保留原来的两个单词之间的空格长度。比如:" Nice to meet you! \0" -> " you! meet to Nice \0"
(题很简单,肯定是O(n)解决。但是面试官考察的更多是在问能不能优化性能(常数级别),比如要求传入的是一个char *,直接在原串的空间上把答案存进去。)(然而我为了写的顺手用了一堆string)
(还好第一题手速比较快,面试官又给了道题,不然写代码部分就惨了)
2. 给两个数组表示rank的分数,比如[6, 3, 5], [8, 4, 6]这两个,每一个代表给每个下标的page的一个打分,但是最终结果不关心打分的分数,只关心这一组page里的排名大小是否相同。写一个函数判断这两个数组代表的排名是否相同。
(问了一下要求O(n)吗?面试官说那至少有一个排序的复杂度吧。直接不想神仙离散化操作,直接开数组sort。。两个数组分别存一下val和idx后sort,然后判断两个数组的idx是否相同)
(思路没问题,问能否优化?答只sort一个数组根据idx判断另一个序列的val是否递增的,面试官说对的)
感想
写完第二道题,面试官说后面也没有别的场次面试了,和我多聊一聊吧,然后就问了些情况之类的。
当时面完觉得算法题太简单了,没展示出什么优势,然后八股答得又比较一般,结果聊到最后还蛮愉快的,感觉面试官人很随和,顺利通过一面。
3.19 二面(45min)
介绍
用英文介绍一个你做的项目吧(当时现说的,有些磕磕绊绊)
CCF-CSP是什么?CCPC是什么?
算法题(共享屏幕写代码)
题面:给一个字符串,找到其中最长的回文子串(teams里发的文字描述,还有几点别的要求,能想到的最优复杂度,测试尽量完备的测试数据等)
当时看到就有点慌(平时字符串做得比较少),,说,我知道最优解是的manacher,但是我可能忘记了几个关键点,现场可能手写不出来。面试官说没事,他面试几百人可能现场能写的也没几个,你写你能想到的最好算法就行了。
我当时纠结了一会儿,没什么思路,感觉除了马拉车肯定都是的,面试官说,你可以写dp啊。
我又想了很久,觉得dp的复杂度似乎都没有暴力扫一遍优秀啊,如果有二维那肯定是起步,状态看着也有点小儿科。于是说我可能还是打算写暴力吧。
然后就开始写,我直接想到的暴力就是插入分隔符后扫一遍中心扩展,一边写一边在说我的思路。【面试官直接打断说,你确定你有认真读题吗?请发挥出最好水平,写出你能想到的最优复杂度的解法。】我那会儿就很慌了,说我可能dp想不到很好的定义状态的方法,没有马拉车那步关键的优化复杂度肯定是的。
于是我还是接着写中心扩展,一边写一边试图解释我的思路,【面试官再次打断,说你安静写你的好了,时间也不多了。】
写完之后,我说应该没问题了,我多出几组测试样例再试试。面试官突然说时间差不多了,你那边代码写的怎么样了?我说差不多了,我的暴力写好了。然后面试官直接说,那你还有什么问题想问我的吗?(当时心情挺复杂的,我写代码的时候看不到teams的摄像头,看他说问问题的时候似乎也在看电脑屏幕别的地方,好像完全没读我的代码之类的……)问了问题他也没回答,直接嗯嗯了两句说,你现在大三是吧?以后机会还多,拜拜。
感想
终面的体验真的很糟糕,感觉面试官后半段都不愿意理我,也不看我的代码也不听我说话,有种拳头打在棉花上的感觉,可能这就是Lead面吧(苦笑)重温了一下manacher发现当时距离正解就差一个maxRight的点拨。当时百思不得其解,难道有O(n)的dp解法我不知道吗。。
后来和同学复盘,发现LC上题解的dp就是,且空间也是
,那么复杂度其实是劣于中心扩展法的,而我把中心扩展称为“暴力”,可能面试官当时以为我说的是
的暴力,就完全不想听我的思路了。。思考了一下,感觉这次最主要是吃亏在了自己知道自己的算法不够优秀,就说了是暴力,下次得先说,“我有一个
的算法”了。。
但是面完到现在心里还是很难受,有种很强的挫败感。感觉自己很不被尊重吧,没有在面试时间里进行有效沟通就被否决了。后半段也仿佛是在和空气说话,代码不读也不保存,就草草结束了。感觉和之前看到的微软面经比起来,心理落差还是有点大。。
不过归根结底也是自己太菜了吧,如果能在说出正解是manacher后直接写出来,也没有那么多事情了。。
3.20 感谢信
结果很意料之中,但是内心很拧巴
祝大家面试好运,加油
全部评论
(15) 回帖