一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2787|回复: 30
收起左侧

Snapchat挂经一则

[复制链接] |试试Instant~ |关注本帖
jxyfwrj 发表于 2015-12-6 14:36:59 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Snapchat - 内推 - Onsite |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

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

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

各种求人品。。。


补充内容 (2015-12-7 03:01):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一题描述不对 class里的成员是直属下属而不是boss sorry了大家。。。

评分

9

查看全部评分

kennethinsnow 发表于 2015-12-7 13:55:59 | 显示全部楼层
jxyfwrj 发表于 2015-12-6 15:23
你这样返回的依然是其中一个employee,必须要加条件判断。。。 其实这个题api给的实在是。。。蛋疼,我有 ...

改一下,如果找到一个人返回此人的上司就好了
find(node, parent, a, b){
  if (node.val == a || node.val==b) return parent;-google 1point3acres
  Node left = find(node.left, node, a, b);
  Node right = find(node.right, node, a, b);
  if ( left == null) return right;
  if (right == null) return left;
  return node;
}
  
回复 支持 1 反对 0

使用道具 举报

kennethinsnow 发表于 2015-12-7 14:09:40 | 显示全部楼层
第二题也不需要trie, 直接查每个词的字符是否都存在一个map counter里面就好,同样都是O(n) n是所有字符的数量,trie的复杂度可能还略高。
回复 支持 1 反对 0

使用道具 举报

MCwong 发表于 2015-12-6 15:01:03 | 显示全部楼层
感觉第一题应该是dfs找到两个employee, 搜索过程中维护对应的两条路径,然后返回两条路径的最后一个common manager
回复 支持 反对

使用道具 举报

 楼主| jxyfwrj 发表于 2015-12-6 15:23:49 | 显示全部楼层
MCwong 发表于 2015-12-6 15:01.鐣欏璁哄潧-涓浜-涓夊垎鍦
感觉第一题应该是dfs找到两个employee, 搜索过程中维护对应的两条路径,然后返回两条路径的最后一个common  ...

你这样返回的依然是其中一个employee,必须要加条件判断。。。 其实这个题api给的实在是。。。蛋疼,我有个简便的做法是如果e1和e2在同一直线上,我返回e1和e1的lca就是答案。但这里给的是string,着实麻烦,最后也没搞出来。。。
回复 支持 反对

使用道具 举报

MCwong 发表于 2015-12-6 15:30:57 | 显示全部楼层
jxyfwrj 发表于 2015-12-6 15:23. 1point 3acres 璁哄潧
你这样返回的依然是其中一个employee,必须要加条件判断。。。 其实这个题api给的实在是。。。蛋疼,我有 ...

记录path的时候只要记录到target employee的direct manager为止就可以了. 举个例子:
有employee A,B,C,D,E在一条直线上, target employee 分别是D, E.
D的path: CEO->A->B->C
E的path: CEO->A->B->C->D
返回最后一个commonManagerC即可
回复 支持 反对

使用道具 举报

 楼主| jxyfwrj 发表于 2015-12-6 15:37:38 | 显示全部楼层
MCwong 发表于 2015-12-6 15:30. 1point3acres.com/bbs
记录path的时候只要记录到target employee的direct manager为止就可以了. 举个例子:
有employee A,B,C,D ...

有道理。。。我看的那个做法理解的不是很好 于是融会贯通也不够好。。。
回复 支持 反对

使用道具 举报

beefcurtain5 发表于 2015-12-6 16:58:34 | 显示全部楼层
MCwong 发表于 2015-12-6 15:30
记录path的时候只要记录到target employee的direct manager为止就可以了. 举个例子:. more info on 1point3acres.com
有employee A,B,C,D ...

我觉得楼主这题, describe的不对。  employee class里面, 只有名字和direct boss, 就是说一个treenode里知道id和parent point, 不知道children。。。 从CEO, 根本就没法走DFS。。。
回复 支持 反对

使用道具 举报

ryb 发表于 2015-12-6 17:21:26 | 显示全部楼层
看到第一题深有感触。。一次电面也是遇到了LCA的题,按照Leetcode的recursion方法就给秒了, 结果面试官说公共祖先不能包含任何一个node(当时我听到的时候也是shock了一下)。。。最后也是改来改去都没改好recursion的方法。 后来想了一下感觉可以这样做,还是先求LCA,如果是LCA就是p,q中的任意一个node(说明p是q的祖先或者q是p的祖先),那么再求一下LCA的parent。。
回复 支持 反对

使用道具 举报

 楼主| jxyfwrj 发表于 2015-12-7 02:59:26 | 显示全部楼层
beefcurtain5 发表于 2015-12-6 16:58
我觉得楼主这题, describe的不对。  employee class里面, 只有名字和direct boss, 就是说一个treenode ...

噗 确实描述错了 类里面是直属下属 不是boss 我二了。。。
回复 支持 反对

使用道具 举报

 楼主| jxyfwrj 发表于 2015-12-7 03:03:19 | 显示全部楼层
beefcurtain5 发表于 2015-12-6 16:58
我觉得楼主这题, describe的不对。  employee class里面, 只有名字和direct boss, 就是说一个treenode ...
-google 1point3acres
我去。。。 对啊 先求完再确认。。。 我也没想到。。。 但是我那个方法是recursion的 这样改有点略为麻烦
回复 支持 反对

使用道具 举报

kennethinsnow 发表于 2015-12-7 14:18:49 | 显示全部楼层
第三题其实可以用dp解 dp[m][n][k]代表k步走到m,n点的走法,这里顶多记录4个值就是前一步哪里来的;.鐣欏璁哄潧-涓浜-涓夊垎鍦
最后从dp[m[n][k] backtrack回去就解出来了。复杂度是O(m*n*k + actual paths), space是O(m*n*k)
回复 支持 反对

使用道具 举报

 楼主| jxyfwrj 发表于 2015-12-7 14:39:39 | 显示全部楼层
kennethinsnow 发表于 2015-12-7 14:09 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第二题也不需要trie, 直接查每个词的字符是否都存在一个map counter里面就好,同样都是O(n) n是所有字符的 ...

我也觉得trie的复杂度高 是面试官要我用的。。。
回复 支持 反对

使用道具 举报

yyd_yahoo 发表于 2015-12-11 10:42:53 | 显示全部楼层
jxyfwrj 发表于 2015-12-7 14:39
我也觉得trie的复杂度高 是面试官要我用的。。。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Trie的话,可以省掉一些查找吧,比如有些词的prefix就不满足条件,如果用trie的话,凡是有这个prefix的词就不用查了,但是hash的话,你还是没个词都要查一遍。。。
回复 支持 反对

使用道具 举报

sevensevens 发表于 2016-1-3 18:00:59 | 显示全部楼层
yyd_yahoo 发表于 2015-12-11 10:42
Trie的话,可以省掉一些查找吧,比如有些词的prefix就不满足条件,如果用trie的话,凡是有这个prefix的词 ...

你的意思是对字典里的词建trie么
回复 支持 反对

使用道具 举报

sevensevens 发表于 2016-1-4 05:45:27 | 显示全部楼层
jxyfwrj 发表于 2015-12-7 14:39
我也觉得trie的复杂度高 是面试官要我用的。。。

楼主你好 面试官有说为啥要用trie么...感觉一次查询的话trie没降低时间啊...毕竟string的字符是可以任意顺序的...
回复 支持 反对

使用道具 举报

 楼主| jxyfwrj 发表于 2016-1-6 05:46:32 | 显示全部楼层
sevensevens 发表于 2016-1-4 05:45.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主你好 面试官有说为啥要用trie么...感觉一次查询的话trie没降低时间啊...毕竟string的字符是可以任意 ...

字典很大的情况下 用trie的内存消耗比hash map小的多
回复 支持 反对

使用道具 举报

RagingSword 发表于 2016-1-6 09:02:51 | 显示全部楼层
kennethinsnow 发表于 2015-12-7 13:55
改一下,如果找到一个人返回此人的上司就好了. 1point3acres.com/bbs
find(node, parent, a, b){
  if (node.val == a || node ...

这个想法不错
回复 支持 反对

使用道具 举报

RagingSword 发表于 2016-1-6 09:04:17 | 显示全部楼层
kennethinsnow 发表于 2015-12-7 13:55
改一下,如果找到一个人返回此人的上司就好了.鐣欏璁哄潧-涓浜-涓夊垎鍦
find(node, parent, a, b){
  if (node.val == a || node ...

应该是general tree
回复 支持 反对

使用道具 举报

RagingSword 发表于 2016-1-6 09:53:45 | 显示全部楼层
sevensevens 发表于 2016-1-4 05:45
楼主你好 面试官有说为啥要用trie么...感觉一次查询的话trie没降低时间啊...毕竟string的字符是可以任意 ...

我觉得这儿Trie 不是用来查询的,trie是用来存放最后输出结果的
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 18:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表