avatar
攒人品发亚麻家面经# JobHunting - 待字闺中
M*7
1
四轮白板
每轮一个面试官一个观察者
估计下面面试很多要培训面试官
其实这样反而好, 一定程度上保证了公正性,
起码不会让面试官肆无忌惮的搞无耻.
一个东欧的头,口音重,但做到上面交流没问题.
一个印度mm,口音不重,虽然能听出来一点,人挺和善.
一个白,感觉是极客那种,人挺和善.
一个美华,很有活力,也挺和善.
题不难,不用英文描述了,大家懂的.
面的题:
1
打印给定树,指定层的节点.
写好程序后,写测试用例.
对方选择一个用例进行测试.
2.
判断两个词是否由相同的字母重排构成(你懂的)
找一个字符串里面的最长对称子串(你也懂的)
3.
一个数组,先严格升序,再严格降序,找最大值.
测试用例,对方选例测试.
4.
设计一个缓存系统,每个元素的生命周期后自动注销,实现get, save, 和内部注销机制.
闲聊的题:
1. 最近看过什么书,最喜欢的是什么书
2. 怎样设计网络爬虫, 怎样解析网页中的邮件地址.
总体聊的不错,互有问答,但面头的时候卡了被提示了一次,
写完又忘记处理一个case,应该会减分很多,可能不行了吧.
avatar
M*7
2
所有算法设计方案问复杂度.
avatar
t*7
3
应该没问题啊...小BUG正常啊...关键是能马上改正就好了吧
avatar
M*7
4
之前两轮电面
一题是给两个字符串,其中一个作为排序依据,排另外一个字串.
比如
mitbbs, bt
结果
bbtmis
可以假设第二个里面无重复字符,不出现的字符任意放在最后面可以.
另外的电面题再回想中,应该不难....
avatar
t*7
5
应该没问题啊...小BUG正常啊...关键是能马上改正就好了吧
avatar
M*7
6
谢谢,希望吧.
主要是老大出来以后不像别人那样都握个手寒暄一下,而是直接去找另外一个被面的说
话了,
说他们之前电面过,但今天不好意思安排不开不能亲面.
是不是不待见我的说. LD要求深刻反省中.

【在 t*********7 的大作中提到】
: 应该没问题啊...小BUG正常啊...关键是能马上改正就好了吧
avatar
t*7
7
应该没问题

【在 M**********7 的大作中提到】
: 谢谢,希望吧.
: 主要是老大出来以后不像别人那样都握个手寒暄一下,而是直接去找另外一个被面的说
: 话了,
: 说他们之前电面过,但今天不好意思安排不开不能亲面.
: 是不是不待见我的说. LD要求深刻反省中.

avatar
p*2
8
avatar
a*d
9
2.2 麻烦谁能给个java的例子么?好像是suffix tree但是具体的还不是很明白。
4的话用lru的思路行么?linkedlist + hashtable,不过每次time tick都要更新链表
和hash好像不好。
avatar
M*7
10

suffix tree反正我现场不可能用的,这题就是每次找串从中心开始扩展,平方的复杂
度。不知道有没更好的。
我就是用的这种,time tick用timer的callback,尽量用一个timer 然后根据元素的时
间戳更新下次查看时间。

【在 a********d 的大作中提到】
: 2.2 麻烦谁能给个java的例子么?好像是suffix tree但是具体的还不是很明白。
: 4的话用lru的思路行么?linkedlist + hashtable,不过每次time tick都要更新链表
: 和hash好像不好。

avatar
t*3
11
缓存系统
lz可以说一下思路么?
avatar
M*7
12
就是上面的apollopffd 讲的。
哈希表存数据保证简单存取。
用一个队列存时间和元素。
存取就只看哈希表。
存取的时候注意根据需要要维护下计时器(比如第一个或者最后一个)。
然后计时器到时候清除到期元素在哈希表以及队列。
注意多线程情况。

【在 t********3 的大作中提到】
: 缓存系统
: lz可以说一下思路么?

avatar
M*7
13
顺便发一个花旗的题,看看大家会不会做,偶没想出来很好的方法:
一个数组,所有的数字重复一次,除了两个数字只出现一次,要求找到这两个数字。
只能用O1空间(不能哈希),少于平方时间。
排序不可 (此行为原贴遗漏,后修改加入)
一个偶会,两个是不是要用些数学的结论?
avatar
p*2
14

少于平方时间,sort不就行了?

【在 M**********7 的大作中提到】
: 顺便发一个花旗的题,看看大家会不会做,偶没想出来很好的方法:
: 一个数组,所有的数字重复一次,除了两个数字只出现一次,要求找到这两个数字。
: 只能用O1空间(不能哈希),少于平方时间。
: 排序不可 (此行为原贴遗漏,后修改加入)
: 一个偶会,两个是不是要用些数学的结论?

avatar
p*2
15

2.2 扫一遍就行了吧?N^2复杂度。

【在 a********d 的大作中提到】
: 2.2 麻烦谁能给个java的例子么?好像是suffix tree但是具体的还不是很明白。
: 4的话用lru的思路行么?linkedlist + hashtable,不过每次time tick都要更新链表
: 和hash好像不好。

avatar
M*7
16
忘了说,排序也被禁了。

【在 p*****2 的大作中提到】
:
: 2.2 扫一遍就行了吧?N^2复杂度。

avatar
a*d
17
2.2这么写感觉挺麻烦的啊,还要分abba和abcba两种情况。
能不能说说你的思路?

【在 M**********7 的大作中提到】
: 忘了说,排序也被禁了。
avatar
M*7
18
我就是这么写的,用一个方法,加一个参数来区分这两种情况,因为只是初始条件不同。
在主循环中对同一个位置分别调用一次,之后取大。
从交流中感觉是对方要的做法。

【在 a********d 的大作中提到】
: 2.2这么写感觉挺麻烦的啊,还要分abba和abcba两种情况。
: 能不能说说你的思路?

avatar
r*n
19
1) sort the array in nlogn
2) scan the array in n
get them.

【在 M**********7 的大作中提到】
: 顺便发一个花旗的题,看看大家会不会做,偶没想出来很好的方法:
: 一个数组,所有的数字重复一次,除了两个数字只出现一次,要求找到这两个数字。
: 只能用O1空间(不能哈希),少于平方时间。
: 排序不可 (此行为原贴遗漏,后修改加入)
: 一个偶会,两个是不是要用些数学的结论?

avatar
M*7
20
当时被三哥带到小黑屋里问的,其他还问了许多语言细节性问题,感觉被搞了。

【在 M**********7 的大作中提到】
: 忘了说,排序也被禁了。
avatar
M*7
21
排序不可。

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

avatar
j*l
22
2.1 给个思路吧
avatar
r*g
23
这个有时间空间的要求吗。。我想“bt”用hashtable存,改一下compare函数。。。

【在 M**********7 的大作中提到】
: 之前两轮电面
: 一题是给两个字符串,其中一个作为排序依据,排另外一个字串.
: 比如
: mitbbs, bt
: 结果
: bbtmis
: 可以假设第二个里面无重复字符,不出现的字符任意放在最后面可以.
: 另外的电面题再回想中,应该不难....

avatar
b*y
24
对所有数进行异或,得到的是那两个出现一次的数字的异或值。其他出现两次的异或后
都清0.
然后根据异或值找出任何等于1的位A。
然后再进行两次异或。一次异或对于所有A位上是1的数,第二次异或对于所有A位上是0
的数。
两次异或后分别得到的结果就是所求的两个数字。
好像这题在哪见过.



【在 M**********7 的大作中提到】
: 顺便发一个花旗的题,看看大家会不会做,偶没想出来很好的方法:
: 一个数组,所有的数字重复一次,除了两个数字只出现一次,要求找到这两个数字。
: 只能用O1空间(不能哈希),少于平方时间。
: 排序不可 (此行为原贴遗漏,后修改加入)
: 一个偶会,两个是不是要用些数学的结论?

avatar
M*7
25
标记下回来慢慢看。

是0

【在 b********y 的大作中提到】
: 对所有数进行异或,得到的是那两个出现一次的数字的异或值。其他出现两次的异或后
: 都清0.
: 然后根据异或值找出任何等于1的位A。
: 然后再进行两次异或。一次异或对于所有A位上是1的数,第二次异或对于所有A位上是0
: 的数。
: 两次异或后分别得到的结果就是所求的两个数字。
: 好像这题在哪见过.
:
: ?

avatar
a*d
26
看一个帖子说是suffix和string的逆序的suffix找common ancestor什么的...完全找不
到那个帖子了。两个for好像有点暴力。
题做了过一阵就忘记了...
希望到西雅图有个好状态。

【在 p*****2 的大作中提到】
:
: 2.2 扫一遍就行了吧?N^2复杂度。

avatar
p*2
27

是0
能不能举个例子

【在 b********y 的大作中提到】
: 对所有数进行异或,得到的是那两个出现一次的数字的异或值。其他出现两次的异或后
: 都清0.
: 然后根据异或值找出任何等于1的位A。
: 然后再进行两次异或。一次异或对于所有A位上是1的数,第二次异或对于所有A位上是0
: 的数。
: 两次异或后分别得到的结果就是所求的两个数字。
: 好像这题在哪见过.
:
: ?

avatar
M*7
28
没说要求,就是提了几个思路,然后对方说喜欢那个就开搞了。
我是用的计数排序,因为字母就那么多,也是哈希存排序字,这样排序只需要线性。

【在 r********g 的大作中提到】
: 这个有时间空间的要求吗。。我想“bt”用hashtable存,改一下compare函数。。。
avatar
r*g
29
多谢多谢,刚才觉得这个有点复杂了,等会编一下。。感觉lz这实力应该没啥问题的,
大大地bless!

【在 M**********7 的大作中提到】
: 没说要求,就是提了几个思路,然后对方说喜欢那个就开搞了。
: 我是用的计数排序,因为字母就那么多,也是哈希存排序字,这样排序只需要线性。

avatar
M*7
30
偶的经验是别太执着于答案和题,而影响了自己的状态。
有想法就多说说思路,对方正常的话都会有些对答。
交流感觉好比算法好要重要,当然算法不能太差。
快上阵了就让自己放开些。bless

【在 a********d 的大作中提到】
: 看一个帖子说是suffix和string的逆序的suffix找common ancestor什么的...完全找不
: 到那个帖子了。两个for好像有点暴力。
: 题做了过一阵就忘记了...
: 希望到西雅图有个好状态。

avatar
b*y
31
找了一下,果然是老题。怪不得有印象。
http://zhedahht.blog.163.com/blog/static/2541117420071128950682

是0
能不能举个例子

【在 b********y 的大作中提到】
: 对所有数进行异或,得到的是那两个出现一次的数字的异或值。其他出现两次的异或后
: 都清0.
: 然后根据异或值找出任何等于1的位A。
: 然后再进行两次异或。一次异或对于所有A位上是1的数,第二次异或对于所有A位上是0
: 的数。
: 两次异或后分别得到的结果就是所求的两个数字。
: 好像这题在哪见过.
:
: ?

avatar
M*7
32
这个就是经典的安娜格拉姆。
一个经典的方法是排序后比较。
另外一个就是哈希计数。
开始说了这两个思路,让给出复杂度,后来选择了哈希计数。
要求用一个哈希表,也没什么就是一次加,一次减。

【在 j*******l 的大作中提到】
: 2.1 给个思路吧
avatar
M*7
33
亲到时别太执着了,到时候可以想一个你能当时做的思路,然后同时抛出这两个思路,
吹一下suffix树,然后说这个现在肯定写不完啥的。对方估计会让你写另外一个。

【在 a********d 的大作中提到】
: 看一个帖子说是suffix和string的逆序的suffix找common ancestor什么的...完全找不
: 到那个帖子了。两个for好像有点暴力。
: 题做了过一阵就忘记了...
: 希望到西雅图有个好状态。

avatar
s*y
35
题目是现场写代码还是说说思路就可以啊?
avatar
a*d
36
板上原来的题。xor找这两个数的抑或,找到第一个不同的位置将所有数按此位分两组
,分别异或得结果。

【在 M**********7 的大作中提到】
: 顺便发一个花旗的题,看看大家会不会做,偶没想出来很好的方法:
: 一个数组,所有的数字重复一次,除了两个数字只出现一次,要求找到这两个数字。
: 只能用O1空间(不能哈希),少于平方时间。
: 排序不可 (此行为原贴遗漏,后修改加入)
: 一个偶会,两个是不是要用些数学的结论?

avatar
M*7
37
写代码,但是有想法先交流一下是好习惯。

【在 s***y 的大作中提到】
: 题目是现场写代码还是说说思路就可以啊?
avatar
h*n
38
这题应该用hashtable 和 min heap吧,libevent中处理timer就是用min heap做的。

【在 M**********7 的大作中提到】
: 就是上面的apollopffd 讲的。
: 哈希表存数据保证简单存取。
: 用一个队列存时间和元素。
: 存取就只看哈希表。
: 存取的时候注意根据需要要维护下计时器(比如第一个或者最后一个)。
: 然后计时器到时候清除到期元素在哈希表以及队列。
: 注意多线程情况。

avatar
M*7
40
min heap插删应该是log n 稍微多一点,不过可以轻易支持不统一的生命长度。

【在 h*********n 的大作中提到】
: 这题应该用hashtable 和 min heap吧,libevent中处理timer就是用min heap做的。
avatar
p*2
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空间(不能哈希),少于平方时间。
: 排序不可 (此行为原贴遗漏,后修改加入)
: 一个偶会,两个是不是要用些数学的结论?

avatar
M*7
42
赞简洁

【在 p*****2 的大作中提到】
:
: 我写了一个练练。
: def findDup(l):
: xor=0
: for i in l:
: xor^=i
:
: checker=1
:
: while not (xor & checker):

avatar
M*7
43
想起来了另外一个面题
求x乘y
可以假设正数
要求Olog(min(X/Y))
用位操作做

【在 M**********7 的大作中提到】
: 之前两轮电面
: 一题是给两个字符串,其中一个作为排序依据,排另外一个字串.
: 比如
: mitbbs, bt
: 结果
: bbtmis
: 可以假设第二个里面无重复字符,不出现的字符任意放在最后面可以.
: 另外的电面题再回想中,应该不难....

avatar
j*l
44
第3题方法是不是有点类似Binary Search?
avatar
M*7
45
对,属于二分查找变种题之一。
类似的一道经典题是严格升序数组移位查找最大值位置
如789123456

【在 j*******l 的大作中提到】
: 第3题方法是不是有点类似Binary Search?
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。