l*****o
发帖数: 214 | 1 一点想法，不知到对不对：
用doubly linked list
step 1. scan text, if in the target word set, add to doubly linked list,
until the doubly linked list has all the target words: you get [word1, word1
, word2, word1, word1, word3]
step 2. from the end of the linked list, go backwards, until find all the
words in target word set, remove the words before, and the result is a
probably shorter list with first element A: you get [word2, word1, word1,
word3], and record the span
step 3. keep scanning the text, push wor... 阅读全帖 |
|
j***u
发帖数: 16 | 2 如果按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个链表的重复数据，
然后根据得到的重复数据集合，和下一个链表比较 找交集 |
|
j***u
发帖数: 16 | 3 就是
i.e. m = 3 = word1 + word2 + word3,
1>先求 union(m) = H(word1) + H(word2) + H(word3) 链表里所以doc_id 数目（有重
复)
这个union 包括 同时有3个word的doc_id, 也有只有1个或2个 的doc_id,
2>求交集 intersect(p = m) = H(word1) 交 H(word2) 交 H(word3), 得到的 集合就是
同时含有3个word的doc_id 数目,
3>结果 sum (p < m) = union(m) - 3 * intersect( p = m) (去掉所有 同时含3个
word的doc_id) |
|
r*****n
发帖数: 2 | 4 onsite之后有个interviewer旅游去了，4周之后才拿到feedback，提交HC之后又一周没
动静了，给recruiter发信也不回。实在等得心烦。发个面经就算挂了然后move on吧。
是fresh master.
两轮电面，都是经典题。写完2个题还有点时间，讨论了一个设计题，我到现在也不理
解题意。
有一种新型存储设备，特点是：
1. 价格贵，稳定性高
2. 可读写，但写入的内容不能修改
如何利用它的特点设计一个存储系统。在聊天过程中增加了一些条件，如果有个人写了
个脚本不停用同样的内容写你的文件系统怎么办，怎么判断每次写入的东西是不是新的
呢。
4轮Onsite 3个印度人一个欧洲人。都是从简单的题开始，不停改改改。都讨论了项目
经验，还问得很细。写完代码都是要照相的，我有个题是开始写得挺干净，后来条件加
加加就改花了，然后interviewer掏出手机拍了一张。。我觉得是不是可以在写完第一
版之后就请他拍一张先。。。
1.一个binary search变体。 写完之后开始抠代码，说如果把终止条件从low<=high 改
成low阅读全帖 |
|
b***p
发帖数: 700 | 5 这个是python solution, worst case 是O(n^2). 比普通的Greedy Solution, 有两个
改进
1. 计算bit map of word, and AND operation to check if there is common char
2. 遍历是从最长的word开始
还有一个可以改进的地方是，利用元音字母，用word_len+vowel 作key，减少不必要
的compare
class DiffWordsMaxLenProduct:
def __init__(self):
# dict: word -> word char bit map
self.dict_word_bit = {}
# dict: word_len -> [word1, word2, word3...]
self.dict_word_len = {}
#
# compute the bit map of word char
#
def bit_word(self... 阅读全帖 |
|
f*****r
发帖数: 229 | 6 I think about how to use cache line. For example, if the L1 cache line is 4
words (16 bytes), we move word1 to register a, then move word2 to reg b, then
move word3 to reg c, then move word4 to reg d; after those operations, move
rega to dest1, regb to dest2, etc. Is it faster?
Another possible way is using MMX mode. In each operation you can operate 16
bytes (or more). maybe MMX2 can give you better choice. But I guess that this
may be only good for bulk data copy, since mode switch has some ov |
|
r***e
发帖数: 31 | 7 Maybe I did not describe the problem clearly, the attribute A1 is a string,
how can I find all the records that have the value in A1 has the format "word1
word2 word3".
the |
|
B*****g
发帖数: 34098 | 8 1. 有很多种ETL tools
2. 啥数据这么大，怀疑mysql能存这么大的数据。
3. word0 - word3字里面有空格吗？number_0是number吗，里面有没有空格？ |
|
