【面经】Facebook, Snapchat, Uber, Linkedin实习面经， 回报地里~

楼主请问一下扫地机器人那道题怎么做，以及getRandomChar()是怎么实现O（1）的？谢谢！

同问扫地机器人啊。。。

求问楼主是如何得到snapchat和uber的实习面试的，内推/校招/海投？而且snapchat的实习在网上没看到有可以投的地方。。

扫地机器人就是leetcode 54 spiral matrix的变形吧？解法应该是一样的

不对不太一样。。任意起点的话，先跑去一个角然后按spiral matrix开始遍历？感觉还有更效率的办法

Badger96 发表于 2016-10-20 13:51
不对不太一样。。任意起点的话，先跑去一个角然后按spiral matrix开始遍历？感觉还有更效率的办法

其实我就是按照spiral matrix那样做的，这个题比较tricky的地方在于遍历第一条边的长度,可以是m也可以是n我觉得

Badger96 发表于 2016-10-20 13:42
求问楼主是如何得到snapchat和uber的实习面试的，内推/校招/海投？而且snapchat的实习在网上没看到有可以投 ...

我是校招投的，楼主是Waterloo的必须要找winter intern，公司的engineer会来学校面试这样

小飞侠我去 发表于 2016-10-20 08:13
楼主请问一下扫地机器人那道题怎么做，以及getRandomChar()是怎么实现O（1）的？谢谢！

getRandomChar()这个我是用arraylist解决的，a 3就把三个a放在array里面。因为字母的顺序并不重要，所以可以用arraylist。不过对于同样characterupdate概率这种状况，我们可以用一个hashmap+arraylist，多添变少就去掉。添很简单，直接加在后面。去掉的话直接删除是O(n)。所以还是可以借助顺序不重要这个特征，把最后的一些element replace到需要删掉的elements那里，这样就可以保证O(1)

这个删除方法跟GetRandom() O(1)那个leetcode题很像

MicX 发表于 2016-10-20 08:01
snapchat放intern岗位出来了吗？job page没看到0.0

我是走的校招，没有官网申请~