g*******e
发帖数: 140 | 1 难度应该是中等偏下，发挥一般，顺求bless
一共4轮技术面试，HM生病了，没见着。每轮2个工程师，一般是一个本地 + 一个远程
1st: 亚裔小弟弟+英式口音的大姐：
1. 项目自我介绍
2. 浮点bst，找greatest one in the tree that's smaller than the target，
二分搜索简单变形。我犯了个错误，但是自己dry run测试用例的时候发现更正了。另外
一个小问题要注意的就是处理查找结果不存在。
3. 类似utf8字符串(一个字符是单字节还是双字节取决于第一个字节的首bit)，给定中
间一个字符，删除前面一个。在这道题上卡了一会，关键是弄明白向前查找的终止
条件是什么。
2nd: 一位老美大叔+老美小弟弟
1. 项目介绍
2. 从stream中找到top-k frequent items 用hash-table + priority queue解即可,
解释了一下时间复杂度。问了一下写什么测试用例来测试代码。
3. 扩展到多机器大数据上500mm数据，500台机器，怎么解。就是用hash mapping分散
数据到500台机器上，分... 阅读全帖 |
|
f********t
发帖数: 6999 | 2 http://www.informationweek.com/news/security/attacks/240001623?
All users of the LinkedIn social network should immediately change their
password.
Security experts began broadcasting that warning Wednesday after reports
emerged that nearly 6.5 million LinkedIn password hashes--encrypted using
SHA1, but not salted--had been posted to a Russian hacking forum on Monday,
together with a request to help decrypt them.
Hackers have already reported breaking 163,267 of the passwords, reported
Norwegian ... 阅读全帖 |
|
z******4
发帖数: 4716 | 3 是，无聊了
此章写Join
Oracle有四种join方式，妈的，真麻烦，真难记，怎么办，我告诉你，超级简单，大家
都学过数学的集合吧
交集，并集，看下面的图
http://codinghorror.typepad.com/.a/6a0120a85dcdae970b0128777027
inner join
就是图中AB部分
left join (A left join B)
就是 A和AB部分
full join (A full join B)
就是 A和B 全部
结束，简单吧
那么Oracle在实际join过程中，数据是怎么match的哪，且听下回分解
==========================================================
下面讲join的具体方式
例如，我有个电信话单记录表，还有个产品id和描述表，现在我要拿到产品的说明，按
产品算消费金额，例如168套餐，这个月有多少收入
你用头脑想，你怎么做，肯定是拿一行，按产品id去产品代码表找描述，对吧
Oracle不是神，Oracle也只能这么做
问题来了，加入，北京移动一天话单1000... 阅读全帖 |
|
o**2
发帖数: 168 | 4 我不是很明白“不能通过大oj”是什么意思，只是从一个程序员的角度指出你的程序的
两个问题。
一个是你的算法的问题，很明显你的思路是建立在“先排序，再寻找”的基础上，所以
有很多多余的操作。比如：
1，每个元素都要先在hash里找一次，排除掉重复元素；
2，然后为了探测序列的边缘，每个元素在hash里又找一次；
3，一个序列里，除了第一个被挑中的元素，其他所有的元素在被删除后，在hash里又
找一次，一共三次；
4，每个元素都要在hash里删除一次。
另一个是编程技术问题，你是用递归来探测序列的边缘的，为什么不直接用循环呢？
for (int i = 0; i < num.length; i++) {
if (hash.containsKey (num[i])) {
int lower = num[i];
while (hash.containsKey (lower - 1)) {
lower--;
}
... 阅读全帖 |
|
P********e
发帖数: 2610 | 5 看你最后想要什么，hash pnter还是hash object，我比较倾向第二种
区别就是：
vector vh;
vh.push_back(new hash(random));
hash* h1 = new hash[10];
hash** h2 = new hash*[10];
但属 |
|
g*******y
发帖数: 1930 | 6 这个题目挺好的，顶上来大家讨论下。
我觉得用hash来count occurence应该是需要做的吧，有了hash file(may be
distributed across servers)之后就很简单了。
不过对于多servers的大系统如何高效的实现hash？单独的server算自己的hash，再跟
其他server通讯，merge hash file？
有个问题是，因为hash file太大，肯定是要写到disk上的文件，不可能在mem里面装下
，这样就涉及到一个disk write的问题，read时连续地址的item对应在hash表里的地址
都是不连续，而高效的disk write要求一次写入一个large chunk的data，如果你每次
只能disk write一个10Byte的数据，岂不是效率太低了？怎么解决这个问题？ |
|
p********7
发帖数: 549 | 7 其实不用map,用一个数组hash[N]就行了.
如果有入点[i]
hash[i]++;
如果有出点[j]
hash[j]++;
hash[j+1]--;
最后遍历一次这个hash数组就搞定了.
如果guest = hash[i] + guest; 遇到hash[i]>0 就更新max
entry. |
|
j***y
发帖数: 2074 | 8 倒是没有问什么太难的算法和数据结构方面的题，大多是和实际工作相结合的题目，比
如debug一段程序，等等，都不算难。
不过还是有个数据结构的问题把我问倒了：
具体问题的起源我也记不清了，反正就是要求我implement一个数据结构，要求access
是O(1)量级的。
一开始我提了用数组，但是被否决，因为将要储存的数据量很大而且预先不知道终止条
件，所以很难给定数组的range。
用list显然也不可行，因为list一般是unsorted的，要找一个数据，必须遍历一次，也
就是O(n)的complexity。
接着我又提了Hash Table，隐约记得Hash Table的access是O(1)的量级，但大叔说如果
Hash Table的row是M，而每个entry（key mapped via hash function）是个linked
list（因为不同key的key-value pair经过hash function的运算后得出相同的index）
，假设linked list里面所含的元素是N，那么access的时间复杂度是O(N/M)。好了，再
次被枪毙。
最后，我在大叔这里... 阅读全帖 |
|
s******d
发帖数: 61 | 9 我的返回结果是这个,不知道哪里错了
d:1e:1h:1l:1o:1r:1w:1
import java.util.Collection;
import java.util.Collections;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Vector;
public class Findfrequency {
public String find(String s){
char[] ch=s.toCharArray();
Hashtable hash=new Hashtable();
for(int i=0;i
Character temp=new Character(ch[i]);
if(!hash.contains(temp)){
hash.put(temp, new Integer(1));
}
else{
Integer in=hash.get(temp);
in++;... 阅读全帖 |
|
r**********1
发帖数: 292 | 10 “那另外一个例子，如果要计算一本书里每个字的出现次数，那简单的 array 做不到了
。因为 key 是 word，不能直接以 index 来 hash，那就用比较general的hashtable来
做。”
我是想弄清出啊。对于这个例子，用hashtable是不是如下做法？
对于每个word，我算一个hash value, 比如把每个character的ascii码加在一块得到一
个sum值，我可以把这个sum值作为hash value。
然后，我建立一个大小为1000的数组，A，初始化为0。
然后，对于每个word，算出hash value，然后以它来作为index，把相应的A[hash]进行
++操作。
对于hash value 大于1000的，进行动态扩展数组，然后继续。
这么说来，hash table 似乎是高级的动态数组。
ihasleetcode，您觉得我的理解对吗？ |
|
r****s
发帖数: 1025 | 11 这个就扯淡了，很简单的consisten hashing的题目。天下所有的高级码工都知道，你
不知道？
9. 然后让我设计一个分布式文件系统，给定
path name，可以读写文件。具体的system design这里就不提了。其中一个细节是，给
定path name，怎么知道哪个node拥有这个文件。我提出需要实现一个lookup function
，它可以是一个hash function，也可以是一个lookup table。如果是lookup table，
为了让所有client sync，可以考虑额外做一个lookup cluster。然后Interviewer很纠
结，既然可以用hash function，为什么还搞得那么复杂。我就告诉他hash function的
缺点。假定一开始有N个node，hash function把M个文件uniformly distribute到N个
node上。某天发现capacity不够，加了一个node。首先，要通知所有的client machine
，configuration 改变了。如果不想重启client machine的proce... 阅读全帖 |
|
h**o
发帖数: 548 | 12 how to define hash function? if it is to hash content of document, will the
hash function be sth. like:
hash=A[length of content]...A[3]+131(A[2]+131(A[1] + 131 A[0])) mod 10G ??
如果document content很长, hash 岂不很复杂？
假如不考虑split, what is mod of hash? 为什么网上说是 mod/10G?
然后怎么办， 把正好在一个hash index的link list里的不同documents 内容 逐字比
吗？ |
|
d*k
发帖数: 207 | 13 说一个思路，适合k很小或者char的取值范围很小时候。预处理把所有长度为k的string
和B的距离算出来放到hash table里面。顺序扫描一遍A，对于每个遇到的字串，在hash
table里直接获得它和B的距离。
普通的hash table算一个字串的hash需要O(k)的时间，这样总体和暴力解法一样。因此
需要自己设计hash。很多rolling hash（http://en.wikipedia.org/wiki/Rolling_hash）都可以满足。这样计算第一个字串的hash需要O(k)的时间，后面每一个只需O（1）的时间。
若char的取值个数是O(v)，则预处理时间是O(v^k），之后扫描的时间是O(n)。
如A |
|
m******e
发帖数: 82 | 14 第三题是不是这样
方法一，对hash table的add/get/change操作都加锁，且是同一把锁，可以保证thread
-safe，但是效率低下。
方法二，对每一个slot各加一把锁，效率高，缺点是锁的数量要随
着slot扩展而增加，不太现实。
方法三，参照java的ConcurrentHashMap，将hash table划分为若干个segment，比如32
，每个segment拥有一把锁和一个非thread-safe的hash table。任何key先进行一次
hash，选择对应的segment，如果两个key hash到同一个segment就争抢同一把锁，否则
它们之间没有影响。抢到锁之后就可以对非thread-safe的hash table进性具体操作。
这个方法相当于最多允许32个线程同时对hash table访问。 |
|
x****u
发帖数: 81 | 15 根本不能说是handle，这方面我不懂，比起其他面试很没自信。对面是两个人，期间扯
不清楚还用了collabedit边写边讲，具体对话如下。大家谨慎阅读，很有可能我说了很
多错的东西，他们也没有当场指出。如果懂行的朋友望指正一下。
对方：reverted index怎么partition，怎么scale
我：按term来hash，用consistent hashing来保证加机器之后数据不用全部reshuffle。
对方：consistent hashing怎么工作的
我：blahblah（写了个小例子解释）
对方：你讲讲加了个node之后发生了什么
我：加了机器后，新机器收到了查某个term的请求，就去老机器上拉数据过来再存着..
（被打断）
对方：client怎么会发请求到新机器
我：因为加了机器之后hash ring更新了，有一部分term的请求导到新机器了
对方：怎么更新的
我：可以用ZooKeeper存机器列表，新机器register到zookeeper后，各client那边的
listener就更新列表
对方：新加的机器怎么知道到哪里去找某个term的数据
我：顺着hash... 阅读全帖 |
|
i***l
发帖数: 9994 | 16 每个文件都有自己独特唯一的hash值，比如SHA-1/2，CRC32，MD5都是属于常见hash。
每个不同的hash有不同的算法，对一个文件实施这种算法，就能得出一个唯一值。一般
来说如果两个文件hash一样，那么这两个文件就是相同文件。和人类的指纹一样，都是
一一对应的。
百度客户端在上传文件之前第一件事就是先计算你要上传的文件的hash值。这样基本上
如果你要上传的文件和百度已经保存在server上的一个文件的hash值一样（匹配），那
么百度云管家的客户端就不会再重新上传你的文件。服务器会自动把那个服务器上已经
存在的文件分配给你的账户。这样看起来好像是你的文件极速上传了。实际上就是两步
：hash匹配，然后服务器映射那个文件到你的账户。 |
|
w***g
发帖数: 5958 | 17 hash table和文件有多大？内存能存下吗？
已经是hash table了，我觉得没什么更好的办法了。如果你的hash table是固定的，而
文件有多个的话，可以考虑用perfect hash。这样hash function跟string一一对应，
直接比较hash key就可以，不用比较字符串了。不过建立perfect hash比较费时间。 |
|
a****9
发帖数: 418 | 18 你如果用第二题解法 则要求使用的Hash是perfect Hash
也就是对50亿个元素hash以后没有collision
(注意在第二题当中, 这个perfect hash是自然满足的,
第i个数就对应第i个entry.
但在你这里就不能这样,url不是自然有序的,
当然你可以用tire来排序,trie也是一种可以用来hash的方式了)
其实关于BloomFilter的paper里也提到
使用Perfect Hash+fingerprint是可以达到information theoretic bound的
就是这个perfect hash太难弄了 特别规模大 |
|
p****i
发帖数: 6135 | 19 然后来看hashmap
hashmap的特点就是用空间换时间
重点就是你准备用多大的空间来换你的时间呢？
而且这个也跟你的key密切相关
举个简单的例子， 如果你的key是integer， range 1-100
那最简单的hash就是建立一个空间为100个entry 的hash table
直接用key作index
这样你的查找时间无论是miss还是hit， 都只有一个compare operation而已
稍微变化一下这个例子， 如果你key的range是1-10000呢？
你是否还会愿意用一个空间为10000个entry的hashtable来储存你仅仅40个的数据？
如果说，你不愿意， 那你需要在hash function上下功夫，
generally speaking， hash function通常的形势是： Key part 1 * prime number A
+ Key part 2 * prime number B +...
通过认真设计hash function来达到节约一定空间的目的
但是， 不是没有代价的， 代价就是这个hash function的复杂度。
不考... 阅读全帖 |
|
w****w
发帖数: 521 | 20 Memory够的话，hash一下就出来了。不够的话得分批。
#!/usr/bin/env python
smallfile = file("small.txt","r")
largefile = file("large.txt","r")
outfile=file("out.txt","w")
HASHSIZE=10*1024*1024
maxvalue=0
hash={}
while 1:
line=largefile.readline()
if not line:
break
v=int(line.strip())
if v>maxvalue:
hash={}
while 1:
r=smallfile.readline()
if not r:
break
maxvalue=int(r.strip())
hash[maxvalue]=1
if le... 阅读全帖 |
|
b***i
发帖数: 3043 | 21 不难制造另一种算法，另一种币。我们公司的老哥去年退休前就说要研究。那个时候好
象起伏。今年5月末他回来，涨到230左右。现在来看看比特币的特点。我目前的理解：
为了模拟劳动产生价值，比特币规定了一种算法，来让各个节点证明自己在工作：这个
工作就是计算反Hash，使得hash之后得到一个开始有连续很多0的值。这个计算是耗时
的，保证了需要一定时间。另外，这个块中还包括上一次的hash，一个每次增加的
nonce，所有的交易。这个所有的交易我不理解，是历史上所有的，还是两次计算反
Hash之间的所有的?反正，这样的计算是在所有节点之间公认的。如果有个节点算出了
反Hash,就立即发布之。
http://bitcoin.org/bitcoin.pdf
5.1新的交易广播给所有节点
2每个节点把新的交易放入一个块中
3每个节点开始计算反Hash
4找到的节点广播
5如果一个节点听到有的节点发布了结果，就检查。如果所有交易是合法的，没有一
个币两次使用的情况，就接受这个块
6接受的意思，就是这个块的hash用来计算下一个块。这样，为了能够和大伙一致，
就必须接受最先出来的结果... 阅读全帖 |
|
b***i
发帖数: 3043 | 22 新的信息
大神帮看看那里可以提高？
[ 0.128265] omap_i2c omap_i2c.1: bus 1 rev2.4.0 at 100 kHz
[ 0.129791] tps65910 1-002d: JTAGREVNUM 0x1
[ 0.133728] print_constraints: VRTC:
[ 0.135223] print_constraints: VIO: at 1500 mV
[ 0.137603] print_constraints: VDD1: 600 <--> 1500 mV at 1100 mV normal
[ 0.139923] print_constraints: VDD2: at 1100 mV
[ 0.140960] print_constraints: VDD3: 5000 mV
[ 0.142425] print_constraints: VDIG1: at 1800 mV
[ 0.143890] print_constraints: VDIG2: at 1800 mV
[ ... 阅读全帖 |
|
d*l
发帖数: 1810 | 23 二手交易风险自负！请自行验证是否合法和一手卡！:
我想卖的物品:
Staples GC $[email protected]
/* */, $[email protected]
/* */,$[email protected]
/* */
单张面值:
$25, $75, $100
可接受价格(必须明码标价！):
6x$[email protected]
/* */
6x$[email protected]
/* */
3x$[email protected]
/* */
物品新旧要求:
邮寄方式要求:
email
买卖双方谁承担邮寄损失(Required if not code only):
付款方式说明:
non-cc paypal
其他补充说明:
广告的有效期:
物品来源(Required for All Cards!):
ebay paypal or giftcardmall
我的联系方式:
站内
Warranty期限:
till gone
能否证明是合法的一手卡?(Required for All Card... 阅读全帖 |
|
c*********e
发帖数: 704 | 24 每张25，每种有1050
推荐邮件联系 [email protected]
/* */ |
|
d*l
发帖数: 1810 | 25 二手交易风险自负！请自行验证是否合法和一手卡！:
我想卖的物品:
Staples GC $[email protected]
/* */, $[email protected]
/* */,$[email protected]
/* */
单张面值:
$25, $75, $100
可接受价格(必须明码标价！):
6x$[email protected]
/* */
6x$[email protected]
/* */
3x$[email protected]
/* */
物品新旧要求:
邮寄方式要求:
email
买卖双方谁承担邮寄损失(Required if not code only):
付款方式说明:
non-cc paypal
其他补充说明:
广告的有效期:
物品来源(Required for All Cards!):
ebay paypal or giftcardmall
我的联系方式:
站内
Warranty期限:
till gone
能否证明是合法的一手卡?(Required for All Card... 阅读全帖 |
|
d*l
发帖数: 1810 | 26
/* */, $[email protected]
/* */,$[email protected]
/* */
/* */
/* */
/* */ |
|
d*l
发帖数: 1810 | 27 up
/* */, $[email protected]
/* */,$[email protected]
/* */
/* */
/* */
/* */ |
|
d*l
发帖数: 1810 | 28 up
/* */, $[email protected]
/* */,$[email protected]
/* */
/* */
/* */
/* */ |
|
d*l
发帖数: 1810 | 29 up
/* */, $[email protected]
/* */,$[email protected]
/* */
/* */
/* */
/* */ |
|
d*l
发帖数: 1810 | 30 up
/* */, $[email protected]
/* */,$[email protected]
/* */
/* */
/* */
/* */ |
|
d*l
发帖数: 1810 | 31
/* */, $[email protected]
/* */,$[email protected]
/* */
/* */
/* */
/* */ |
|
d*l
发帖数: 1810 | 32 re
/* */, $[email protected]
/* */,$[email protected]
/* */
/* */
/* */
/* */ |
|
|
d*l
发帖数: 1810 | 34 up
/* */, $[email protected]
/* */,$[email protected]
/* */
/* */
/* */
/* */ |
|
c*********e
发帖数: 704 | 35 每张25，每种有1050
推荐邮件联系 [email protected]
/* */ |
|
|
|
c*********e
发帖数: 704 | 38 每张25，每种有1050
推荐邮件联系 [email protected]
/* */ |
|
|
|
|
b********w
发帖数: 110 | 42 这道题目我第二面的时候也问过，
两次hash,第一次hash 人名， 然后chain pages
第二次，每个chain，依次取三个，再hash
在第二个hash table 里面返回最大值。
interviewer 还算满意，但是又问我，可能有一个用户click的次数可能大大多余
其他的，譬如1000此，按我的方法就要998个triplet用来hash, 怎样优化。我说
可以用distributed hash table， 他说其实不是，好像是优先考虑最新的click，但是
他没有说很详细。
|
|
j**l
发帖数: 2911 | 43 这里不讨论Hash表内部具体的实现细节，假定Hash都是O(1)时间查找到。实际运行时候
是很有可能遇到你说的问题的.槽位不够肯定要有冲突,拉链法是其中一种解决方法.
除非面试官问到Hash表的具体细节，你才跟他讨论hash函数，解决冲突，拉链法，装填
因子，再hash, 二次hash这些技术。
1000 |
|
I*******l
发帖数: 203 | 44 How about using one hash table together with one array? The hash table can
be used to support O(1)-time insertions and deletions and use the array for
getRandom. Basically we maintain an array (or more precisely, a dynamic
array) of pointers for the integers in the set and a counter k for how many
integers the hash table currently contains. We will also store the index of
an element in the array in the hash table of that element. When an integer
is inserted, we add a new entry to the end of the ... 阅读全帖 |
|
I*******l
发帖数: 203 | 45 How about using one hash table together with one array? The hash table can
be used to support O(1)-time insertions and deletions and use the array for
getRandom. Basically we maintain an array (or more precisely, a dynamic
array) of pointers for the integers in the set and a counter k for how many
integers the hash table currently contains. We will also store the index of
an element in the array in the hash table of that element. When an integer
is inserted, we add a new entry to the end of the ... 阅读全帖 |
|
o******e
发帖数: 81 | 46 btw这个是俺的马甲
今天第一轮电面，我是experienced的不是fresh
感觉不怎么好，就问了一道题，太多detail了
电话来迟了8分钟，加拿大人。先问了问最challenge/favorite的project，说了几分钟
后他说我知道了，考你个题吧
很简单，Unicode的charactor array/string，找出现次数最多的char
我给了3个解，基本没有用任何考虑时间
1. double loop, O(n^2)
2. hash，他问我worse case，我一不留神说了O(n)，忘了hash的陷阱。他说恩perfect
hashing是不存在的，blablabla，我说我完全同意。我说如果space足够的话效率比较
好的char hashing是不太难的，他说anyway那也是O(n)，好吧。。
3. int[65536]的array，因为是unicode，我跟他确认了一下是2 bytes。我一开始说复
杂度的时候原来的solution是iterate string一遍，然后iterator count的array一遍
，突然想到可以用一个temp varia... 阅读全帖 |
|
f*********i
发帖数: 197 | 47 都是这么难吗，太夸张了一点吧。
第一题谁能给个思路啊，monte carlo simulation好像没有说圆周率的。
第三题的思路如下
hashtable先过一遍｛1，2，2，3｝， 这次是往hashtable加的，hashtable的value可
以是
if(hash.get(i)!=null){
hash.put(i,hash.get(i)+1);
}
然后再过一遍（1，3，2，2）如果hash的值为0，那么就remove这个element from hash
，最后check if the hash is empty.
保证了O(n)和重复数字的问题 |
|
j***y
发帖数: 2074 | 48 在看Hacking_a_Google_Interview_Handout_2.pdf，里面提到：
Classic Question #6: Data structure for anagrams
Given an English word in the form of a string, how can you quickly find all
valid anagrams for that string (all valid rearrangements of the letters that form
valid English words)? You are allowed to pre‐compute whatever you want to and
store whatever you optionally pre‐compute on disk.
Answer: We want to use a hash table! If your interviewer really hates hash tables (which they sometimes do for some... 阅读全帖 |
|
c*****t
发帖数: 13 | 49 本人CS硕士名校非牛人,一年前去了一家中型软件公司做SD,不喜欢,刚刚跳去一家小HF.面试
的过程好像西游记一样,路途遥遥,艰险不断,怪物层出不穷,自己的本领也日渐增长,2年来承蒙
版上各路豪杰照顾分享,今日也算有个结果;特此拿出小弟所见所闻共勉,纪念找工作的艰辛,愿
大家早日心想试成,取到真经!
/***********************
小测验
***********************/
首先来个小测验,看你能看懂多少
1.array,list,BST,Hashtable,queue,stack,suffix tree,collection...
2.BFS,DFS,DP,D&C,Greedy,Dijkstra,tree traversal,recursion,quick
sort...
3.A,F,G,L,M,O,T,Y...
4.OOP,GC,Polymorphism,interface,abstract class,singleton...
5.bar raiser,white board programming,lunch interview..... 阅读全帖 |
|
G******i
发帖数: 5226 | 50 ☆─────────────────────────────────────☆
currant (葡萄干) 于 駡 提到:
/***********************
小测验
***********************/
首先来个小测验,看你能看懂多少
1.array,list,BST,Hashtable,queue,stack,suffix tree,collection...
2.BFS,DFS,DP,D&C,Greedy,Dijkstra,tree traversal,recursion,quick
sort...
3.A,F,G,L,M,O,T,Y...
4.OOP,GC,Polymorphism,interface,abstract class,singleton...
5.bar raiser,white board programming,lunch interview...
如果以上任何概念不能熟练给出详细解答,请在往下面看之后抓紧复习1.数据结构(这个如果一
个没看懂可以按后退关窗口了)2.算法3.公司背景4.面向对象编程5.on... 阅读全帖 |
|
