D*****t
发帖数: 558 | 1 i have to admit i have zero confidence in my interest rate prediction. i
would argue that even if there were a mild yield curve flattening with the
short end going up more than the long end, one who holds short term bonds
would still lose less money than the long bond holders. and i really can't
see a severe and quick yield curve flattening or inverted yield curve. that
would be a harbinger of another upcoming recession.
generally i would say that bond market in the next decade won't be as
gener... 阅读全帖 |
|
发帖数: 1 | 2 "I would rather believe there will be a 20 to 30 years of rising
interest rate environment." That's not a well-kept secret, is it? Why
would I want to do something differently and what alternatives do I have?
如果這個20到30 年rising interest rate 的打環境大家意見一致就好辦了.
Laddered bond 本身并不比bond fund 更好. 但在这个利率将长期上涨的大环境&#
11015;️，laddered bond 是比bond fund 更合适的投资bond 的方法. 如果说
确定的现金流不足以令人信服。那么，换个角度。就是投资如何出来. 还是以十年为例
吧。投资bond fund, 无论你怎么样rebalance, 总是要🈶️一个时候从
bond fund 里出来. 从bond fund 里... 阅读全帖 |
|
发帖数: 1 | 3 "I would rather believe there will be a 20 to 30 years of rising
interest rate environment." That's not a well-kept secret, is it? Why
would I want to do something differently and what alternatives do I have?
如果這個20到30 年rising interest rate 的打環境大家意見一致就好辦了.
Laddered bond 本身并不比bond fund 更好. 但在这个利率将长期上涨的大环境&#
11015;️，laddered bond 是比bond fund 更合适的投资bond 的方法. 如果说
确定的现金流不足以令人信服。那么，换个角度。就是投资如何出来. 还是以十年为例
吧。投资bond fund, 无论你怎么样rebalance, 总是要🈶️一个时候从
bond fund 里出来. 从bond fund 里... 阅读全帖 |
|
b********g
发帖数: 47 | 4 每天在版上潜水，看大家写的面经，收益很多 呵呵。现在找工作告一段落，我也写一
下我面试的几个公司吧。本人UIUC CS MASTER
Google：
我第一家面的是Google，campus event听到的招人消息，9月底他们再次来学校进行
campus interview。这个campus interview是连续的两轮面试，各45分钟。题目都很简
单，后来看了版上精华区才知道原来100%都覆盖了。依稀记得是：
1、两个sorted array，求交集
2、已知一篇文章和它的inverted index，求可以覆盖所有单词的最小窗口。就是大家
讨论了好多次的题目
3、实现memcpy
4、上台阶问题，就是那个可以一步可以两步的fibonacci数
5、如何验证一个binary search tree的合法性
一周后收到onsite通知，奇怪的是让我改面software engineer in test。onsite是10
月24号，只有三场面试，题目都很简单，精华区几乎100%覆盖，不大记得了，只记得有
一题开放性问题问一个地图上面的若干个城市，根据什么因素来对这些城市进行排名， |
|
b********g
发帖数: 47 | 5 每天在版上潜水，看大家写的面经，收益很多 呵呵。现在找工作告一段落，我也写一
下我面试的几个公司吧。本人UIUC CS MASTER
Google：
我第一家面的是Google，campus event听到的招人消息，9月底他们再次来学校进行
campus interview。这个campus interview是连续的两轮面试，各45分钟。题目都很简
单，后来看了版上精华区才知道原来100%都覆盖了。依稀记得是：
1、两个sorted array，求交集
2、已知一篇文章和它的inverted index，求可以覆盖所有单词的最小窗口。就是大家
讨论了好多次的题目
3、实现memcpy
4、上台阶问题，就是那个可以一步可以两步的fibonacci数
5、如何验证一个binary search tree的合法性
一周后收到onsite通知，奇怪的是让我改面software engineer in test。onsite是10
月24号，只有三场面试，题目都很简单，精华区几乎100%覆盖，不大记得了，只记得有
一题开放性问题问一个地图上面的若干个城市，根据什么因素来对这些城市进行排名，
... 阅读全帖 |
|
b******7
发帖数: 79 | 6 以前听论坛上有人提过，但是没给过解，不知道哪位大侠能偶赐教啊！
Given a document and a query of K words, how do u find the smallest window
that covers all the words at least once in that document? (given you know
the inverted lists of all K words, that is, for each word, you have a list
of all its occurrrences). This one is really hard. Could someone propose an
algorithm in O(n)? |
|
|
b******7
发帖数: 79 | 8 来自主题: JobHunting版 - 新鲜面试题 @geniusxsy, 对对，版上牛人是不少，可能大部分潜水（我潜水，但是我不是牛人）。
不过blaze确实也是经常提出很好的算法。Algorithmics怎么不出来了。有时候他能给
点新点子。
你的方法的思路2我很同意。就是很难找到一个合适的index organization，你的方法1
有点像给URL自己建inverted list,尽管不太一样。我记得我当时连这个也说了，好象
也不再点子上。但是你的思路2应该肯定是对的。哪位大侠救人啊！～ |
|
b***e
发帖数: 1419 | 9 有重复也没关系. 两个hash, 一个存s2的inverted index, 一个存现在已经找到的. 设
两个指针i, j来traverse s1(j >= i), 多退(i++)少补(j++), 没找到就重新来过. 唯一
tricky的地方就是如果j++多扫进来一个字母, 假设是a, 那么i++要一直repeat直到把上一个a吐出
来. 沿路经过都要吐出去. |
|
v*****t
发帖数: 127 | 10 an issue is
small string = "aab"
inverted index:
'a': 1 4 5 6 7...
'a': 1 4 5 6 7
'b': 2 3 6 9 10...
run the min window coverage algorithm will return an answer of
window[6,6] which is wrong
covered? |
|
d**a
发帖数: 84 | 11 1. 如果预处理， 用 inverted index? |
|
|
k***e
发帖数: 556 | 13 phd不过是training吧 至少我在面试中用到inverted index, k-gram,birthday
paradox, coupon collection, augumented data structure,一般本科是不可能接触到
的.
刚开始不读phd没有奖学金怎么搞.
来了后ta啥的,还有老板的任务,加上有当faculty的梦想,熬了几年,
发现找faculty job太难,而且找到可能去大农村,就开始industry了
有谁能一眼看到将来咋样? 真的目光这么深远就直接毕业去炒股炒房当煤老板了,哈哈. |
|
P********l
发帖数: 452 | 14 Depends.
suppose there are 1,000 words in the dictionary.
If the telephone number is only 3 digits, you can transform the numbers into
words and lookup the dictionary
to see if it is there. Because there are only 3**3 = 27 kinds of combination
. no pre prcessing needed.
If the telephone is 10 digits, the corresponding space of words is too large
. you have to invert index the
dictionary by telephone numbers. Build a suffix tree and you can directly
lookup the numbers. |
|
p*****u
发帖数: 310 | 15 能否具体说下关键词的最佳解法. 我觉得对每个关键字找出inverted index, 再多路
merge已经是最佳了 |
|
s*********g
发帖数: 153 | 16 淡定，淡定。但我还是总结出来这个经验，推荐的确有用，也很让人怀疑。很多
interview的指导书，在引言中都写着，推荐乃一法宝，因为信任成分增加了不少分。
记得我有个博士同学，告诉我他，学长被推荐去MS面试，直接onite，然后人家问了一
道题，字符串invert。然后中了MS的offer，而他自己却被问得跟白痴了一样。我还有
一同学，被推荐到一个网络公司，当然，这回人家没给他面子，被问得灰头土脸。 It
depends.
onsite |
|
d****n
发帖数: 233 | 17 Given a document and a query of K words, how do u find the smallest window
that covers all the words at least once in that document? (given you know
the inverted lists of all K words, that is, for each word, you have a list
of all its occurrrences). This one is really hard. Could someone propose an
algorithm in O(n)? |
|
I**********s
发帖数: 441 | 18 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对
重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许
是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :(
总结: 面试既是技术活, 又是运气活.
无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助.
Interview Qs
Data Structures
1. Integer
- find number of 1s
- next largest smaller
- smallest larger number
- determine if is palindrom
- itoa, atoi
- add 2 numbers w/o using + or arithmetic operators
- implement *, -, / using only +
- find max of two numbers w/o co... 阅读全帖 |
|
s***e
发帖数: 793 | 19 The complexity of an elementary function is equivalent to that of its
inverse, since all elementary functions are analytic and hence invertible by
means of Newton's method.
The computational complexity of computing the natural logarithm (using the
arithmetic-geometric mean) is O(M(n) ln n). Here n is the number of digits
of precision at which the natural logarithm is to be evaluated and M(n) is
the computational complexity of multiplying two n-digit numbers.
http://en.wikipedia.org/wiki/Natural_ |
|
|
j*****u
发帖数: 1133 | 21 the key is to build inverted index, otherwise it is O(N^2): N is #sentenses
if data can be put into memory in full(2G usually okay), build two hashtable
s when reading the file
ha: sentense -> list of words in the sentense
hb: word -> list of sentenses that contain this word
then:
foreach sentense s in ha
{
get related sentenses by iterating s.words and looking up in hb;
foreach (rs in related sentenses)
calculate similiary(s, rs);
}
finally sort and get top 10.
Complexity is redu... 阅读全帖 |
|
n******n
发帖数: 49 | 22 嗯 我也想到了inverted index. 但是具体做法 和你的有些不同。和jerryju的相比，
可能不能算个好算法。。。。 但是 还是贴出来 讨论
首先，如果给2个句子算相似度，我就把其中一个hash，对另一个句子进行遍历，看这
第二个句子当中有多少个词出现在第一个句子对应的hashset里面。
现在，如果是1千万个句子，
第一步，我就用个mapreduce统计每个词在整个文本中出现的次数，输出
frequency>这样的pair。把这些pairs中的前n个（比如前500位）定义为“高频词”。
第二步，统计每个句子当中高频词数，比如i am a programmer, i，am, a这三个词都
是高频词，那就认为这个句子中高频词数为3。
第三步，取所有句子中最高频和次高频的两个句子，按照公式计算相似度，把这个相似
度作为一个下限，等下第四步用这个下限对文本中的句子对进行排除。
第四步，因为我们知道相似度一定是小于min(句子a单词数，句子b单词数）/(句子a单
词数+句子b单词数),所以我们取所有可能的句子对，算min(句子a单词数，句子b单词数
）/(句子a单词数+... 阅读全帖 |
|
j*****u
发帖数: 1133 | 23 看起来挺难的。。
单个文件里没有conflict吧。2 way merge sort?
只想到build一个char->word的inverted index，复杂度可以减到O(n*AVG(#words_
share_no_letter)), worse case还是O(n^2)
有什么更好的方法？
还好这个不难，如果用C#做traversal的时候yield return就行了
middle tier要做什么：requirement是啥？e.g. load balancing? logging?
preprocessing? |
|
j*****u
发帖数: 1133 | 24 看起来挺难的。。
单个文件里没有conflict吧。2 way merge sort?
只想到build一个char->word的inverted index，复杂度可以减到O(n*AVG(#words_
share_no_letter)), worse case还是O(n^2)
有什么更好的方法？
还好这个不难，如果用C#做traversal的时候yield return就行了
middle tier要做什么：requirement是啥？e.g. load balancing? logging?
preprocessing? |
|
o********s
发帖数: 66 | 25 我来试试：
1.Vds？channel width？fanout？是不是应该是inverter的速度？
2. 应该是工艺能做到的最小沟道宽度。
3. no idea
4. n type? 因为电子迁移率更高? |
|
F**********r
发帖数: 237 | 26 版上的题，但是考古找不到讨论了。。。大家看看怎么做好？只能想到brute force的
。。。。
Given a document and a query of K words, how do u find the smallest window
that covers all the words at least once in that document? (given you know
the inverted lists of all K words, that is, for each word, you have a list
of all its occurrrences). |
|
y******5
发帖数: 43 | 27 My thoughts:
Inverted list + Page ranking + B+ tree
We can also use user's search history if available. |
|
g**f
发帖数: 414 | 28 Search company could ask about it.
It is used in inverted list, a key data structure for indexing documents. |
|
g**f
发帖数: 414 | 29 Search company could ask about it.
It is used in inverted list, a key data structure for indexing documents. |
|
d****t
发帖数: 6 | 30 hash table, unless perfect hashing can be applied, it needs to store both
key(array[i]) and the value(i) for conflict resolution in most default
implementation, which results in somehow a waste of space. See this for
more explanation. http://javarevisited.blogspot.com/2011/02/how-hashmap-
works-in-java.html
But in terms of space complexity, inverted indexing is still O(n). I don't
see a big advantage anyway. |
|
g**f
发帖数: 414 | 31 如果有很多text data，可以看 co－occurrence。
比如两个 word A，B 常常同时出现在相近的位置（small text window size）。
那么 他们有可能是近意词。
为了提高准确率，可以 extract key sentence segments 然后分析
比如原文常常是ruby on rails（ROR） 或 ruby on rails,i.e., ror.
就可以分析 （ 或 i.e.等符号。
btw，inverted lists一般都存位置信息。
But in general synonym detection and word disambiguation is a tricky problem. |
|
k****n
发帖数: 369 | 32 like the merging of posting lists in IR
build invert index of the integers
let the shortest posting list length be m
can be done in m*(k-1)logn
practically will usually be much faster, I think...
of |
|
g*****i
发帖数: 2162 | 33 **********************************
M:
phone interview (1 round):
why MS?
biggest challenge
why like coding and algorithm?
what is good code?
your longest code
biggest accomplishment
if you don't want some functions to be modified in java, what to do?
does java allow multiple inheritance?
what does synchronized keyword mean in java?
CEO wants a book, you find it in the system of a nearby bookshop. You went
to the bookshop but fail to find, you have 5 minutes, what will you do?
you have to test 10... 阅读全帖 |
|
g*****i
发帖数: 2162 | 34 **********************************
M:
phone interview (1 round):
why MS?
biggest challenge
why like coding and algorithm?
what is good code?
your longest code
biggest accomplishment
if you don't want some functions to be modified in java, what to do?
does java allow multiple inheritance?
what does synchronized keyword mean in java?
CEO wants a book, you find it in the system of a nearby bookshop. You went
to the bookshop but fail to find, you have 5 minutes, what will you do?
you have to test 10... 阅读全帖 |
|
b**********e
发帖数: 100 | 35 第一题greedy算法一般都能找到反例，e.g.如果一个点是hub，他可以直接和很多点
connect，如果先选他之后，他只能把这个消息传给其中一个，下一个就可能跟谁也不
连了。
第二题我给的是先建一个inverted index，但是他们想要的好像是直接存每个status，
然后用map reduce。不过都有trade off了，现在学术界也在讨论map reduce和
traditional database的好坏，或者说什么时候更适合用那种，两边都有大牛支持
第三题是比较简单，紧跟着的问题是，如果文件大，不能fit在内存怎么办。 |
|
l*********c
发帖数: 29 | 36 I created an inverted file at that time。key is interesting area, value is a
linkedlist of users. If a user is interested in x1, x2, x3 interesting area
, then we will use the users in the three linkedlist as a neighborhood of
the current user. Find the users shared the same interested areas, for
example share at least two same interest area, then find their shopping
history from Amazon, then give recommendation. |
|
s*******f
发帖数: 1114 | 37 面试了很多，有一个offer，不过没赶上H1B。我懒，一直没总结，多数问题板上都有。
慢慢更新帖子列出来，不列公司名。
1. 正则表达式匹配字符串，包含 *， ?
2. give u a function IsBad(item) and an array: good, good, .., bad, bad, ...
always bad, find out first bad
3. design a data structure, support 2 functions: Insert and GetMedian.
4. give a matrix, sorted as follow, M[i][col - 1] < M[i + 1][0]
1 3 4
5 6 8
10 14 16
write function: bool Find(int k)
5. linkedin经典format文本题，我居然没复习到，真得给h1b进度逼死了
6. write function: search(keywords). you have invert table, return top10
b... 阅读全帖 |
|
S**I
发帖数: 15689 | 38 ☆─────────────────────────────────────☆
recursive (递归) 于 (Mon Apr 11 10:56:49 2011, 美东) 提到:
大半夜收到HR的thank you note。不用管什么NDA了
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array with repeated elements
for given element, find out its range.
e.g. A A B B B B B C C D D E F G, given B, the out... 阅读全帖 |
|
S**I
发帖数: 15689 | 39 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 40 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
d******p
发帖数: 335 | 41 一共两次电面一次onsite
电面1. 印度人：
1. research相关问题
2. 给一个巨大的文件(>10GB)，每一行都是一个数字，怎么sort。只要答到external
sort就可以了
3. 一个概率题，具体记不清了，大概的意思是有红色和蓝色球，如果拿到红色，那么
放回，如果拿到蓝色，再拿下一个，根据下一个的花色来判断是否放回。问：拿到就剩
最后一个球是红色的概率是多少
电面2. 欧洲人：
1. research相关
2. 和twitter很相关的一个问题，根据twitter的follow关系，如何efficiently找到所
有的connected components。有一个很大的文件，每行存一条follow关系的边。基本上
达到hash就差不多对了。会不断问细节，然后如何改进。这轮面的很好。
onsite记得的题目如下：
1. 国人大哥
twitter怎么做fraud detection，怎么根据tweet做clustering，问了一些IR的问题
2. 南美人
自己最满意的项目是什么，又按照简历问了一些问题
怎么找hot的tag（就是#tag这种）
3. 白人
1
... 阅读全帖 |
|
d******p
发帖数: 335 | 42 一共两次电面一次onsite
电面1. 印度人：
1. research相关问题
2. 给一个巨大的文件(>10GB)，每一行都是一个数字，怎么sort。只要答到external
sort就可以了
3. 一个概率题，具体记不清了，大概的意思是有红色和蓝色球，如果拿到红色，那么
放回，如果拿到蓝色，再拿下一个，根据下一个的花色来判断是否放回。问：拿到就剩
最后一个球是红色的概率是多少
电面2. 欧洲人：
1. research相关
2. 和twitter很相关的一个问题，根据twitter的follow关系，如何efficiently找到所
有的connected components。有一个很大的文件，每行存一条follow关系的边。基本上
达到hash就差不多对了。会不断问细节，然后如何改进。这轮面的很好。
onsite记得的题目如下：
1. 国人大哥
twitter怎么做fraud detection，怎么根据tweet做clustering，问了一些IR的问题
2. 南美人
自己最满意的项目是什么，又按照简历问了一些问题
怎么找hot的tag（就是#tag这种）
3. 白人
1
... 阅读全帖 |
|
w****x
发帖数: 2483 | 43 /*
Given tweet's inverted index，how to find phrases combination，e.g
phrase "twitter good tool", "twitter is a good tool" is better than "twitter
is good,
facebook is a better tool"
*/
bool GetClosestPhrase(hash_map>& dic, vector& strs,
int& nStart, int& nEnd)
{
for (vector::iterator it = strs.begin(); it != strs.end(); it++)
{
if (dic.find(*it) == dic.end())
return false;
}
int nNum = strs.size();
vector*> vec;
ve... 阅读全帖 |
|
w****x
发帖数: 2483 | 44 /*
Given tweet's inverted index，how to find phrases combination，e.g
phrase "twitter good tool", "twitter is a good tool" is better than "twitter
is good,
facebook is a better tool"
*/
bool GetClosestPhrase(hash_map>& dic, vector& strs,
int& nStart, int& nEnd)
{
for (vector::iterator it = strs.begin(); it != strs.end(); it++)
{
if (dic.find(*it) == dic.end())
return false;
}
int nNum = strs.size();
vector*> vec;
ve... 阅读全帖 |
|
m*****k
发帖数: 731 | 45 5. team lead
悲剧就悲剧在他身上了，问了一个电面一样的问题，我说问过了，换一个吧，然后就换
了一个，结果答的比较烂：
给一组tweet的inverted index，怎么找一个phrase（多个词）的最短组合，比如找
phrase "twitter good tool", twitter is a good tool就比twitter is good,
facebook is a better tool距离近
找最短的包涵所有单词的句子？
顺序重要么？ |
|
f*********m
发帖数: 726 | 46 下面三题的想法：
（1）2. 和twitter很相关的一个问题，根据twitter的follow关系，如何efficiently
找到所
有的connected components。有一个很大的文件，每行存一条follow关系的边。基本上
达到hash就差不多对了。会不断问细节，然后如何改进。这轮面的很好。
想法：
通过follow关系给每个用户建立adjacent list，其中存放其followers。这样我们得到
一个graph.然后用bfs 或dfs找出和一个给定用户连接的节点（用户）。
(2) 5. team lead
悲剧就悲剧在他身上了，问了一个电面一样的问题，我说问过了，换一个吧，然后就换
了一个，结果答的比较烂：
给一组tweet的inverted index，怎么找一个phrase（多个词）的最短组合，比如找
phrase "twitter good tool", twitter is a good tool就比twitter is good,
facebook is a better tool距离近
想法：
计算tweet和candidate phrase的“距... 阅读全帖 |
|
m*****k
发帖数: 731 | 47 5. team lead
悲剧就悲剧在他身上了，问了一个电面一样的问题，我说问过了，换一个吧，然后就换
了一个，结果答的比较烂：
给一组tweet的inverted index，怎么找一个phrase（多个词）的最短组合，比如找
phrase "twitter good tool", twitter is a good tool就比twitter is good,
facebook is a better tool距离近
找最短的包涵所有单词的句子？
顺序重要么？ |
|
f*********m
发帖数: 726 | 48 下面三题的想法：
（1）2. 和twitter很相关的一个问题，根据twitter的follow关系，如何efficiently
找到所
有的connected components。有一个很大的文件，每行存一条follow关系的边。基本上
达到hash就差不多对了。会不断问细节，然后如何改进。这轮面的很好。
想法：
通过follow关系给每个用户建立adjacent list，其中存放其followers。这样我们得到
一个graph.然后用bfs 或dfs找出和一个给定用户连接的节点（用户）。
(2) 5. team lead
悲剧就悲剧在他身上了，问了一个电面一样的问题，我说问过了，换一个吧，然后就换
了一个，结果答的比较烂：
给一组tweet的inverted index，怎么找一个phrase（多个词）的最短组合，比如找
phrase "twitter good tool", twitter is a good tool就比twitter is good,
facebook is a better tool距离近
想法：
计算tweet和candidate phrase的“距... 阅读全帖 |
|
g*********e
发帖数: 14401 | 49 ihas1337code上面有 还有k way invert的形式 |
|
r******r
发帖数: 700 | 50 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把
整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash
_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最
大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
