x****e
发帖数: 55 | 1 我的数据格式是这样的
1，2，3，4
21，21.2,9,11
...
数据量很大，几百万条
想要快速检索，请问有什么HASH算法能解决这个问题？
多谢！ |
|
i******r
发帖数: 861 | 2 data A;
Input x1 $ y1;
Cards;
A 10
B 20
C 30
;
Run;
Data B;
Input x2 $ y2;
Cards;
A 1
C 8
D 9
;
Run;
希望得到：
x1 y1 x2 y2
A 10 a 1
B 20 . .
C 30 C 8
. . D 9
我希望用hash table的方法 |
|
b*********n
发帖数: 2975 | 3 Hash table不是这么玩儿的, 你这个用merge 就行了 |
|
s*********h
发帖数: 6288 | 4 有点不是很明白它的理念。
比如用来寻找相似项。原本需要过O(N^2)遍，但是每一次比较需要的运算量比较大？。
使用LSH也是需要过至少O(N^2)遍，但是先通过简单的比较来把可能相似的项hashing
to the same bucket，然后再从筛选过的结果中寻找？
所以减少的其实是复杂运算的次数？ |
|
l******n
发帖数: 648 | 5 这个很好理解
比如你做一个数据查询服务，用来存储所有的饮料
比如coke，和pepsi，是很类似的饮料，相比较juice或者酒
这个similarity你是知道的
如果用最原始的办法存储，比如是原始的明文
coke
7 up
orange juice,
vodka
stella beer
.... 此处省略一万行
pepsi
你不能把这些东西都存在内存里，太大了，想想一个字符多大。你只能存在disk上。
一个简单的查询，输入coke，那么和它相似的饮料是什么？你需要在disk上，一个一个
的看，每个entry都要用你已经知道的similarity metric看，哪个算是相似。比如查到
pepsi，你发现similarity score是0.9 － ok找到了，return它。
这个查询要在disk上，很慢。
这时候就要用lsh。每个长长的字符串，都会变成一个很短的binary string 比如
0101010
而且是binary string的similarity，比如不同的个数，和原来你知道的字符串的
similarity近似
binary的字符串是很小的，因为是binary，一... 阅读全帖 |
|
s*********h
发帖数: 6288 | 6 有点不是很明白它的理念。
比如用来寻找相似项。原本需要过O(N^2)遍，但是每一次比较需要的运算量比较大？。
使用LSH也是需要过至少O(N^2)遍，但是先通过简单的比较来把可能相似的项hashing
to the same bucket，然后再从筛选过的结果中寻找？
所以减少的其实是复杂运算的次数？ |
|
l******n
发帖数: 648 | 7 这个很好理解
比如你做一个数据查询服务，用来存储所有的饮料
比如coke，和pepsi，是很类似的饮料，相比较juice或者酒
这个similarity你是知道的
如果用最原始的办法存储，比如是原始的明文
coke
7 up
orange juice,
vodka
stella beer
.... 此处省略一万行
pepsi
你不能把这些东西都存在内存里，太大了，想想一个字符多大。你只能存在disk上。
一个简单的查询，输入coke，那么和它相似的饮料是什么？你需要在disk上，一个一个
的看，每个entry都要用你已经知道的similarity metric看，哪个算是相似。比如查到
pepsi，你发现similarity score是0.9 － ok找到了，return它。
这个查询要在disk上，很慢。
这时候就要用lsh。每个长长的字符串，都会变成一个很短的binary string 比如
0101010
而且是binary string的similarity，比如不同的个数，和原来你知道的字符串的
similarity近似
binary的字符串是很小的，因为是binary，一... 阅读全帖 |
|
H***a
发帖数: 189 | 8 想把FreedomPop的VoIP username/password弄出来装到其他SIP client上，发现
password是hashed了，以前iPhone上的的.linphonerc 里的property name是password,
现在是ha1. 放到SIP client上就报错，401-unauthorized
哪位大侠有新的功略把password 还原出来吗？
谢谢！ |
|
r******r
发帖数: 700 | 9 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：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 | 10 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：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，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
s**********o
发帖数: 14359 | 11 【 以下文字转载自 JobHunting 讨论区 】
发信人: rongxuer (蓉儿), 信区: JobHunting
标 题: 如何秒杀99%的海量数据处理面试题
发信站: BBS 未名空间站 (Thu Apr 5 02:08:57 2012, 美东)
海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的... 阅读全帖 |
|
发帖数: 1 | 12 左起：查济民女儿，周光召，刘璧如，王小云，杨振宁，姚期智
来源 | 《数学文化》2019第10卷第2期
访问整理 | 王涛、王坤
昨天 （9月7日），2019年“未来科学大奖”数学与计算机科学奖宣布授予密码学
家王小云，奖励她在密码学领域的开创性贡献。王小云创造了一种毁灭性的密码分析方
法，破解了一个又一个国际通用的算法。那么，她的数学和密码人生是怎样展开的呢？
王小云，1966年出生于山东诸城，1981年进入诸城一中学习，1983年起就读于山东
大学数学系，先后获得学士、硕士、博士学位，师从潘承洞院士；1993年毕业后留校任
教，历任讲师、副教授、教授；2005年6月受聘为清华大学高等研究院“杨振宁讲座教
授”。现为第十三届全国人大代表、中国科协女科技工作者专门委员会委员、中国密码
学会副理事长、中国数学会常务理事。
王小云的主要研究领域为密码学。在密码分析领域，她系统给出了包括 MD5， SHA
-1 在内的系列 Hash 函数算法的碰撞攻击理论，提出了对多个重要 MAC 算法 ALPHA-
MAC、MD5-MAC 和 PELICAN 等的子密钥恢复攻击，以及 HMAC-MD5 的... 阅读全帖 |
|
i**********e
发帖数: 1145 | 13 My code found two valid answers for the following input in about 3 secs (
obviously not as good as grass, but the algorithm is easier to code).
Input, A = {2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23
24 25 26 28 29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56 }
Answer:
2 7 2 4 8 8 8 10 7
7 10 8 8 8 4 2 7 2
grass, can you explain whether your code generates the solution {7 10 8 8 8
4 2 7 2} ?
Test cases:
A = {7,10,5,2,8,3}
Answer:
2 5 3
3 5 2
A = {1,1,1,2,3,2}
Answer:
1 1 1
A ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 14 My code found two valid answers for the following input in about 3 secs (
obviously not as good as grass, but the algorithm is easier to code).
Input, A = {2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23
24 25 26 28 29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56 }
Answer:
2 7 2 4 8 8 8 10 7
7 10 8 8 8 4 2 7 2
grass, can you explain whether your code generates the solution {7 10 8 8 8
4 2 7 2} ?
Test cases:
A = {7,10,5,2,8,3}
Answer:
2 5 3
3 5 2
A = {1,1,1,2,3,2}
Answer:
1 1 1
A ... 阅读全帖 |
|
|
f********t
发帖数: 6999 | 16 【 以下文字转载自 JobHunting 讨论区 】
发信人: mudhoof (正在长牙的羊), 信区: JobHunting
标 题: 这么热闹, 我也报Google offer
发信站: BBS 未名空间站 (Tue Feb 23 12:32:47 2010, 美东)
今天刚刚通知的, 特别感谢一起讨论的krone, geniusxsy, hnm, 特别是blaze教了我很
多, 还要特别感谢mitbbs59的总结帖
一起报offer, 好事成三, 大吉大利, 包子分光为止
贴下我的复习材料
题目大全:
http://www.spellscroll.com/viewquestions/?tag=algorithm
http://www.thecareerplus.com/?page=resources&cat=10
http://interviewcyclopedia.blogspot.com/
http://www.doctorinterview.com/A.html
http://toptechnotes.blogspot.com/search/label/algorith... 阅读全帖 |
|
w********2
发帖数: 632 | 17 IPMI 2.0 RAKP Authentication Remote Password Hash Retrieval
More recently, Dan Farmer identified an even bigger issue with the IPMI 2.0
specification. In short, the authentication process for IPMI 2.0 mandates
that the server send a salted SHA1 or MD5 hash of the requested user's
password to the client, prior to the client authenticating. You heard that
right - the BMC will tell you the password hash for any valid user account
you request. This password hash can broken using an offline brutefor... 阅读全帖 |
|
c*******r
发帖数: 309 | 18 网上看的Hashtable的Implementation. 这里边定义table.put(key,value)的时候value
是必须要定义为hashEntry object么。 感觉学hashtable的时候value只要是object即
可。但是如果value不定义成hashEntry在rehash的时候无法确认table[hash]这个位置
的key是否重复。
public class HashEntry {
private int key;
private int value;
HashEntry(int key, int value) {
this.key = key;
this.value = value;
}
public int getKey() {
return key;
}
public int getValue() {
return value;
}
}
public... 阅读全帖 |
|
b******7
发帖数: 92 | 19 “perfect hash function”和该问题是两个不同的问题
前者是静态hash，即key的hash（key）已知，求hash函数。
而对于你贴中提到的hash排序，即要求key1< key2等价于hash（key1）
具体hash（key）的值未知，理想中是hash（key)为key排序时的相对序数。
所以基本上总绕不开要排序（包括非比较的排序）
非要用hash表排序的话，可能是用hash表替换数组实现基数排序
比如abc gf
用hash表hash 存储 <'a'*128*128+'b'*128+'c', "abc"> <'g'*128+'f'
, "gf">
然后查询key从0~maxvalue，检测是否key在hash表中 |
|
Z**********4
发帖数: 528 | 20 我的意思是不用整个pair用一个hash map就可以了。不过我想做点改动 利用hash里面
key对应的value来标志对（3，4）已经找过了，下次不论是（4，3）还是（3，4）都视
而不见。
hash_map hash;
vector::iterator iter;
vector result;
for(iter = array.begin(); iter!= array.end(); iter++){
if(hash.find(*iter) == hash.end() && hash.find(n-*iter) == hash.end(
)){
hash[n-*iter] = 1; //这是第一次遇见3的时候，存入 4->1
}
else if(hash[*iter]==1){ //发现hash里面有4，而且value是1 就算找到了
（3，4）
hash[*iter]=0; //将hash... 阅读全帖 |
|
|
c********p
发帖数: 1969 | 22 前几天在job问过，但还是想不通，所有又来这里问了。
这回我按网友建议把求hashtable size改成直接count删去的个数了，还是不能通过大
oj。所以又跑来问问我到底哪里出了问题？！
http://www.mitbbs.com/article_t0/JobHunting/32465791.html
原帖在这里。
我新的代码：
import java.util.*;
public class Solution {
public int longestConsecutive(int[] num) {
if(num == null || num.length == 0){
return 0;
}
int max = 1;
int count = 1;
Hashtable hash = new Hashtable();
for(int i = 0; i < num.leng... 阅读全帖 |
|
S*A
发帖数: 7142 | 23 因为我最近在 hack 这个 Pogoplug V4 mobile。我顺便帮
你看了以下。
我从 UBoot 上面去掉了 serial cosole。这个是 dmesg。
时钟初始化是在 12 妙开始, 并不是 Linux 真正启动了 12 妙。
所以走到 systemd 启动也才 3.5 秒钟。注意其中有 USB 硬盘
访问，因为那个 rootfs 是在 USB 上面。仔细看 demsg，去掉
USB 硬盘访问，去掉 SATA 寻找硬盘，去掉 Ethernet 寻找
Link 的时间，剩下初始化应该就在 2 秒钟以内了。这个 3.5
秒钟很多时间是在和 USB storage 的东西相关。你只要
rootfs 不在 USB flash 上面，这些都可以启动的时候不做。
所以 2 秒钟启动应该是可以的，不需要特别多定制。
基本上改改 kernel config 或者启动参数就可以了。
[ 0.000000] Booting Linux on physical CPU 0x0
[ 0.000000] Initializing cgroup subsys cpuset
[ ... 阅读全帖 |
|
S*A
发帖数: 7142 | 24 因为我最近在 hack 这个 Pogoplug V4 mobile。我顺便帮
你看了以下。
我从 UBoot 上面去掉了 serial cosole。这个是 dmesg。
时钟初始化是在 12 妙开始, 并不是 Linux 真正启动了 12 妙。
所以走到 systemd 启动也才 3.5 秒钟。注意其中有 USB 硬盘
访问，因为那个 rootfs 是在 USB 上面。仔细看 demsg，去掉
USB 硬盘访问，去掉 SATA 寻找硬盘，去掉 Ethernet 寻找
Link 的时间，剩下初始化应该就在 2 秒钟以内了。这个 3.5
秒钟很多时间是在和 USB storage 的东西相关。你只要
rootfs 不在 USB flash 上面，这些都可以启动的时候不做。
所以 2 秒钟启动应该是可以的，不需要特别多定制。
基本上改改 kernel config 或者启动参数就可以了。
[ 0.000000] Booting Linux on physical CPU 0x0
[ 0.000000] Initializing cgroup subsys cpuset
[ ... 阅读全帖 |
|
j*****2
发帖数: 457 | 25 Representations: Hash Table vs Binary Search Tree (self-balancing)
There are two main efficient data structures used to represent associative
arrays, the hash table and the self-balancing binary search tree. Skip lists
are also an alternative, though relatively new and not as widely used.
Relative advantages and disadvantages include:
* Hash tables have faster average lookup and insertion time (O(1)),
while some kinds of binary search tree have faster worst-case lookup and
insertion time (O(... 阅读全帖 |
|
s*****y
发帖数: 897 | 26 写了好几个小时，终于用差不多brute force得解了，算了1337的几个例子，全部都一
样，但是我是算好了一个result，就return了，其他的就不算了。
速度还行，1337的几个例子都是10-20ms就算好了。
但是算火鸡同学的那个终极测试，真的是算了10分钟还没有好，难道要用公司的server
算.....
#include "stdafx.h"
#include
#include
#include |
|
s*****y
发帖数: 897 | 27 写了好几个小时，终于用差不多brute force得解了，算了1337的几个例子，全部都一
样，但是我是算好了一个result，就return了，其他的就不算了。
速度还行，1337的几个例子都是10-20ms就算好了。
但是算火鸡同学的那个终极测试，真的是算了10分钟还没有好，难道要用公司的server
算.....
#include "stdafx.h"
#include
#include
#include |
|
w**********2
发帖数: 20 | 28 大家好，5天前，hc 送审的时候， 纠结通过率，搜到了这个网站，（这网站在新加坡
貌似没什么人用） 相见恨晚。。 3天前，写了onsite 小面筋，想求个祝福。可惜新注
册的用户，禁言三天，没有发上来。三天后，hc 的结果出来了， 还要加一轮。不管机
率如何， 既然还有希望，准备拼一枪。
“our profile was actually reviewed at our hiring committee in the US this
morning and I just received the results. The committee has actually decided
they need some additional data through a couple more interviews.
Accordingly, I'd like to set up 2 more interviews for you, these interviews
will be focused on system design and open ended questions.”
看了版上... 阅读全帖 |
|
w**********2
发帖数: 20 | 29 大家好，5天前，hc 送审的时候， 纠结通过率，搜到了这个网站，（这网站在新加坡
貌似没什么人用） 相见恨晚。。 3天前，写了onsite 小面筋，想求个祝福。可惜新注
册的用户，禁言三天，没有发上来。三天后，hc 的结果出来了， 还要加一轮。不管机
率如何， 既然还有希望，准备拼一枪。
“our profile was actually reviewed at our hiring committee in the US this
morning and I just received the results. The committee has actually decided
they need some additional data through a couple more interviews.
Accordingly, I'd like to set up 2 more interviews for you, these interviews
will be focused on system design and open ended questions.”
看了版上... 阅读全帖 |
|
g*******y
发帖数: 1930 | 30 写hash function太detailed了吧
就拿乘法hashing function来说，你背得下来(sqrt(5)-1)/2的32位小数？
其他的一些hash函数(除法，universal)，也涉及到找合适的质数
另外是不是还要考考hash的几种解决冲突的方法，chain，Open addressing, perfect, 还有什么随机版本的cockoo hashing
对于hashing有个不错的了解就行了，面试时间写个比library还好的版本不太现实吧
另外，我不太懂java，也许java的hash需要一些customize的处理
不过lz明显写的是C++嘛，摆在那里的库不用干嘛。。。这个题目本身重点就不是hash，hash只是实现算法的一个工具。
不过我提一点，直接用C++的库的hash，对于比较多的数据实际上达不到O(1)性能的insert，这个可以跟面试官侃一侃，如果有时间的话 |
|
b*****o
发帖数: 715 | 31 说说我看到你答案的感想吧：
He: how would you design a distributed key-value store
Me: DHT or just using clusters
我不知道这一问一答是你简化过了还是实际就这么简单。如果实际就这么简单，
回答就很有问题。一般问一个设计题，是先要把问题的各种要求先和面试官讨
论清楚。你这么回答就好像考官问如果搜索速度太慢怎么办，你回答说用
cache一样（正确的回应是先讨论哪个环节慢了）。而对于这个问题我觉得首
先应该问清楚这个系统有多大，有多少Machine，有没有balance的要求，会
不会add或者delete整个machine，等等。
然后，即使在问清楚条件的情况下，也不要马上给一个specific的方案，而是
依旧泛泛地谈大致有几类思路。然后根据考官的反应，再说具体的技术细节。
He: details?
Me: we have a large number of machines. first we use a hash function to
retrieve machine ID from the key... 阅读全帖 |
|
c********p
发帖数: 1969 | 32 这个是今天的。。。
import java.util.*;
public class Solution {
public ArrayList> fourSum(int[] num, int target) {
// Start typing your Java solution below
// DO NOT write main() function
HashSet> set = new HashSet>();
if(num == null || num.length <= 3){
return new ArrayList>(set);
}
Arrays.sort(num);
Hashtable> hash = new Has... 阅读全帖 |
|
y*k
发帖数: 80 | 33 背景：EE毕业但是做行业软件的，工作好多年了一直用C++。没有专门学过计算机专业
课。刷题刷了好几个月了。
上星期经历了几次店面，Linkedin是我自己觉得面得最好的，以为可以拿onsite了，结
果被据了。
别的店面感觉比Linkedin差很多的都过了，所以特别surprise. 我把问题详细贴出来，
并附上我自己的解答，请大家帮忙分析一下，是哪里出了问题，还是被三哥黑了。面试
一共分三部分。因为最后的题做得比较快，三哥还跟我谈笑风生了几分钟，说你的
coding不错，你来面试的时候需要多准备点系统设计，多线程之类的，搞得我以为我都
拿到onsite在为下一步准备了。
1. 10分钟互相介绍，然后问之前做的最难的项目，我说了一下，三哥问了几个问题，
双方都比较满意（之后的回答过程中，三哥不会说你哪里回答得不大好，但是会一直追
问直到他说ok，当然也不知道这个ok是好还是嘿嘿你丫错了）
2. 基础知识。
Q: virtual memory是如何工作的？优缺点？
A：操作系统一般在内存不够时分配虚拟内存，不够的虚拟空间存硬盘上。优点是内存
不够时还能转，缺点是硬盘读写速度慢
Q：如果有... 阅读全帖 |
|
b******7
发帖数: 79 | 34 我刚刚面试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没法得到。
希望牛人指点！！！非常感谢！ |
|
N*D
发帖数: 3641 | 35 正确的做法是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没法得 |
|
d********n
发帖数: 54 | 36 本人PhD，3年半工作经验。2个月前收到Google recruiter电话，开始面试，一个月前
拿到offer，然后开始了漫长的谈判，昨天终于签字。上来share一下面经。
2年前面过google，职位不喜欢，把它拒了。因为他们有记录，所以这次只安排了4人面
试。
第一个是老美，先问了一些简单问题，比如怎么判断一个32 bit是big endian 还是
small endian等等。最后出了一道算法题，也很容易，给定K个sorted array，要求输
出一个大的sorted array。简单的merge sort就解决了。不过merge sort 要求每次K个
array中，最小的element。简单的当然是scan这K个array。我提出可以把K个array的当
前element放入Heap structure，这样每次搜索就从O(K)降低到O(logK)。最后写了个程
序。
第二个是老中。也是先问了一些简单问题，然后让我设计一个分布式文件系统，给定
path name，可以读写文件。具体的system design这里就不提了。其中一个细节是，给
定path name，怎么知... 阅读全帖 |
|
S**I
发帖数: 15689 | 37 ☆─────────────────────────────────────☆
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 | 38 ☆─────────────────────────────────────☆
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... 阅读全帖 |
|
e*******s
发帖数: 1979 | 39 Given an array of strings, return all groups of strings that are anagrams.
All inputs will be in lower-case
Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"].
Given ["ab", "ba", "cd", "dc", "e"], return ["ab", "ba", "cd", "dc"].
9章的参考程序如下, 他给每一个string换成26长度的int array. 然后用这个array生
成一个hash code. 问题是这个hashcode能够唯一对应一个anagram么. 不同的anagram
有没有对应同一个hashcode的可能 (考虑int overflow的情况下).
public class Solution {
private int getHash(int[] count) {
int hash = 0;
int a ... 阅读全帖 |
|
d********g
发帖数: 10550 | 40 我的意思就是key不在数据库
比如用户密码明文是12345，hash之后是1a2b3c4d。数据库里存的是hash后的值，而用
来加密CC的是用明文。这个明文是无法避免的，如果你要用form提交，除非你在客户端
先hash一遍传hash后的值，大多数网站都是把password明文传给服务器。这个password
12345传到服务器之后，那边hash一遍和数据库的1a2b3c4d对比，就完成验证了。然后
12345这个明文是通过POST过去的，可以保存在服务器内存中。只要用户session有效，
服务器就靠那个明文来把加密的CC解出来
用来加密CC的也可以是密文。比如12345，采用另一套算法，或者加个salt，形成
4a3b2c1d的hash，和数据库里的hash不一致，也没办法猜测。用这个变形的hash当作
key来加密CC，然后这个hash同时放session里来解CC。整套过程密钥和密文一直分离的
，而且是在物理层面上（一个在硬盘，一个在内存）
SSL会把服务器和客户端传输的过程也加密。LVM能把整个硬盘加密。多搞几层服务器能
减少漏洞。整个一套流程下来，除非你是从敌人内部下手... 阅读全帖 |
|
n***n
发帖数: 15 | 41 如果能找着一对输入,hash后的值是一样的,这个hash就不是强抗撞的(strong collision
resistant);如果任给一个输入,都能找着另一个输入和它有相同的hash值,那这个hash连
弱抗撞的都不是.这次Crypto上三家攻击hash的,都是随便找一对,也就是证明了被攻击的
东东不是强抗撞的. 这样一来在需要强抗撞函数的时候就不能再用这个东东啦.这是很了
不起的成就,因为大家写(垃圾)文章,(瞎)编协议,都假设有个强抗撞函数放在那里给人用,
到程序实现的时候就把SHA1啦MD5啦套上,现在一下子好些这种函数都不是强抗撞了,只剩S
HA1了,而且大牛们已经担心SHA1也保不了多少天了,必须去造新的hash函数.造个新hash函
数很难,必须是那几个最牛的巨牛绞尽脑汁搞出来的,把那个输入给hash的稀吧烂,而且谁
也不能理论证明它就是强抗撞的,只能天长日久靠实践检验.如果把这个工作的级别打个比
方,造hash函数相当于造CPU,其他的文章(包括顶尖会议的),协议(包括成了标准的)相当于
攒机子,IBM攒的好一点,电子商场攒的差一点而已.现在突然有人举个例子说Intel |
|
w********u
发帖数: 71 | 42 你不去做老师的话，真是教育届的损失:-)
如果能找着一对输入,hash后的值是一样的,这个hash就不是强抗撞的(strong collision
resistant);如果任给一个输入,都能找着另一个输入和它有相同的hash值,那这个hash连
弱抗撞的都不是.这次Crypto上三家攻击hash的,都是随便找一对,也就是证明了被攻击的
东东不是强抗撞的. 这样一来在需要强抗撞函数的时候就不能再用这个东东啦.这是很了
不起的成就,因为大家写(垃圾)文章,(瞎)编协议,都假设有个强抗撞函数放在那里给人用,
到程序实现的时候就把SHA1啦MD5啦套上,现在一下子好些这种函数都不是强抗撞了,只剩S
HA1了,而且大牛们已经担心SHA1也保不了多少天了,必须去造新的hash函数.造个新hash函
数很难,必须是那几个最牛的巨牛绞尽脑汁搞出来的,把那个输入给hash的稀吧烂,而且谁
也不能理论证明它就是强抗撞的,只能天长日久靠实践检验.如果把这个工作的级别打个比
方,造hash函数相当于造CPU,其他的文章(包括顶尖会议的),协议(包括成了标准的)相当于
攒机子,IBM攒的好一点,电子商场攒的 |
|
发帖数: 1 | 43 谁叫自己上了嵌入式的贼船，工资低呢。。。C看多了，也不能刷题转码搞互联网
为什么摄像头领域不能有像开源openwrt一样的项目呢？
把海康的dmesg贴出来，大家可以参考，他们用安霸S3L，https://www.ambarella.com/
products/security-ip-cameras/security-ip-camera-products#S3L
[ 0.000000] Booting Linux on physical CPU 0x0
[ 0.000000] Linux version 3.10.73+ ([email protected]) (gcc version 5
.2.1 20151005 (Linaro GCC 5.2-2015.11-2) ) #1 PREEMPT Mon Jan 23 10:38:22
CST 2017
[ 0.000000] CPU: ARMv7 Processor [414fc091] revision 1 (ARMv7), cr=
10c53c7d
[ 0.000000] CPU: PIPT / ... 阅读全帖 |
|
I********T
发帖数: 22 | 44 看到一道面试题
给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出
共同的URL。
这个题目在网上看到有两种解法：
解法一：（1），读取文件，计算HASH，按HASH值分段放入不同的文件，文件数可以比
较多，两个
文件的URL，分开不同的文件放（a1，a2,...，b1，b2，...），保存时可以把HASH值也
保存进
去，避免再次计算HASH值
（2），对每一个HASH段，读出两个文件中的一个，比如a1，对HASH值有冲突的放一个
连表里，然
后读b1文件，取HASH值和URL，如果HASH值在a1中有，则进一步判断URL是否相同。
解法二：Bloom Filter（广泛应用于URL过滤、查重。参考
http://en.wikipedia.org/wiki/Bloom_filter、
http://blog.csdn.net/jiaomeng/archive/2007/01/28/1496329.aspx）
可是我算了下内存4G，换成bit位是4 * 2^30 * 8 =32 *2^30 个位， 数据有5*2^30,
这样把全部
内存用来做h |
|
j*****u
发帖数: 1133 | 45 good point,如果子树的叶节点必须在原树中也是叶节点，可不可以这样:
原树和子树bottom->up算每个node的hash，这个hash function考虑到当前node的data和
location, i.e. hash(node)=f1(data),f2(hash(node.left)),f3(hash(node.right))
算hash是O(n)
然后foreach node，比较hash跟子树root的hash，也是O(n) |
|
s*****y
发帖数: 897 | 46 Sounds good. I write the code according to your idea. But still need to defi
ne a 256 byte array to hash the reference string and count the times they ap
pear.
Any better way I could ger rid of the 256 byte array?
#define SWAP(A,B) { \
char tmp; \
tmp = A; \
A = B; \
B = tmp; }
char input[] = "ABBFKCEDGAB";
char pattern[] = "BAC";
void SortString(char input[], char pattern[])
{
char hash[256] = {0};
int i,j;
int count;
i = 0;
while... 阅读全帖 |
|
t*********n
发帖数: 89 | 47 2sum,如果用hash table的话，循环中每一次查元素都只在已有的hash table 查，比如
1 -> 此时 hash table为空，则无结果
2 -> 此时 hash table 里有仅有1， 无结果
....
9 -> 此时 hash table 里有{1，2，3，..8},查到1，成立
对于duplicate,我的想法是在hash_table的value以一个bool来表示是否已经用过，即
hash_table myhash。比如数组为{5，5，5}，目标是10
5-> 此时hash table为空，无结果
5-> 此时hash table里面有5，标记myhash[5] = false;
5 -> 此时hash table里面虽然有5，但是myhash[5] = false,则不成立。
请问下大家有没有更巧的方法？ |
|
j********8
发帖数: 10 | 48 //Best first search, time complexity O(klog(n)). The size of heap is at most
2*n. Every time an element is popped from the heap or inserted to the heap,
O(log(n)). We need to do the pop and insert operations k times. So the time
complexity is O(klog(n)).
//Space complexity O(n), because there are at most 2*n nodes in the priority
queue.
struct node
{
int index;
int val;
node(int index_, int val_): index(index_), val(val_){}
bool operator > (const node& other) const
{
... 阅读全帖 |
|
j********8
发帖数: 10 | 49 //Best first search, time complexity O(klog(n)). The size of heap is at most
2*n. Every time an element is popped from the heap or inserted to the heap,
O(log(n)). We need to do the pop and insert operations k times. So the time
complexity is O(klog(n)).
//Space complexity O(n), because there are at most 2*n nodes in the priority
queue.
struct node
{
int index;
int val;
node(int index_, int val_): index(index_), val(val_){}
bool operator > (const node& other) const
{
... 阅读全帖 |
|
c******b
发帖数: 13 | 50 public static List topK(int[] test,int k){
List l = new ArrayList();
if(k>test.length) return l;
//用hash存放股票名称，和出现次数
HashMap hash = new HashMap();
for(int i=0;i
if(hash.containsKey(test[i])){
hash.put(test[i], hash.get(test[i])+1);
} else {
hash.put(test[i], 1);
}
}
//用一个priorityqueue，可以对出现次数进行排序... 阅读全帖 |
|
