M**********7
发帖数: 378 | 1 四轮白板
每轮一个面试官一个观察者
估计下面面试很多要培训面试官
其实这样反而好, 一定程度上保证了公正性,
起码不会让面试官肆无忌惮的搞无耻.
一个东欧的头,口音重,但做到上面交流没问题.
一个印度mm,口音不重,虽然能听出来一点,人挺和善.
一个白,感觉是极客那种,人挺和善.
一个美华,很有活力,也挺和善.
题不难,不用英文描述了,大家懂的.
面的题:
1
打印给定树,指定层的节点.
写好程序后,写测试用例.
对方选择一个用例进行测试.
2.
判断两个词是否由相同的字母重排构成(你懂的)
找一个字符串里面的最长对称子串(你也懂的)
3.
一个数组,先严格升序,再严格降序,找最大值.
测试用例,对方选例测试.
4.
设计一个缓存系统,每个元素的生命周期后自动注销,实现get, save, 和内部注销机制.
闲聊的题:
1. 最近看过什么书,最喜欢的是什么书
2. 怎样设计网络爬虫, 怎样解析网页中的邮件地址.
总体聊的不错,互有问答,但面头的时候卡了被提示了一次,
写完又忘记处理一个case,应该会减分很多,可能不行了吧. |
M**********7
发帖数: 378 | |
t*********7
发帖数: 255 | 3 应该没问题啊...小BUG正常啊...关键是能马上改正就好了吧 |
M**********7
发帖数: 378 | 4 之前两轮电面
一题是给两个字符串,其中一个作为排序依据,排另外一个字串.
比如
mitbbs, bt
结果
bbtmis
可以假设第二个里面无重复字符,不出现的字符任意放在最后面可以.
另外的电面题再回想中,应该不难.... |
t*********7
发帖数: 255 | 5 应该没问题啊...小BUG正常啊...关键是能马上改正就好了吧 |
M**********7
发帖数: 378 | 6 谢谢,希望吧.
主要是老大出来以后不像别人那样都握个手寒暄一下,而是直接去找另外一个被面的说
话了,
说他们之前电面过,但今天不好意思安排不开不能亲面.
是不是不待见我的说. LD要求深刻反省中.
【在 t*********7 的大作中提到】
: 应该没问题啊...小BUG正常啊...关键是能马上改正就好了吧
|
t*********7
发帖数: 255 | 7 应该没问题
【在 M**********7 的大作中提到】
: 谢谢,希望吧.
: 主要是老大出来以后不像别人那样都握个手寒暄一下,而是直接去找另外一个被面的说
: 话了,
: 说他们之前电面过,但今天不好意思安排不开不能亲面.
: 是不是不待见我的说. LD要求深刻反省中.
|
p*****2
发帖数: 21240 | |
a********d
发帖数: 195 | 9 2.2 麻烦谁能给个java的例子么？好像是suffix tree但是具体的还不是很明白。
4的话用lru的思路行么？linkedlist + hashtable，不过每次time tick都要更新链表
和hash好像不好。 |
M**********7
发帖数: 378 | 10
suffix tree反正我现场不可能用的，这题就是每次找串从中心开始扩展，平方的复杂
度。不知道有没更好的。
我就是用的这种，time tick用timer的callback，尽量用一个timer 然后根据元素的时
间戳更新下次查看时间。
【在 a********d 的大作中提到】
: 2.2 麻烦谁能给个java的例子么？好像是suffix tree但是具体的还不是很明白。
: 4的话用lru的思路行么？linkedlist + hashtable，不过每次time tick都要更新链表
: 和hash好像不好。
|
|
|
t********3
发帖数: 567 | |
M**********7
发帖数: 378 | 12 就是上面的apollopffd 讲的。
哈希表存数据保证简单存取。
用一个队列存时间和元素。
存取就只看哈希表。
存取的时候注意根据需要要维护下计时器（比如第一个或者最后一个）。
然后计时器到时候清除到期元素在哈希表以及队列。
注意多线程情况。
【在 t********3 的大作中提到】
: 缓存系统
: lz可以说一下思路么？
|
M**********7
发帖数: 378 | 13 顺便发一个花旗的题，看看大家会不会做，偶没想出来很好的方法：
一个数组，所有的数字重复一次，除了两个数字只出现一次，要求找到这两个数字。
只能用O1空间(不能哈希)，少于平方时间。
排序不可 (此行为原贴遗漏，后修改加入)
一个偶会，两个是不是要用些数学的结论？ |
p*****2
发帖数: 21240 | 14
少于平方时间，sort不就行了？
【在 M**********7 的大作中提到】
: 顺便发一个花旗的题，看看大家会不会做，偶没想出来很好的方法：
: 一个数组，所有的数字重复一次，除了两个数字只出现一次，要求找到这两个数字。
: 只能用O1空间(不能哈希)，少于平方时间。
: 排序不可 (此行为原贴遗漏，后修改加入)
: 一个偶会，两个是不是要用些数学的结论？
|
p*****2
发帖数: 21240 | 15
2.2 扫一遍就行了吧？N^2复杂度。
【在 a********d 的大作中提到】
: 2.2 麻烦谁能给个java的例子么？好像是suffix tree但是具体的还不是很明白。
: 4的话用lru的思路行么？linkedlist + hashtable，不过每次time tick都要更新链表
: 和hash好像不好。
|
M**********7
发帖数: 378 | 16 忘了说，排序也被禁了。
【在 p*****2 的大作中提到】
:
: 2.2 扫一遍就行了吧？N^2复杂度。
|
a********d
发帖数: 195 | 17 2.2这么写感觉挺麻烦的啊，还要分abba和abcba两种情况。
能不能说说你的思路？
【在 M**********7 的大作中提到】
: 忘了说，排序也被禁了。
|
M**********7
发帖数: 378 | 18 我就是这么写的，用一个方法，加一个参数来区分这两种情况，因为只是初始条件不同。
在主循环中对同一个位置分别调用一次，之后取大。
从交流中感觉是对方要的做法。
【在 a********d 的大作中提到】
: 2.2这么写感觉挺麻烦的啊，还要分abba和abcba两种情况。
: 能不能说说你的思路？
|
r*******n
发帖数: 3020 | 19 1) sort the array in nlogn
2) scan the array in n
get them.
【在 M**********7 的大作中提到】
: 顺便发一个花旗的题，看看大家会不会做，偶没想出来很好的方法：
: 一个数组，所有的数字重复一次，除了两个数字只出现一次，要求找到这两个数字。
: 只能用O1空间(不能哈希)，少于平方时间。
: 排序不可 (此行为原贴遗漏，后修改加入)
: 一个偶会，两个是不是要用些数学的结论？
|
M**********7
发帖数: 378 | 20 当时被三哥带到小黑屋里问的，其他还问了许多语言细节性问题，感觉被搞了。
【在 M**********7 的大作中提到】
: 忘了说，排序也被禁了。
|
|
|
M**********7
发帖数: 378 | 21 排序不可。
【在 r*******n 的大作中提到】
: 1) sort the array in nlogn
: 2) scan the array in n
: get them.
|
j*******l
发帖数: 19 | |
r********g
发帖数: 1351 | 23 这个有时间空间的要求吗。。我想“bt”用hashtable存，改一下compare函数。。。
【在 M**********7 的大作中提到】
: 之前两轮电面
: 一题是给两个字符串,其中一个作为排序依据,排另外一个字串.
: 比如
: mitbbs, bt
: 结果
: bbtmis
: 可以假设第二个里面无重复字符,不出现的字符任意放在最后面可以.
: 另外的电面题再回想中,应该不难....
|
b********y
发帖数: 42 | 24 对所有数进行异或，得到的是那两个出现一次的数字的异或值。其他出现两次的异或后
都清0.
然后根据异或值找出任何等于1的位A。
然后再进行两次异或。一次异或对于所有A位上是1的数，第二次异或对于所有A位上是0
的数。
两次异或后分别得到的结果就是所求的两个数字。
好像这题在哪见过.
？
【在 M**********7 的大作中提到】
: 顺便发一个花旗的题，看看大家会不会做，偶没想出来很好的方法：
: 一个数组，所有的数字重复一次，除了两个数字只出现一次，要求找到这两个数字。
: 只能用O1空间(不能哈希)，少于平方时间。
: 排序不可 (此行为原贴遗漏，后修改加入)
: 一个偶会，两个是不是要用些数学的结论？
|
M**********7
发帖数: 378 | 25 标记下回来慢慢看。
是0
【在 b********y 的大作中提到】
: 对所有数进行异或，得到的是那两个出现一次的数字的异或值。其他出现两次的异或后
: 都清0.
: 然后根据异或值找出任何等于1的位A。
: 然后再进行两次异或。一次异或对于所有A位上是1的数，第二次异或对于所有A位上是0
: 的数。
: 两次异或后分别得到的结果就是所求的两个数字。
: 好像这题在哪见过.
:
: ？
|
a********d
发帖数: 195 | 26 看一个帖子说是suffix和string的逆序的suffix找common ancestor什么的...完全找不
到那个帖子了。两个for好像有点暴力。
题做了过一阵就忘记了...
希望到西雅图有个好状态。
【在 p*****2 的大作中提到】
:
: 2.2 扫一遍就行了吧？N^2复杂度。
|
p*****2
发帖数: 21240 | 27
是0
能不能举个例子
【在 b********y 的大作中提到】
: 对所有数进行异或，得到的是那两个出现一次的数字的异或值。其他出现两次的异或后
: 都清0.
: 然后根据异或值找出任何等于1的位A。
: 然后再进行两次异或。一次异或对于所有A位上是1的数，第二次异或对于所有A位上是0
: 的数。
: 两次异或后分别得到的结果就是所求的两个数字。
: 好像这题在哪见过.
:
: ？
|
M**********7
发帖数: 378 | 28 没说要求，就是提了几个思路，然后对方说喜欢那个就开搞了。
我是用的计数排序，因为字母就那么多，也是哈希存排序字，这样排序只需要线性。
【在 r********g 的大作中提到】
: 这个有时间空间的要求吗。。我想“bt”用hashtable存，改一下compare函数。。。
|
r********g
发帖数: 1351 | 29 多谢多谢，刚才觉得这个有点复杂了，等会编一下。。感觉lz这实力应该没啥问题的，
大大地bless！
【在 M**********7 的大作中提到】
: 没说要求，就是提了几个思路，然后对方说喜欢那个就开搞了。
: 我是用的计数排序，因为字母就那么多，也是哈希存排序字，这样排序只需要线性。
|
M**********7
发帖数: 378 | 30 偶的经验是别太执着于答案和题，而影响了自己的状态。
有想法就多说说思路，对方正常的话都会有些对答。
交流感觉好比算法好要重要，当然算法不能太差。
快上阵了就让自己放开些。bless
【在 a********d 的大作中提到】
: 看一个帖子说是suffix和string的逆序的suffix找common ancestor什么的...完全找不
: 到那个帖子了。两个for好像有点暴力。
: 题做了过一阵就忘记了...
: 希望到西雅图有个好状态。
|
|
|
b********y
发帖数: 42 | 31 找了一下，果然是老题。怪不得有印象。
http://zhedahht.blog.163.com/blog/static/2541117420071128950682
是0
能不能举个例子
【在 b********y 的大作中提到】
: 对所有数进行异或，得到的是那两个出现一次的数字的异或值。其他出现两次的异或后
: 都清0.
: 然后根据异或值找出任何等于1的位A。
: 然后再进行两次异或。一次异或对于所有A位上是1的数，第二次异或对于所有A位上是0
: 的数。
: 两次异或后分别得到的结果就是所求的两个数字。
: 好像这题在哪见过.
:
: ？
|
M**********7
发帖数: 378 | 32 这个就是经典的安娜格拉姆。
一个经典的方法是排序后比较。
另外一个就是哈希计数。
开始说了这两个思路，让给出复杂度，后来选择了哈希计数。
要求用一个哈希表，也没什么就是一次加，一次减。
【在 j*******l 的大作中提到】
: 2.1 给个思路吧
|
M**********7
发帖数: 378 | 33 亲到时别太执着了，到时候可以想一个你能当时做的思路，然后同时抛出这两个思路，
吹一下suffix树，然后说这个现在肯定写不完啥的。对方估计会让你写另外一个。
【在 a********d 的大作中提到】
: 看一个帖子说是suffix和string的逆序的suffix找common ancestor什么的...完全找不
: 到那个帖子了。两个for好像有点暴力。
: 题做了过一阵就忘记了...
: 希望到西雅图有个好状态。
|
M**********7
发帖数: 378 | 34 原来这样，不过这个现场想我肯定不行。
【在 b********y 的大作中提到】
: 找了一下，果然是老题。怪不得有印象。
: http://zhedahht.blog.163.com/blog/static/2541117420071128950682
:
: 是0
: 能不能举个例子
|
s***y
发帖数: 203 | |
a********d
发帖数: 195 | 36 板上原来的题。xor找这两个数的抑或，找到第一个不同的位置将所有数按此位分两组
，分别异或得结果。
【在 M**********7 的大作中提到】
: 顺便发一个花旗的题，看看大家会不会做，偶没想出来很好的方法：
: 一个数组，所有的数字重复一次，除了两个数字只出现一次，要求找到这两个数字。
: 只能用O1空间(不能哈希)，少于平方时间。
: 排序不可 (此行为原贴遗漏，后修改加入)
: 一个偶会，两个是不是要用些数学的结论？
|
M**********7
发帖数: 378 | 37 写代码，但是有想法先交流一下是好习惯。
【在 s***y 的大作中提到】
: 题目是现场写代码还是说说思路就可以啊？
|
h*********n
发帖数: 46 | 38 这题应该用hashtable 和 min heap吧，libevent中处理timer就是用min heap做的。
【在 M**********7 的大作中提到】
: 就是上面的apollopffd 讲的。
: 哈希表存数据保证简单存取。
: 用一个队列存时间和元素。
: 存取就只看哈希表。
: 存取的时候注意根据需要要维护下计时器（比如第一个或者最后一个）。
: 然后计时器到时候清除到期元素在哈希表以及队列。
: 注意多线程情况。
|
p*****2
发帖数: 21240 | 39
牛。多谢。
【在 b********y 的大作中提到】
: 找了一下，果然是老题。怪不得有印象。
: http://zhedahht.blog.163.com/blog/static/2541117420071128950682
:
: 是0
: 能不能举个例子
|
M**********7
发帖数: 378 | 40 min heap插删应该是log n 稍微多一点，不过可以轻易支持不统一的生命长度。
【在 h*********n 的大作中提到】
: 这题应该用hashtable 和 min heap吧，libevent中处理timer就是用min heap做的。
|
|
|
p*****2
发帖数: 21240 | 41
我写了一个练练。
def findDup(l):
xor=0
for i in l:
xor^=i
checker=1
while not (xor & checker):
checker<<=1
ans=[0,0]
for i in l:
if i&checker:
ans[0]^=i
else:
ans[1]^=i
return ans
l=[1,1,2,2,3,3,4,5]
print findDup(l)
【在 M**********7 的大作中提到】
: 顺便发一个花旗的题，看看大家会不会做，偶没想出来很好的方法：
: 一个数组，所有的数字重复一次，除了两个数字只出现一次，要求找到这两个数字。
: 只能用O1空间(不能哈希)，少于平方时间。
: 排序不可 (此行为原贴遗漏，后修改加入)
: 一个偶会，两个是不是要用些数学的结论？
|
M**********7
发帖数: 378 | 42 赞简洁
【在 p*****2 的大作中提到】
:
: 我写了一个练练。
: def findDup(l):
: xor=0
: for i in l:
: xor^=i
:
: checker=1
:
: while not (xor & checker):
|
M**********7
发帖数: 378 | 43 想起来了另外一个面题
求x乘y
可以假设正数
要求Olog(min(X/Y))
用位操作做
【在 M**********7 的大作中提到】
: 之前两轮电面
: 一题是给两个字符串,其中一个作为排序依据,排另外一个字串.
: 比如
: mitbbs, bt
: 结果
: bbtmis
: 可以假设第二个里面无重复字符,不出现的字符任意放在最后面可以.
: 另外的电面题再回想中,应该不难....
|
j*******l
发帖数: 19 | 44 第3题方法是不是有点类似Binary Search? |
M**********7
发帖数: 378 | 45 对，属于二分查找变种题之一。
类似的一道经典题是严格升序数组移位查找最大值位置
如789123456
【在 j*******l 的大作中提到】
: 第3题方法是不是有点类似Binary Search?
|
