剩女是怎样炼成的——韩军伟图片电影 zz (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Piebridge - 鹊桥

剩女是怎样炼成的——韩军伟图片电影 zz (转载)

剩女是怎样炼成的——韩军伟图片电影 zz (转载)# Piebridge - 鹊桥

S*e2010-08-23 07:08

1 楼

本月初从amazon买的，刚查了rebate status 是 Program Violation. "We could not fulfill
your rebate because your supporting information showed that your purchase
did not fulfill the terms of the program." 有经验的能说说是咋回事？

B*42010-08-23 07:08

2 楼

Amazon的电面online test挂了。很纳闷，因为我觉得题不难，当时还以为自己都做对
了呢。大家看看我哪道题做错了？
1）给一段代码，用queue实现对binary tree的遍历。问time complexity and space
complexity.
我一看，这不是BFS吗，答O(n) and O(n)。
2）一段代码，在sorted array number[]里查找某个值。代码用的递归，每次比较目标
值和number[(min+max)/2],然后根据比较结果决定是min+1或者max-1.
我看每次递归只是array index范围缩小一个。所以答O(n)。
3）有一个online server 群，要求实现3个方法：
add(serverId): 添加一个新server，
remove(serverId):去掉一个server，
get(): 随机返回一个online server ID.提示可以用Random.random(i).
并要求所有方法time complexity 必须为O(1).
我想，必须用Hashtable来实现OnlineServers。我选用serverId作为hashtable的value
。add(serverId)的时候，我定义int作为hashtable的key,数值就是加入的顺序。比如
第一台加入的就是OnlineServers.put(0,FirstServer),第二台就是OnlineServers.put
(1，SecondServer)...
这样get()实现就很方便，生成一个随机数作为key，然后调用OnlineServers.get(key)。
麻烦是remove(serverId)，因为OnlineServers.remove(key),参数不能是value。想了
比较久，决定生成一个镜像Hashtable Mirror, 每当向OnlineServers放一个(key,
value),就向Mirror里放一个(value,key)。这样，在实现remove(serverId)的时候，我
先用Mirror.get(serverId)找到对应的key,然后调用OnlineServers.remove(key)，
Mirror.remove(serverId)。
当然，我也考虑了如果serverId不存在的情况。
4）设计题，说有个网上系统存有客户资料，有100TB的数据，要求处理查询客户资料速
度是10000tps。但每台机器只能容纳10TB数据，处理速度是1000tps，问怎么设计这个
系统。
我想这不简单吗，用10台机器，并且设计一个隐射，能把customerId平均映射到10台机
器上。处理请求时，先根据customerId确定机器号，再把请求发到那台机器上。
我究竟哪些题答错了？

u*r2010-08-23 07:08

3 楼

【以下文字转载自 Love 讨论区】
发信人: usagator (usagator), 信区: Love
标题: 剩女是怎样炼成的——韩军伟图片电影 zz
发信站: BBS 未名空间站 (Mon Aug 23 16:39:16 2010, 美东)
(一）有钱没文化的，你看不上。
（二）帅气的你喜欢，人家不爱你。
（三）演艺界的，你没兴趣。
（四）劳动人民，你又看不起。
（五）市脍的，嫌俗。
（六）传统男人，不堪束缚。
（七）小男人面前，你就是女皇。
（八）父母代为相亲的，没感觉。

c*k2010-08-23 07:08

4 楼

where to check?

not fulfill

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

: 本月初从amazon买的，刚查了rebate status 是 Program Violation. "We could not fulfill
: your rebate because your supporting information showed that your purchase
: did not fulfill the terms of the program." 有经验的能说说是咋回事？

J*n2010-08-23 07:08

5 楼

第二个题目直接Binary Search不行么？

u*r2010-08-23 07:08

6 楼

（九）心理变态的，只能做姐妹。
（十）帅气潇洒的，嫌没素质。
（十一）好不容易碰上对眼的，又是个衣冠禽兽。
（十二）这么多，没一个合适的
(十三）所以，你就自己过一辈子吧。

S*e2010-08-23 07:08

7 楼

https://www.acbpromotions.com/canonrebates/

【在 c*********k 的大作中提到】

: where to check?
:
: not fulfill

l*o2010-08-23 07:08

8 楼

楼主做的是电面还是online test呀？

c*k2010-08-23 07:08

9 楼

my status:
xxxxxx Amazon Pro9000 Mk II + DSLR MIR $400.00 crystalcock
10/18/2010 -- -- Audit Completed

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

:
: https://www.acbpromotions.com/canonrebates/

k*e2010-08-23 07:08

10 楼

2是log n 折半查找

S*e2010-08-23 07:08

11 楼

打了电话，被告知要切upc时要在箱子上留个洞。rebate表上没提要留洞啊。难道要bbb
it？！

B*42010-08-23 07:08

12 楼

可能我表达不清，不是我写的代码。头两道都是给出代码，要求回答time complexity。
第二道代码写的仿佛是Binary Search，但每次递归，搜索范围只是缩小1，所以我认为
这是个陷阱，不是O(logn),应该是O(n).

【在 J*****n 的大作中提到】

: 第二个题目直接Binary Search不行么？

q*f2010-08-23 07:08

13 楼

Payment Appd
447 oved ?
没留洞啊

bbb

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

: 打了电话，被告知要切upc时要在箱子上留个洞。rebate表上没提要留洞啊。难道要bbb
: it？！

J*n2010-08-23 07:08

14 楼

第三个，hashtable的 key 因为 remove 操作已经不连续了，这时候用random，你也考
虑了不存在 key, value 的情况，那这样最差就是O(n)了吧？

h*m2010-08-23 07:08

15 楼

我刚给他们打了电话，说不用CUT出来一个洞。UPC揭下来就行。
跟他们ARGU,实在不行，你就说你刚问过BRIDGET，这个是接我电话的接线员。看他们怎么说。

B*42010-08-23 07:08

16 楼

难道电面不就是要online test吗？我刚开始在美国找工作，没有经验，这是第一家电
面。先是Amazon有人发电邮和我确认电面时间，然后有人打电话和我聊了一下简历和考
了几个概念题，就说screening过了，你做一下网上测试吧。然后就给我链接让我上网
做题去了。

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

: 楼主做的是电面还是online test呀？

b*e2010-08-23 07:08

17 楼

俺的都还查不到....

J*n2010-08-23 07:08

18 楼

第四题，如果customerID % 机器数都是映射到某几台机器，不平均分布，怎么办？如
果现在满了，再进来，就会冲垮server. 是否可以考虑队列，或者一个函数判断是否
超载，超载到下台机器，我也不太清楚实际中应该怎么设计

d*r2010-08-23 07:08

19 楼

Mine was approved.

B*42010-08-23 07:08

20 楼

考虑了不存在 key, value 的情况，那这样最差就是O(n)了吧？
你说的很对，看来这道题我栽了。你有什么好方法没有？
你再看看我别的题答得对吗？

【在 J*****n 的大作中提到】

: 第三个，hashtable的 key 因为 remove 操作已经不连续了，这时候用random，你也考
: 虑了不存在 key, value 的情况，那这样最差就是O(n)了吧？

z*02010-08-23 07:08

21 楼

mark

B*42010-08-23 07:08

22 楼

根据题意，不会有新增数据，只要处理查询请求就行了。所以找到一种平分ID的方法就
不会有数据溢出的问题。
请求的速率平均每台应该是1000tps，但繁忙时刻可能超出。我提到用排队来处理这种
情况，反正队列是不会无限增长的。

如果现在满了，再进来，就会冲垮server. 是否可以考虑队列，或者一个函数判断是
否超载，超载到下台机器，我也不太清楚实际中应该怎么设计

【在 J*****n 的大作中提到】

: 第四题，如果customerID % 机器数都是映射到某几台机器，不平均分布，怎么办？如
: 果现在满了，再进来，就会冲垮server. 是否可以考虑队列，或者一个函数判断是否
: 超载，超载到下台机器，我也不太清楚实际中应该怎么设计

k*u2010-08-23 07:08

23 楼

bbb
留个洞是什么意思啊？

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

: 打了电话，被告知要切upc时要在箱子上留个洞。rebate表上没提要留洞啊。难道要bbb
: it？！

l*o2010-08-23 07:08

24 楼

我也收到online test链接了，是hackerrank的，以为是写代码，原来题目是这样的
是写描述性质的话吗？
谢谢楼主

难道电面不就是要online test吗？我刚开始在美国找工作，没有经验，这是第一家电
面。先是Amazon有人发电邮和我确认电面时间，然后有人打电话和我聊了一下简历和考
了几个概........

【在 B********4 的大作中提到】

: 根据题意，不会有新增数据，只要处理查询请求就行了。所以找到一种平分ID的方法就
: 不会有数据溢出的问题。
: 请求的速率平均每台应该是1000tps，但繁忙时刻可能超出。我提到用排队来处理这种
: 情况，反正队列是不会无限增长的。
:
: 如果现在满了，再进来，就会冲垮server. 是否可以考虑队列，或者一个函数判断是
: 否超载，超载到下台机器，我也不太清楚实际中应该怎么设计

l*i2010-08-23 07:08

25 楼

整个剪下来

【在 k*********u 的大作中提到】

:
: bbb
: 留个洞是什么意思啊？

B*42010-08-23 07:08

26 楼

我的第三题是写代码，要求写个完整的class,implement 3 methods.
头两道就是叙述。第4道我叙述中夹杂了点伪代码。

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

: 我也收到online test链接了，是hackerrank的，以为是写代码，原来题目是这样的
: 是写描述性质的话吗？
: 谢谢楼主
:
: 难道电面不就是要online test吗？我刚开始在美国找工作，没有经验，这是第一家电
: 面。先是Amazon有人发电邮和我确认电面时间，然后有人打电话和我聊了一下简历和考
: 了几个概........

u*c2010-08-23 07:08

27 楼

打印机还是照相机要剪下来？

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

: 整个剪下来

g*g2010-08-23 07:08

28 楼

Memcached is a typical case for No.4, and you can use consistent hashing to
minimize rehashing.

d*r2010-08-23 07:08

29 楼

both

g*g2010-08-23 07:08

30 楼

#3, hashtable + array, swap the last element with the deleted one to make
removal O(1). addition is O(1) if the initial size is big enough and you don
't need resize, as is the case with hashtable.

b*i2010-08-23 07:08

31 楼

吹下来不行？

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

: both

B*42010-08-23 07:08

32 楼

能否展开说说hashtable + array怎么存放数据的？怎么决定（k,v)的？
为啥3个方法都是O(1)？
先谢谢了

removal O(1). addition is O(1) if the initial size is big enough and you don
't need resize, as is the case with hashtable.

【在 g*****g 的大作中提到】

: #3, hashtable + array, swap the last element with the deleted one to make
: removal O(1). addition is O(1) if the initial size is big enough and you don
: 't need resize, as is the case with hashtable.

m*a2010-08-23 07:08

33 楼

beachcamera的deal吧。好像就那个店要洞

bbb

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

: 打了电话，被告知要切upc时要在箱子上留个洞。rebate表上没提要留洞啊。难道要bbb
: it？！

g*g2010-08-23 07:08

34 楼

You have a hashtable with keys as your server id and values for the
positions in the array. You just keep
the size of the array and every time you delete something, you swap the last
element in the array with the deleted one and reduced the size by 1, you
don't actually need to resize the array physically.
With a continuous array, obviously random access stays at O(1).

don

【在 B********4 的大作中提到】

: 能否展开说说hashtable + array怎么存放数据的？怎么决定（k,v)的？
: 为啥3个方法都是O(1)？
: 先谢谢了
:
: removal O(1). addition is O(1) if the initial size is big enough and you don
: 't need resize, as is the case with hashtable.

S*e2010-08-23 07:08

35 楼

又打了电话，正好BRIDGET接。这次要盒子和打印机上的sn照片。

【在 h**m 的大作中提到】

: 我刚给他们打了电话，说不用CUT出来一个洞。UPC揭下来就行。
: 跟他们ARGU,实在不行，你就说你刚问过BRIDGET，这个是接我电话的接线员。看他们怎么说。

w*k2010-08-23 07:08

36 楼

第4题显然应该是consistent hashing吧，至于第三题，最好是hash + doubly linked
list, 因为后者易于删除，但我没仔细看题。

h*m2010-08-23 07:08

37 楼

我刚又打了电话，这下真相大白了。
首先PRINTER和CAMERA都只要把UPC揭下来，不用CUT一个洞（如果接线员说要CUT一个洞
，你就说刚刚是BRIDGET接的电话，说不用CUT洞，然后接线员就会说，那好吧，你就寄
吧。）
关于SN,只要PRINTER的SN，相机的SN不需要。

a*i2010-08-23 07:08

38 楼

2，错。应是O(1)
3，错。应用HASHSET add, get, remove 都是O（1）
4, 错。用cluster server hash manager user id and user fold address

H*82010-08-23 07:08

39 楼

you might be use the wrong rebate form, I did onee, they sent me the check.

not fulfill

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

c*n2010-08-23 07:08

40 楼

不能用dequeue,因为dequeue.get(i) 的复杂度是n, 用array就可以了。删除的时候就
像好虫说的作Swap

linked

【在 w****k 的大作中提到】

: 第4题显然应该是consistent hashing吧，至于第三题，最好是hash + doubly linked
: list, 因为后者易于删除，但我没仔细看题。

c*n2010-08-23 07:08

41 楼

2为什么是constant?
3用hashset你怎么随机返回？

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

: 2，错。应是O(1)
: 3，错。应用HASHSET add, get, remove 都是O（1）
: 4, 错。用cluster server hash manager user id and user fold address

e*a2010-08-23 07:08

42 楼

SDE 2?

B*42010-08-23 07:08

43 楼

我认为第二题肯定不是O(1)。
比如一个已经排序数组 1，2，3，4，5，6，7，8，9.
按照代码，如果我要搜索1，
第一步，找到5，不对，往下挪一个，
第二步找到4，不对，往下挪一个，
。。。。
第五步找到1.
如果有1000个数，那就要找500次。

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

: 2，错。应是O(1)
: 3，错。应用HASHSET add, get, remove 都是O（1）
: 4, 错。用cluster server hash manager user id and user fold address

a*y2010-08-23 07:08

44 楼

这题就是binary search, O(logn).

complexity。

【在 B********4 的大作中提到】

: 我认为第二题肯定不是O(1)。
: 比如一个已经排序数组 1，2，3，4，5，6，7，8，9.
: 按照代码，如果我要搜索1，
: 第一步，找到5，不对，往下挪一个，
: 第二步找到4，不对，往下挪一个，
: 。。。。
: 第五步找到1.
: 如果有1000个数，那就要找500次。

s*72010-08-23 07:08

45 楼

楼主应该倒在第三题上，删除了后续顺序号不连贯就不能O（1）了，应该用hashmap+
array(arraylist) 的数据结构
其他没太多问题，最后一道，回答出 hash分段的load balancer就行了，至于具体用什
么hash, 比如consistent hash没必要说那么细，也没说要考虑动态增加或者减少node
的情况，这个只是online test, 又不是onsite有follow up的。

d*w2010-08-23 07:08

46 楼

第一个就错了。空间复杂度是O(h)，你在遍历的时候会出queue的，空间复杂度怎么会
是o(n)

【在 B********4 的大作中提到】

: Amazon的电面online test挂了。很纳闷，因为我觉得题不难，当时还以为自己都做对
: 了呢。大家看看我哪道题做错了？
: 1）给一段代码，用queue实现对binary tree的遍历。问time complexity and space
: complexity.
: 我一看，这不是BFS吗，答O(n) and O(n)。
: 2）一段代码，在sorted array number[]里查找某个值。代码用的递归，每次比较目标
: 值和number[(min+max)/2],然后根据比较结果决定是min+1或者max-1.
: 我看每次递归只是array index范围缩小一个。所以答O(n)。
: 3）有一个online server 群，要求实现3个方法：
: add(serverId): 添加一个新server，

B*42010-08-23 07:08

47 楼

会是o(n)
queue的长度是不定的，最大长度等于树的宽度，不是高度(深度）。题目中只说是
binary tree。如果是complete binary tree, 应该是n/2。
也许我的表达方式不对，准确地应该是
time complexity O(bxd)
space complexity O(b)
where b is the breadth of the tree, and d is the depth of the tree.
但是BFS一般都是写时间O(V + E) and 空间O (V)。实际上我对这个空间O (V)也不是太
明白，因为显然queue不用把所有节点都装进去。我个人以为这是考虑最坏情况。
因为这个题的数据结构不是图，是二叉树，不用管V，我想了几秒钟就还是写了O(n), O
(n).
反正现在已经绕糊涂了。

【在 d******w 的大作中提到】

: 第一个就错了。空间复杂度是O(h)，你在遍历的时候会出queue的，空间复杂度怎么会
: 是o(n)