r******r
发帖数: 700 | 1 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：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，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
k*******r
发帖数: 355 | 2 难道不是用inverted indexing做? |
|
w***y
发帖数: 6251 | 3 是这个思路， 但是不知道面试的时候具体怎么写code啊
好比inverted index这个 word 到docID的map 怎么实现; 每个docID 包含word个数的
count存、怎么increase.........
答用两个hashtable做的同学已经fail了， 囧 |
|
b********e
发帖数: 386 | 4 This is hard problem for people who do not have search related experiences.
for basics, you need to know how a compiled query goes through an inverted
index.
which may take long paragraph to explain.
code |
|
j***u
发帖数: 16 | 5 如果按inverted index方法
DocID_1 = { word1,word2,word3}
DocID_2 = { word2,word3}
DocID_3 = { word1,word3,word4}
那么,Hash链表
H(word1)-->DocID_1-->DocID_3
H(word2)-->DocID_1-->DocID_2
H(word3)-->DocID_1-->DocID_2-->DocID_3
如查询 word1+word2, 就是求每个word的hash链的交集 {DocID_1}
就变成求所有查询word的hash链的交集.
如果是这样的话，问题可以先简化找2个链表的重复数据，
然后根据得到的重复数据集合，和下一个链表比较 找交集 |
|
w****m
发帖数: 146 | 6 你这个就是forward index啊，和inverted index有什么关系 |
|
G******i
发帖数: 5226 | 7 ☆─────────────────────────────────────☆
guangyi ( 光一) 于 (Sat Oct 29 00:10:37 2011, 美东) 提到:
**********************************
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 ... 阅读全帖 |
|
a*******y
发帖数: 1040 | 8 kth min简单，kth max 要是用inverted inorder的话，要是那个值在left tree里，这
样return回来的不对啊 |
|
b*******d
发帖数: 750 | 9 除了上边说的suffix tree之外，
一个比较粗的想法:
很多“famous” sequence都是指数级增长，所以越界是比较快的（assume，相信几百
万个这样数之后就overflow了，那么存下来也就是几个M而已）。对于很大的数，可以
直接标记是否他们是fabonacii数or not。对比较短的数列，标记几个level的inverted
index，如上边说的3连续，4连续，5连续，6连续。6连续的话就已经是shingle了，算
得上是finger print了，查询可以非常快的。 |
|
p*****2
发帖数: 21240 | 10 The way Microsoft’s review system works, a whole bunch of Microsoft
employees just got their annual performance reviews. The September 15
paystub will reflect their new “numbers”. If they got a merit increase
the paystub will show it. If they got a bonus, it will show up there too.
This post is for those Microsoft employees who are not happy with their
review…
That September 15 date is what motivates managers to finally get busy
delivering the bad news to employees who didn’t fare so well in s... 阅读全帖 |
|
a*******y
发帖数: 1040 | 11 if you have inverted index, you can find all of the other string which are
greater than your input string, you can do this by hashmap storing the
string to string mapping, the second string contains the first string |
|
n******n
发帖数: 567 | 12 来自主题: JobHunting版 - 两个设计题 1, 怎么根据tweet做clustering??
2, 给一组tweet的inverted index，怎么找一个phrase（多个词）的最短组合，比如找
phrase "twitter good tool", twitter is a good tool就比twitter is good,
facebook is a better tool距离近??
有没有相关的书之类的，这应该是信息检索？？ |
|
M*******c
发帖数: 4371 | 13 先问问你小妹喜欢什么的。
在我看来，这两都是大方向了
power electronics can be divided into switch mode power supply, motor drive,
alternative energy, power device, converter/inverters...
Not everyone is promising in find a job in the US. But could be interesting
area for China
Power system can be divided into even more areas. In general, needs very
good at maths and (my two cents) boring.Job is usually stable.。
其实，我觉得，不一定要把路子想得那么窄。非要方向对口才行。
想想以后，中国更需要什么。 |
|
r**********g
发帖数: 22734 | 14 trie 的话只能从头搜。想fancy一点，prefix, suffix, infix都搜的话用suffix tree
想再fancy点，模糊匹配的话用inverted document |
|
P*******b
发帖数: 1001 | 15 Given a document and a query of K words, how do u find the smallest window t
hat 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 a
ll its occurrrences). This one is really hard. Could someone propose an algo
rithm in O(n)? |
|
d*s
发帖数: 699 | 16 感觉跟inverted index有关，但想不出比sorting更好的算法 |
|
f*********m
发帖数: 726 | 17 给一组tweet的inverted index，怎么找一个phrase（多个词）的最短组合，比如找
phrase "twitter good tool", twitter is a good tool就比twitter is good,
facebook is a better tool距离近
多谢。 |
|
f*********m
发帖数: 726 | 18 每个cadidant句子是一个tweet吧？从inverted index中得到的吧？ |
|
d**********x
发帖数: 4083 | 19 题目叙述太模糊了。。。
如果是只有inverted index，那貌似就完全是另外一道题了。。 |
|
a*******3
发帖数: 27 | 20 说了inverted index，应该是吧tweet good tool三个词分别拉出倒排doc list
对出现同时在三个doc list中的doc(phrase）,找最小的吧
如果找不到的话就对同时出现在tweet good或者tweet tool或者good tool的phrase找
最小的 |
|
h*****n
发帖数: 15 | 21 inverted index
IR里面的经典问题 |
|
r**h
发帖数: 1288 | 22 请教一下，使用inverted index的话，求并集或者交集如何做到小于O(N)呢？
无论是sort之后有序查找还是使用bitmap，最坏情况下复杂度还是O(N)呀 |
|
h*****n
发帖数: 15 | 23 inverted index
IR里面的经典问题 |
|
r**h
发帖数: 1288 | 24 请教一下，使用inverted index的话，求并集或者交集如何做到小于O(N)呢？
无论是sort之后有序查找还是使用bitmap，最坏情况下复杂度还是O(N)呀 |
|
s******e
发帖数: 128 | 25 为什么前面人说用inverted index 或 hash 什么的？
我看就是普通的trie嘛。从根往下走，记住沿路的叶子点（有flag的点）。 |
|
f********4
发帖数: 988 | 26 从3月中上旬到现在，面了一些小公司。。基本都挂了。。还有一个onsite。。不知道
哪年哪月能安排上。。ORZ
yelp
第一轮HR，问得全是网上能找到的题。。
一个华裔女问的，大部分都是简历。。问我database咋样，data mining，最后是
longest common prefix,一个小bug。。不过面试官没发现。。问题是跑leetcode的时
候也没发现。。真给跪了。三天后悲剧
bloomberg
电面就是invert integer。。前三十分钟都在问简历，面这个的时候刚开始刷题，大约
三月中下旬。。感觉刷题真有用。。。onsite遥遥无期的等待中
commvault
先做skill test。。大约30题，很全面。。各种知识点。。不过时间来得及google
这家从HM到面试官都是印度人。。我还去linkedin上看了下，也全部是印度人。。店面
问了一个小时概念题。。大约20道吧，从complier到multithread都有，当然也有c++基
础知识
zocdoc
面这个的时候还没开始刷题，被问了个cluster index和non cluster index，还... 阅读全帖 |
|
f******p
发帖数: 173 | 27 就比如windows explorer里面，在一个有很多子文件和子文件夹的目录里面搜素，第一
次建index可能会慢一些，但是改变搜索字符串之后就很快出结果了。
比较好奇是用的什么来做incremental search的。inverted index? |
|
A*********c
发帖数: 430 | 28 懂的不多，胡扯凑凑热闹：）
IR没啥高深的算法，基本数据结构就是inverted list, skip list。然后加上几个
matching model，用的最多的估计还是vector space或者OKAPI 25。
ML实践中真正好使的都是最基本的算法吧。比较鬼扯的那些个灌水算法，加上一堆乱七
八糟regularizer或者推convergence bound的，估计也没人care，因为实际上一碰上真
实数据全不work。要么就是仅仅在小规模数据上work，碰上大数据就要算一光年或者要
1TB内存...呵呵。
随便乱说的，大牛们再指教～ |
|
A*********c
发帖数: 430 | 29 本来我是带着娱乐的态度来回帖的，但是既然碰到了大牛，请educate我。
请告诉我任意一个数据结构，比inverted list 更重要，并且广泛地应用到了实际的
text retrieval system中.
请告诉我任意一个document retrieval model，比vector space model 或者 Okapi
BM25, Statistically significantly better for general purpose document
retrieval. Either implemented in Lucene or Lemur.
请告诉我任意一个clustering algorithm，other than Kmeans，will be your safe
first choice of clustering when you see some arbitrary data.
对于Classification，Old Stuff Like KNN works well in many cases. Kernel
algorithms are go... 阅读全帖 |
|
A*********c
发帖数: 430 | 30 懂的不多，胡扯凑凑热闹：）
IR没啥高深的算法，基本数据结构就是inverted list, skip list。然后加上几个
matching model，用的最多的估计还是vector space或者OKAPI 25。
ML实践中真正好使的都是最基本的算法吧。比较鬼扯的那些个灌水算法，加上一堆乱七
八糟regularizer或者推convergence bound的，估计也没人care，因为实际上一碰上真
实数据全不work。要么就是仅仅在小规模数据上work，碰上大数据就要算一光年或者要
1TB内存...呵呵。
随便乱说的，大牛们再指教～ |
|
A*********c
发帖数: 430 | 31 本来我是带着娱乐的态度来回帖的，但是既然碰到了大牛，请educate我。
请告诉我任意一个数据结构，比inverted list 更重要，并且广泛地应用到了实际的
text retrieval system中.
请告诉我任意一个document retrieval model，比vector space model 或者 Okapi
BM25, Statistically significantly better for general purpose document
retrieval. Either implemented in Lucene or Lemur.
请告诉我任意一个clustering algorithm，other than Kmeans，will be your safe
first choice of clustering when you see some arbitrary data.
对于Classification，Old Stuff Like KNN works well in many cases. Kernel
algorithms are go... 阅读全帖 |
|
f******s
发帖数: 25 | 32 (⊙o⊙)哦， 没有注意maximize len*len的条件。
那就把所有的string都在inverted index中扫一遍，然后选一个符合条件的最长串和他
匹配。
需要事先按照串的长度sort一下。
找符合条件的最长串可以用一个bitset，unset所有不符合条件的串， 然后用位操作找
出least significant 1的位置就是最长的串 |
|
w*******i
发帖数: 186 | 33 感觉字典这题如果做成inverted index也可以的，也是o(n)预处理和match，但如果有
低频字符的话先找低频字符，速度应该会很快吧。 |
|
x******0
发帖数: 178 | 34 用了inverted index之后不是还要用O（N^2×t） 遍历所有的pair和word，t是word数
目，吗？ |
|
z*******3
发帖数: 13709 | 35 不过min heap还是max heap真心不重要
你就是做成min&max heap又怎样？两头都能pop就好了
能pop最小也能pop最大的，反正insert效率都是一样的
这只是定义，对方的理解是把min想成你存最小值了
就象空穴来风，明明文字上意思是言之有据
但是无数人认为这个是扯蛋的意思
纠结这个就有些书呆了，无所谓，互相理解一下
如果你想结合理论的话，pirorityqueue就是基于heap的实现
这个是我从swjtuer那边偷来的
多线程对方考点还真的不是fairness strategy
对方其实目的很简单，就想知道你知道不知道最常用的core java类是什么
inverted index那题估计也不是纯粹考理论，应该是希望看到类似半海那种答案
半海遇到过类似的问题，问的是distributed lock
半海答案很简单，用zookeeper
就过了 |
|
m*****n
发帖数: 2152 | 36 对doc里出现的word建inverted index的那道题，烙印要的最佳答案是什么？
是用B-Tree吗？
情况 |
|
p*****e
发帖数: 537 | 37 这道题自我感觉不是在考multithreading，因为从头到尾都没有提到thread，最后那个
thread的小题和这个inverted index没啥关系，这一轮应该是在考大数据处理。 |
|
c****8
发帖数: 76 | 38 Inverted Index 那个分布式的解法，谁能给我连接？想学习学习。 |
|
z*******3
发帖数: 13709 | 39 不过min heap还是max heap真心不重要
你就是做成min&max heap又怎样？两头都能pop就好了
能pop最小也能pop最大的，反正insert效率都是一样的
这只是定义，对方的理解是把min想成你存最小值了
就象空穴来风，明明文字上意思是言之有据
但是无数人认为这个是扯蛋的意思
纠结这个就有些书呆了，无所谓，互相理解一下
如果你想结合理论的话，pirorityqueue就是基于heap的实现
这个是我从swjtuer那边偷来的
多线程对方考点还真的不是fairness strategy
对方其实目的很简单，就想知道你知道不知道最常用的core java类是什么
inverted index那题估计也不是纯粹考理论，应该是希望看到类似半海那种答案
半海遇到过类似的问题，问的是distributed lock
半海答案很简单，用zookeeper
就过了 |
|
m*****n
发帖数: 2152 | 40 对doc里出现的word建inverted index的那道题，烙印要的最佳答案是什么？
是用B-Tree吗？
情况 |
|
p*****e
发帖数: 537 | 41 这道题自我感觉不是在考multithreading，因为从头到尾都没有提到thread，最后那个
thread的小题和这个inverted index没啥关系，这一轮应该是在考大数据处理。 |
|
c****8
发帖数: 76 | 42 Inverted Index 那个分布式的解法，谁能给我连接？想学习学习。 |
|
D***0
发帖数: 138 | 43 将近三个月里两次面它家，
第一次折在第一个电话onsite了，一个巨长的名字的老印，coding题不难，看一段代码
，指出哪有问题，第二题是删除linkedlist里的一个node，就用一个指针。然后就是写
sql query，老印说要用having，我说ok，然后就写了一个带having的，然后第二天就
收到拒信，说db太弱。。。这个确实没机会练，也没机会接触。
过了一阵子网投另一组，然后店面，计算一个数组的inverted元素的个数，没见过，直
接给了O(n^2)的，然后问如何改进，实在没想到，就说应该用binary search或者merge
sort的，最低也就是O(nlogn)了，店面过了，然后是一轮code challenge，不难，2个
小时做完发过去。然后onsite，
5轮，每轮一个小时，尼玛，其中一轮还是打电话，
1 像是欧洲人， 一道简单题，不记得了，做完了，面试官说good，然后照相，然后就
是design一个system，说他们现在做这个，好像是个什么连续的incoming字符串流，如
何存储，query，如何得到当前某个metric的lifetime的min... 阅读全帖 |
|
S******1
发帖数: 216 | 44 来自主题: JobHunting版 - FB 面筋
Minimum
写一个考虑顺序的inverted indexing做法
//7:10
//给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
substring，结果是AUB
int findMinWindow(String s, String p) {
if (s == null || p == null || s.length() < p.length())
return -1;
if (p.isEmpty())
return 0;
Map> indexMap = new HashMap
Integer>>();
for (int i = 0; i < s.length(); i++) {
if (!indexMap.containsKey(s.charAt(i)))
indexMap.put(s.charAt(i), new Arra... 阅读全帖 |
|
c*******r
发帖数: 610 | 45 auyin 说得是对的，其实就是inverted index的简单版本吧。
基本思想应该是：对每一个词，记录它的index （从小到大）。然后对于s1, s2，计算
索引
之间的最小值，就是两个词之间的最小距离了。
glassdoor上面原题 |
|
c*******r
发帖数: 610 | 46 auyin 说得是对的，其实就是inverted index的简单版本吧。
基本思想应该是：对每一个词，记录它的index （从小到大）。然后对于s1, s2，计算
索引
之间的最小值，就是两个词之间的最小距离了。
glassdoor上面原题 |
|
Z**********4
发帖数: 528 | 47 有快的思路嘛？
本来想着按照字母顺序做inverted index，这样找没有相同字母的string就是集合操作
了。
不过好像还是很傻逼这个办法。 |
|
|
h*********g
发帖数: 51 | 49 PhD summer intern，都是11月面的
F第一轮
Q1：两个string s1, s2, 比较前n个的字符的大小，n可能比s1, s2的长度长
Q2：每个user都有很多email联系人,,把这些user分
组，一个组内的user 可以通过一些共同的Email account连起来，还有一些改进
F第二轮
聊了很多的research和以前的project
Q1：一个文件里存着代码和注释，注释在/××/中间，要求print所有line除了注释
G家
Interview 1
有一些set of names, 比如first name, middle name, last name,写个iterator打印
名字的组合
Interview 2
Longest Consecutive Sequence
Simplify path 变型。。具体要求不太记得了
Interview 3 （是国人大哥）
聊了以前的project，题目是Interleaving String的一个变种，也是用DP做
T
Q1:设计数据结构快速查找一... 阅读全帖 |
|
i*******e
发帖数: 7 | 50 用bucket是不是可以放弃double linked list直接上array就好了，array size = W，
index = frequency - 1. 这样是不是省点事？hashmap works as inverted index,
key = hashtag, value = index of bucket array |
|
