l****h
发帖数: 1189 | 1 这个做的很棒。 我用hash做了一个。和这个比起来弱点在不能stream. 如果log是不断
更新的， 这个方法很容易改成实用的工具。
HASH方法：
一个set 记录顺序时间， hash table 记录时间map到index. buckets记录人数。
直接扫描日志，每个过去，把覆盖的 bucket都加1. 如果用户平均在线时间都是有限的
，这个还是O(N)的。如果用户时间当变量M考虑，就是 O(NM)了。这个应该考虑吗？ |
|
l****h
发帖数: 1189 | 2 这个做的很棒。 我用hash做了一个。和这个比起来弱点在不能stream. 如果log是不断
更新的， 这个方法很容易改成实用的工具。
HASH方法：
一个set 记录顺序时间， hash table 记录时间map到index. buckets记录人数。
直接扫描日志，每个过去，把覆盖的 bucket都加1. 如果用户平均在线时间都是有限的
，这个还是O(N)的。如果用户时间当变量M考虑，就是 O(NM)了。这个应该考虑吗？ |
|
e******g
发帖数: 51 | 3 刚刚收到Amazon的Offer消息，下周谈Offer细节.
我是Fresh MS，被recruiter骚扰参加了Online Test,然后上周五去Seattle On-site的
，四轮面试。
第一轮是个中国大哥，7年exp。
一开始谈了下他的项目，问了下我的经历，最后半个小时给了道题。
题目：Given Movies,Actors. Each movie includes some actors. How to find all
shortest paths between two given actors?
e.g.
Movie: A, B, C
Actor: a, b, c
relation: A(a,b),B(b,c)
from: a, To: c
Ans: a-b-c
这就是一道BFS问题，写完OK。他也很满意。
第二轮也是个中国大哥，Bar Raiser, 4年exp。
简单介绍下他自己后开始问我问题，都是关于OOD的一些概念。
然后让我设计一个在web doc页面上的画图程序，要求能够处理各种图形（增添，删除
，编辑，染色等等）。
用了Observer,Factory... 阅读全帖 |
|
m**********g
发帖数: 153 | 4 RateLimit是否可以用token bucket 来实现， 一个timer thread定期添加token, 一个
请求消耗一个token, bucket 为空时reject request. 也可以用类似select()的
function实现timer 与demultiplex. |
|
j*****4
发帖数: 12 | 5 估计挂了，有一题基本不知道怎么解。
设计一个function: bool cancall(), 保证每秒钟内return true的数量小于 N,
想了两个办法，
a)写个queue, 每次 call 把 request time放到queue 里面，dequeue 1秒以前的
request.然后看queue的size..没效率，被否。
b)每秒一个bucket,然后保证当前bucket,的count小于N/2,不精确，被否。
然后就没时间了，这个怎么搞，到底？ 提示是"keep track of available count
instead... "
面试管好像说是一个XXX algorithm,在network里面用的。有人听着耳熟么？ 我是不是
被黑了。 |
|
g*********e
发帖数: 14401 | 6 今天HR打电话来说HC没过，记下来参考
电面1：
第一个问题记不得了
第二个，给一系列string，要求找两个string,使得它们没有共同字符，并且长度乘积
最大。好像给了个暴力解
电面2：
给两个string array A,B，要求返回三个array，第一个只包含只出现在A中的字符串，
第二个只包含只出现在B中的字符串，第三个只包含common字符串
然后海量数据下该怎么code。貌似这个电面反馈很好
onsite:
1. 先寒暄介绍，稍稍问现在工作。题目是run length encoding的变种，decoder的规
则是： a3x1bc -> a111bc (用x来表示重复）
该怎么设计encoder。写代码。开头想了很久，才写了代码，写得比较罗嗦。再跑了几
个测试。这轮发挥不好，HR开头也迟到了一会儿，导致时间稍稍不够，没时间再做一题
了，问了几个问题结束。
2. 稍稍介绍下google的工作。题目是常见题二维平面上过最多点的直线。问清后写了
个n^2logn的解法，然后在提示下讲了n^2的方法。扩展问海量数据下的做法，这里纠结
了，给了个比较复杂的方法。时间到。这轮应该... 阅读全帖 |
|
l*y
发帖数: 70 | 7 来自主题: JobHunting版 - 谈G家面经 congrats!
我觉得算法不错，最多 bucket partition during first scan and do second scan
for largest bucket.
--------
这算法有点弱啊。。。 |
|
S******1
发帖数: 216 | 8 3个数组来做，
一个a是普通的bucket, 元素存储array b 的index
一个array b, 递增存储值， 删除就swap然后更新a的index值， 有一个len维护这个数
组b的有效长度，a的index如果小于len就当作无效。
clear的时候set len = 0;
一个back ward validation array c. 如果a有两个bucket都是index 3, 这个数组做
validation.
或者两个数组，但是数组b是
class Rec {
int val;
int a'sIndex;
} |
|
S******1
发帖数: 216 | 9 3个数组来做，
一个a是普通的bucket, 元素存储array b 的index
一个array b, 递增存储值， 删除就swap然后更新a的index值， 有一个len维护这个数
组b的有效长度，a的index如果小于len就当作无效。
clear的时候set len = 0;
一个back ward validation array c. 如果a有两个bucket都是index 3, 这个数组做
validation.
或者两个数组，但是数组b是
class Rec {
int val;
int a'sIndex;
} |
|
S***A
发帖数: 133 | 10 你没明白我的意思，假设k为100，你第一个bucket装了10个，第二个装了30，第三个可
能没有，第四个装了80个，你怎么找呢？而且你可能不知道哪个bucket里装多少吧？
：假设当然是k<<n啦
：k非常小，比如10,20这种
：n非常大，几十万肯定不只，几百万至少了
：【 在 SEKKA (努力备考中......) 的大作中提到: 】
：: too optimistic，你怎么知道你的一个group会/不会cover k个值？
：: ：我大概明白了
：: ：heap没有错
…… |
|
c*******y
发帖数: 98 | 11 bucket神马的感觉靠谱，不同bucket存到不同机器上去，估计最好用平衡二叉树做一个
可以O lgn 插入，Olgn 查找第k个元素的结构。节点结构至少要包括node左边几个元素
，右边几个元素。每次插入还有平衡都得把这个也考虑一下。 |
|
f*****u
发帖数: 308 | 12 这个应该是说到点子上了!多谢大拿点拨!以前还真是没有接触过这种系统,没有这些概
念.学习了.
TSD是指Time Series Database对吧?这里的bucket,你是说对于每个出现的timestamp,
建一个bucket?还是对每小段时间?能再具体点说说怎么实现么?多谢多谢! |
|
|
r******t
发帖数: 250 | 14 根本就没有哪个 bucket 非得是空的，他把 min 和 max 两个数拿出来，凑成 n - 2
个数玩鸽巢原理
玩完了发现没考虑 max 和 min 再加回去，还能至少有一个 bucket 是空的吗，搞了个
不严谨的原理，不搞笑吗？
一共 n 个数 n - 1 个 gap，平均 gap 都有 (max - min) / (n - 1)
我就说最大值不小于平均数就完了，就是这么一个简单的道理
不是说这个题简单打击楼主，这题不弱，我也想了很久，但是我一直在说的是有些人的
解法就是故弄玄虚，把简单的东西搞复杂 |
|
m********a
发帖数: 128 | 15 Thanks! thinking about the buckets, how do you guarantee the range is well
determined such that the numbers are evenly distributed (since each machine
only stores and operates N number)?
divides
bucket |
|
r*****h
发帖数: 505 | 16 不需要sort array吧，对bucket做binary search,复杂度只要nlogx, x= number of
buckets |
|
c*****m
发帖数: 271 | 17 要求设计一个数据结构，满足insert(int key)，remove(int key)和int
getMostFrequentKey()。对于同一个key，每次被insert，计数加1；每次被remove，计
数减1；然后需要取最大count的key。要求所有操作都是O(1)复杂度。
看了你的blog，不太理解你的数据结构是怎么保证这三个操作是O(1)的，不知道是怎么
组织数据存储的。可能是我没太理解，我问题在于：insert/delete的时候是不是Node
要换一个bucket存储？怎么保证bucket是有序的？ |
|
w*******i
发帖数: 186 | 18 由于count只会加一或者减一，一个key只会移到相邻的bucket中，或者创建一个新的插
入或者将当前的bucket删除，用双向链表就可以了。
Node |
|
c*****m
发帖数: 271 | 19 要求设计一个数据结构，满足insert(int key)，remove(int key)和int
getMostFrequentKey()。对于同一个key，每次被insert，计数加1；每次被remove，计
数减1；然后需要取最大count的key。要求所有操作都是O(1)复杂度。
看了你的blog，不太理解你的数据结构是怎么保证这三个操作是O(1)的，不知道是怎么
组织数据存储的。可能是我没太理解，我问题在于：insert/delete的时候是不是Node
要换一个bucket存储？怎么保证bucket是有序的？ |
|
w*******i
发帖数: 186 | 20 由于count只会加一或者减一，一个key只会移到相邻的bucket中，或者创建一个新的插
入或者将当前的bucket删除，用双向链表就可以了。
Node |
|
i*******e
发帖数: 7 | 21 用bucket是不是可以放弃double linked list直接上array就好了，array size = W，
index = frequency - 1. 这样是不是省点事？hashmap works as inverted index,
key = hashtag, value = index of bucket array |
|
b**********5
发帖数: 7881 | 22 先问: map reduce mean
我说， mapper emit （number， 1）， 可以弄几个combiner， emit （partial sum
， partial N）， 然后最后一个reducer， add up sum divide by N
问： 会有什么问题
答： sum overflow， 可以用 long， 或者big integer？
此处省略一千字
原来是这样的：something called rolling average
let's say avg0 is average for a0... aN0, avg1 is average for aN0 .... aN1....
so the total average is avg0*(N0/N) + avg1*(N1/N) + avg2*(N2/N)....
so the combiner can emit (avg0, N0), (avg1, N1) ... pair
and the reducer would calculate the total average
=============... 阅读全帖 |
|
g****v
发帖数: 971 | 23 第二题为什么bucket的方法不准确？
第一遍mapreduce可以确定最多2个buckets，然后第二遍最多sort下不行么？
能不能展开讲讲sampling?
sum
... |
|
g****v
发帖数: 971 | 24 比如第一遍是100 billion的数字，我找到了2个bucket，这2个bucket只有1million个
数字，第二遍我用mapreduce sort这1milion个数字，然后找到median不行么？
你说的sampling是什么？ |
|
s****a
发帖数: 794 | 25 bucket sort像是一个办法 把bucket size搞搞好 |
|
s********l
发帖数: 998 | 26 同赞 “踢了丫一脚” haha
这个题 为什么用 double linked list和hash table啊？bucket啊？
top k 难道不是用priority queue吗？
题目是在东岸和西岸之间有很多位置记录装置
，有很多车一起从西岸开到东岸，然后你要返回top k的车，这些车时开的最快的。用
double linked list和hash table来做。然后说可以不可以优化，就是把相同距离的车
放到一个bucket里面，比如说set里面，这是我在版上看到的。白人和印度人都表示挺
满意的。 |
|
|
b*****n
发帖数: 618 | 28 不需要吧
唯一的要求就是bucket的size是d，
这个bucket到底从哪里开始算的，是不是整数完全不重要。 |
|
a********5
发帖数: 1631 | 29 贪心是错的。你每个插入都要考虑插在当前子串的左边还是右边，其实它们是不同的。
这个用dp做。
hashset有很多做法，我的做法是每个bucket里填clean的数字，如果get时候拿到的数
字比当前已经clean过的次数少就视为无效。每次clean把这个数字加一，add就把这个
数字填到bucket里。还有别的解法
output |
|
h*******e
发帖数: 1377 | 30 为啥要lock 数字入哪个 bucket 不会错啊， 可能出错的是入bucket 的顺序， 可是那
个重要吗， 线程本来就不能guarentee顺序啊。 |
|
x*****z
发帖数: 15 | 31 Leaky bucket 就是个带时间记录的counter，具体可以看guava ratelimiter
：leaky bucket用queue实现可以么？？ |
|
x*****z
发帖数: 15 | 32 Leaky bucket 就是个带时间记录的counter，具体可以看guava ratelimiter
：leaky bucket用queue实现可以么？？ |
|
d********y
发帖数: 2114 | 33 来自主题: JobHunting版 - 亚麻设计题 建个bucket list。有了统计结果后就知道那个bucket以上是25%，哪个是25%以下。用
户对号入座就可以了
to |
|
发帖数: 1 | 34 来自主题: JobHunting版 - 亚麻设计题 就是对 bucket list 进行 top k quick sort.
能把bucket list摊开来讲讲么？ |
|
s*******n
发帖数: 305 | 35 普通解法就是binary search 吧， 找到离这个target的左右邻居， 比较下就行。
更快是不是bucket idea, 分成[0,1), [1,2) [2,3), 假如太细的话， 可以多层， 然
后每个bucket里面是有序的double list. |
|
发帖数: 1 | 36 哥们，hashtable每个bucket里面是一个linked list。multithreading的时候一大堆读
thread在里面，怎么可以变动underlying datastructure? 整个linkedlist锁住才能写
(写操作包括change value, delete/add/change nodes)， in practise至少要锁住一
个或者多个bucket。 |
|
T*****g
发帖数: 1306 | 37 哥们你做过synchronization相关的工作么？你知道你一个bucket有100个element，多
线程同时写在mutex上要等多久么？不过你提的这个throughput可能用mutex也能达到，
只能说你是没见过高性能的salable hashtable
不要误导人了，谁告诉你要copy一整条bucket来做copy on write？（有人提到RCU了，
RCU就可以做）。RCU的难点只在于resize的时候不好处理，不过已经有人把这个问题解
决了。
如， |
|
w***u
发帖数: 156 | 38 不知道思路对不对
假设bucket 里面有50个token，每秒都会填满bucket，每个reguest需要先拿到token，
service才会执行这个request。 |
|
p**f
发帖数: 3549 | 39 这是真的吗？？？单身索男的buckets：
24% $82,500 to $157,500
32% $157,500 to $200,000
挣16万的得去撞墙了吧？
赶脚大部分龟公fall在32%这个bucket里啊。
龟公还不起来造反？ |
|
Y*****2
发帖数: 38613 | 40 32%也只是
16万减去15万7剩下的部分才32%
15万七还是上一个bracket 啊
[在 plff (bbb) 的大作中提到：]
:这是真的吗？？？单身索男的buckets：
:挣16万的得去撞墙了吧？
:赶脚大部分龟公fall在32%这个bucket里啊。
:龟公还不起来造反？ |
|
m********3
发帖数: 2125 | 41 从来没有报过税？
[在 plff (bbb) 的大作中提到：]
:这是真的吗？？？单身索男的buckets：
:挣16万的得去撞墙了吧？
:赶脚大部分龟公fall在32%这个bucket里啊。
:龟公还不起来造反？ |
|
m**********2
发帖数: 6568 | 42 sue a bucket to fill it with water, count how many buckets, then calculate. |
|
p*****e
发帖数: 537 | 43 这个贷款利息和property tax免税的地方算得不完全对。在同一个交税的bucket里是这
样算得，但如果interest和property tax能帮你掉进另一个bucket的话，那就是四两拨
千斤的效果了。 |
|
j*******0
发帖数: 347 | 44 did this bucket test and the water in the bucket just kept the same level.
too bad |
|
u****q
发帖数: 24345 | 45 from this magical thing called internet:
Put a bucket and have buckets ready as back ups when the first one fills up.
Then poke a hole with a screwdriver and 2 or 3 spaced in the lowest part of
the sag is best. If the ceiling drops then it was so waterlogged it would
have dropped if you did not poke holes for drainage. Time is of the essence
把一个桶和水桶准备作为备份使用，当第一个填满了。然后戳一个洞，用螺丝刀和2个
或3个间隔中的最低部分的凹陷是最好的。如果天花板下降，那么它是如此涝会下降，
如果你不戳孔排水。时间是至关重要的 |
|
u****q
发帖数: 24345 | 46 老夫是一个HD Homer Bucket+Husky Bucket Tool Organizer，加一起要$10大洋呢。。。 |
|
x****u
发帖数: 12955 | 47
Can't you just put your hand in the bucket and scoop out whatever solid that
's in there first, then dump the bucket in the toilet? |
|
h*******9
发帖数: 308 | 48 1. $25 OFF $100 OR MORE ON GALLON CANS AND 5-GALLON BUCKETS OF PRIMER
2. Buy 2 get the third free ON BEHR MARQUEE® INTERIOR 5-GALLON BUCKETS
OF PAINT
expire 3/7/2016
who needs any/both, send me a msg with your email, I can email you.
I will appreciate if you can give me a baozi. |
|
|
|
