x****k
发帖数: 2932 | 1 来自主题: JobHunting版 - 再问一道题 bucket sort to find the bucket holding median number, then generic sort or
heap or bucket sort again. |
|
t*****j
发帖数: 1105 | 2 sell rating的可能值很少，有的是几星几星，数字的话最多是一位小数。
比如 1，2，3，4，5等相当于不同的bucket，先把书放进不同bucket，
然后根据价格排序。最后连起来就行。
design的话，可以考虑bucket总的是个大容器，里面有5个小容器桶，存书的ID和price
.每次新增加书或者书的rating变化的话，就插入到相应的桶里。桶里各个书的结构可
以用BST.
这样排序是O(nlogn),插入，删除，rating调整都是O(logn)
我瞎说的，请高人看看行不行。 |
|
g*****e
发帖数: 282 | 3 这个bitmap开销很大。2^32 bits。建ht的过程又要读一遍。这个ht能直接count，还是
类似bucket sort要来好几轮？
我觉得还是类似bucket sort的思路好，每次2^8个buckets，最坏的情况全部数字读4遍
。从space和time的cost均衡一些。
但是我觉得tree不是更好，类似Huffman coding，每个node带一个counter？ |
|
c******n
发帖数: 4965 | 4 就是binpacking 啊。
这题的decision 形式就是
given bins of bucket size X , N integers . X < sum(N)
and given bucket count M, is it possible to pack all N integers into
buckets?
decision---optimization 转换是search X,
original bin packing 的转换是search M |
|
g**********y
发帖数: 14569 | 5 按位bucket sort =>
1. 把所有数按从左数第k位分进9~0的bucket, 如果某数没有k位，直接用掉。
2. 从9～0的bucket, 依次call above function with k+1 |
|
g**********y
发帖数: 14569 | 6 3, 3, 43 =>
1. 分成{43}, {3, 3}
2. {43} 用掉
3. {3, 3}都没有下一位，用掉both
结果：4333
举个复杂点的例子：{9, 98, 987, 902, 399, 380}
1. 分成两个bucket {9, 98, 987, 902}, {399, 380}
2. 对第一个bucket, 9用掉；剩下分成两个bucket: {98, 987}, {902}
3. 对{98, 987}, 用掉98； 然后再call function, 用掉987
4. 对{902}, 用掉902
5. 对{399, 380}, 分成{399}, {380},
6. 用掉399,
7. 用掉380
结果：
9 98 987 902 399 380 |
|
s*****n
发帖数: 5488 | 7 我的理解是，
先allocate 64个buckets.清零。
for int i to x
convert to bcd code;
for int j to 8
sum up bcd code
bucket[sum]++;
return max of buckets and its index. |
|
d*******l
发帖数: 338 | 8 上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
的满足条件的窗口。
对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
这样总的时间复杂度可以达到nlogn。空间复杂度O(n)。 |
|
d*******l
发帖数: 338 | 9 上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
的满足条件的窗口。
对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
这样总的时间复杂度可以达到nlogn。空间复杂度O(n)。 |
|
i**********e
发帖数: 1145 | 10 来自主题: JobHunting版 - 问一道题目 几年前写的程序，忘了。基本思路是分成 n_w x n_h 个格子没错。
n_w 是多少个 column，n_h 是多少个 row.
然后生成 buckets:
bucket = new list[n_w*n_h];
把每个点 hash 到相对的格子去:
temp_pt.x = coor_x[i]; temp_pt.y = coor_y[i]; temp_pt.id = i;
int col = (int)((coor_x[i] - min_x) / j);
int row = (int)((coor_y[i] - min_y) / k);
int index = row * n_w + col;
bucket[index].push_back(temp_pt);
然后就是搜索的算法了，用 visited table 来记录搜过的格子，然后一层一层往外搜
。当时没考虑可读性，写的比较乱，请见谅。
http://ideone.com/suHFu |
|
d*****8
发帖数: 38 | 11 没有搜到以前类似的题。问一下大牛们：
Given a list of water buckets,
you can pour water from one to another buckets. if it's full, the remaining
water will be wasted.
how to get max number of full buckets? |
|
h**********9
发帖数: 3252 | 12 1分零1秒就是 current bucket + 59/60*prev bucket
如果嫌精度不够就用更小的bucket size. |
|
h****n
发帖数: 1093 | 13 suppose the hash is implemented by chaining
Hash size is m, key number is n, the longest length of chain is L
Then we can do:
1. randomly select a bucket, suppose the length of chain is k (1<=k<=L)
2. for the list in bucket k, randomly generate a number l between 1 to L
if l is less than k, then we return the lth item in the list
It is just like a rejection sampling in a 2D array
Time complexity: The expected number per bucket is n/m
The probability that rejection sampling succeeds is n/m/L
The ... 阅读全帖 |
|
n****p
发帖数: 193 | 14 Big data means big IT job opportunities -- for the right people
As companies embrace big data, they're in the market for high-level
strategists and communicators. Do you have the chops to snag a big data job?
As big data gathers momentum, it's helping to create big career
opportunities for IT professionals -- if they have the right qualifications.
According to a report published in 2011 by McKinsey & Co., the U.S. could
face a shortage by 2018 of 140,000 to 190,000 people with "deep analytical
t... 阅读全帖 |
|
c*********m
发帖数: 43 | 15 都有依据key查找了，Msg getMsg(long key);肯定得用hash table啊，只是最好每个
bucket给个锁，而不是锁整个表
还有一个trick应该就是根据原有的n条消息的averge value,当加入一条消息时，更新
averge.
average = (n * average + new value) / (n + 1)
最近5分钟的message这个实现，可以当每次访问一个bucket的item时，把这个bucket的
大于5分钟的东西去掉，memcached应该有处理这个的策略，我有些忘了。。 |
|
q*****w
发帖数: 62 | 16 在glassdoor上facebook版上看的的。
Given 10,000 servers containing a Billion integers each how would you find
how to find the median?
1. 用2 heap? 全部数走这个two heap内存消耗太大吧。
2. 用类似 find median of two sorted array 方法？那每台机都要把全部数放到内存
去。每台机都是2^32*4， 也就是4GB内存（假设int32）。感觉消耗太大。
3. bucket sort将所有server的所有数都放到master的bucket中去，这样只要master开
一个4G的内存就好了。而且可以并行。锁的粒度可以到bucket。
大家怎么认为？ |
|
q*****w
发帖数: 62 | 17 在glassdoor上facebook版上看的的。
Given 10,000 servers containing a Billion integers each how would you find
how to find the median?
1. 用2 heap? 全部数走这个two heap内存消耗太大吧。
2. 用类似 find median of two sorted array 方法？那每台机都要把全部数放到内存
去。每台机都是2^32*4， 也就是4GB内存（假设int32）。感觉消耗太大。
3. bucket sort将所有server的所有数都放到master的bucket中去，这样只要master开
一个4G的内存就好了。而且可以并行。锁的粒度可以到bucket。
大家怎么认为？ |
|
w********s
发帖数: 1570 | 18 假设password=abcdef
那么每次给3位x,y,z的话，x只可能在{a,b,c}中，z只可能在{d,e,f}中，
那么根据随机给的可以得出{a,b,c}和{d,e,f}
为了确定顺序，a,b,c有6种排列，d,e,f有6种排列，总共36中可能
对每一种可能做一个bucket，那么每次检验这36个bucket，直到过滤剩下1个bucket，
那个就是password. |
|
r*******k
发帖数: 1423 | 19 heap就是2个数组
如果连这个都装不下，又怎么算中值？
至少得遍历一遍吧？
除非知道数的范围，碰到最大最小值可以删一对
否则没办法减少空间要求吧
要不用bucket统计一下，能猜出中值在哪个bucket里
然后等于是求那个bucket的第k个值
要遍历数组2遍 |
|
z******g
发帖数: 271 | 20 C路过
But if I were to do it, I would make the iterator data structure contain the
bucket size, a bucket cursor and a reference to the underlying linked list
node. The worst case time complexity would be O(m + n) where m is the bucket
size. |
|
d****n
发帖数: 397 | 21 ….那我把每个数转化为二进制，然后用32Xn 的radix sort为什么过不了oj，理论上也
是O（n）time，O（n）space。
也不是bucket sort就一定行。对bucket size也有要求。
我也不是想不到bucket sort。 |
|
s******d
发帖数: 9806 | 22 找frequency的部分用bucket（double linked）更好一些。每个node就是frequency是
某一个值的所有hashtag，这样每次操作只需要移动到相邻的bucket，或者创建新的
bucket（因为frequency只有加减1）。
node。 |
|
s******d
发帖数: 9806 | 23 找frequency的部分用bucket（double linked）更好一些。每个node就是frequency是
某一个值的所有hashtag，这样每次操作只需要移动到相邻的bucket，或者创建新的
bucket（因为frequency只有加减1）。
node。 |
|
b*****n
发帖数: 618 | 24 这个难道不是Palantir的万年不变电面题。
扩展2，把原来的HashSet换成TreeSet就行了，不过时间复杂度是O(nlogk)
如果一定要O(n)的话，把每个数对应到一个长度为差的上限的bucket，这样每次只需要
看相邻两个bucket和自己所对应的bucket的情况。 |
|
p**********i
发帖数: 276 | 25 同感，任意1s滑动窗口而且要跑满50/s，肯定需要记录每一个Request时间。
如果不要求1s滑动窗口，bucket之类的应该比较合适，而且一个变量就够啦。
每个request应该在上一个request后，等1/50才进入。这样正好每秒50个。如果有一个
request太快了，等了1/100就进入了，那它就用掉后面request的1/100时间。
总的bucket计为-1/100，这样过一段时间强制把bucket清零。是不是也可以？ |
|
h*********2
发帖数: 192 | 26 给定一个单调递增的数列，找到一个partition into N bucket，使得所有bucket的数字
的variance最小。bucket个数是已知的。
听起来像binary search + dp
请问大家见过这题吗？ |
|
M***6
发帖数: 895 | 27 产生buckets不是需要O（n）？
[在 sunvssoon (sunvssoon) 的大作中提到：]
:普通解法就是binary search 吧， 找到离这个target的左右邻居， 比较下就行。
:更快是不是bucket idea, 分成[0,1), [1,2) [2,3), 假如太细的话， 可以多层， 然
:后每个bucket里面是有序的double list. |
|
p******a
发帖数: 130 | 28 Bucket 里存指向linked list的指针，有thread在读的时候swap指针没什么问题，只要
保证读写这个指针是原子的。
[在 linuxhacker (linuxhacker) 的大作中提到：]
:哥们，hashtable每个bucket里面是一个linked list。multithreading的时候一大堆
读thread在里面，怎么可以变动underlying datastructure? 整个linkedlist锁住才能
写(写操作包括change value, delete/add/change nodes)， in practise至少要锁住一
:个或者多个bucket。 |
|
发帖数: 1 | 29 来自主题: JobHunting版 - 税改出来了 看你处在那个bucket里了，26万到41万的bucket提高了2%，其余bucket都是不变或者下
降甚至大幅下降的。
以夫妻合报为例：
7.5万到15万：税率不变 (25%->25%)
15万到23万：税率下降3% （28%->25%）
23万到26万：税率下降8% （33% ->25%)
26万到41万：税率提高2% （33% -> 35%)
41万到46.7万：税率不变 (35%->35%)
46.7万到100万：税率下降4.6% （39.6 -> 35%)
100万以上：税率不变 (39.6% -> 39.6%)
原先税率（2016年）：
夫妻合报：0—18550美元 单身： 9275美元，税率10%
夫妻合报：18551—75300美元 单身： 9276 — 37650美元，税率15%
夫妻合报：75301—151900美元 单身：91151—190150美元，税率25%
夫妻合报：151901—231450美元 单身：91151—190150美元，税率28%
夫妻合报：231451—413350美元 单身：19015... 阅读全帖 |
|
p*********g
发帖数: 2998 | 30 这题只可能接近o(n)解， 思路很简单的， bucket. sort,
step 1: find 最大， 最小数值， o(n)
step 2: bucket[max-min]; 只记录次数
step 3: num.value-min找到index, 放进对应的bucket
step 4: 从最后开始往前扫， num[i] *(i＋min), 是否大于target
时间复杂度是o(max-min), 如果max－min=n, 那么就是o(n)的
你要o(n), 除非是找连续的subarray才有可能 |
|
t***e
发帖数: 3601 | 31 Bucket of death:
A big bucket half filled with water, put a thick layer of sunflower seeds to
cover the water surface. Place a piece of wood board that allows chipmunk
to climb up the side of the bucket. put a few seeds on the board as lure.
check every day for dead chipmunks under the water, sometimes you can find
squirrel too... It's disgusting work. |
|
k******1
发帖数: 1746 | 32 1 bucket cl2, 1 bucket acid, 1.5 buckets shock, done! |
|
j******2
发帖数: 544 | 33 家里老人6个月时候就让他就荡过秋千，小区里full bucket那种。后来听说这么小小孩
不应该荡秋千？网上查了一下，秋千确实分好几种，还分step1， step2什么的，最后
才是full bucket那种。现在心里有点担心。宝宝还老是嚷嚷着要荡秋千，路过full
bucket就不肯走。请问该怎么办？ |
|
|
t*****e
发帖数: 2228 | 35 file separately is not much different from filing jointly as the tax bucket
is all half off married jointly..we will hit 33% bucket if each of us has
income over 105k, which is much lower than 33% bucket of single status which
is 178k, sigh...and hit AMT as well by filing separately..sigh.. |
|
|
n*****e
发帖数: 27 | 37 在buckete有la的U1的团很久了，我加入后等了好几个月也没凑够5个人，8月26号这个
团就expire了。Anyway, 给大家贴个link也可以参考一下价格。
https://www.buckete.com/group/50587452/
我偏向想买U1, 如果这里能把团组起来，一定算上我。如果组团不顺的话，只要有五个
人，可以联系一下buckete这个团购的组织人，看看她还能不能重新开个团。
如果凑不到足够的人买u1的话，K300也行。
dealer |
|
|
j*****g
发帖数: 94 | 39 【 以下文字转载自 NewYork 讨论区 】
发信人: jerwang (jerwang), 信区: NewYork
标 题: 美东雅马哈钢琴U1团购 $6150 全包
发信站: BBS 未名空间站 (Sat Jan 3 09:44:19 2015, 美东)
刚刚开了个新团：https://www.buckete.com/group/74229172/
2月25号截团。
价格： $6150 全包
（琴凳，运费，全新日本早Yamaha U1等，详细去看团里介绍，这里面已经包含了雅马
哈的$250 rebate），人数多的话更低。
Dealer的话这三家里面的一家：faust and son， jacobs music， rockaway music
买家必须是美东NY, NJ，PA，其他地方可能有额外的shiping fee。
加团去这里：https://www.buckete.com/group/74229172/
disclaimer：buckete网站本上不收费，但是每台钢琴我会从dealer那里收$50的组织费
，有异议着请不要加我的团。 |
|
j*****g
发帖数: 94 | 40 【 以下文字转载自 NewYork 讨论区 】
发信人: jerwang (jerwang), 信区: NewYork
标 题: 美东雅马哈钢琴U1团购 $6150 全包
发信站: BBS 未名空间站 (Sat Jan 3 09:44:19 2015, 美东)
刚刚开了个新团：https://www.buckete.com/group/74229172/
2月25号截团。
价格： $6150 全包
（琴凳，运费，全新日本早Yamaha U1等，详细去看团里介绍，这里面已经包含了雅马
哈的$250 rebate），人数多的话更低。
Dealer的话这三家里面的一家：faust and son， jacobs music， rockaway music
买家必须是美东NY, NJ，PA，其他地方可能有额外的shiping fee。
加团去这里：https://www.buckete.com/group/74229172/
disclaimer：buckete网站本上不收费，但是每台钢琴我会从dealer那里收$50的组织费
，有异议着请不要加我的团。 |
|
c******e
发帖数: 355 | 41 ZJLBT，你好。那个”破网“是我公司网站，谢谢宣传。Buckete是一个方便大家组织团
购的平台，这个平台上买家成团以后，不同商家来投标这样。Buckete本身并不团购任
何产品，也不保证任何团购最后一定可以成团。一个团购是否成团，很大因素取决于发
起人的组织能力。欢迎你在Buckete上组团，我想一定可以成团的，让不同dealer竞拍
一下，价格应该比现在你拿到的更好。另外，smith是个公用的ID，钢琴我们好几个
intern做过，我会和他们沟通一下以前发帖的情况，如有任何误会，请谅解。 |
|
|
|
|
j*****g
发帖数: 94 | 45 【 以下文字转载自 NewYork 讨论区 】
发信人: jerwang (jerwang), 信区: NewYork
标 题: 美东雅马哈钢琴U1团购 $6150 全包
发信站: BBS 未名空间站 (Sat Jan 3 09:44:19 2015, 美东)
刚刚开了个新团：https://www.buckete.com/group/74229172/
2月25号截团。
价格： $6150 全包
（琴凳，运费，全新日本早Yamaha U1等，详细去看团里介绍，这里面已经包含了雅马
哈的$250 rebate），人数多的话更低。
Dealer的话这三家里面的一家：faust and son， jacobs music， rockaway music
买家必须是美东NY, NJ，PA，其他地方可能有额外的shiping fee。
加团去这里：https://www.buckete.com/group/74229172/
disclaimer：buckete网站本上不收费，但是每台钢琴我会从dealer那里收$50的组织费
，有异议着请不要加我的团。 |
|
m**********6
发帖数: 59 | 46 群主MM写的很不错，我在buckete上开了一个group，大家可以去那里登记一下。群主有
空可以注册一个ID，我把这个团转给你吧：
K300 这里加： https://www.buckete.com/product/YBD00TAWHK/
K500 这里加： https://www.buckete.com/group/62768939/
加里面的第一个团。
Kawai今年出了新型号K300, K500 和K800, 对应于之前的K3, K5, K8，价钱上涨了一点
，但是性能提升了很多。尤其是K500由之前K5的48寸改至51寸。有意购买的MM大家一起
团购吧。楼主正在跟两个钢琴dealer谈价钱, 其中一个已经给我报价了，另一个如果报
价更低的话楼主会来更新。请感兴趣的MM將你的姓名和联系方式尽快站内短信发给我。
如果有需要grand或其它型号的MM，也可以告诉我，我试着一起讲价。
十人团价格。以下价格包括delivery, tax, instant rebate, 一次tuning和bench。如
果十五人以上可以再谈下来一点。
K300: $5100
K500: $6750
... 阅读全帖 |
|
m**********6
发帖数: 59 | 47 群主MM写的很不错，我在buckete上开了一个group，大家可以去那里登记一下。群主有
空可以注册一个ID，我把这个团转给你吧：
K300 这里加： https://www.buckete.com/product/YBD00TAWHK/
K500 这里加： https://www.buckete.com/group/62768939/
加里面的第一个团。
Kawai今年出了新型号K300, K500 和K800, 对应于之前的K3, K5, K8，价钱上涨了一点
，但是性能提升了很多。尤其是K500由之前K5的48寸改至51寸。有意购买的MM大家一起
团购吧。楼主正在跟两个钢琴dealer谈价钱, 其中一个已经给我报价了，另一个如果报
价更低的话楼主会来更新。请感兴趣的MM將你的姓名和联系方式尽快站内短信发给我。
如果有需要grand或其它型号的MM，也可以告诉我，我试着一起讲价。
十人团价格。以下价格包括delivery, tax, instant rebate, 一次tuning和bench。如
果十五人以上可以再谈下来一点。
K300: $5100
K500: $6750
... 阅读全帖 |
|
|
H**********g
发帖数: 22 | 49 感恩节前的事情
发信人: jerwang (jerwang), 信区: SanFrancisco
标 题: Yamaha 钢琴团购 已经有20多个人了，下午截团
发信站: BBS 未名空间站 (Mon Nov 24 13:54:31 2014, 美东)
sf很多妈妈可能需要买钢琴，希望版主手下留情先不要删，下午我会自己删掉。
全新日本早yamaha u1 价格是$5999或者更低，送琴凳和调音，免费湾区送货上门。
U3的话7300多，也是送琴凳和调音，免费湾区送货上门。
这次报价的是湾区最大的授权经销商，10年保修，质量和服务都有保障。
想加团的必须在下午6点前去buckete 上 sign up，因为是节假日期间，所以一旦过期
就不加人
了.
U1： https://www.buckete.com/group/24539900/
U3： https://www.buckete.com/group/21787895/ |
|
s****2
发帖数: 4569 | 50 May 13, 2015
Cherries
Our early Corral Cherries are now sold out.
It is looking like our Bing & Rainier Cherries will be ready sometime middle
of next week. We will send another email with an exact date.
White Peaches
We will be open with our early U-Pick White Peaches this
Saturday and Sunday May 16 & 17 our fruitstand at
600 Eureka Ave. Brentwood, CA 94513
Hours:9AM - 4PM
Orchard closes for u-pick at 3:30pm
U-pick Peach Price:
Full Bucket $1.25/lb
Less than a bucket $2.00/lb
minimum for full... 阅读全帖 |
|
