一亩三分地论坛

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

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

Snapchat面经

[复制链接] |试试Instant~ |关注本帖
pineapple1985 发表于 2016-10-5 07:43:30 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Snapchat - 内推 - 技术电面 |Other在职跳槽

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

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

x
朋友内推的位置
. 鍥磋鎴戜滑@1point 3 acres

public interface Task {
    public void execute();
    public Set<Task > getDependencies();
};
给一个vector of Task, use the given interfaces to execute all the tasks by the following rules:
// no task should be executed more than once. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
// all dependent tasks should executed first

我不熟java, 跟面试官说比较comfortable using C++. 他让我继续写C++ code, 要用到他提供的接口。我解释这题目本质就是拓扑排序。check 有没有circle,没有的话,按拓扑排序依次execute。我用的是递归,过程中记录各个task的state(unvisited 0, visiting 1, visited 2), 如果访问过,就跳过,如果在 visiting,就说明有环,throw exception,否则就改state 为visiting, 然后执行dependent的tasks,最后执行该task并修改state为 visited.

然后让我写test cases。最后让我run code来测试各个test cases。 我说java 跟 c++不兼容,然后小样让我改为C++code。 我觉得我时间不够了....

最郁闷的面试了。挂定了!
. 鍥磋鎴戜滑@1point 3 acres

评分

4

查看全部评分

本帖被以下淘专辑推荐:

ericlee27 发表于 2016-10-5 10:12:21 | 显示全部楼层
pineapple1985 发表于 2016-10-5 09:33
加油!祝一切顺顺利利

谢谢楼主,还有一件事想问,他只给了interface,那么是要我们自己写类implement这个interface还是直接调用接口就行?如果直接调用的话构造函数也不知道呀。
回复 支持 1 反对 0

使用道具 举报

shuiguo 发表于 2016-10-5 08:19:01 | 显示全部楼层
请问如何表示dependent?是输入一个树么?还是自己设计?
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-5 09:07:29 来自手机 | 显示全部楼层
啥都不说...让我自己想...自己写。我说其实可以把它dependency rephrase 有向图,把task当成图的一个node,dependent task当成邻居。但那是后话。
回复 支持 反对

使用道具 举报

ofdkk88 发表于 2016-10-5 09:11:15 | 显示全部楼层
感谢楼主分享
回复 支持 反对

使用道具 举报

ericlee27 发表于 2016-10-5 09:12:08 | 显示全部楼层
谢谢楼主,后天面~
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-5 09:33:50 | 显示全部楼层
ericlee27 发表于 2016-10-5 09:12
谢谢楼主,后天面~

加油!祝一切顺顺利利
回复 支持 反对

使用道具 举报

wcongying 发表于 2016-10-5 10:25:32 | 显示全部楼层
楼主您在简历上有写您会Java 吗?
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-5 10:39:30 来自手机 | 显示全部楼层
哦哦....有写...但是我没说熟悉,我告诉她说我比较熟悉C++.难道是这个原因?但是不是coding都是选自己喜欢的语言么?面了那么多家公司都这样哦.
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-5 10:41:07 来自手机 | 显示全部楼层
ericlee27 发表于 2016-10-5 10:12. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
谢谢楼主,还有一件事想问,他只给了interface,那么是要我们自己写类implement这个interface还是直接调 ...

原来他要code最后在hackerRank上run的。所以我认为什么都要写....
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-5 10:42:44 来自手机 | 显示全部楼层
还有,面试用视频的...我中间还断线了几次...
回复 支持 反对

使用道具 举报

wcongying 发表于 2016-10-5 10:52:02 | 显示全部楼层
pineapple1985 发表于 2016-10-5 10:39
哦哦....有写...但是我没说熟悉,我告诉她说我比较熟悉C++.难道是这个原因?但是不是coding都是选自己喜欢 ...

public Set<Task > getDependencies();,这个条件已经给了,所以当然是set啊。  我本科计算机语言的入门写当然是谭浩强的C语言,但是我在简历上不写我会C/C++。我在本科也用C#写过带界面计算器,大家都知道这个要多水有多水,所以我现在也不写我会C#.  Python有用过爬虫,我也没在简历上写我会python。简历的项目有matlab写的,但是我也没在programming写我会matlab。。。    但是我最近看到有人 argue 说能约二轮电面,期待楼主的状态更新。   最后:这道题我绝对用的是BFS,我猜面试官想让您输出 一个 甚至是 多个 可能的task的运行顺序 List。
回复 支持 反对

使用道具 举报

ericlee27 发表于 2016-10-5 11:04:38 | 显示全部楼层
wcongying 发表于 2016-10-5 10:52
public Set getDependencies();,这个条件已经给了,所以当然是set啊。  我本科计算机语言的入门写当然 ...

这个题是COURSE SCHEDULE II 只不过换了一个表述方式
回复 支持 反对

使用道具 举报

wcongying 发表于 2016-10-5 11:48:34 | 显示全部楼层
ericlee27 发表于 2016-10-5 11:04
这个题是COURSE SCHEDULE II 只不过换了一个表述方式

如果Output是可能的顺序,就是这题。  我在之前的面经看到了,而且肯定是最近90天的面经,搞不好还30天内。  我想楼主没这么背吧
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-5 12:07:52 来自手机 | 显示全部楼层
ericlee27 发表于 2016-10-5 11:04
这个题是COURSE SCHEDULE II 只不过换了一个表述方式

我也觉得是这道题的变种。就是一开始被他误导说要用他的interfaces,然后说要了C++code后让run,但是接口是java,我的code是C++,明显过不去呀。反正我已经不抱希望了。还是好好准备脸家的onsite吧。家的onsite已经fail了
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-5 12:09:20 来自手机 | 显示全部楼层
wcongying 发表于 2016-10-5 10:52
public Set getDependencies();,这个条件已经给了,所以当然是set啊。  我本科计算机语言的入门写当然 ...

我用的是DFS,就是要记录state
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-5 12:14:21 | 显示全部楼层
wcongying 发表于 2016-10-5 10:52
public Set getDependencies();,这个条件已经给了,所以当然是set啊。  我本科计算机语言的入门写当然 ...
-google 1point3acres
请问用BFS的话,怎么输出所有可能的task执行顺序呢?
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-5 12:24:30 来自手机 | 显示全部楼层
是呀。觉得是DFS. 要不然得把没有dependency的task找到,再BFS
回复 支持 反对

使用道具 举报

xietao0221 发表于 2016-10-5 12:37:19 | 显示全部楼层
BFS更直观吧,建立一个map来表示dependency,在建立一个数组来表示indegree,先把indegree为0的放入queue,然后while loop,每次poll一个,将它的邻居indegree--,如果变成0了,放入queue。poll的顺序就是答案
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-5 12:43:18 来自手机 | 显示全部楼层
嗯...也可以...这里也要特殊处理有环的情况。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 00:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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