1+在美国可以用？ - 未名空间MITBBS历史存档

e*02014-09-09 07:09

1 楼

1. 一个程序自动在网上不断的搜集不同的URL, 个数是billions级别了. 请问怎么实
时记录的其中长度(String.length)相对较短的95%URL的平均长度? 也就是最长的那5%
的URL不考虑, 只计算那95%的平均长度, 而且需要当前实时数据
2. 一个3D空间, 有很多半径为1的气球, 有很多点, 他们个数是million级别... 知道
所有气球球心和所有点的坐标, 怎么最快找到包裹点最多的那个气球.
感觉都是搜索相关

f*b2014-09-09 07:09

2 楼

ATT 的LTE可以用？

s*52014-09-09 07:09

3 楼

1. 假设要纪录最长过去24小时的url长度，最快每秒更新一次，可以把每秒内的url长
度aggregate起来存在一个hashtable里。过去24小时内，最多有24*3600个这样的
hashtable，用linked list连起来，另外用一个hashtable统计这个time window里所有
url长度。每次新的url进来，把linked list里最老的数据去掉，同时更新总的
hashtable。
基于那个总hashtable很容易算出bottom 95%url平均长度。

w*r2014-09-09 07:09

4 楼

美国版的可以，据说根国内版的不一样

l*f2014-09-09 07:09

5 楼

大牛能透露一下背景吗（站内信即可）
小弟最近申g家intern 连面试都没给哭

z*92014-09-09 07:09

6 楼

h2o 是H，H+

g*e2014-09-09 07:09

7 楼

第二题是把数据丢到很多台机器上并行着算吧？也就是google所谓的"mapreduce"?

i*c2014-09-09 07:09

8 楼

100% for sure on at&t

h*y2014-09-09 07:09

9 楼

第二题是用kd tree是mlog(n)吧, m是点数, n是气球数, 还能更快吗?

5%

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

: 1. 一个程序自动在网上不断的搜集不同的URL, 个数是billions级别了. 请问怎么实
: 时记录的其中长度(String.length)相对较短的95%URL的平均长度? 也就是最长的那5%
: 的URL不考虑, 只计算那95%的平均长度, 而且需要当前实时数据
: 2. 一个3D空间, 有很多半径为1的气球, 有很多点, 他们个数是million级别... 知道
: 所有气球球心和所有点的坐标, 怎么最快找到包裹点最多的那个气球.
: 感觉都是搜索相关

l*n2014-09-09 07:09

10 楼

的确是要用hashmap来记录aggregated counts，不管是某个时间段还是到目前所有的。
根据counts算percentile好像只能o(n)遍历，好在aggreated bins的数量不可能太多。

【在 s***5 的大作中提到】

: 1. 假设要纪录最长过去24小时的url长度，最快每秒更新一次，可以把每秒内的url长
: 度aggregate起来存在一个hashtable里。过去24小时内，最多有24*3600个这样的
: hashtable，用linked list连起来，另外用一个hashtable统计这个time window里所有
: url长度。每次新的url进来，把linked list里最老的数据去掉，同时更新总的
: hashtable。
: 基于那个总hashtable很容易算出bottom 95%url平均长度。

h*y2014-09-09 07:09

11 楼

用一个queue装实时数据, 有新的插入, 过时的删除.
所有queue插入QUEUE的数据同时插入一个BST, 用hash存在BST中的位置, 从QUEUE中删
除时也从BST中删除,
BST中的节点加一个信息, 记录以此为根的子树所有的string的总长和string的个数,
log(n)时间算出95%的平均

5%

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

: 1. 一个程序自动在网上不断的搜集不同的URL, 个数是billions级别了. 请问怎么实
: 时记录的其中长度(String.length)相对较短的95%URL的平均长度? 也就是最长的那5%
: 的URL不考虑, 只计算那95%的平均长度, 而且需要当前实时数据
: 2. 一个3D空间, 有很多半径为1的气球, 有很多点, 他们个数是million级别... 知道
: 所有气球球心和所有点的坐标, 怎么最快找到包裹点最多的那个气球.
: 感觉都是搜索相关

f*p2014-09-09 07:09

12 楼

第一题counting，url长度不会太大，分配一个Bundle[400]的数组，
class Bundle {
int count;
int avgLen;
}
存每个长度的url的个数和均值。然后还有
total_url_count, total_url_avg_length
95%url的平均长度就是： (total_url_count * total_url_avg_length-sum_{i in top
5% url set}{count_i*avgLen_i}) divided by (total_url_count - sum_{i in top
5% url set}{count_i})
第二题不会。。可以退化成二维或者一维的。怎么感觉和closest pair of points的解
法有些类似。

5%

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

: 1. 一个程序自动在网上不断的搜集不同的URL, 个数是billions级别了. 请问怎么实
: 时记录的其中长度(String.length)相对较短的95%URL的平均长度? 也就是最长的那5%
: 的URL不考虑, 只计算那95%的平均长度, 而且需要当前实时数据
: 2. 一个3D空间, 有很多半径为1的气球, 有很多点, 他们个数是million级别... 知道
: 所有气球球心和所有点的坐标, 怎么最快找到包裹点最多的那个气球.
: 感觉都是搜索相关

s*u2014-09-09 07:09

13 楼

好像不是要记录多少时间内的url长度吧，跟时间好像没啥关系啊，只是说按长度靠前
的95%。
我在想弄两个堆怎么样，一个95%的min heap，一个5%的max heap。插入的时候比较两
边的头，然后注意balance？然后min heap可以记录节点数量以及当前的平均。

【在 s***5 的大作中提到】

: 1. 假设要纪录最长过去24小时的url长度，最快每秒更新一次，可以把每秒内的url长
: 度aggregate起来存在一个hashtable里。过去24小时内，最多有24*3600个这样的
: hashtable，用linked list连起来，另外用一个hashtable统计这个time window里所有
: url长度。每次新的url进来，把linked list里最老的数据去掉，同时更新总的
: hashtable。
: 基于那个总hashtable很容易算出bottom 95%url平均长度。

J*32014-09-09 07:09

14 楼

我也是这么想的但这样是不是空间要求太大？

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

: 好像不是要记录多少时间内的url长度吧，跟时间好像没啥关系啊，只是说按长度靠前
: 的95%。
: 我在想弄两个堆怎么样，一个95%的min heap，一个5%的max heap。插入的时候比较两
: 边的头，然后注意balance？然后min heap可以记录节点数量以及当前的平均。

e*02014-09-09 07:09

15 楼

嗯, 其实我也是这个意思.
当时第一想法就是用两个堆, 但是被否定了, 因为没那么多空间

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

: 好像不是要记录多少时间内的url长度吧，跟时间好像没啥关系啊，只是说按长度靠前
: 的95%。
: 我在想弄两个堆怎么样，一个95%的min heap，一个5%的max heap。插入的时候比较两
: 边的头，然后注意balance？然后min heap可以记录节点数量以及当前的平均。

e*02014-09-09 07:09

16 楼

嗯, 我觉得也是, 当时和面试官纠结了一下怎么提高单一气球和点如何提高计算效率,
但是面对这么多数据, 那些细节基本是扯淡, 只能分部到多个单机去计算

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

: 第二题是把数据丢到很多台机器上并行着算吧？也就是google所谓的"mapreduce"?

s*n2014-09-09 07:09

17 楼

一个min heap存5％较长的，一个max heap存95％较短的
新入的URL，先判断max heap是否需要加element，如果要，max_heap.add ( min(new_
URL, min_heap.top()) ), min_heap.add ( max(new_URL, min_heap.top()) )。如果
不要，比较max_heap.top()和new_URL是否要交换，min_heap再插入不要的那个

5%

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

: 1. 一个程序自动在网上不断的搜集不同的URL, 个数是billions级别了. 请问怎么实
: 时记录的其中长度(String.length)相对较短的95%URL的平均长度? 也就是最长的那5%
: 的URL不考虑, 只计算那95%的平均长度, 而且需要当前实时数据
: 2. 一个3D空间, 有很多半径为1的气球, 有很多点, 他们个数是million级别... 知道
: 所有气球球心和所有点的坐标, 怎么最快找到包裹点最多的那个气球.
: 感觉都是搜索相关

b*g2014-09-09 07:09

18 楼

依上面的讨论，第一题可以用两个堆：minHeap (right, 5%) & maxHeap (left, 95%).
堆中节点为：
class Node{
int length;
int count;
}
另外用两个HASHMAP，用来记录各个堆中某个长度在堆中对应的节点；对每个堆，用两
个变量分别记录其总URL个数和平均长度。插入新的URL长度时，只要维护两个堆的平衡
和相关变量既可。空间复杂度为O(n)，n为最长的URL长度，可以理解为常数
第二题可以先算出空间的边界，然后将整个空间分割成边长为１的立方体，并给每个立
方体分配ID。用一个HASHMAP记录与每个立方体相交的球体链表。如果某个立方体不与
任何球体相交，则不用记录。然后是处理每个点，计算出其所在的立方体ID，然后检查
其对应的球体链表，并将包含它的球体计数加１.
如果球体均匀分布的话，时间复杂度为O(m + n)。

e*82014-09-09 07:09

19 楼

觉得第二题这么做有点太简单化了呀：比如可能所有的点都在单位立方体里，然后每个
球也和单位立方体相交呢（比如每个球和其他球的位置差不多，就是稍稍移动一点点）？
觉得要是用space partition的数据结构，kd-tree或者quad-tree都可以用，但是这样
就没有用到所有的球体都是半径为１的条件？然后对每个球体算包含的点数，觉得有点
inefficient来着。。。

).

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

: 依上面的讨论，第一题可以用两个堆：minHeap (right, 5%) & maxHeap (left, 95%).
: 堆中节点为：
: class Node{
: int length;
: int count;
: }
: 另外用两个HASHMAP，用来记录各个堆中某个长度在堆中对应的节点；对每个堆，用两
: 个变量分别记录其总URL个数和平均长度。插入新的URL长度时，只要维护两个堆的平衡
: 和相关变量既可。空间复杂度为O(n)，n为最长的URL长度，可以理解为常数
: 第二题可以先算出空间的边界，然后将整个空间分割成边长为１的立方体，并给每个立

l*n2014-09-09 07:09

20 楼

两个都是million级别的话，要么指望有nlogn的解法，要么就只能map reduce了。
如果点和球分布均匀的话，可以考虑用interval sorting的办法，然后x、y、z三个维
度上都和代表球的线段有重合才计算该点是否真的在球内。

,

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

: 嗯, 我觉得也是, 当时和面试官纠结了一下怎么提高单一气球和点如何提高计算效率,
: 但是面对这么多数据, 那些细节基本是扯淡, 只能分部到多个单机去计算

u*o2014-09-09 07:09

21 楼

多谢总结，但不是太明白第一题为什space complexity 是o(n)
按说要维护两个堆，空间很大啊
比如说前20个URL，最长的放在minheap, 19个放在maxheap, 用hashmap记录average
再进来20个，最长的两个放在minheap, 38个放在maxheap,update hashtable.
随着数据越来越多，两个堆就像堆雪球越来越大啊，虽然随时可以从hashtable读当前
average，但heap要放在memory不是太可能吧，难道有什么flushing system?

).

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

: 依上面的讨论，第一题可以用两个堆：minHeap (right, 5%) & maxHeap (left, 95%).
: 堆中节点为：
: class Node{
: int length;
: int count;
: }
: 另外用两个HASHMAP，用来记录各个堆中某个长度在堆中对应的节点；对每个堆，用两
: 个变量分别记录其总URL个数和平均长度。插入新的URL长度时，只要维护两个堆的平衡
: 和相关变量既可。空间复杂度为O(n)，n为最长的URL长度，可以理解为常数
: 第二题可以先算出空间的边界，然后将整个空间分割成边长为１的立方体，并给每个立

l*n2014-09-09 07:09

22 楼

这里的heap是aggregated之后的heap，长度相等的url就只是一个length数，然后count
为2，只要保证95%heap的count和占total的95%就行。如果second max of 95% heap的
count数太大，导致去掉max of 95% heap也能占比超过95的话，就把这个max扔到5%
heap去。

95%
用两
平衡
个立

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

: 多谢总结，但不是太明白第一题为什space complexity 是o(n)
: 按说要维护两个堆，空间很大啊
: 比如说前20个URL，最长的放在minheap, 19个放在maxheap, 用hashmap记录average
: 再进来20个，最长的两个放在minheap, 38个放在maxheap,update hashtable.
: 随着数据越来越多，两个堆就像堆雪球越来越大啊，虽然随时可以从hashtable读当前
: average，但heap要放在memory不是太可能吧，难道有什么flushing system?
:
: ).

b*g2014-09-09 07:09

23 楼

We are not storing every URL itself.
Instead, we only store the number of URLs for each length.
Actually a simpler solution is to use an integer array of size n, where n is
the max length: int[] count
Maintain these parameters:
idx: count[0], ..., count[idx] (partial) contains the first 95% url lens
offset: # of urls in count[idx], which belongs to the first 95%, 0 < offset
<= count[idx]
sumCount: count[0] + ... + count[idx - 1]
avg: average length of the first sumCount urls
At any point, the answer is: (avg * sumCount + offset * (idx + 1)) / (
sumCount + offset)
To insert a new url with length k, just set count[k - 1]++, and then update
idx, offset, sumCount and avg, such that sumCount + offset = 95% of total

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

: 多谢总结，但不是太明白第一题为什space complexity 是o(n)
: 按说要维护两个堆，空间很大啊
: 比如说前20个URL，最长的放在minheap, 19个放在maxheap, 用hashmap记录average
: 再进来20个，最长的两个放在minheap, 38个放在maxheap,update hashtable.
: 随着数据越来越多，两个堆就像堆雪球越来越大啊，虽然随时可以从hashtable读当前
: average，但heap要放在memory不是太可能吧，难道有什么flushing system?
:
: ).

e*02014-09-09 07:09

24 楼

嗯, 感觉这个方法最可取

count

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

: 这里的heap是aggregated之后的heap，长度相等的url就只是一个length数，然后count
: 为2，只要保证95%heap的count和占total的95%就行。如果second max of 95% heap的
: count数太大，导致去掉max of 95% heap也能占比超过95的话，就把这个max扔到5%
: heap去。
:
: 95%
: 用两
: 平衡
: 个立

l*n2014-09-09 07:09

25 楼

直接用array的麻烦在于如果array中间断档，那么要扫很多次才能找到下个地方。

is
offset

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

: We are not storing every URL itself.
: Instead, we only store the number of URLs for each length.
: Actually a simpler solution is to use an integer array of size n, where n is
: the max length: int[] count
: Maintain these parameters:
: idx: count[0], ..., count[idx] (partial) contains the first 95% url lens
: offset: # of urls in count[idx], which belongs to the first 95%, 0 < offset
: <= count[idx]
: sumCount: count[0] + ... + count[idx - 1]
: avg: average length of the first sumCount urls

u*o2014-09-09 07:09

26 楼

解释的很清楚，多谢了！真是好办法呀！

count

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

: 这里的heap是aggregated之后的heap，长度相等的url就只是一个length数，然后count
: 为2，只要保证95%heap的count和占total的95%就行。如果second max of 95% heap的
: count数太大，导致去掉max of 95% heap也能占比超过95的话，就把这个max扔到5%
: heap去。
:
: 95%
: 用两
: 平衡
: 个立

b*g2014-09-09 07:09

27 楼

aglee

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

: 直接用array的麻烦在于如果array中间断档，那么要扫很多次才能找到下个地方。
:
: is
: offset

s*u2014-09-09 07:09

28 楼

也就是说hashtable + heap么？

count

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

: 这里的heap是aggregated之后的heap，长度相等的url就只是一个length数，然后count
: 为2，只要保证95%heap的count和占total的95%就行。如果second max of 95% heap的
: count数太大，导致去掉max of 95% heap也能占比超过95的话，就把这个max扔到5%
: heap去。
:
: 95%
: 用两
: 平衡
: 个立

b*g2014-09-09 07:09

29 楼

Here is the code:
public class URLAverage{
private static final int MAX_LEN = 400;
private int total = 0;
private int sumCount = 0;
private double avg = 0.0;
private int idx = 0;
private int offset = 0;
int[] count = new int[MAX_LEN];
public double getAverage(){
if(offset + sumCount == 0) return 0.0;
return (sumCount * avg + offset * (idx + 1)) / (offset + sumCount);
}
public void addURL(String url){
int k = url.length();
count[k - 1]++;
if(k - 1 < idx){
avg = (sumCount * avg + k) / (sumCount + 1);
sumCount++;
}
total++;
int target = (int)(total * 0.95);
if(offset + sumCount < target){
offset += target - offset - sumCount;
while(offset > count[idx]){
avg = (sumCount * avg + count[idx] * (idx + 1)) / (sumCount + count
[idx]);
sumCount += count[idx];
offset -= count[idx];
idx++;
}
}
if(offset + sumCount > target){
// similar to the above part, just need to move "point" left
}
}

is
offset

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

: We are not storing every URL itself.
: Instead, we only store the number of URLs for each length.
: Actually a simpler solution is to use an integer array of size n, where n is
: the max length: int[] count
: Maintain these parameters:
: idx: count[0], ..., count[idx] (partial) contains the first 95% url lens
: offset: # of urls in count[idx], which belongs to the first 95%, 0 < offset
: <= count[idx]
: sumCount: count[0] + ... + count[idx - 1]
: avg: average length of the first sumCount urls

s*u2014-09-09 07:09

30 楼

Mark,说的很清楚

).

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

: 依上面的讨论，第一题可以用两个堆：minHeap (right, 5%) & maxHeap (left, 95%).
: 堆中节点为：
: class Node{
: int length;
: int count;
: }
: 另外用两个HASHMAP，用来记录各个堆中某个长度在堆中对应的节点；对每个堆，用两
: 个变量分别记录其总URL个数和平均长度。插入新的URL长度时，只要维护两个堆的平衡
: 和相关变量既可。空间复杂度为O(n)，n为最长的URL长度，可以理解为常数
: 第二题可以先算出空间的边界，然后将整个空间分割成边长为１的立方体，并给每个立

p*u2014-09-09 07:09

31 楼

第一题：
参见这个文章：http://www.jb51.net/article/18858.htm
url的最大长度限制为8208个字节，更长的url，请求会报414错误
那就直接弄个8208的bucket存每个长度url的个数，剩下的事情怎么优化，都是常数级
别的复杂度了。
另外95%，可否直接把长度1000以上的算在一起，比如长度>1000的有多少个。按照实际
情况，最后结果不可能大于1000的。

5%

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

: 1. 一个程序自动在网上不断的搜集不同的URL, 个数是billions级别了. 请问怎么实
: 时记录的其中长度(String.length)相对较短的95%URL的平均长度? 也就是最长的那5%
: 的URL不考虑, 只计算那95%的平均长度, 而且需要当前实时数据
: 2. 一个3D空间, 有很多半径为1的气球, 有很多点, 他们个数是million级别... 知道
: 所有气球球心和所有点的坐标, 怎么最快找到包裹点最多的那个气球.
: 感觉都是搜索相关

p*u2014-09-09 07:09

32 楼

问题2：
先把问题简化为2D空间，million级别的圆和点。可以把整个空间分割为1*1的方格。
圆包含点的充分条件就必须是：
0 1 2
3 4 5
6 7 8
圆心在4号方格，点在0-8号方格。
问题规模就直接缩小了，在0-8号方格内的点和4号方格内的圆心，求距离，判断是否真
在圆内。
最后把问题推广到3D空间的球和点，是一样的道理。

5%

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

: 1. 一个程序自动在网上不断的搜集不同的URL, 个数是billions级别了. 请问怎么实
: 时记录的其中长度(String.length)相对较短的95%URL的平均长度? 也就是最长的那5%
: 的URL不考虑, 只计算那95%的平均长度, 而且需要当前实时数据
: 2. 一个3D空间, 有很多半径为1的气球, 有很多点, 他们个数是million级别... 知道
: 所有气球球心和所有点的坐标, 怎么最快找到包裹点最多的那个气球.
: 感觉都是搜索相关

c*d2014-09-09 07:09

33 楼

请问这8208是哪来的？哪个标准或协议？
据我所知，http协议不规定uri最大长度，各个web servers和browsers实现各不相同，
实际中最常考虑的限制是IE限制的2083.

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

: 第一题：
: 参见这个文章：http://www.jb51.net/article/18858.htm
: url的最大长度限制为8208个字节，更长的url，请求会报414错误
: 那就直接弄个8208的bucket存每个长度url的个数，剩下的事情怎么优化，都是常数级
: 别的复杂度了。
: 另外95%，可否直接把长度1000以上的算在一起，比如长度>1000的有多少个。按照实际
: 情况，最后结果不可能大于1000的。
:
: 5%

p*o2014-09-09 07:09

34 楼

不是很清楚, 这９５％指的是url长度排序的95%, 还是出现的所有url的95%?
比方说
url length: occurrence
1: 1
2: 1
3: 1
...
94: 1
95: 2
...
99: 0
100:1
如果按url"长度"排序的95%: (1+2+..94+95+95)/96
而如果按"所有"url排序的95%: (1+2+..94+95)/95
指的是哪一种?

5%

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

: 1. 一个程序自动在网上不断的搜集不同的URL, 个数是billions级别了. 请问怎么实
: 时记录的其中长度(String.length)相对较短的95%URL的平均长度? 也就是最长的那5%
: 的URL不考虑, 只计算那95%的平均长度, 而且需要当前实时数据
: 2. 一个3D空间, 有很多半径为1的气球, 有很多点, 他们个数是million级别... 知道
: 所有气球球心和所有点的坐标, 怎么最快找到包裹点最多的那个气球.
: 感觉都是搜索相关