一亩三分地论坛

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

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

Snapchat onsite 3/24

[复制链接] |试试Instant~ |关注本帖
hzyslddm 发表于 2016-3-26 03:56:17 | 显示全部楼层 |阅读模式

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

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

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

x
第一轮.亚裔小哥自我介绍,对项目经历问得挺细的,问了实习过程中遇到过的困难有什么,详细说一个.1point3acres缃

1.给我看了一个snapchat给好友群发消息的功能,可以任意选中和删除想要投递消息的好友,并显示群发好友的list(按先后选中的顺序),设计一个数据结构,实现
toggle(String username);. visit 1point3acres.com for more.
getList();
LZ给的hashmap + doubly linked list的设计,类比LRU cache, 详细解释了一下,分析了时间复杂度。小哥说是最优解了,不coding

2.给如下结构
  class ChainSnap {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        List<ChainSnap> recipients;
        boolean hasCycle();
  }
让实现其中的hasCycle()。实际就是有向图判断有没cycle,用dfs加两个hashset判断globally visited 和 temporarily visited。 小哥问能不能不用额外的数据结构(那两个hashset),但可以把以上的class修改一下。LZ说可以加两个boolean变量在class里。小哥问了两种方法在空间消耗上的差异,然后问能不能再减少空间的开销。。后来提示说那两个变量可能的值只有几种组合,然后提示用enum类型。然后让LZ写了用enum的那种方法的代码。


午饭时间
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. more info on 1point3acres.com
第二轮.美国小哥
小哥说话挺慢的,先让自我介绍,问了why snapchat, 实习经历里面最exciting的事是啥以及实习过程中有没有不开心的事
题目问了XML parser, LZ不熟悉XML,就改成了HTML Parser, 本质上一样
输入是一个tokenizer对象,可以调用其getNextToken()函数获得下一个token, token结构包括name和tag,name就是具体的文字,tag有open,close,text三种,让把所有的token建成一棵树
比如:
       <html>
            <user>
                <id>aa</id>
                <meta>bb</meta>
            </user>
       </html>

得到的token就是
("html","open")
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷("user","open")
("id","open")
("aa","text")
("id","close")
("meta","open")
("bb","text")
("meta","close")
("user","close"). from: 1point3acres.com/bbs
("html","close")

LZ的方法是用stack来存parent, 遇到open和text建新node, 并把新node加到stack顶部node的child list里面,如果是open就把新node压栈,遇到close就pop掉stack顶端的node
写完以后小哥的follow up是如果输入的token有问题,比如close tag和open tag不匹配,如何做verification。LZ加了几行判断的code以后,小哥说他木有follow up了,于是开始聊天。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

第三轮. 两个人,主面试官有口音,但是看不出是哪里人
问了简历+why snapchat+最喜欢的feature-google 1point3acres
主要面的是unique paths I + II, 加了面试官自己的follow up, 就是如果给定的grid里面有三种情况,0能走,1不能走,2表示弹簧,可以走到2右边2格的位置,求结果
对于I, LZ直接说用dp做了,面试官表示其实直接一个公式就能算出来- -。但还是让LZ在白板上画了图,讲了思路,然后coding, 以及写test case测试
然后问LZ代码可以怎样优化让其更reliable更readable...LZ没啥概念,瞎扯了下...然后又问如果grid很大,如何encapsulate input, 依旧有点答非所问。。然后开始聊天。。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第四轮. 中国小哥
下午三轮是连着的,看到中国小哥简直热泪盈眶
问了简历+why snapchat+最喜欢的feature 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1.反对角线打印矩阵,电面面经题 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
2.给两个string判断是不是anagram.1point3acres缃
follow up, 给一个长string一个短string, 判断长string里是否存在substring和短string是anagram,要求O(n)时间,n是长string的长度
LZ用了移动窗口+hashmap存出现次数的方法,好像不是小哥想到的方法,纠结了一段时间此法是否work, 小哥想到了overfit的问题,好心提醒了一下可以在hashmap存负数,然后coding解决,闲聊了一会
*overfit指的是当前substring某个字母出现个数多于短string里面该字母的出现次数.鐣欏璁哄潧-涓浜-涓夊垎鍦

面完以后回到lobby,本来要跟hr聊天,幸好有hr出差了人手不够,这个环节就省了
每轮面试都是1个小时。上午11点让到,11点15才开始面,12点半吃饭,1点半开始下午的面试,下午连着3轮,面完还是很累的,不过面试的房间里就能看到海景,确实很漂亮
-google 1point3acres
.1point3acres缃




补充内容 (2016-3-29 01:02):
拿到offer啦!

评分

4

查看全部评分

eternity59 发表于 2016-3-27 02:55:25 | 显示全部楼层
楼主,hasCycle为什么要用两个set呢?一个不可以吗?
回复 支持 反对

使用道具 举报

eternity59 发表于 2016-3-27 03:04:06 | 显示全部楼层
楼主能具体说下第一题嘛?
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2016-3-28 06:22:27 | 显示全部楼层
eternity59 发表于 2016-3-27 02:55
楼主,hasCycle为什么要用两个set呢?一个不可以吗?

https://en.wikipedia.org/wiki/Topological_sorting
可以看一下里面DFS的那段

就是要标globally visited 和 temporarily visited, temporarily visited是标记当前搜索路径中访问过的点,globally visited是避免重复计算,不然复杂度会很高。可以做一下leetcode上的course schedule,本质上一样,都是判断图是不是DAG
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2016-3-28 06:27:29 | 显示全部楼层
eternity59 发表于 2016-3-27 03:04
楼主能具体说下第一题嘛?
. visit 1point3acres.com for more.
好友群发消息那题?
比如toggle("zhang"), toggle("Li"), getList()的结果就是"zhang", "Li",接着toggle("zhang"), getList()的结果就是"Li", 接着toggle("zhang"), getList()的结果是"Li","Zhang" 这样
回复 支持 反对

使用道具 举报

endeavorchan 发表于 2016-3-28 08:34:33 | 显示全部楼层
楼主你好,请问 onsite 时候 写code的环境是什么(是在网站上写  像hackerrank这种)?   还是随便自己(比如在自己terminal里面run)。谢谢
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2016-3-29 01:01:14 | 显示全部楼层
endeavorchan 发表于 2016-3-28 08:34. visit 1point3acres.com for more.
楼主你好,请问 onsite 时候 写code的环境是什么(是在网站上写  像hackerrank这种)?   还是随便自己(比 ...

自己带电脑,ide什么的随意
回复 支持 反对

使用道具 举报

eternity59 发表于 2016-3-29 01:53:15 | 显示全部楼层
hzyslddm 发表于 2016-3-28 06:27
好友群发消息那题?
比如toggle("zhang"), toggle("Li"), getList()的结果就是"zhang", "Li",接着toggl ...
. 1point3acres.com/bbs
楼主拿到offer了吗?那如果第一题是楼主这样描述的,一个set不就搞定了吗?LRU的想法是什么呢?
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2016-3-29 02:20:19 | 显示全部楼层
eternity59 发表于 2016-3-29 01:53. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
楼主拿到offer了吗?那如果第一题是楼主这样描述的,一个set不就搞定了吗?LRU的想法是什么呢?

拿到offer了~~要记录选中的顺序,getList()的时候要顺序输出
回复 支持 反对

使用道具 举报

LT89 发表于 2016-3-29 02:45:57 | 显示全部楼层
eternity59 发表于 2016-3-28 09:53
楼主拿到offer了吗?那如果第一题是楼主这样描述的,一个set不就搞定了吗?LRU的想法是什么呢?

按照加入的顺序排序吧,微信群也是这样要求的
回复 支持 反对

使用道具 举报

eternity59 发表于 2016-3-29 04:16:08 | 显示全部楼层
hzyslddm 发表于 2016-3-29 02:20. more info on 1point3acres.com
拿到offer了~~要记录选中的顺序,getList()的时候要顺序输出

恭喜楼主!是不是得把所有的题答出来才能过啊TT,感觉好虚啊,我明天面试!
还有楼主,请问除了题答的好,还有什么要注意的吗?.1point3acres缃
谢谢!
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2016-3-29 05:07:54 | 显示全部楼层
eternity59 发表于 2016-3-29 04:16
恭喜楼主!是不是得把所有的题答出来才能过啊TT,感觉好虚啊,我明天面试!
还有楼主,请问除了题答的好 ...

放轻松,面试官都挺nice的,我当时面之前也挺虚的,面试的时候就好好想就行了,题不难,碰到面经的概率很大
回复 支持 反对

使用道具 举报

kemeng1314 发表于 2016-3-29 06:24:31 | 显示全部楼层
楼主您好,按照第一题的思路我写了下面这个数据结构,但不知道getList这个api合不合适,目前我是没次都要从frontUser开始遍历加进去。而且doublelinkedlist这里面的优势主要是在toggle成false的时候有用处吧。谢谢!希望您提些建议!

public class UserCache {
   
    int capacity = 0;
    Map<String,User> map = new HashMap<>();
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    User firstUser=null;. From 1point 3acres bbs
    User endUser=null;
   
     class User {
        
        String username;
        boolean toggle;
        ...
        User prev;
        User next;
        
        public User(int name,boolean toggle) {
            this.username = name;
            this.toggle = true;
        }
        
     }
    . From 1point 3acres bbs
   
     public SnapCache(int capacity) {
        this.capacity = capacity;
     }
   
   
      
      public void setEnd(User newUser) {
      
          newUser.next = null;
         
          if (endUser!=null) {
             newUser.prev = endUser;
          }
         
          endUser = newUser;. visit 1point3acres.com for more.
         
          if (frontUser==null) frontUser = newUser;
      
      }
      
      public void updateList(User oldUser) {
      
           User preUser = oldUser.prev;
           User nextUser = oldUser.next;
           
           if (preUser!=null) {
              preUser.next = nextUser;
           } else frontUser = nextUser;
      . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
           if (nextUser!=null) {. visit 1point3acres.com for more.
              nextUser.prev = preUser;
           } else endUser = preUser;
      
      }
      
      public void toggle(String username) {
          if (!map.containsKey(username)) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
             User newUser = new User(username,true);
             map.put(username,newUser);
             setEnd(newUser);
             return;
          }
         
          User oldUser = map.get(username);
          updateList(oldUser);
          map.remove(username);
         
      }.鏈枃鍘熷垱鑷1point3acres璁哄潧
      
      public List<User> getList() {
         
         List<User> userList = new LinkedList<User>();
         User tmp = frontUser;
         while (tmp!=null) {
            userList.add(tmp);
            tmp = tmp.next;
         }.1point3acres缃
         
         return userList;
      }.鐣欏璁哄潧-涓浜-涓夊垎鍦
      
  
}
回复 支持 反对

使用道具 举报

eternity59 发表于 2016-3-29 07:14:06 | 显示全部楼层
hzyslddm 发表于 2016-3-29 05:07.鏈枃鍘熷垱鑷1point3acres璁哄潧
放轻松,面试官都挺nice的,我当时面之前也挺虚的,面试的时候就好好想就行了,题不难,碰到面经的概率很 ...

楼主求加微信,关于整个面试的具体流程还想咨询你下!
回复 支持 反对

使用道具 举报

hedayue 发表于 2016-3-30 04:43:54 | 显示全部楼层
hzyslddm 发表于 2016-3-28 06:27
好友群发消息那题?
比如toggle("zhang"), toggle("Li"), getList()的结果就是"zhang", "Li",接着toggl ...

所以每次能够显示的数量是有限的吗?比如你举得例子中,每次getlist只能get2个,多出的就会删除?
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2016-3-30 05:38:29 | 显示全部楼层
hedayue 发表于 2016-3-30 04:43
所以每次能够显示的数量是有限的吗?比如你举得例子中,每次getlist只能get2个,多出的就会删除?

数量没有限制,所有选中的都要输出,按选中的顺序,我举的例子只是想说如果一个用户被选中后被取消,之后又被选中,是重新加到队尾的,而不是在原来的位置
回复 支持 反对

使用道具 举报

kemeng1314 发表于 2016-3-30 09:40:13 | 显示全部楼层
hzyslddm 发表于 2016-3-28 06:22. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
https://en.wikipedia.org/wiki/Topological_sorting
可以看一下里面DFS的那段

想问一下hasCycle()的含义是要判断是否存在经过该chainSnap node的环吗,还是整个图判断有cycle。如果是后者的话,不明白为什么要单独设计一个方法放在node中。
回复 支持 反对

使用道具 举报

hedayue 发表于 2016-3-30 12:46:41 | 显示全部楼层
hzyslddm 发表于 2016-3-30 05:38
数量没有限制,所有选中的都要输出,按选中的顺序,我举的例子只是想说如果一个用户被选中后被取消,之后 ...

懂了 谢谢楼主~  还想请问下PARSE XML那个题 对END是怎么处理的 需要新建Node嘛?最后的输出是string 还是Tree Root呢?
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2016-3-30 14:05:41 | 显示全部楼层
hedayue 发表于 2016-3-30 12:46
懂了 谢谢楼主~  还想请问下PARSE XML那个题 对END是怎么处理的 需要新建Node嘛?最后的输出是string 还 ...
. 1point3acres.com/bbs
遇到close的token,只要把stack顶端的node pop掉就好了,相当于回溯了一层
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2016-3-30 14:08:47 | 显示全部楼层
kemeng1314 发表于 2016-3-30 09:40
想问一下hasCycle()的含义是要判断是否存在经过该chainSnap node的环吗,还是整个图判断有cycle。如果 ...

他当时给的background里面说的是传到chainSnap node最多N层范围内没有cycle,后来实现的时候又改了要求,变成判断图有没有cycle了,只是class的定义没有改掉,确实看起来有点奇怪
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 22:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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