Redian新闻
>
1+在美国可以用?
avatar
1+在美国可以用?# PDA - 掌中宝
e*0
1
1. 一个程序自动在网上不断的搜集不同的URL, 个数是billions级别了. 请问怎么实
时记录的其中长度(String.length)相对较短的95%URL的平均长度? 也就是最长的那5%
的URL不考虑, 只计算那95%的平均长度, 而且需要当前实时数据
2. 一个3D空间, 有很多半径为1的气球, 有很多点, 他们个数是million级别... 知道
所有气球球心和所有点的坐标, 怎么最快找到包裹点最多的那个气球.
感觉都是搜索相关
avatar
f*b
2
ATT 的LTE可以用?
avatar
s*5
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平均长度。
avatar
w*r
4
美国版的可以,据说根国内版的不一样
avatar
l*f
5
大牛能透露一下背景吗 (站内信即可)
小弟最近申g家intern 连面试都没给 哭
avatar
z*9
6
h2o 是H,H+
avatar
g*e
7
第二题是把数据丢到很多台机器上并行着算吧?也就是google所谓的"mapreduce"?
avatar
i*c
8
100% for sure on at&t
avatar
h*y
9
第二题是用kd tree是mlog(n)吧, m是点数, n是气球数, 还能更快吗?

5%

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

avatar
l*n
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平均长度。

avatar
h*y
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级别... 知道
: 所有气球球心和所有点的坐标, 怎么最快找到包裹点最多的那个气球.
: 感觉都是搜索相关

avatar
f*p
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级别... 知道
: 所有气球球心和所有点的坐标, 怎么最快找到包裹点最多的那个气球.
: 感觉都是搜索相关

avatar
s*u
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平均长度。

avatar
J*3
14
我也是这么想的 但这样是不是空间要求太大?

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

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

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

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

【在 g*********e 的大作中提到】
: 第二题是把数据丢到很多台机器上并行着算吧?也就是google所谓的"mapreduce"?
avatar
s*n
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级别... 知道
: 所有气球球心和所有点的坐标, 怎么最快找到包裹点最多的那个气球.
: 感觉都是搜索相关

avatar
b*g
18
依上面的讨论,第一题可以用两个堆:minHeap (right, 5%) & maxHeap (left, 95%).
堆中节点为:
class Node{
int length;
int count;
}
另外用两个HASHMAP,用来记录各个堆中某个长度在堆中对应的节点;对每个堆,用两
个变量分别记录其总URL个数和平均长度。插入新的URL长度时,只要维护两个堆的平衡
和相关变量既可。空间复杂度为O(n),n为最长的URL长度,可以理解为常数
第二题可以先算出空间的边界,然后将整个空间分割成边长为1的立方体,并给每个立
方体分配ID。用一个HASHMAP记录与每个立方体相交的球体链表。如果某个立方体不与
任何球体相交,则不用记录。然后是处理每个点,计算出其所在的立方体ID,然后检查
其对应的球体链表,并将包含它的球体计数加1.
如果球体均匀分布的话,时间复杂度为O(m + n)。
avatar
e*8
19
觉得第二题这么做有点太简单化了呀:比如可能所有的点都在单位立方体里,然后每个
球也和单位立方体相交呢(比如每个球和其他球的位置差不多,就是稍稍移动一点点)?
觉得要是用space partition的数据结构,kd-tree或者quad-tree都可以用,但是这样
就没有用到所有的球体都是半径为1的条件?然后对每个球体算包含的点数,觉得有点
inefficient来着。。。

).

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

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

,

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

avatar
u*o
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长度,可以理解为常数
: 第二题可以先算出空间的边界,然后将整个空间分割成边长为1的立方体,并给每个立

avatar
l*n
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?
:
: ).

avatar
b*g
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?
:
: ).

avatar
e*0
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%
: 用两
: 平衡
: 个立

avatar
l*n
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

avatar
u*o
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%
: 用两
: 平衡
: 个立

avatar
b*g
27
aglee

【在 l*n 的大作中提到】
: 直接用array的麻烦在于如果array中间断档,那么要扫很多次才能找到下个地方。
:
: is
: offset

avatar
s*u
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%
: 用两
: 平衡
: 个立

avatar
b*g
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

avatar
s*u
30
Mark,说的很清楚

).

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

avatar
p*u
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级别... 知道
: 所有气球球心和所有点的坐标, 怎么最快找到包裹点最多的那个气球.
: 感觉都是搜索相关

avatar
p*u
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级别... 知道
: 所有气球球心和所有点的坐标, 怎么最快找到包裹点最多的那个气球.
: 感觉都是搜索相关

avatar
c*d
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%

avatar
p*o
34
不是很清楚, 这95%指的是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级别... 知道
: 所有气球球心和所有点的坐标, 怎么最快找到包裹点最多的那个气球.
: 感觉都是搜索相关

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。