一亩三分地论坛

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

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

Snapchat 电面

[复制链接] |试试Instant~ |关注本帖
manan000 发表于 2016-3-12 14:10:00 | 显示全部楼层 |阅读模式

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

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

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

x
发个面经回报地里的各位。楼主是找人内推的,大神晚上9点多推完我HR夜里2点就发邮件约电面了,这个速度简直碉堡了。
面试时间是上午11点,面试官是个亲切的白人小哥。上来自我介绍一下,然后聊了聊家常,得知小哥原来也是在湾区工作。之后小哥问为什么想来Snapchat,楼主说我可是你们的用户,特别喜欢里面的Stories里面的Discover类别。然后小哥问楼主最喜欢哪一个频道,楼主说Tastemade,小哥说我也喜欢啊,特别喜欢几个妹子做饭。之后就开始聊楼主的工作,问了目前干什么,工作中遇到过什么挑战。楼主说自己是做网站的,前端后端都搞。小哥问楼主喜欢什么技术,楼主说AngularJS,这时候小哥又共鸣了,貌似他也是搞网页了,然后又聊了一下。

这些有的没的说完了,然后就是做题。这里还一个小插曲,小哥问我语言是不是用JS,楼主说并不我要用Java。小哥有点愣住了,说Java我不是很熟,估计看到我web的背景所以给我安排了一个用JS的面试官。
问题一个走迷宫问题。给了一个矩阵,"1"代表起点,位于左上角;"9"代表重点,位于右下角;"0"代表通路,"5"代表墙。
矩阵长得是这样
[.鐣欏璁哄潧-涓浜-涓夊垎鍦
  [1, 5, 5, 5, 5, 0],
  [0, 5, 0, 5, 5, 0],
  [0, 5, 0, 0, 0, 0],
  [0, 5, 0, 0, 5, 0],
  [0, 0, 0, 5, 0, 9]
]
设计一个算法,看看这个迷宫能不能从起点走到重点。

楼主因为面试经验少,上来突然慌神了,完全不知道从哪里下手,感觉这是一个DP的问但是又不像。楼主突然跟面试官说这个问题用DFS解决,然后小哥说好,那就写代码吧。Snapchat允许查各种资料,Google Hangout也不需要Share Screen,如果运气好貌似查到原题就可以一步登天了,不过楼主并没有去查原题。自己在草稿纸画了画走迷宫的方法,然后确定这个就是DFS问题,而且准备使用递归来实现。之后楼主开始写代码,刚开始跟小哥聊一下思路,小哥没有说话,就说我这边都看得,你自己写就好了,估计小哥是跟楼主一样安静工作的人。代码写完了就是运行,这个时候问题就来了。楼主一直做web而且用leetcode刷题不用自己搭环境,对于Java的运行不是很清楚了,包括各种头文件的引用。由于小哥也不懂Java,楼主只能自己来找错。楼主急中生智打开Eclipse查以前写的代码,发现自己"static"和"length"拼错了,实在是不应该。改了这些拼写错误以后,代码就可以运行了而且结果也正确。然后小哥说能不能打印出来路径,楼主便加入了打印的代码并且输出路径数组。小哥又把迷宫改了改,运行几次说没问题了。

本以为还有一道题,结果小哥说就这样问我还有没有什么问题。楼主问了一下选组和Training的问题,小哥简单介绍了一下。然后楼主说没问题了,小哥说你真的没问题了么,意思再跟我聊聊啊。幸好楼主之前问过一个朋友是Snapchat的资深用户,她说新消息来的时候不知道是照片还是视频,有时候上班的时候想看结果发现是视频,搞得非常尴尬。楼主把这个问题跟小哥说了,小哥说消息之前会有红框或者紫框,一个说明是照片另一个说明是视频,楼主说我不知道啊,小哥说没事这个设计也并不是很清楚,会作为用户反馈的。之后就是小哥说楼主表现还可以,HR会在一周内给消息,简单告别就挂了。面试的第二天下午楼主就收到了HR的邮件约onsite了。


总结一下,Snapchat面试我的问题并不难,楼主感觉自己发挥一般,能给onsite真的是运气不错。感觉面试的心态真的是太重要了,还是要多面才能更加从容。遇到问题以后千万不能慌,如果想不出来算法可以现在纸上画一画,看看自己如何手工实现解法,然后把自己变成机器来思考,这样就把这个解法转换成算了。千万不要把面试当做是一件特别严肃的事情,做题并不是考试,把解题当做一个解决问题的过程就可以了。

最后在扯一点题外话,楼主找工作的原因是老板要在1个月内让楼主走人。老板跟楼主说你的东西做的太慢而且同事们花了很多的时间来培训我公司需要一个更高级的工程师来提高效率,但是楼主在工作前并没有任何的web开发经验,所有东西都是后来慢慢学的,根本不可能像高级工程师一样快速完成任务。更重要的原因是楼主之前一直在跟老板沟通h1b的事情,当时签offer时老板承诺给楼主提供支持,但是现在老板突然变卦,与其被楼主问来问去所以不如让楼主直接走人。作为国际学生在美真的很不容易,没有立足以前会被各种人欺负。作为在外的中国人,我们一定要勇于争取自己的权利,自己努力去实现自己的价值。楼主现在能做的就是好好努力,争取找到一家好的公司,让老板尽情的去后悔。就算楼主没能找到新的工作,我们的背后还有日益强大的祖国,美国不带我们玩,我们自己可以玩的更好!.鏈枃鍘熷垱鑷1point3acres璁哄潧
-google 1point3acres
希望同找工作的各位亲们共勉!

评分

5

查看全部评分

 楼主| manan000 发表于 2016-3-13 08:13:08 | 显示全部楼层
jiebour 发表于 2016-3-13 03:54
恭喜楼主,楼主都不用OA?直接电面?
-google 1point3acres
是的,没有OA,电面也只有一次,可能是跟我工作了一年有关系吧
回复 支持 1 反对 0

使用道具 举报

jiebour 发表于 2016-3-13 03:54:37 | 显示全部楼层
恭喜楼主,楼主都不用OA?直接电面?
回复 支持 反对

使用道具 举报

endeavorchan 发表于 2016-3-23 12:15:21 | 显示全部楼层
我今天也店面的这题,不过起点和终点是输入的。其实大同小异。国人大哥.鏈枃鍘熷垱鑷1point3acres璁哄潧
先写了指数级的接,优化成n平方了。
. more info on 1point3acres.com
但是还出了一题, 就是墙可以打穿,问最少打穿多少墙可以到达终点。想了半天没想出来,只是说要dp,并不知道具体怎么dp. visit 1point3acres.com for more.
现在还没想明白。。。。

估计要跪
回复 支持 反对

使用道具 举报

he2004365 发表于 2016-3-23 12:26:40 | 显示全部楼层
楼主原公司是什么公司啊,这么不人性啊?
回复 支持 反对

使用道具 举报

 楼主| manan000 发表于 2016-3-23 13:31:09 | 显示全部楼层
he2004365 发表于 2016-3-23 12:26
楼主原公司是什么公司啊,这么不人性啊?

湾区某个Startup
回复 支持 反对

使用道具 举报

 楼主| manan000 发表于 2016-3-23 13:35:27 | 显示全部楼层
endeavorchan 发表于 2016-3-23 12:15
. 1point3acres.com/bbs我今天也店面的这题,不过起点和终点是输入的。其实大同小异。国人大哥
先写了指数级的接,优化成n平方了 ...

墙可以打穿这个确实比我的难多了,感觉是每打穿一面墙之后就进行一次搜索,还是BFS的意思
回复 支持 反对

使用道具 举报

endeavorchan 发表于 2016-3-24 06:07:38 | 显示全部楼层
manan000 发表于 2016-3-23 13:35. 1point 3acres 璁哄潧
墙可以打穿这个确实比我的难多了,感觉是每打穿一面墙之后就进行一次搜索,还是BFS的意思

我一开始也差不多这么想的,但是他说用dp,poly 时间就可以解。到现在都没想通怎么解
回复 支持 反对

使用道具 举报

 楼主| manan000 发表于 2016-3-24 10:39:55 | 显示全部楼层
endeavorchan 发表于 2016-3-24 06:07. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我一开始也差不多这么想的,但是他说用dp,poly 时间就可以解。到现在都没想通怎么解

好吧,现在也不用想了,等对方给消息就好。目前就是好好刷题刷面经,准备面对接下来的面试,祝好运啦~
回复 支持 反对

使用道具 举报

zoufengboy 发表于 2016-3-24 13:45:04 | 显示全部楼层
大家帮忙review一下,看看能简化不?复杂度应该是4^N (N 是点的总数)
  1. class Solution {
  2. public:
  3.         bool hasPath(vector<vector<int>>& mtx) {
  4.                 int numRow = mtx.size();
  5.                 if (numRow == 0) return false;
  6.                 int numCol = mtx[0].size();

  7.                 vector<vector<bool>> visited(numRow, vector<bool>(numCol, 0));
  8.                 int startX = 0, startY = 0;
  9.        
  10.                 bool res = 0;
  11.                 findPath(startX, startY, mtx, visited, res);
  12.                 return res;. From 1point 3acres bbs
  13.         }. more info on 1point3acres.com

  14.         void findPath(int startX, int startY, vector<vector<int>>&mtx, vector<vector<bool>>&visited, bool&res)
  15.         {
  16.                 if (res == 1) return;

  17.                 int numRow = mtx.size();
  18.                 int numCol = mtx[0].size();-google 1point3acres

  19.                 int xOffset[4] = { 0, 1, -1, 0 };
  20.                 int yOffset[4]= { 1, 0, 0, -1 };. 1point 3acres 璁哄潧

  21.                 visited[startY][startX] = 1;
  22.                 for (int idx = 0; idx < 4; idx++)
  23.                 {
  24.                         int curX = startX + xOffset[idx];. 鍥磋鎴戜滑@1point 3 acres
  25.                         int curY = startY + yOffset[idx];

  26.                         if (curX >= 0 && curX < numCol && curY >= 0 && curY < numRow)
  27.                         {
  28.                                 if (visited[curY][curX] == 0)
  29.                                 {
  30.                                         if (mtx[curY][curX] == 9) //target pos
  31.                                         {. more info on 1point3acres.com
  32.                                                 res = true;. visit 1point3acres.com for more.
  33.                                                 return;
  34.                                         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  35.                                         else if (mtx[curY][curX] == 0)
  36.                                         {
  37.                                                 findPath(curX, curY, mtx, visited, res);
  38.                                         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  39.                                 }
  40.                                
  41.                         }

  42. -google 1point3acres
  43.                 }
  44.                 visited[startY][startX] = 0;
  45.         }
  46. };
复制代码
回复 支持 反对

使用道具 举报

endeavorchan 发表于 2016-3-24 16:31:49 | 显示全部楼层
zoufengboy 发表于 2016-3-24 13:45
大家帮忙review一下,看看能简化不?复杂度应该是4^N (N 是点的总数)

应该是对的,不过这题可以达到n^2
回复 支持 反对

使用道具 举报

zoufengboy 发表于 2016-3-25 04:51:14 | 显示全部楼层
endeavorchan 发表于 2016-3-24 16:31
应该是对的,不过这题可以达到n^2

请求N^2做法,这题不能用DP吧,因为走向不一定是向下或向右
回复 支持 反对

使用道具 举报

moonprince0801 发表于 2016-3-25 12:20:35 | 显示全部楼层
打穿墙的问题可以通过一次走两步来解决吧
回复 支持 反对

使用道具 举报

 楼主| manan000 发表于 2016-3-25 13:41:33 | 显示全部楼层
moonprince0801 发表于 2016-3-25 12:20
打穿墙的问题可以通过一次走两步来解决吧

其实还是DP问题,可以这样做:从起点开始走,把能走到的点都标记成0,然后把所有阻隔的墙的位置存入一个栈或者队列;之后从这些墙的位置出发,把当前墙和从这些墙出发能走到的点标记成1,然后把继续阻隔的墙存起来;这么反复下去,直到到达终点,结果就是重点的标记值
回复 支持 反对

使用道具 举报

zoufengboy 发表于 2016-3-26 02:51:58 | 显示全部楼层
manan000 发表于 2016-3-25 13:41
其实还是DP问题,可以这样做:从起点开始走,把能走到的点都标记成0,然后把所有阻隔的墙的位置存入一个 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这不是N^2啊,有好多点要重复走啊
回复 支持 反对

使用道具 举报

endeavorchan 发表于 2016-3-26 04:29:22 | 显示全部楼层
zoufengboy 发表于 2016-3-25 04:51
请求N^2做法,这题不能用DP吧,因为走向不一定是向下或向右

把你代码第50行去掉 就是O(n^2).  当然我是这么认为的。有可能我理解有错误。 因为相当于你第二次退到那个点时候说明这个点是死路,死路就不用再考虑了。
回复 支持 反对

使用道具 举报

zoufengboy 发表于 2016-3-27 06:20:25 | 显示全部楼层
endeavorchan 发表于 2016-3-26 04:29. 1point3acres.com/bbs
把你代码第50行去掉 就是O(n^2).  当然我是这么认为的。有可能我理解有错误。 因为相当于你第二次退到那 ...

嗯,如果问题是是否存在通路,我感觉你的solution的正确的,只要找到一条就可以。或者BFS,每次用queue记录下次可以访问的周围点,如果已被访问过则不加入queue,这样也保证N^2复杂度。

如果是要输出所有路径,好像还得DFS,复杂度4^N
回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-4-17 02:34:35 | 显示全部楼层
只求通路就是DFSOn^2,打穿最少墙到达终点其实就是最短路径吧。只是这里的路径是指墙的数目而不是走了多少步,BFSO n^2应该可解
  1. static int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  2.         public static boolean findPath(int[][] board, int sr, int sc, int tr, int tc) {
  3.                 if(sr < 0 || sr >= board.length || sc < 0 || sc >= board[0].length) return false;
  4.                 if(sr == tr && sc == tc) return true;
  5.                 if(board[sr][sc] == 9 || visited[sr][sc] != 0) return false;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6.                 visited[sr][sc] = 1;
  7.                 boolean ret = false;
  8.                 for(int[] d : dirs) {
  9.                         ret = ret || findPath(board, sr + d[0], sc + d[1], tr, tc);
  10.                 }
  11.                 return ret;
  12.         }
复制代码
回复 支持 反对

使用道具 举报

sabrinalanlan 发表于 2016-10-4 02:45:01 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!
. 鍥磋鎴戜滑@1point 3 acres
想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 00:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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