Snapchat挂经

第一次onsite，发个面经攒RP

电面：聊天＋minimum window substring

onsite：
onsite四轮，每轮都是聊天＋coding。面试官会介绍自己的组和工作，然后让你介绍自己＋讲一个project。聊完天后做题。做题我的流程都是，先说自己的思路，然后解法。这时候面试官可能会跟你讨论，或者让你直接写。总之交流很重要。

1. number removal：给一个数组，元素是0-9的int，remove掉其中n个数，使剩下的数在原顺序的情况下最小。e.g. 7129，去掉两个数字，最小为12。 57294，去掉两个数字，剩下的最小为294。复杂度 O(length + n)。
follow up: 如果其中有一个负数怎么办？这里你需要跟面试官cl

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

site，感觉面得还不错，第二天收到拒信。还是有些表现不好的地方。比如第二轮不该写出bug，然后调很久，以至于没有follow up的时间。第三轮跟面试官交流得不太好，感觉面得有点累，脑子不转，这一轮再积极点说不定就把follow up写完了。

最后，个人觉得去Snapchat工作成长的话会很不错，就是LA这个地方有点偏。旁边就是海滩，好多好多好多肌肉男帅哥，没去有点可惜。攒RPRPRPRPRPRPRP～

lzzhang07 发表于 2016-8-23 00:46
楼主这个number removal怎么做到O(length + n)的？我觉得需要每次找min，用heap的话应该是O(length*lg(n)) ...

用贪心，从左往右扫，遇到左边的数比右边小时，remove左边大的数。
e.g.， 57294，删掉3个数
扫到5，这是第一个数，不做什么
扫到7，7比5大，不做什么
扫到2，2比7小，删掉7，现在数变成了 5294，2比5大，删掉5，数变成了294，2变成了第一个数
扫到9，9比2大，不做什么
扫到4，4比9小，删掉9，数变成了24

所以最后答案是24，数据结构的话，可以用stack

pawprinter 发表于 2016-10-2 03:00
remove 3个数，那么前4个数里面最小的是1，remove了两个 还需要remove 1个，57里面最小的是5，取5，78里 ...

嗯嗯，我理解你的意思了，是这个解法？
http://www.geeksforgeeks.org/bui ... rom-a-given-number/

其实这个解法跟我的解法本质上一样。

你的做法：每次找最小的一个数，取最小数，然后递归是只考虑这个最小数后面的数 ＝ 删掉所有这个最小数前面的数。这个做法的复杂度跟怎么找这个最小数有关。最坏的情况是递增序列，12345，每次你都会取第一个数，所以。如果是n个数删m个，用heap是O((n-m)logm) or O(nlogm)。如果是每次扫m个数找最小数，就是O((n-m)*m) or O(n*m)。如果是贪心最坏是O(n)

只是运气差了点，来战TOC

楼主这个number removal怎么做到O(length + n)的？我觉得需要每次找min，用heap的话应该是O(length*lg(n))啊。谢谢！

楼主IP filter具体是问什么? 有原题吗，谢谢。

rasperrypie 发表于 2016-8-23 01:17
用贪心，从左往右扫，遇到左边的数比右边小时，remove左边大的数。
e.g.， 57294，删掉3个数
扫到5，这 ...

楼主，这题要求去掉n个数。比如57294，要求去掉2个数，是不是在扫描的时候，去掉了前面的5和7这两个数之后，就直接终止扫描了？

是......................

谎言之躯 发表于 2016-8-23 01:47
楼主，这题要求去掉n个数。比如57294，要求去掉2个数，是不是在扫描的时候，去掉了前面的5和7这两个数之 ...

是的。。。。。。。。。。

prodigalr 发表于 2016-8-23 01:38
楼主IP filter具体是问什么? 有原题吗，谢谢。

比如 rules = {"7.0.0.0/8", "208.130.28.0/22", "7.7.0.0/16"};
每个ip地址都是二进制的32位数，7.0.0.0/8 表示7.0.0.0的前八位。208.130.28.0/22表示208.130.28.0的前22位。7.7.0.0/16表示7.7.0.0的前16位。

ip 7.1.1.1符合7.0.0.0/8，因为7.1.1.1的前八位是7。

肌肉男 哈哈哈哈