由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 攒人品发亚麻家面经
相关主题
问一道题一个算法题目
google phone interview question贡献一道面试题目:找出在一个数组里面只出现1次的两个数字
有没有大虾可以终结一下和“字典”相关的题目啊?About 异或
facebook 面经一道位运算题
G 面经貌似是G家的面试题。。。吧。。。
word search follow up的问题A家一道题
一道M$算法题。关于OPT新规则的行政程序法背景
被基础题搞挂了请教2个 huge file的面试题
相关话题的讨论汇总
话题: checker话题: ans话题: xor话题: finddup话题: 异或
进入JobHunting版参与讨论
1 (共1页)
M**********7
发帖数: 378
1
四轮白板
每轮一个面试官一个观察者
估计下面面试很多要培训面试官
其实这样反而好, 一定程度上保证了公正性,
起码不会让面试官肆无忌惮的搞无耻.
一个东欧的头,口音重,但做到上面交流没问题.
一个印度mm,口音不重,虽然能听出来一点,人挺和善.
一个白,感觉是极客那种,人挺和善.
一个美华,很有活力,也挺和善.
题不难,不用英文描述了,大家懂的.
面的题:
1
打印给定树,指定层的节点.
写好程序后,写测试用例.
对方选择一个用例进行测试.
2.
判断两个词是否由相同的字母重排构成(你懂的)
找一个字符串里面的最长对称子串(你也懂的)
3.
一个数组,先严格升序,再严格降序,找最大值.
测试用例,对方选例测试.
4.
设计一个缓存系统,每个元素的生命周期后自动注销,实现get, save, 和内部注销机制.
闲聊的题:
1. 最近看过什么书,最喜欢的是什么书
2. 怎样设计网络爬虫, 怎样解析网页中的邮件地址.
总体聊的不错,互有问答,但面头的时候卡了被提示了一次,
写完又忘记处理一个case,应该会减分很多,可能不行了吧.
M**********7
发帖数: 378
2
所有算法设计方案问复杂度.
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
8
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好像不好。

相关主题
word search follow up的问题一个算法题目
一道M$算法题。贡献一道面试题目:找出在一个数组里面只出现1次的两个数字
被基础题搞挂了About 异或
进入JobHunting版参与讨论
t********3
发帖数: 567
11
缓存系统
lz可以说一下思路么?
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 的大作中提到】
: 忘了说,排序也被禁了。
相关主题
一道位运算题关于OPT新规则的行政程序法背景
貌似是G家的面试题。。。吧。。。请教2个 huge file的面试题
A家一道题求“bar组成的histogram求最大内切矩形”的link...
进入JobHunting版参与讨论
M**********7
发帖数: 378
21
排序不可。

【在 r*******n 的大作中提到】
: 1) sort the array in nlogn
: 2) scan the array in n
: get them.

j*******l
发帖数: 19
22
2.1 给个思路吧
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好像有点暴力。
: 题做了过一阵就忘记了...
: 希望到西雅图有个好状态。

相关主题
facebook面试google phone interview question
Amazon onsite面经有没有大虾可以终结一下和“字典”相关的题目啊?
问一道题facebook 面经
进入JobHunting版参与讨论
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
35
题目是现场写代码还是说说思路就可以啊?
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做的。
相关主题
facebook 面经一道M$算法题。
G 面经被基础题搞挂了
word search follow up的问题一个算法题目
进入JobHunting版参与讨论
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?
1 (共1页)
进入JobHunting版参与讨论
相关主题
请教2个 huge file的面试题G 面经
求“bar组成的histogram求最大内切矩形”的link...word search follow up的问题
facebook面试一道M$算法题。
Amazon onsite面经被基础题搞挂了
问一道题一个算法题目
google phone interview question贡献一道面试题目:找出在一个数组里面只出现1次的两个数字
有没有大虾可以终结一下和“字典”相关的题目啊?About 异或
facebook 面经一道位运算题
相关话题的讨论汇总
话题: checker话题: ans话题: xor话题: finddup话题: 异或