给小孩买床垫，求个us-mattress ref code吧。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Living

给小孩买床垫，求个us-mattress ref code吧。

给小孩买床垫，求个us-mattress ref code吧。# Living

P*y2012-10-26 07:10

1 楼

一共两轮，通过LinkedIn找人内推拿到的面试。
第一轮：美国人
1. three sum，很快给了n^2的解，然后问nlogn的解，提示说用hash_map，想了一会儿
想不出来，然后就move on下一题。后来到版上问发现被忽悠了，应该不存在nlogn的解
2. 2G 大文件，RAM只有1G，怎么sort。
3. 一个image，每个pixel一个颜色。给你其中一个pixel的位置，以及一个颜色，如果
那个pixel颜色和给的一样，什么都不用做，如果不一样，就把这个pixel变成给定的颜
色，同时把他的neighbor和这个pixel原来颜色一样的也换成新的颜色，然后再
neighbor的neighbor这样下去。给了思路，没让写code，说我肯定写得出，然后就结束
了。
他家recruiter效率很高，结束后一个多小时就通知过了，安排第二轮。
第二轮昨天，一个三姐，迟到了十分钟。recruiter原来邮件里有说如果面试官十分钟
内没来，给她说一下。十分钟刚到，给recruiter发了邮件，三姐就打过来了。就开始
面了。
1. 给个时间，string格式，比如10:35，让你求时针和分针小的夹角
2. 另一种rotated array，比如 1,3,5,8,10,12,7,6,2 就是中间大，两边小，让
binary search一个数
/* 这题上面例子错了，应该是这样 1,2,3,10,9,8,7,6,5,4 就是说新的array是原来的
递增array的后面一部分反转得到的。不过上面那样也是一个很有意思的题 */
3. 找有环linked list的环的结点数，说这题之前给我说如果有做到的给她说一下，可
能前面两题写太快了，她以为我前面都做过了。其实我也没做过前面的，只是做过类似
的。这题我就给她说做过怎么确定有没有环，没有做过找环个数的，然后就让做了。说
了思路，说对的，没让写code,就接着问怎么找环的第一个结点，我说这个我做过，也
说了思路，这题就过去了。没写code
4. maximum subarray sum，leetcode原题。这题她先给了一个人的做法，问复杂度，
我看了下，说是N^3。然后问我有没有更好的方法，我就给他说了O(n)的解法，然后写
code。
这时候差不多面了半小时，三姐就不问了，让我问她问题。然后就好了。
然后一个小时后就收到recruiter的邮件说可以on site了，效率很高。
他家的题我碰到的比较传统，运气比较好，不会像网上别人的面经那种完全没思路的
面试有时候运气真的很重要。希望上面的题目对大家有帮助。

z*y2012-10-26 07:10

2 楼

人穷，不过还是可以转点伪币以表谢意。
顺便问问，有没有人买了这款＂Simmon Beautyrest Classic Tomahawk Firm＂该小孩
用的，硬度合适吗？原来想在costco买的，不过它家的firm给我的感觉还是有点软。

l*b2012-10-26 07:10

3 楼

bless

h*e2012-10-26 07:10

4 楼

看油箱

f*e2012-10-26 07:10

5 楼

bless.

【在 P*******y 的大作中提到】

: 一共两轮，通过LinkedIn找人内推拿到的面试。
: 第一轮：美国人
: 1. three sum，很快给了n^2的解，然后问nlogn的解，提示说用hash_map，想了一会儿
: 想不出来，然后就move on下一题。后来到版上问发现被忽悠了，应该不存在nlogn的解
: 2. 2G 大文件，RAM只有1G，怎么sort。
: 3. 一个image，每个pixel一个颜色。给你其中一个pixel的位置，以及一个颜色，如果
: 那个pixel颜色和给的一样，什么都不用做，如果不一样，就把这个pixel变成给定的颜
: 色，同时把他的neighbor和这个pixel原来颜色一样的也换成新的颜色，然后再
: neighbor的neighbor这样下去。给了思路，没让写code，说我肯定写得出，然后就结束
: 了。

l*12012-10-26 07:10

6 楼

我也在想给小娃买床垫，最近有DEAL吗？什么时候有DEAL呢？

A*i2012-10-26 07:10

7 楼

bless

l*12012-10-26 07:10

8 楼

我也在犹豫这款～～

x*02012-10-26 07:10

9 楼

mark

e*l2012-10-26 07:10

10 楼

Simmons用所谓individual pocket coil，小孩跳两下容易坏。建议买Sealy
Posturepedic入门级的（Sealy现在高档的也用pocket coil）。另外注意别要memory
foam，对小孩可能有毒。硬度找个本地店试一下。
US Mattress可以打电话直接讨价还价，按MSRP 60-70% off。

p*22012-10-26 07:10

11 楼

中间大两头小但是并不是sorted呀。能用bs吗？

p*22012-10-26 07:10

12 楼

貌似要两头一起搞了。

【在 p*****2 的大作中提到】

: 中间大两头小但是并不是sorted呀。能用bs吗？

f*e2012-10-26 07:10

13 楼

先用BS找最大的位置，然后对两边BS。

【在 p*****2 的大作中提到】

: 中间大两头小但是并不是sorted呀。能用bs吗？

r*62012-10-26 07:10

14 楼

谢谢分享。"同时把他的neighbor和这个pixel原来颜色一样的也换成新的颜色，然后再

P*y2012-10-26 07:10

15 楼

是sorted,从左边到高点递增，然后再递减这样。这一题安静了想了一两分钟，给了她
方法
跟传统的rotated sorted array有点像，但是判断哪边混合的哪边单调的方法不太一样

【在 p*****2 的大作中提到】

: 中间大两头小但是并不是sorted呀。能用bs吗？

P*y2012-10-26 07:10

16 楼

不用这样的，直接找中间，然后判断中间的右边那个是大是小就知道两边的情况了
然后就可以找其中一边BS

【在 f*****e 的大作中提到】

: 先用BS找最大的位置，然后对两边BS。

P*y2012-10-26 07:10

17 楼

嗯，就是做BFS，不过要mark visit过的点

【在 r*******6 的大作中提到】

: 谢谢分享。"同时把他的neighbor和这个pixel原来颜色一样的也换成新的颜色，然后再

l*i2012-10-26 07:10

18 楼

我怎么觉得不需要mark visit过的点。因为在BFS的同时，修改了点的颜色。

【在 P*******y 的大作中提到】

: 嗯，就是做BFS，不过要mark visit过的点

j*y2012-10-26 07:10

19 楼

比如是 1 2 4 0, 要搜索 0
第一次中间的数字是 2，这个时候怎么确定哪边搜索呢 ?

【在 P*******y 的大作中提到】

: 不用这样的，直接找中间，然后判断中间的右边那个是大是小就知道两边的情况了
: 然后就可以找其中一边BS

l*i2012-10-26 07:10

20 楼

你这个没法确定选择哪一半吧。

【在 P*******y 的大作中提到】

: 不用这样的，直接找中间，然后判断中间的右边那个是大是小就知道两边的情况了
: 然后就可以找其中一边BS

s*12012-10-26 07:10

21 楼

bless~
先Binary Search找最大数，再两个单调递增或递减的binary search找那个值

P*y2012-10-26 07:10

22 楼

找到2，然后看右边是4，右边比中间大，说明右边是混合的，左边是单调递增的
然后就把你的target和左边范围比较，如果在左边里，就找左边，反之，找右边
这是当时写的代码：
if(A[mid] > A[mid+1]){
if(target < A[mid] && target >= A[end])
return search(A, mid+1, end);
else
return search(A, begin, mid-1);
}else{
if(target >= A[begin] && target < A[mid])
return search(A, begin, mid-1);
else
return search(A, mid+1, end);
}

【在 j*****y 的大作中提到】

: 比如是 1 2 4 0, 要搜索 0
: 第一次中间的数字是 2，这个时候怎么确定哪边搜索呢 ?

P*y2012-10-26 07:10

23 楼

需要的，而且mark要在入队的时候，不然会有重复入队的情况发生
因为一个点可能是好几个点的neighbor

【在 l****i 的大作中提到】

: 我怎么觉得不需要mark visit过的点。因为在BFS的同时，修改了点的颜色。

j*y2012-10-26 07:10

24 楼

用你的代码跑
-1 2 4 0, target = 0 就有问题

【在 P*******y 的大作中提到】

: 找到2，然后看右边是4，右边比中间大，说明右边是混合的，左边是单调递增的
: 然后就把你的target和左边范围比较，如果在左边里，就找左边，反之，找右边
: 这是当时写的代码：
: if(A[mid] > A[mid+1]){
: if(target < A[mid] && target >= A[end])
: return search(A, mid+1, end);
: else
: return search(A, begin, mid-1);
: }else{
: if(target >= A[begin] && target < A[mid])

l*i2012-10-26 07:10

25 楼

入队之前，把点的颜色就改了，应该就不会出现重复入队了。

【在 P*******y 的大作中提到】

: 需要的，而且mark要在入队的时候，不然会有重复入队的情况发生
: 因为一个点可能是好几个点的neighbor

n*m2012-10-26 07:10

26 楼

这样有问题吧
如果target比中值小两边都有可能。

【在 P*******y 的大作中提到】

: 不用这样的，直接找中间，然后判断中间的右边那个是大是小就知道两边的情况了
: 然后就可以找其中一边BS

w*p2012-10-26 07:10

27 楼

这道题cc150上有高度类似的体。
总的来说比较合理的题。
不过电面里的任何一题， bug free 的写出来都是要功夫的。

【在 P*******y 的大作中提到】

: 嗯，就是做BFS，不过要mark visit过的点

P*y2012-10-26 07:10

28 楼

有道理，我上面举的例子有问题，原来题目的例子是这样子：
rotate之后： 1,2,3,10,9,8,7,6,5,4
rotate之前： 1,2,3,4,5,6,7,8,9,10
就是原来增序的后面一半反转后形成的的。这样子就可以用那个方法

【在 j*****y 的大作中提到】

: 用你的代码跑
: -1 2 4 0, target = 0 就有问题

P*y2012-10-26 07:10

29 楼

嗯，这个想法不错，这样可以省去mark了

【在 l****i 的大作中提到】

: 入队之前，把点的颜色就改了，应该就不会出现重复入队了。

l*b2012-10-26 07:10

30 楼

这个差距好大啊。

【在 P*******y 的大作中提到】

: 有道理，我上面举的例子有问题，原来题目的例子是这样子：
: rotate之后： 1,2,3,10,9,8,7,6,5,4
: rotate之前： 1,2,3,4,5,6,7,8,9,10
: 就是原来增序的后面一半反转后形成的的。这样子就可以用那个方法

G*A2012-10-26 07:10

31 楼

递增、递减两种情况，都调用同一个search()函数，搞不定吧？

找到2，然后看右边是4，右边比中间大，说明右边是混合的，左边是单调递增的
然后就把你的target和左边范围比较，如果在左边里，就找左边，反之，找右边
这是当时写的代码：
if(A[mid] > A[mid+1]){
if(target < A[mid] && target >= A[end])
return search(A, mid+1, end);
else
return search(A, begin, mid-1);
}else{
if(target >= A[begin] && target < A[mid])
return search(A, begin, mid-1);
else
return search(A, mid+1, end);
}

【在 P*******y 的大作中提到】

l*a2012-10-26 07:10

32 楼

第二轮第二题,跟那道rotated的做法有区别吗?
我感觉是一样的

【在 P*******y 的大作中提到】

l*a2012-10-26 07:10

33 楼

每个子问题有两种情况
1)单调递增或递减
2)跟原问题一样

【在 G****A 的大作中提到】

: 递增、递减两种情况，都调用同一个search()函数，搞不定吧？
:
: 找到2，然后看右边是4，右边比中间大，说明右边是混合的，左边是单调递增的
: 然后就把你的target和左边范围比较，如果在左边里，就找左边，反之，找右边
: 这是当时写的代码：
: if(A[mid] > A[mid+1]){
: if(target < A[mid] && target >= A[end])
: return search(A, mid+1, end);
: else
: return search(A, begin, mid-1);