一亩三分地论坛

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

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

报个snapchat挂经

[复制链接] |试试Instant~ |关注本帖
TR07 发表于 2016-1-15 00:07:37 | 显示全部楼层 |阅读模式

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

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

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

x
都是面经里的题,感觉他家最近正在扩招,好好准备的话还是有机会。希望对大家有帮助。
OA:valid sudoku

第一轮电面两道题:
1. find amicable numbers. 1point3acres.com/bbs
2. basic calculator,只考虑数字0-9和加减乘除
第二轮电面一道题:
game of life
follow up怎么优化,答曰把1和neighbor放进map. 鍥磋鎴戜滑@1point 3 acres

onsite四轮:
第一轮亚裔小哥:
给我看了一个snapchat给好友群发消息的功能,说是可以任意选中和删除想要投递消息的好友,并显示群发好友的list,要设计一个数据结构实现。答曰linked hash map,没要写代码. 1point 3acres 璁哄潧
第二题detect cycle in directed graph,我写了个标记node颜色的解法,小哥表示满意

第二轮美国白人:
问了下工作经历,然后一道Alien dictionary,很快写好,run 了几个test case提前结束

中午吃饭扯淡一轮,一个特别能扯的小哥带我去食堂吃的饭,途中遇到CEO和他的超模女友,在背后八卦了两句,不知道是不是挂掉的原因。。。

第三轮 国人大哥:. from: 1point3acres.com/bbs
写一个函数,返回boolean,表示任意两个snapchat好友之间是不是可以通过最多6个中间好友认识
楼主说BFS,提示说时间空间复杂度太高,改成dfs,提示说还是太高,最后楼主写了个从两头开始dfs的减法,然后两边总共限制走6步。大哥说看上去可以,但有些corner case肯定没cover到,我一时也看不出来。

第四轮 国人大哥2:
和前一个面试官同一个组的,考了一道DAG in order traversal的题。
第一问说是有一个DAG,每个node表示一个字符,总共n个node,每个node有最多两个child,但是可能有多个parent,求这个DAG中序遍历输出的String的长度是多少。
一下就懵了,记得面经里似乎看过这题,但好像也没找着答案。磕磕绊绊说了个大概,说好像加一个node,长度可能会double。。。大哥表示捉急,于是说行我告诉你是exponential (2^n)。
然后要求输出第k个node,楼主弄了个counter计数,记到第k个的时候输出字符并返回true。不过感觉不是他想要的答案。之后随便扯了两句就送我出了房间。估计挂在这一轮了。。。.1point3acres缃
. From 1point 3acres bbs
第二周收到拒信,效率挺高的。。。

评分

1

查看全部评分

gjxwin 发表于 2016-1-21 02:58:44 | 显示全部楼层
TR07 发表于 2016-1-17 12:45
我写的类似 iterative deepening depth-first search,其实搜索过程和BFS差不多。假设graph的branching f ...

请问楼主,这题用DFS的话,为什么stack里的node总数最多是O(dh)呢,怎么感觉应该是O(h)
回复 支持 2 反对 0

使用道具 举报

 楼主| TR07 发表于 2016-11-6 01:31:03 | 显示全部楼层
liurudahai 发表于 2016-11-5 14:14
关键为啥要双向DFS,双向DFS能保证搜到一条道上吗?

http://www.zhihu.com/question/21 ... 6e8d952ce9d0e620022
回复 支持 1 反对 0

使用道具 举报

haifengc 发表于 2016-1-15 02:23:30 | 显示全部楼层
是在电脑上写代码还是在白板上啊,谢谢。
回复 支持 反对

使用道具 举报

 楼主| TR07 发表于 2016-1-15 02:46:10 | 显示全部楼层
haifengc 发表于 2016-1-15 02:23
是在电脑上写代码还是在白板上啊,谢谢。

eclipse里写,有两轮要compile and run吧,另外只是写就好
回复 支持 反对

使用道具 举报

haifengc 发表于 2016-1-15 05:29:40 | 显示全部楼层
TR07 发表于 2016-1-15 02:46
eclipse里写,有两轮要compile and run吧,另外只是写就好
. From 1point 3acres bbs
恩,好,谢谢,自己带电脑吧。
回复 支持 反对

使用道具 举报

hitowings 发表于 2016-1-15 10:13:50 | 显示全部楼层
TR07 发表于 2016-1-15 02:46
eclipse里写,有两轮要compile and run吧,另外只是写就好

楼主是自己投还是找的内推啊?之前找的内推不理我  可能我背景不强吧  刚又自己投了 不知道多久会给回复呢?
回复 支持 反对

使用道具 举报

 楼主| TR07 发表于 2016-1-15 10:20:02 | 显示全部楼层
hitowings 发表于 2016-1-15 10:13
楼主是自己投还是找的内推啊?之前找的内推不理我  可能我背景不强吧  刚又自己投了 不知道多久会给回复 ...

我找的内推,找工作确实不容易,加油。
回复 支持 反对

使用道具 举报

Gianluigi 发表于 2016-1-15 13:53:14 | 显示全部楼层
lz 第四题能描述的更详细些吗?DAG 的 in order traversal 在这里是怎么定义的?
回复 支持 反对

使用道具 举报

G_cy 发表于 2016-1-15 13:59:40 | 显示全部楼层
lz真棒走到了onsite,想想我game of life第一遍写完漏了一个规则,就跪了。。。
回复 支持 反对

使用道具 举报

say543 发表于 2016-1-15 14:17:02 | 显示全部楼层
能问问game of life 怎么优化吗?
回复 支持 反对

使用道具 举报

G_cy 发表于 2016-1-15 15:21:23 | 显示全部楼层
say543 发表于 2016-1-15 14:17
能问问game of life 怎么优化吗?

优化的方法之前一个帖子有提到,而且wiki上也有解释
回复 支持 反对

使用道具 举报

Gianluigi 发表于 2016-1-17 07:10:22 | 显示全部楼层
另外,lz 第三题说的是两头 BFS 吗?两头的 DFS 是如何实现的?
回复 支持 反对

使用道具 举报

 楼主| TR07 发表于 2016-1-17 09:32:08 | 显示全部楼层
Gianluigi 发表于 2016-1-17 07:10
另外,lz 第三题说的是两头 BFS 吗?两头的 DFS 是如何实现的?

我一开始写的BFS,但面试官说太耗空间,于是把queue改成stack。
回复 支持 反对

使用道具 举报

Gianluigi 发表于 2016-1-17 10:38:45 | 显示全部楼层
TR07 发表于 2016-1-17 09:32
我一开始写的BFS,但面试官说太耗空间,于是把queue改成stack。

不太懂,从 queue 变成 stack 为啥省空间了呢?. more info on 1point3acres.com

用 stack 的是什么算法呢?
回复 支持 反对

使用道具 举报

 楼主| TR07 发表于 2016-1-17 12:45:02 | 显示全部楼层
Gianluigi 发表于 2016-1-17 10:38
不太懂,从 queue 变成 stack 为啥省空间了呢?

用 stack 的是什么算法呢?

我写的类似 iterative deepening depth-first search,其实搜索过程和BFS差不多。假设graph的branching factor是d,总共h层。做dfs时,在stack里的node总数最多可能是O(dh),而做bfs的时候在queue里面的node总数最多可能是O(d^h)。不过这题不论是dfs还是bfs都需要一个HashSet来记录visit过的node,似乎这个才是最大的开销。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Gianluigi 发表于 2016-1-17 13:43:17 | 显示全部楼层
TR07 发表于 2016-1-17 12:45
我写的类似 iterative deepening depth-first search,其实搜索过程和BFS差不多。假设graph的branching f ...

明白了,也就是用 stack 存 dfs 的路径,而不是用 recursive 的方式写 dfs,是吗?

多谢 lz 的回答。
回复 支持 反对

使用道具 举报

say543 发表于 2016-1-21 02:15:53 | 显示全部楼层
LZ能说说第四轮吗? 题目不是太懂? 不是几个node 长度就是多少吗?
回复 支持 反对

使用道具 举报

manjusaka077 发表于 2016-1-26 00:49:19 | 显示全部楼层
好羡慕见到了CEO和超模女友。。。他家唯一吸引我的地方就是这对的颜值啊!
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-11-5 13:12:25 | 显示全部楼层
Gianluigi 发表于 2016-1-17 10:38
不太懂,从 queue 变成 stack 为啥省空间了呢?. Waral 鍗氬鏈夋洿澶氭枃绔,

用 stack 的是什么算法呢?

DFS最多存K个元素吧,BFS就多了去了。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 22:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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