o****e
发帖数: 916 | 1 文件的index是一个伪MD5（读取部分内容做hash）
button下面的文字是有的，程序设置，界面下面。中文界面应该缺省会显示，其它不会
，因为文字长短很难控制。界面有很多设置可以调整，比如按钮大小等。
下一首歌的提示在当前歌曲结束前5秒会出提示，或许可以把这个5秒弄成可调参数，或
者多次提示，比如1分钟时提示一下，30秒再提示一下
mplayer的消音代码很老了，估计没那么fancy
评分是一直想弄，主要是算法比较复杂，又涉及到性能问题（要把歌曲的原唱提取出来
做比较），慢慢来了。
pan
source |
|
n****t
发帖数: 241 | 2 面试官：老印，英语挺清楚的
1. introduce yourself.
2. Does Java pass by reference or pass by value?
3. collection / how to casting data type.
4. C++/ virtual fuction definition and effect...
5. algorithm question: input int arrayA[], int sum.
find 多少pairs in arrayA[]的和是sum...
return count...
先说了idea， 然后让我写code，然后读给他听。。。
我先问的是不是unique的 arry...
6. design a web spider . for example. exit after get 500 pages.
我说用graph存pairs(url,content);
bfs遍历。。。 check 内容是否重复可以采用md5
7. amazon有15millon users,and some new contents |
|
b******7
发帖数: 79 | 3 我刚刚面试amazon被问得，首先，这是一道老题，后悔当时看到这道题的时候没仔细研
究。以前我在版内看过这道题，但是没有人提出正确解，我也就大概想了想，没仔细想
，结果今天吃亏了。
一个分布式文件系统，7个server, 原来的文件用MD5 hash后分布到这7个server中的某
一个(比如hash%7)，现在这些server快满了，就增加了7个server, 这样新文件来了可
以放到这些新的server上面。问题是，我们不能挪动原有server的文件，旧的文件仍旧
可以被访问。那么我们怎么改这个hash系统以至于新，旧文件都可以被正常read,
write。举例，如果新文件来了，我们如果还是hash%7，那么就会放到旧的server上，
但是如果放到新的上，那怎么改hash?
肯定要用hierarchical 的hash,比如，如果hash%7==1, 这些hahs被再次hash为0，1，
为0的去旧server,1的去新server,但是这个缺点是旧的已经满了，而且给你一个hash,
旧的文件属于新的还是就得server没法得到。
希望牛人指点！！！非常感谢！ |
|
g*******y
发帖数: 1930 | 4 用一个hashset来存旧server的所有文件的MD5，这个hashset的size肯定很小，相对于原来存文件本身来说
新文件就%7以后存到server上，query的时候，先在hashset上查，然后确定在旧server还是新server上
server. |
|
N*D
发帖数: 3641 | 5 正确的做法是backfill，其他解法都是hack
我刚刚面试amazon被问得，首先，这是一道老题，后悔当时看到这道题的时候没仔细研
究。以前我在版内看过这道题，但是没有人提出正确解，我也就大概想了想，没仔细想
，结果今天吃亏了。
一个分布式文件系统，7个server, 原来的文件用MD5 hash后分布到这7个server中的某
一个(比如hash%7)，现在这些server快满了，就增加了7个server, 这样新文件来了可
以放到这些新的server上面。问题是，我们不能挪动原有server的文件，旧的文件仍旧
可以被访问。那么我们怎么改这个hash系统以至于新，旧文件都可以被正常read,
write。举例，如果新文件来了，我们如果还是hash%7，那么就会放到旧的server上，
但是如果放到新的上，那怎么改hash?
肯定要用hierarchical 的hash,比如，如果hash%7==1, 这些hahs被再次hash为0，1，
为0的去旧server,1的去新server,但是这个缺点是旧的已经满了，而且给你一个hash,
旧的文件属于新的还是就得server没法得 |
|
|
r****o
发帖数: 1950 | 7 谢谢，再问一下，你这里所说的签名是什么意思呢？MD5? |
|
t****t
发帖数: 6806 | 8 其实大家说的求和, 求平方和, 求XOR都是一个意思, 就是用一个hash function或者说
signature, 只是这里要求invariant to element order
普通的signature很常见的, 比如说CRC32, MD5之类, 不是invariant to element
order, 可以做一些诸如验证下载是否正确的事情. 这是一个快速的方法, 特别是正确
序列的signature已知的情况. 它不能保证检测正确, 但是它能保证检测错误, 在随机
错误的情况下, 检测正确的成功率也很高.
我觉得你要能答出这些, 就差不多了. 关键是given random error pattern, it has
high probability of successful. 如果是人为forged error pattern, 那么再另说. |
|
k*n
发帖数: 150 | 9
...
size+md5, and consider MR if corpus is too large
This is interesting... I don't think search result will be acommpanied...
my solution:
1. find synset, usually nearby queries tend to be synonyms, so
for each query bigram, count their occurrence, set a threshold
for indicating a pair of synonyms
2. judge multiple meanings via synonyms, that is : a ~ b, and a ~ c
then a is likely to be candidate...
英语太差，所以更得献丑来练练了，bow |
|
g**t
发帖数: 49 | 10 Now I think it is not too hard to find such hash function :)
Simply calculate md5 sum of the record then mod 4G and get the index |
|
m****y
发帖数: 28 | 11 我来说个比较可行的思路吧
首先人家给了disk space就是让你放些中间结果的
我的想法是用hash来先把data record粗略归类到很小的子集，然后在每个子集里面找
重复就可以了。
1. 对每个data record，我们生成一个形如的ID，假设用md5作
为hash函数，再假设record number占用4个字节，那么每个ID的大小是16+4=20字节。
2. 生成ID的时候，把它归类到一个较小的子集，写到磁盘上去。对于2^30个record，
我们根据(hash mod 2^13)的结果，把它分成2^13个子集，每个子集存成一个文件，每
个文件包含大约2^17个record的ID，这样子集文件的平均大小大概是2^17*20=2MB左右
，总共需要大约2^30*20=4GB的磁盘空间。
3. 最后就是把这么些子集文件读到内存里，然后找重复。显然重复的data record的ID
肯定属于同一个子集，简单的办法是把这2MB的数据排个序，对于重复的hash再根据
record number去读实际的data record来作比较。这样基 |
|
v****s
发帖数: 1112 | 12 for https , u need to pay more for the host server company.....
i'm running our CSSA forum and I tried to sign up for https, but it cost
like 200-300$ / yr so I gave up....
besides, the md5 of some weak passwords can be found on line and can be hack
too..... |
|
g*****g
发帖数: 34805 | 13 Start with sorting file size.
Then for files with same size, compare byte by byte.
If other attributes can be carried, which is typical
for DB storage, you can save MD5 and use it for comparison.
out.
) |
|
s*i
发帖数: 388 | 14 right, that's my 2nd improvement i gave during the interview. but i don't think we need to explicitly "sort" it, 'coz that's O(nlogn).
assume the file size ranges from 1KB to 1GB, we can use a table of 1M size,
and put the files into this file_size_array, then after this round, check
the md5 for those files fallen into the same slot.
but the interviewer still push me after this stage.....
any more ideas? thanks.... |
|
t**n
发帖数: 272 | 15 1M个字符用hash并不好，碰撞的可能比较高，如何选hash函数貌似有个公式的，wiki上有
1M个file, 用MD5啊，碰撞几率很低 |
|
a*d
发帖数: 47 | 16 The complexity of computing hash function is also a key factor, because it
is very common for hash function to be called inside a loop.
MD5 is good in terms of collision rate, but it is expensive to compute.
There is no cure-all hash functions for all applications. Many factors need
to be considered for real application.
上有 |
|
|
e***l
发帖数: 710 | 18 不是考精确算法，想想MD5...
另外2^256这个数字已经没有实际意义了 |
|
l****e
发帖数: 131 | 19 http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V24-
2&_user=10&_coverDate=12/31/1994&_rdoc=1&_fmt=high&_orig=search&_origin=se
arch&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&
_userid=10&md5=5b83f3e8a54c8b5ae95fed4678f0d0fa&searchtype=a
Microbiological stability of wastewater sludges from activated sludge
systems
Thanks |
|
|
k****n
发帖数: 369 | 21 太感谢了！
suffix tree，不过真的要白板编么？能不能写下阿
key is to reduce disk access
if it is possible to keep it in memory, then first bucket files with sizes,
then inside the bucket use (MD5 => file) hash map.
ob)
thread
have no idea，求布道
生成正方形uniform分布的点，丢弃圆外面的点
笛卡尔坐标系就麻烦多了，距圆心距离不同概率不同
Open question好多，我最讨厌这种，谁知道面试官prefer什么答案阿 |
|
w****r
发帖数: 245 | 22 第一个直接找
第二个不一定要放整个文件，MD5是不错的选择
第四个感觉就是让node自己定期去哪里下新image，然后自动重装，加速的话个人认为
是指整个系统被block的时间，比如可以在有些node更新中的情况下，其他node继续用
旧版本工作，用扩散的方法太容易出错。。实际中应该很少用
第七个要问很多问题，比如这个定期得间隔是多少，扫描一个sensor要多久，如果坏了
需要最慢多久探测到，判断错误的话有没有什么后果。这在实际应用中可能都有
requirement的，根据这些条件再设计具体
方法
方法 |
|
s***c
发帖数: 50 | 23
第二个问题我也用了类似的回答。把文件按size分类。然后对同样大小的文件，用某种
编码计算signature。signature相同的就是内容相同。同时用hash表来加速signature
的匹配查询。可是那个面试官说任何编码都会有conflict，也就是不同内容生成相同的
编码。其实MD5的编码可以做到重复率低于硬盘故障率。 |
|
H***e
发帖数: 476 | 24 我觉得第一道题说的也不是很清楚啊
是不是每个字符串特别长？需要用它的hash（比如md5) 做key来存进hashtable来判断
重复？
能不能把constraints说清楚电啊？ |
|
S**I
发帖数: 15689 | 25 ☆─────────────────────────────────────☆
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 | 26 ☆─────────────────────────────────────☆
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... 阅读全帖 |
|
H***e
发帖数: 476 | 27 有个超大文件，每行存一个string,要求去除重复，如果直接hash行string的话，放不
进内存
如果存 md5(string)做为 key 存进hashmap,有可能存下，但是有可能不同string重复
key,我在想，
我可以把hashmap 的value用来存此string在原文件中的行数，那么重复的时候，可以
去原文件，看一下，是不是真的重复
只是这样如果不能直接读某行string的话，sequential的读花费就太高了。 |
|
z**********g
发帖数: 209 | 28 请问你的回答是不是和下面的介绍rsync一样？
rsync算法要解决的问题很简单：A和B两个文件在两台服务器中，要将A同步到与B一致
，要求尽量减少同步带来的网络传输开销。
rsync基本算法
先说基本的rsync算法，并不复杂，简单的说是三步：
1、按固定大小将A分为多块，每块都计算出一个32位的滚动哈希值和一个128位的MD4（
有些也用MD5），发给B一端。
2、B一端从位置0开始按的同样块大小的滚动哈希值，查找看是否命中A给的某个滚动哈
希值，若匹配，则表明B文件中的这块内容与对应的A中的那块内容很可能是一致的，但
由于32位的哈希值强度不够，因此再计算MD4，若还是匹配，则确认是一致内容，这时B
发给A端匹配的段号。对于那些不能匹配的内容，则发给A端原始内容。
3、A端得到B端给的匹配信息，构造一个与B一致的复本，若是匹配的块，则拷贝原A文
件中对应的块，若是不匹配内容则追加之。
滚动哈希值的设计基于Adler32算法，使得2~K+1字节的哈希可以根据1~K字节哈希和1、
K+1字节的内容快速计算得到，这可以提高从位置0开始依次计算滚动哈希值的效率。
据试验一般来说块大小取5... 阅读全帖 |
|
T****y
发帖数: 36 | 29 来自主题: JobHunting版 - G家电面题 我就说把数据砍成小块分开运，每块做hash md5 checksum分开存储 blabla
到达目的地后逐一验证并组合，如果哪块丢数据了就再送那块就行了。
也可以用网络送，（理论上） 方式同上。
感觉有点若，对方也没给啥评论。 |
|
w***y
发帖数: 6251 | 30 来自主题: JobHunting版 - G家电面题 你们说的md5/rsync我都没听说过呀, 咋整捏, 现在恶补这块也来不及了
这种题目是不是也跟background有关呢? 我好像从来没有做过这个方向啊 |
|
r******r
发帖数: 700 | 31 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：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，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
r******r
发帖数: 700 | 32 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：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，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
O******i
发帖数: 269 | 33 G的：
3. 一个硬盘上全是文件，求把同样文件不同文件名去重怎么做
是否要hash一下比如用MD5? |
|
z********c
发帖数: 72 | 34 恩，他跟我讨论了什么hash比较好，我说了比如k base digit modular或者MD5 |
|
y**********u
发帖数: 6366 | 35 2. merge 2颗bst是不是第一个问题的后续？
第一个问题隐含inorder traversal
所以merge 2颗bst可以转换成2个linklist的merge 。。。
3. 文件名去重复，难道就用md5/sha1这样的hash?
4. os的调度，太复杂了，以前做个berkeley schedular就爆了 |
|
r*****d
发帖数: 1924 | 36 【 以下文字转载自 WashingtonDC 讨论区 】
发信人: Westridge (西岭), 信区: WashingtonDC
标 题: Java开发人员知识点（更新）
发信站: BBS 未名空间站 (Wed Apr 18 00:03:19 2012, 美东)
Java开发人员知识点
1.听说过James Gosling，SUN和Oracle公司。知道网上下载Java的地址，在哪讨论Java
。练习过Java在Windows下的安装和配置。知道Java应用系统中常见的几种license和JCP。了
解bytecode和Java在不同系统下可以轻松移植的原理。
2.懂得基本的Java编程和行命令格式。了解面向对象的编程思路。
几个基本点：Java基本语法和控制结构，命名和代码风格，结构化，对象封装，继承，
抽象，多态，接口，异常处理，堆空间，栈空间，垃圾回收器，static，this，
synchronized，annotations，JUnit，JDBC，JSP/servlet
Java Core APIs: java.lang，java.util，java.io，java.a... 阅读全帖 |
|
l*****z
发帖数: 3022 | 37 那家公司啊？
image这题要是duplicate images 是binary file exactly the same, 搞个md5就行了
，要是会有文件格式转换，或重压缩编码。。。那就要上image fingerprint鸟。
想到heap，也不是一般人啊。
。问为什么用base64， 答，只知道base64，不太懂image processing
啥，reducer 做啥。答，不清楚，只知道大概。 |
|
w**z
发帖数: 8232 | 38 我好像也提到了md5 。。。反正把知道的全提了一下。
公司本身是internet company， 和image processing 没啥关系。 |
|
s*********5
发帖数: 514 | 39 这个是不是要先用SHA-2（better and stronger than MD5)把所有document搞出一个
unique hash value, 然后搞个hash table, 通过ID找SHA-2. 再做个reverse lookup
table, 每个SHA-2都列出其相应的ID list
6.两个白人SDE，主要是其中一个在面，另外一个自始至终没说话。
问题: 有一个大的catalog，总共有500Million个entry，每个entry内容是 （ID，
document），每个document大小约10KB，不同的ID对应的document可能相同，怎样设计
一个程序，对每个给定的一个ID，找出与该ID对应着相同的document的所有其他ID。
Follow Up: 如果每台机器内存只有1GB，硬盘100GB，怎么做 |
|
C**5
发帖数: 202 | 40 每个文件内容hash（例如md5) 然后放到hashtable 可以识别文件重复 |
|
S*******C
发帖数: 822 | 41 我很多demo都是文件上传于下载，生成验证码，md5加密，java mail，SAX parser，留
言板，购物车等等。有点类似于北大青鸟的项目，呵呵
我完全照抄的也不多，大部分是借鉴修改啊 |
|
s****n
发帖数: 70 | 42 排序的话代价略高了，如果用Hashmap来做的话是O(n)的，如果有很多很多的Incoming
list的话，最好的办法应该是先计算整个list的hash code(比如sha1, md5)，效率高很多 |
|
A***o
发帖数: 358 | 43 看MD5 digest，相当于做个hash join |
|
r****s
发帖数: 1025 | 44 request来来往往的，不能用内存地址。
用64位MD5差不多了。 |
|
g*****g
发帖数: 34805 | 45 我老提供个思路吧。从尾部截取一个固定长度，比如最长1K，以md5做hash，以hash值
为key放入Cassandra DB，原始url为column name，column name是排序好的. 产生一个
UUID来作为tinyurl的索引。Quorum Read/Write
也就是说用hash粗比较，用原始url在相同hash里面做两分比较。这是个分布式数据库
，整个架构可以linear scaleout。
另外，既然是公开的服务，被猜到索引并不是问题，也不会是要求。 |
|
m*****7
发帖数: 4 | 46 用户量不大的话就md5一下然后存在mysql里面就行了。在mysql admin里面先把table建
好比如有两个column：USER | PASSWORD，然后就insert进去就OK。 |
|
A*****e
发帖数: 26 | 47 two c++ positions
1. interviewer: one Korean guy
C++ basics: public, private, struct, etc. 秒掉
C++ : the member functions of map,list, vector, how to resize vector, how
to delete the middle element in a given list, time complexity。 Nothing
difficult for me. list in stl is actually doubly linked list, so remove one
member would take O(1) time, but the reviewer seemed to disagree. Ask is
there a size member available for list in STL. A: i think so. I: er..ok (
seems he did not know that)
Programm... 阅读全帖 |
|
c*********t
发帖数: 171 | 48 我猜第一个问题是要考察你会不会用hash。通常很大很大就是说你只能从头到尾扫描。
我对（1）的解法：
1、对每一个句子计算hash，可以用MD5，也可以用SHA256，结果存入另一个文件。
2、对所有结果进行排序（hash值算一大整数）
3、遍历此排序后文件，如前后均不相等，说明此数对应的句子只出现一次。
two" |
|
c*********t
发帖数: 171 | 49 我这个hash值不是32位整数，而是256位整数。理论上有可能碰撞。如果让你碰到，赶
快写论文海龟。山东大学那个女教授让美国废了MD5。好虫让美国废了SHA256！
谷歌就是有钱任性。好虫你是谷歌的么？ |
|
t**r
发帖数: 3428 | 50 每个上传给开一個新thread.
用udp传, chunk by chunk。 加checksum验证 避免用tcp，慢。
存放地點放到缓存。不要直接写磁盘，异步往磁盘写 可以增加吞吐。
数据直接在客户端md5加密。安全性基本没问题了，处理好key的交换。
验证数据格式，只存储可识别的文件，未知格式文件拒绝存储。 |
|
