一亩三分地论坛

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

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

Snapchat Onsite

[复制链接] |试试Instant~ |关注本帖
yyd_yahoo 发表于 2016-1-12 03:13:16 | 显示全部楼层 |阅读模式

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

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

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

x
12月中旬面的onsite,全部是算法

第一轮,ABC小哥,给两个string的数组和一个pattern数组,判断将两个string数组分别和pattern转化后的结果是否相同。例如s1={"abc", "a", "ccc"}, s2={"bc", "aa", "d"}, pattern={1, 0},则s1和p的转化结果是"aabc",s2和p的转化结果也是是"aabc",则返回true。如果pattern是{0, 1},则转化结果分别是"abca", "bcaa",则返回false。followup是,如果给定s1和s2,判断是否存在一个pattern使得转化结果一致。 过程中要求分析算法复杂度。
.1point3acres缃
第二轮,韩国大叔,Leetcode的symmetric tree。这题我一开始上来用了最精简的方法,然后似乎大叔不太能follow,要我从最简单的BFS做一遍,然后又从DFS做一遍。现在回过头来总结,其实面试的时候不要一开始给出最优解,给出一个相对naive但是直观的解,然后逐步改进,这样可以向面试官展现你的thinking process,一上来就最优的,很多面试官都不是很喜欢的。followup就是各种DFS和BFS的tradeoff,主要是在social app的应用中。.1point3acres缃

第三轮,华人小哥,就是大家现在看到新OA(http://www.1point3acres.com/bbs/ ... read&tid=162312)。其实算法不是很复杂,按照长度和尾字幕分成bucket,然后没个bucket建trie,用trie来生成缩写。但是在讨论算法复杂度的时候我脑子犯浑了,不知道怎么搞的跟面试官为一个无所谓的复杂度讨论了半天,然后写代码的时间就所剩无几,写完了代码,面试官就问了问打算怎么测试就结束了。本轮面试官是manager,估计跪在这里了。

第四轮,华人小哥,一个矩阵表示的迷宫,1表示有障碍,0表示没有,求一条从A点到B点的路径。第一遍,我忘了写用visited matrix,所以复杂度很高,在面试官提示下,增加了visited matrix,但是时间没有多少了。followup是如果迷宫不是联通的,问怎么remove障碍,使得可以从A到B。这一轮是reverse shadow interview,感觉面我的小哥比我还紧张,各种交流不顺,写完代码后问我是想向他问问题,还是做个follow up,我问能不能介绍一下你的工作,结果他说,看来你不是很有兴趣问问题,那我来问你followup吧。。。心中万匹cnm飞过。。。唉,感觉如果面试遇到reverse shadow,就自认倒霉吧。。。

第二天收到的结果,悲剧。。。第一个onsite面试,感觉失败也很正常,现在面了几个onsite之后回过头来想想这次的onsite,觉得当时太缺少经验了,面试还是有很多技巧的,并不是想得出最优算法就一定会面的好,感觉最好的模式是能够跟面试官慢慢交流,逐步导出最后的解答,即便最后的答案不是最优的也不要紧,重要的是在这个过程当中可以向面试官展现你自己方方面面的能力,而且可以避免很多不必要的麻烦。

关于snapchat公司再多说两句,感觉这个公司目前几乎是个纯前端的公司,后端基本上都包给google了(这也是为什么前段时间google的cloud service挂了,导致snapchat直接也挂了),比较适合喜欢做前端的同学。.鐣欏璁哄潧-涓浜-涓夊垎鍦

最近还有其他面试,发个面经希望对大家有帮助,也为自己赞rp,求大米

评分

5

查看全部评分

 楼主| yyd_yahoo 发表于 2016-1-13 01:46:18 | 显示全部楼层
第一题的意思是,pattern里的值,就是s1和s2的index,把对应index的string拿出来拼成一个长string看看是不是相等,多给几个例子吧.鏈枃鍘熷垱鑷1point3acres璁哄潧

s1: ["abc", "a", "cc"]
s2: ["bc", "aa", "c"]

如果输入pattern是[1,0], 则根据s1可以导出"a"+"abc" -> "aabc",根据s2可以导出"aa"+"bc" -> "aabc",结果相同。. From 1point 3acres bbs
如果输入pattern是[0,1], 则根据s1可以导出"abc"+"a" -> "abca",根据s2可以导出"bc"+"aa" -> "bcaa",结果不同。

解法其实不难,如果你能根据s1和s2分别构建出一个基于pattern的iterator,那么你就直接比较两个iterator是否hasNext(),以及next()的值是是否相等。

followup的解法其实很直接,你先从index 0开始,然后比较对应的字符串是否一个是另一个的前缀,如果不是就去下一个index,如果是,则去短的对应的list里面找prefix匹配长的suffix,如果找到了,就比较两边各自拼接后的结果,直到形成一个完全一致的结果位置(可能有pattern长度的限制,时间太久我记不太清了)。
回复 支持 1 反对 0

使用道具 举报

aiweiwei 发表于 2016-1-12 04:09:05 | 显示全部楼层
楼主你好,内推你的大神能帮我也内推一下吗
回复 支持 反对

使用道具 举报

mooc 发表于 2016-1-12 07:24:46 | 显示全部楼层
lz,第一题啥意思啊?木有看懂啊~
回复 支持 反对

使用道具 举报

qiamoe 发表于 2016-1-12 11:03:06 | 显示全部楼层
求问lz第一题怎么写的
回复 支持 反对

使用道具 举报

Iancss 发表于 2016-1-12 11:06:20 | 显示全部楼层
楼主,求解第一题,不是很理解题意,麻烦了
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-1-19 12:06:47 | 显示全部楼层
yyd_yahoo 发表于 2016-1-13 01:46. From 1point 3acres bbs
第一题的意思是,pattern里的值,就是s1和s2的index,把对应index的string拿出来拼成一个长string看看是不 ...
.1point3acres缃
楼楼,第一题followup想法很直接,但是貌似实现起来挺复杂啊?lz有代码参考吗,谢谢!
回复 支持 反对

使用道具 举报

manjusaka077 发表于 2016-1-26 00:52:38 | 显示全部楼层
话说Reverse shadow interview是什么意思啊- -我的第二轮和你第四轮题一样,小哥全程扑克脸。。。慌了半天
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-1-26 12:28:28 | 显示全部楼层
求问: 第三轮怎么搞? 照长度和尾字幕分成bucket,然后没个bucket建trie,用trie来生成缩写
回复 支持 反对

使用道具 举报

qiamoe 发表于 2016-1-26 13:23:03 | 显示全部楼层
guixi107 发表于 2016-1-26 12:28
求问: 第三轮怎么搞? 照长度和尾字幕分成bucket,然后没个bucket建trie,用trie来生成缩写

. more info on 1point3acres.com只要trie就可以了啊,每个trie node记录一下该node下面有几个词,找的时候找到count为1就返回

补充内容 (2016-1-26 13:23):
等会。。我傻逼了我以为回的是我那个面经贴,无视我
回复 支持 反对

使用道具 举报

say543 发表于 2016-1-26 13:59:01 | 显示全部楼层
LZ 感谢分享第四轮的题目   虽然不是求最短的   但是感觉BFS的复杂度还是优于DFS    至于follow 除了DFS有别的方法可以解吗?
回复 支持 反对

使用道具 举报

Gianluigi 发表于 2016-1-28 09:04:55 | 显示全部楼层
请问lz,第一题的follow up,要找的 pattern 一定是只有两个 index 吗?就是一定是每个 vector<string> 各取两个 string 来拼吗?
回复 支持 反对

使用道具 举报

syftalent 发表于 2016-2-15 08:39:10 | 显示全部楼层
各位大神 求问第一题如何处理这种情况? s1 = {"aa", "a"}  s2 = {"a" ,"aaaaaa"} 这个是有patten的 而我代码的逻辑 s1 = {"aa"}  s2 = {"a" }就死循环了会一直找下去。 求问怎么解决这种情况?
回复 支持 反对

使用道具 举报

lzk031 发表于 2016-4-12 16:06:40 | 显示全部楼层
试着写了下第一题的代码,测试了几个case,感觉应该差不多。找prefix可以用trie树快速锁定包含prefix的word而不用每次都遍历array,但是代码实在太复杂了。。。
[/code]
import java.util.*;
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
public class StringPattern {.1point3acres缃
        private String SEP = ",";
       
        public static void main(String[] args) {
                String[] words1 = {"abc", "a", "cc"};
                String[] words2 = {"bc", "aa", "c"};
                StringPattern sp = new StringPattern();
                System.out.println(sp.hasPattern(words1, words2));
        }
       
       
        public boolean hasPattern(String[] words1, String[] words2) {
                int len = Math.min(words1.length, words2.length);
                Map<Integer, Set<String>> map = new HashMap<Integer, Set<String>>();
                for (int i=0; i<len; i++) map.put(i, new HashSet<String>());. Waral 鍗氬鏈夋洿澶氭枃绔,
                for (int i=0; i<len; i++) {
                        if (helper(words1, words2, words1, words2, i, map)) return true;
                }
                return false;
        }
       
       
        private boolean helper(String[] words1, String[] words2, String s1, String s2, int pos, Map<Integer, Set<String>> map) {
                if (map.get(pos).contains(""+s1.length()+SEP+s2.length())) return false;
                map.get(pos).add(""+s1.length()+SEP+s2.length());. Waral 鍗氬鏈夋洿澶氭枃绔,
                int i=0;
                int j=0;
. 1point 3acres 璁哄潧                int len = Math.min(words1.length, words2.length);
                for (; i<s1.length() && j<s2.length(); i++, j++) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                        if (s1.charAt(i) != s2.charAt(j)) break;
                }
                if (i!=s1.length() && j!=s2.length()) return false;
                if (i == s1.length() && j == s2.length()) return true;
                if (i < s1.length()) {
                        String prefix = s1.substring(i);
                        for (int index=0; index<len; index++) {
                                if (words2[index].startsWith(prefix)) {
                                        if (helper(words1, words2, words1[index], words2[index].substring(prefix.length()), index, map))
                                                return true;
                                }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        }
                } else {
                        String prefix = s2.substring(j);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        for (int index=0; index<len; index++) {
                                if (words1[index].startsWith(prefix)) {
                                        if (helper(words1, words2, words1[index].substring(prefix.length()), words2[index], index, map))
                                                return true;
                                }
                        }
                }
                return false;
        }
}-google 1point3acres
[/code]
回复 支持 反对

使用道具 举报

TsengJuiWang 发表于 2016-4-28 03:52:28 | 显示全部楼层
say543 发表于 2016-1-26 13:59
LZ 感谢分享第四轮的题目   虽然不是求最短的   但是感觉BFS的复杂度还是优于DFS    至于follow 除了DFS有 ...

请问DFS做follow up啥思路?Backtracking吗?
回复 支持 反对

使用道具 举报

rasperrypie 发表于 2016-7-31 06:05:47 | 显示全部楼层
LZ,第一题的pattern index可以重复吗
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-30 08:00:14 | 显示全部楼层
第一轮的复杂度怎么分析? 感觉是NP啊
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-11-14 10:39:39 | 显示全部楼层
请问一下第四题FOLLOW UP还能讲讲吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 12:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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