B********4
发帖数: 7156 | 1 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确定机器号，再把请求发到那台机器上。
我究竟哪些题答错了？ |
J*****n
发帖数: 137 | 2 第二个题目直接Binary Search不行么？ |
l**o
发帖数: 356 | |
k******e
发帖数: 145 | |
B********4
发帖数: 7156 | 5
可能我表达不清，不是我写的代码。头两道都是给出代码，要求回答time complexity。
第二道代码写的仿佛是Binary Search，但每次递归，搜索范围只是缩小1，所以我认为
这是个陷阱，不是O(logn),应该是O(n).
【在 J*****n 的大作中提到】
: 第二个题目直接Binary Search不行么？
|
J*****n
发帖数: 137 | 6 第三个，hashtable的 key 因为 remove 操作已经不连续了，这时候用random，你也考
虑了不存在 key, value 的情况，那这样最差就是O(n)了吧？ |
B********4
发帖数: 7156 | 7
难道电面不就是要online test吗？我刚开始在美国找工作，没有经验，这是第一家电
面。先是Amazon有人发电邮和我确认电面时间，然后有人打电话和我聊了一下简历和考
了几个概念题，就说screening过了，你做一下网上测试吧。然后就给我链接让我上网
做题去了。
【在 l**o 的大作中提到】
: 楼主做的是电面还是online test呀？
|
J*****n
发帖数: 137 | 8 第四题，如果customerID % 机器数 都是映射到某几台机器，不平均分布，怎么办？如
果现在满了，再进来，就会冲垮server. 是否可以考虑队列，或者一个函数判断是否
超载，超载到下台机器，我也不太清楚实际中应该怎么设计 |
B********4
发帖数: 7156 | 9
考虑了不存在 key, value 的情况，那这样最差就是O(n)了吧？
你说的很对，看来这道题我栽了。你有什么好方法没有？
你再看看我别的题答得对吗？
【在 J*****n 的大作中提到】
: 第三个，hashtable的 key 因为 remove 操作已经不连续了，这时候用random，你也考
: 虑了不存在 key, value 的情况，那这样最差就是O(n)了吧？
|
B********4
发帖数: 7156 | 10 根据题意，不会有新增数据，只要处理查询请求就行了。所以找到一种平分ID的方法就
不会有数据溢出的问题。
请求的速率平均每台应该是1000tps，但繁忙时刻可能超出。我提到用排队来处理这种
情况，反正队列是不会无限增长的。
如果现在满了，再进来，就会冲垮server. 是否可以考虑队列，或者一个函数判断是
否超载，超载到下台机器，我也不太清楚实际中应该怎么设计
【在 J*****n 的大作中提到】
: 第四题，如果customerID % 机器数 都是映射到某几台机器，不平均分布，怎么办？如
: 果现在满了，再进来，就会冲垮server. 是否可以考虑队列，或者一个函数判断是否
: 超载，超载到下台机器，我也不太清楚实际中应该怎么设计
|
|
|
l**o
发帖数: 356 | 11 我也收到online test链接了，是hackerrank的，以为是写代码，原来题目是这样的
是写描述性质的话吗？
谢谢楼主
难道电面不就是要online test吗？我刚开始在美国找工作，没有经验，这是第一家电
面。先是Amazon有人发电邮和我确认电面时间，然后有人打电话和我聊了一下简历和考
了几个概........
【在 B********4 的大作中提到】
: 根据题意，不会有新增数据，只要处理查询请求就行了。所以找到一种平分ID的方法就
: 不会有数据溢出的问题。
: 请求的速率平均每台应该是1000tps，但繁忙时刻可能超出。我提到用排队来处理这种
: 情况，反正队列是不会无限增长的。
:
: 如果现在满了，再进来，就会冲垮server. 是否可以考虑队列，或者一个函数判断是
: 否超载，超载到下台机器，我也不太清楚实际中应该怎么设计
|
B********4
发帖数: 7156 | 12 我的第三题是写代码，要求写个完整的class,implement 3 methods.
头两道就是叙述。第4道我叙述中夹杂了点伪代码。
【在 l**o 的大作中提到】
: 我也收到online test链接了，是hackerrank的，以为是写代码，原来题目是这样的
: 是写描述性质的话吗？
: 谢谢楼主
:
: 难道电面不就是要online test吗？我刚开始在美国找工作，没有经验，这是第一家电
: 面。先是Amazon有人发电邮和我确认电面时间，然后有人打电话和我聊了一下简历和考
: 了几个概........
|
g*****g
发帖数: 34805 | 13 Memcached is a typical case for No.4, and you can use consistent hashing to
minimize rehashing. |
g*****g
发帖数: 34805 | 14 #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********4
发帖数: 7156 | 15 能否展开说说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.
|
g*****g
发帖数: 34805 | 16 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.
|
w****k
发帖数: 755 | 17 第4题显然应该是consistent hashing吧，至于第三题，最好是hash + doubly linked
list, 因为后者易于删除，但我没仔细看题。 |
a******i
发帖数: 49 | 18 2，错。 应是O(1)
3，错。应用HASHSET add, get, remove 都是O（1）
4, 错。用cluster server hash manager user id and user fold address |
c******n
发帖数: 100 | 19 不能用dequeue,因为dequeue.get(i) 的复杂度是n, 用array就可以了。删除的时候就
像好虫说的作Swap
linked
【在 w****k 的大作中提到】
: 第4题显然应该是consistent hashing吧，至于第三题，最好是hash + doubly linked
: list, 因为后者易于删除，但我没仔细看题。
|
c******n
发帖数: 100 | 20 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***a
发帖数: 1661 | |
B********4
发帖数: 7156 | 22 我认为第二题肯定不是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***y
发帖数: 852 | 23 这题就是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******7
发帖数: 1758 | 24 楼主应该倒在第三题上，删除了后续顺序号不连贯就不能O（1）了， 应该用hashmap+
array(arraylist) 的数据结构
其他没太多问题，最后一道，回答出 hash分段的load balancer就行了，至于具体用什
么hash, 比如consistent hash没必要说那么细，也没说要考虑动态增加或者减少node
的情况，这个只是online test, 又不是onsite有follow up的。 |
d******w
发帖数: 2213 | 25 第一个就错了。空间复杂度是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********4
发帖数: 7156 | 26
会是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)
|
