一亩三分地论坛

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

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

Snapchat LA Onsite 新鲜面经

[复制链接] |试试Instant~ |关注本帖
euv921 发表于 2016-9-2 14:31:24 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 本科 全职@Snapchat - Other - Onsite |Other在职跳槽

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

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

x
新手攒经验发帖啦。Snapchat电面记不得了,就发个onsite的吧~
1. coding: opposite gender check.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

Given a list of user pairs, return whether or not it's possible all the pairs are of opposite gender.
E.g. oppositeGender([(A, B), (A, C), (E, F), (A, C)]) should return false because if (A, B) is of opposite gender, (B, C) is of opposite gender, then (A, C) can NOT of opposite gender.

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 我的solution就是建个tree/ graph,然后BFS treverse..1point3acres缃

2. coding: encode/ decode message

Given a message, implement encode() and decode() such that:
* encode()
E.g. message is "hello world"
(1) return distinct chars -> 8
(2) sort chars by frequency -> "lohe wrd". visit 1point3acres.com for more.
(3) translate the message with the following dictionary:
"l" -> 01. 1point3acres.com/bbs
"o" -> 011
"h" -> 0111
"e" -> 01111. From 1point 3acres bbs
...
So in the example, after translation it would be "0111011110101...."
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

for this function return (1)+(2)+(3) as a string, i.e. "8lohe wrd0111011110101...."


* decode()
take in the output from encode, return the message string.


FOLLOW UP QUESTION: for encode, how to save space? e.g. (3) translation, we can store them as bits then convert every 8 bits as a char to return.


3. project deep dive + coding: bad ips match
Implement storeBadIps(): storing a list of bad ips, and isBadIp(): return whether or not a given ip is a bad ip.

* storeBadIps()
E.g. storeBadIps(["7.0.0.0/8", "10.3.0.0/16", "6.7.8.134/32"])
In the example "7.0.0.0/8", "7.0.0.0" is ip ranges from 0.0.0.0 to 255.255.255.255, "8" is how many bits from the beginning it needs to match. in this example any "7.x.x.x" would be a bad ip.
In the example "10.3.0.0/16", any "10.3.x.x" would be a bad ip.
In the example "6.7.8.134/32", only exact match "6.7.8.134" would be a bad ip.
. 鍥磋鎴戜滑@1point 3 acres
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
* isBadIp(). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
E.g. isBadIp("7.3.4.5") should return true. isBadIp("6.7.8.0") should return false.

.鏈枃鍘熷垱鑷1point3acres璁哄潧
4. project deep dive + 闲聊

. 鍥磋鎴戜滑@1point 3 acres
新手发帖,希望大家多多鼓励交流,最关键的是想多攒点经验值啦!谢谢!

评分

2

查看全部评分

 楼主| euv921 发表于 2016-9-2 15:15:52 | 显示全部楼层
wtcupup 发表于 2016-9-2 15:09
第三题的思路是什么?

思路就是,以"7.0.0.0/8"为例:
* 转化"7.0.0.0" 转化成 val = 7<<24 + 0<<16 + 0<<8 + 0
* 然后bitwise shift (32 - mask bits) 之后compare. return val >> (32 - 8) == val2 >> (32 - 8).

. Waral 鍗氬鏈夋洿澶氭枃绔,后面有优化,比如说 isBadIp() 被call很多次,怎么优化,就不多说啦,大家自己想吧 :)

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-9-2 15:09:46 | 显示全部楼层
第三题的思路是什么?
回复 支持 反对

使用道具 举报

神罗天征 发表于 2016-9-2 15:25:45 | 显示全部楼层
是不是snapchat的new grad和在职跳槽的难度等级不一样呀?
每次看有工作经验的题都比较难……还是因为我太弱了……
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-9-2 15:26:29 | 显示全部楼层
euv921 发表于 2016-9-2 15:15
思路就是,以"7.0.0.0/8"为例:
* 转化"7.0.0.0" 转化成 val = 7

这解法好赞,楼主offer稳了
回复 支持 反对

使用道具 举报

 楼主| euv921 发表于 2016-9-2 15:29:27 | 显示全部楼层
wtcupup 发表于 2016-9-2 15:26
这解法好赞,楼主offer稳了

并没有,还没有信儿,希望尽快有消息吧。。。 (哭)
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-2 21:24:53 | 显示全部楼层
第二题
encode的时候打乱了顺序,感觉decode restore不回来了吧...
以及感觉那个01串对decode没啥用啊...有前面的字符串长度和字母了为什么不直接把相关的substr下来呢
请问我是不是哪里理解错了

第三题
followup能不能用cache+trie来优化
. From 1point 3acres bbs
补充内容 (2016-9-2 21:36):
第二题似乎明白了,前面数字+decode是定义了字典,最后01串还是按照原来的字符串顺序输出的...
回复 支持 反对

使用道具 举报

xpli521 发表于 2016-9-2 21:31:43 | 显示全部楼层
楼主能解释下为什么“lohe wrd” 经过dict的translate之后变成 “0111011110101” 这个了吗?  看你给的dict的例子,应该是encode成 01 011 0111 01111。。。
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-2 21:37:54 | 显示全部楼层
xpli521 发表于 2016-9-2 21:31
楼主能解释下为什么“lohe wrd” 经过dict的translate之后变成 “0111011110101” 这个了吗?  看你给的dic ...

0111011110101... 是按输入字符串的顺序而不是字典顺序输出的
0111(h)01111(e)01(l)01(l)...
回复 支持 反对

使用道具 举报

厉害的超人 发表于 2016-9-3 10:12:49 | 显示全部楼层
euv921 发表于 2016-9-1 23:15
思路就是,以"7.0.0.0/8"为例:
* 转化"7.0.0.0" 转化成 val = 7

每次要把规则里的n个ip/cidr都比较一下么?
这个题面经里面有,就是建个trie,比如7.0.0.0/8=00000111 00000000 00000000 00000000,最多32层
回复 支持 反对

使用道具 举报

pingfanzhilu 发表于 2016-9-4 02:12:22 | 显示全部楼层
第一题的解法能再详细点吗?谢谢
回复 支持 反对

使用道具 举报

厉害的超人 发表于 2016-9-4 09:59:35 | 显示全部楼层
pingfanzhilu 发表于 2016-9-3 10:12
第一题的解法能再详细点吗?谢谢

第一题是面经题Bipartite graph,. 1point3acres.com/bbs
http://www.geeksforgeeks.org/bipartite-graph/
回复 支持 反对

使用道具 举报

alucardzhou 发表于 2016-9-9 11:16:10 | 显示全部楼层

连题目都得反复琢磨,真是题海无涯啊。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-10 01:47:17 | 显示全部楼层
厉害的超人 发表于 2016-9-3 10:12. 鍥磋鎴戜滑@1point 3 acres
每次要把规则里的n个ip/cidr都比较一下么?
这个题面经里面有,就是建个trie,比如7.0.0.0/8=00000111 0 ...

求层主能不能再细说一下Trie的解法?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 14:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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