Wayfair Labs全程面经

oneshot 发表于 2015-12-23 05:40
嗯啊哈哈，恭喜拿到MS哈！square加油哇！~~~

谢谢呢~~~  
以下是8个字。。。

oneshot 发表于 2015-12-23 04:08
那道题time complexity average 是O(n), space complexity O(1).

同问，楼主是咋实现的O(n)解法啊

额，不好意思，仔细一想我写的那个in place的方法time complexity 差不多是O(n^2),就是遇到负数就一直往前移，直到最前面或者遇到前面的数也是负数。

那我们算法一样, 最后随机挑数那道题楼主你是面试中被问到了吗？你用的就是Reservoir sampling Algorithm吗？谢谢楼主～～

oneshot 发表于 2015-12-23 08:18
额，不好意思，仔细一想我写的那个in place的方法time complexity 差不多是O(n^2),就是遇到负数就一直往前 ...

哦，那就是类似bubble sort

yjtwm 发表于 2015-12-23 08:37
那我们算法一样, 最后随机挑数那道题楼主你是面试中被问到了吗？你用的就是Reservoir sampling Algorithm吗 ...

我的算法是每次random出0到m的一个数，然后把这个数和下标为m的数换一下，下次random一个0到m-1的数

yjtwm 发表于 2015-12-23 08:37
那我们算法一样, 最后随机挑数那道题楼主你是面试中被问到了吗？你用的就是Reservoir sampling Algorithm吗 ...

你的那个取样的算法具体怎么实现啊

https://en.wikipedia.org/wiki/Reservoir_sampling
第一个算法，你也是最近要面吗？

nevermor 发表于 2015-12-23 08:52
你的那个取样的算法具体怎么实现啊

https://en.wikipedia.org/wiki/Reservoir_sampling
第一个算法，你也是最近要面吗？

nevermor 发表于 2015-12-23 08:52
我的算法是每次random出0到m的一个数，然后把这个数和下标为m的数换一下，下次random一个0到m-1的数

你这样是完全随机的吗？照你这样取得话第一个int一定会被取到的吧，还是我理解错了