l****p
发帖数: 397 | 1 两通电话，每个45min，到最后两个都超时
第一通电话：
１、指定我简历中的一篇一作文章，让我描述那文章里的内容
２、如何从一个只含有ASCII字符的字符串中找出最频繁的字符
我说用哈希表记录每个字符出现次数，然后他又补充问到哈希表是怎么工作的，我说包
括哈希函数和冲突处理两部分，并简述了一下，说由于字符不太多，可以用链表处理冲突
３、如果这个字符串含有32位Unicode字符的串，如何修改之前的算法
我说为了节省空间，可以把冲突处理方式改成rehashing
４、如果一个同事提出用一个array来记录各个字符的次数，比较你的算法和该同事算
法的优劣
很明显，他出这个题是期望我在第２问中说用array来记录，然后第３问再让我改成
hash，结果我第二问直接就用hash了。我说时间上差不多，但是用于处理ASCII时，
array比较省空间，处理Unicode时，hash比较省空间
５、如果这个字串数据量很大，而且分布在多台机器上，同时由于带宽限制，不能把整个
hash在多台机器中传输，怎么办？
这题没答上来，花了很长时间，后来先下一题的代码，然后还有时间，继续回答这题，最终还是没答
上来，只是说you are on the right track
６、写代码：给定了个整型数组，建立一个binary search tree
第二通电话：
1、问我当前在研究什么
2、如何把多个字符串连接成一个字符串
选择一个分界符，并在各个字符串中escape
3、写代码：实现一个PeekingIterator，与Java的Iterator不同的是，它多了一个
peek方法，这个方法返回下一个item，但不移动指针，也就是调用peek多次，它将返回
同一个item。
4、写代码：给定一由个位数组成的数组，比如[1,2,9]，用于表示数字129，要求对这
个数组进行加１运算，返回结果，比如[1,3,0]
复习了１０天的算法，唯一用到的是哈希表的原理和binary search tree的概念，每通电话最后
都问我还有什么问题，我都问我的performance跟别人比怎么样，都没得到什么有用信息。大家这种
时候都问什么问题？ |
b******g
发帖数: 1721 | 2 thanks a lot for your share!
bless you strongly. |
f*******t
发帖数: 7549 | |
n****r
发帖数: 471 | 4 bless~
冲突
【在 l****p 的大作中提到】
: 两通电话，每个45min，到最后两个都超时
: 第一通电话：
: １、指定我简历中的一篇一作文章，让我描述那文章里的内容
: ２、如何从一个只含有ASCII字符的字符串中找出最频繁的字符
: 我说用哈希表记录每个字符出现次数，然后他又补充问到哈希表是怎么工作的，我说包
: 括哈希函数和冲突处理两部分，并简述了一下，说由于字符不太多，可以用链表处理冲突
: ３、如果这个字符串含有32位Unicode字符的串，如何修改之前的算法
: 我说为了节省空间，可以把冲突处理方式改成rehashing
: ４、如果一个同事提出用一个array来记录各个字符的次数，比较你的算法和该同事算
: 法的优劣
|
h******6
发帖数: 2697 | |
l****p
发帖数: 397 | 6 是啊，我也很奇怪
【在 h******6 的大作中提到】
: 请问是申请的2012暑期实习？这么早就开始了？
|
h****n
发帖数: 1093 | 7 第五题可以用DHT(Distributed hash table)吧 |
l****p
发帖数: 397 | 8 当时头脑中有闪过用MapReduce，但觉得应该挺耗带宽的，就没往那个方向继续想，现
在觉得用MapReduce稍微优化一下应该可用。
【在 h****n 的大作中提到】
: 第五题可以用DHT(Distributed hash table)吧
|
q****x
发帖数: 7404 | 9 就是map/reduce吧。跟统计词频的经典例子差不多。
【在 l****p 的大作中提到】
: 当时头脑中有闪过用MapReduce，但觉得应该挺耗带宽的，就没往那个方向继续想，现
: 在觉得用MapReduce稍微优化一下应该可用。
|
l****p
发帖数: 397 | 10 我一直觉得这个能做到比经典的用MapReduce统计词频算法更省带宽，因为它最终结果
只要一个字符，而不是各个字符的频繁。我在面试时先想到的是全局最频繁应该是各个
局部最频繁之一，这样只要比较各个局部最频繁字符的全局频率。但后来被面试官举出
反例
【在 q****x 的大作中提到】
: 就是map/reduce吧。跟统计词频的经典例子差不多。
|
|
|
q****x
发帖数: 7404 | 11 of course wrong. the total #1 may not be a subject # 1.
【在 l****p 的大作中提到】
: 我一直觉得这个能做到比经典的用MapReduce统计词频算法更省带宽，因为它最终结果
: 只要一个字符，而不是各个字符的频繁。我在面试时先想到的是全局最频繁应该是各个
: 局部最频繁之一，这样只要比较各个局部最频繁字符的全局频率。但后来被面试官举出
: 反例
|
j********x
发帖数: 2330 | 12 什么叫带宽有限，不能传haSh，是说任何2台机器都不能传?还是什么!
带宽受限定义不确切，没法作，
MR之类的跟这题毫无关系。。。 |
r********3
发帖数: 2998 | 13 有办法，把两台机器的CPU拆下了，组装到一台机器，这样就不用网络带宽了。
【在 j********x 的大作中提到】
: 什么叫带宽有限，不能传haSh，是说任何2台机器都不能传?还是什么!
: 带宽受限定义不确切，没法作，
: MR之类的跟这题毫无关系。。。
|
b***e
发帖数: 383 | 14 "如何把多个字符串连接成一个字符串选择一个分界符，并在各个字符串中escape"
能否把这题解释一下吗？ 什么是“并在各个字符串中escape” ？多谢。 |
l****p
发帖数: 397 | 15 你就直接理解成不能把任何一台机器的本地结果全部传到另外一台机器上就是了。我只
是凭记忆分享一下面经，你这么激动干嘛，又不是非得让你做
【在 j********x 的大作中提到】
: 什么叫带宽有限，不能传haSh，是说任何2台机器都不能传?还是什么!
: 带宽受限定义不确切，没法作，
: MR之类的跟这题毫无关系。。。
|
l****p
发帖数: 397 | 16 我当时的回答是：比如选择空格当各个字串之间的分界符，这样必须把字符本来含有的
空格给去掉，比如用“\b”之类。然后面试官又追问，那么“\”怎么办，我说用两个“\”
代替
【在 b***e 的大作中提到】
: "如何把多个字符串连接成一个字符串选择一个分界符，并在各个字符串中escape"
: 能否把这题解释一下吗？ 什么是“并在各个字符串中escape” ？多谢。
|
g******n
发帖数: 253 | 17 yep. emule kad might be one solution.
【在 h****n 的大作中提到】
: 第五题可以用DHT(Distributed hash table)吧
|
r*******g
发帖数: 1335 | 18 Hi
想问下怎么实现一个PeekingIterator，谢谢了 |
j********x
发帖数: 2330 | 19 我没激动，我只是陈述事实
【在 l****p 的大作中提到】
: 你就直接理解成不能把任何一台机器的本地结果全部传到另外一台机器上就是了。我只
: 是凭记忆分享一下面经，你这么激动干嘛，又不是非得让你做
|
j********x
发帖数: 2330 | 20 这样就无解了，缺任何一个字符的结果，最坏情况下都会影响最后的结果
【在 l****p 的大作中提到】
: 你就直接理解成不能把任何一台机器的本地结果全部传到另外一台机器上就是了。我只
: 是凭记忆分享一下面经，你这么激动干嘛，又不是非得让你做
|
|
|
c**c
发帖数: 4 | 21 thx~~
我一般最后一个问题都会事先看看公司新出了什么东西 然后问问面试官对这个的了解
我前段时间问amazon的是EC2的问题 面试官貌似还挺有兴趣的跟我聊了下 |
l****p
发帖数: 397 | 22 这是我当时的实现：
class PeekingIterator{
private Iterator it;
private Object next = null;
public PeekingIterator(Iteractor it){
this.it = it;
}
public boolean hasNext(){
return next !=null || it.hasNext();
}
public Object next(){
if(next != null)
{
Object result = next;
next = null;
return retsult;
}else{
return it.next();
}
}
public Object peek(){
if(next == null)
next = it.next();
return next;
}
}
【在 r*******g 的大作中提到】
: Hi
: 想问下怎么实现一个PeekingIterator，谢谢了
|
l****p
发帖数: 397 | 23 这主意不错
解
【在 c**c 的大作中提到】
: thx~~
: 我一般最后一个问题都会事先看看公司新出了什么东西 然后问问面试官对这个的了解
: 我前段时间问amazon的是EC2的问题 面试官貌似还挺有兴趣的跟我聊了下
|
b******g
发帖数: 1721 | 24 问一下第3题，为啥要修改之前第2题的算法？ 用chain不是不错啊。
冲突
【在 l****p 的大作中提到】
: 两通电话，每个45min，到最后两个都超时
: 第一通电话：
: １、指定我简历中的一篇一作文章，让我描述那文章里的内容
: ２、如何从一个只含有ASCII字符的字符串中找出最频繁的字符
: 我说用哈希表记录每个字符出现次数，然后他又补充问到哈希表是怎么工作的，我说包
: 括哈希函数和冲突处理两部分，并简述了一下，说由于字符不太多，可以用链表处理冲突
: ３、如果这个字符串含有32位Unicode字符的串，如何修改之前的算法
: 我说为了节省空间，可以把冲突处理方式改成rehashing
: ４、如果一个同事提出用一个array来记录各个字符的次数，比较你的算法和该同事算
: 法的优劣
|
l****p
发帖数: 397 | 25 其实那个我当时也觉得不需要改，既然他让改，那就小改点。我估计他期望我第二题用
array实现，然后提出第3题问我怎么改算法，没想到我第2题就直接用hash，却继续按
准备好的问题问我
【在 b******g 的大作中提到】
: 问一下第3题，为啥要修改之前第2题的算法？ 用chain不是不错啊。
:
: 冲突
|
H*M
发帖数: 1268 | 26 我也没明白什么叫hash不能在两台机器中传？
hash后ascii只有狠小的array,mapreduce的话，中间shuffle带宽肯定比这多
【在 l****p 的大作中提到】
: 你就直接理解成不能把任何一台机器的本地结果全部传到另外一台机器上就是了。我只
: 是凭记忆分享一下面经，你这么激动干嘛，又不是非得让你做
|
l****p
发帖数: 397 | 27 这个是针对32位unicode的，用hash来存32位unicode字符的记数，这个hash可能会很大
【在 H*M 的大作中提到】
: 我也没明白什么叫hash不能在两台机器中传？
: hash后ascii只有狠小的array,mapreduce的话，中间shuffle带宽肯定比这多
|
b******b
发帖数: 300 | 28 ３、如果这个字符串含有32位Unicode字符的串，如何修改之前的算法
这个为什么节省空间了 |
Y**B
发帖数: 144 | 29 1 面的6：给定了个整型数组，建立一个binary search tree
如果array不是sorted怎么建? 有什么其它的条件么? 如果没有,这个建出来的BST可能
有很多情况的. |
v***a
发帖数: 365 | 30
冲突
多谢分享！比atoi有意思多了。。。。
感觉32位Unicode字符统计BST或许会好点。
分布的情况貌似可以这样：
1）所有机器的Top 1% freqent unicodes. 得到这些集合的交集 X。
2）如果 X 是空集，扩展到2%，重做，直到X不是空集。
3）频率最高的在 X 中，统计X中所有unicodes的频率，取最高
肯定code不出来了，涉及到了BST, Heap, Hash, Disjoint Set and splay tree.
而且最坏情况还是传输了所有机器的 BST……比 hash 还糟糕点，呵呵
攒点字数，RP守恒！
【在 l****p 的大作中提到】
: 两通电话，每个45min，到最后两个都超时
: 第一通电话：
: １、指定我简历中的一篇一作文章，让我描述那文章里的内容
: ２、如何从一个只含有ASCII字符的字符串中找出最频繁的字符
: 我说用哈希表记录每个字符出现次数，然后他又补充问到哈希表是怎么工作的，我说包
: 括哈希函数和冲突处理两部分，并简述了一下，说由于字符不太多，可以用链表处理冲突
: ３、如果这个字符串含有32位Unicode字符的串，如何修改之前的算法
: 我说为了节省空间，可以把冲突处理方式改成rehashing
: ４、如果一个同事提出用一个array来记录各个字符的次数，比较你的算法和该同事算
: 法的优劣
|
|
|
z*****n
发帖数: 447 | 31 go through the array, and insert the elements into BST one by one.
【在 Y**B 的大作中提到】
: 1 面的6：给定了个整型数组，建立一个binary search tree
: 如果array不是sorted怎么建? 有什么其它的条件么? 如果没有,这个建出来的BST可能
: 有很多情况的.
|
