logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
攒人品发亚麻家面经
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?
相关阅读
关于毁约2爷从java跳node了，过三五年要后悔吧微软的面试记录保存多久？ (转载)啥时候辞职比较好点？马鬃太搞笑了替朋友报个A的OfferFirmware test automation Engineer 这个工作怎么样？PI assessment是到了哪个阶段？airbnb有啥核心技术吗有没有experienced QA 同学对Apple感兴趣You are calibrated against candidate pool如何从一堆产品里选出一些产品来? (转载)lab126 工厂软件组招人groupon这破网站还不死呢？IT小公司要求真高。内推的帖子怎么越来越少了？从朋友圈看美国老中码农的悲哀请问Google家statistician 哪里刷题？这怎么总有个ID舔狗家舔的那么起劲？中国的讲师工作应该在简历里翻译成什么？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。