Snapchat挂经一则

原帖地址:一亩三分地

周五刚面完的,面完感觉一般,但是内推我的小哥说面试官反馈只有一个yes,只能默默说再见了。。。

第一轮,面经题,给你一个employer类,里面有雇员name,直属boss两个成员,要你写一个函数,给ceo的object和employer1和employer2的名字,注意这里是string不是object,要你返回这两个人最近的boss。刚开始以为是lca问题,所以立马秒了。但是面试官居然说和经典lca不一样!这里假如e1是e2的直属上司,那么返回的是e1的直属上司而不是e1. 我平时用的算法针对这个还确实不太好改,改来改去都有点问题,加上传入的是string而不是employer对象,搞了很久最后也没弄出来。。。 平时刷题什么的还是要多看几种方法并且记住普遍性强的算法比较好一些。

第二轮,第一题是给你一个string和一个字典,返回可由string里的字符组成的字典单词。比如cadat, 字典是cat,dc,aaa,前两个是符合要求的,第三个不符合要求。这里顺序是无所谓的。我一开始纯用hash map做,面试官说字典非常大,于是提示了一下改用trie建字典树。 第二题则是给你若干个单词和若干个字典,返回由这些单词字符重新排序组成的word list。举个栗子,bad cat是单词,字典是dad, tac, bat, cad, 返回[[dad,tac],[bat,cad]]。单词里的字符要用完。我一开始有点懵,说先枚举,面试官提示说要用到第一题,因此就是用第一题返回的word list进行组合,找可以吧所给单词字符用光的单词组合。这一轮没有run,只是写了写,面试官说为了节省时间不用实现trie。

第三轮,面经题,后悔没有仔细想,也是没想到面试官会问这么麻烦。给你一个8*8的矩阵,一个起始点,一个终点,和k值,求从起始点到终点走k步有多少种走法。这里和我们平时刷题的搜索题不同,这里所有点都可以重复走。我愣了一小会儿,说用bfs搜k层看有多少种结果。面试官不满意时间复杂度和空间复杂度太高,要我改进,我说剪枝。面试官还是不满意,说这个其实没什么改进,然后提示下说用其他搜索可以省空间,于是就写了个dfs。然后时间久到了,面试官说你已经在找到答案的方向上了,说时间上还可以提高很多。说完这话我就觉得估计这轮也够呛了。。。吐血,我回家之后也没想到这题有啥好方法,如果没记错的话貌似面试官要求线性复杂度,这打死我也想不出来。。。

第四轮,game of life。一开始我说in place,小哥却把空间讨论到了内存的层次,说如果那bit存每一位的话,in place需要用两位,copy数组的话虽然多开一个数组但是只用一位,其实差不多。。。 我无语,没想到要说到这层次,所以就顺面试官的意写了个copy版本的。然后面试官问有没有什么办法可以优化的,我说像这个问题一般应用场景matrix应该比较空,live的点比较少,因此我可以拿哈希存live的点,然后对每个live的点和其邻居更新,再得到下一轮live点的hash表。小哥说你这个想法我很喜欢,然后聊了点其他的就没了,提前十五分钟结束了面试。

其实面完还不知道是怎样,以为还行,问了内推的小哥之后才知道面的其实不行呐。。。 准备了好多面经题,认真写过代码的一个都没问。。。哎没办法,个人实力还是不足,继续努力吧。

各种求人品。。。
.鐣欏璁哄潧-涓憨-涓夊垎鍦/span>

补充内容 (2015-12-7 03:01):
第一题描述不对 class里的成员是直属下属而不是boss sorry了大家。。。