San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 8800|回复: 41
收起左侧

facebook 第二轮电面

[复制链接] |试试Instant~ |关注本帖
williamwangz 发表于 2015-4-14 06:44:50 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类General 硕士 实习@Facebook - 内推 - 技术电面  | Other | 其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
上周四面了f家电面的第二轮,一共两题。.本文原创自1point3acres论坛
第一题是Leetcode上Merge two sorted array, 唯一的不同点是两个array的有效长度都为n。

第二题是leetcode上strstr那道的衍生题, 要求implement function strstrp(String a, String b) returns index where any permutation of b is a substring of a.
. Waral 博客有更多文章,e.g.
strstrp("hello", ''ell") returns 1
strstrp("hello",  "lle") returns 1
strstrp("hello",  "wor") returns -1
. 1point3acres
我面试的时候是用解决minimum window那道题的思路考虑的,但面试的小哥说虽然work但实现起来太麻烦,有个简单的方法,也是用hash table,时间复杂度O(n), 不过没想出来,就用minimum window的方法做的,还没写完。。

以上.留学论坛-一亩-三分地

评分

2

查看全部评分

LumiG 发表于 2016-10-7 01:46:25 | 显示全部楼层
第二个就是leetcode 76吧,返回条件改一下就行,相对还好写一些。
回复 支持 1 反对 0

使用道具 举报

emersonxsu 发表于 2015-4-15 10:42:30 | 显示全部楼层
你一算permutation,就已经O(n!) time 了吧? 题目要求返回的是true or false, 我觉得没必要把序列排好再找.比如例子里, ell, lle, lel, 管它们怎么排,只要粘在一起,然后又在hello中显示了,就可以返回true了, 所以我觉得这题应该是KMP的简单版本, 先hashmap把子串b按char放入, value用来计数,比如这里'l'的count是2, 然后遍历母串a, 当发现有char在hashmap中而且value>0, 就value--, 继续,如果不在,就reset hashmap(我暂时想到就是保存一份原始的b串hashmap, 用来reset), 直到b.length() 次循环, 如果都没break,就返回true.
回复 支持 1 反对 0

使用道具 举报

mhbkb 发表于 2015-4-14 07:06:11 | 显示全部楼层
惊现王子   妥妥地过了~
回复 支持 1 反对 0

使用道具 举报

sheepmiemies 发表于 2015-4-22 07:18:19 | 显示全部楼层
LZ用的minimum window的思路是用的hashmap吗?
这道题我拿到想到的也是参照这个思路,用一个hashmap先存b中所有字符的次数统计。之后在a里,用两个index表示window,一个count来计算有效字符数,并且不停向右移动,每次都分别删除和加入一个字符,然后更新hashmap和count,一旦count == 0 返回true,否则false。这样对于每个字符,最多在hashmap里查找两次,更新两次,以及更新两次count,应该是O(n)的复杂度。
回复 支持 1 反对 0

使用道具 举报

yyboyz 发表于 2015-4-16 05:03:07 | 显示全部楼层
要nmlogm,  n 是a长度 m是b长度。  在a的每个位置截取a.substring(i,i+m) 排序,跟排序后的b相比 一样就返回。再好点的方法是: 在a的每个位置截取c=a.substring(i,i+m) ,把c每个字符和次数存进hashmap,然后拿b来对比  时间复杂度是O(m),总时间复杂度是O(mn)
回复 支持 1 反对 0

使用道具 举报

lihao814386741 发表于 2015-4-14 06:55:14 | 显示全部楼层
求出b串的所有permutation, 然后放入到hashtable中, 然后从头开始扫描a,如果子串在hashtable中则输出1否则输出-1????
回复 支持 反对

使用道具 举报

 楼主| williamwangz 发表于 2015-4-14 07:09:02 | 显示全部楼层
lihao814386741 发表于 2015-4-14 06:55
求出b串的所有permutation, 然后放入到hashtable中, 然后从头开始扫描a,如果子串在hashtable中则输出1否 ...

不过有个问题就是从a里去拿一个和b长度一样substring出来也会耗时吧。我也不知道正确答案。。。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

 楼主| williamwangz 发表于 2015-4-14 07:15:14 | 显示全部楼层
mhbkb 发表于 2015-4-14 07:06. 1point3acres
惊现王子   妥妥地过了~

你这个头像的意思是 吃掉一切bug?
回复 支持 反对

使用道具 举报

mhbkb 发表于 2015-4-14 07:17:07 | 显示全部楼层
williamwangz 发表于 2015-4-14 07:15
你这个头像的意思是 吃掉一切bug?

这只蜥蜴长得超漂亮
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-4-14 07:26:48 | 显示全部楼层
第二轮的bar是不是要至少完成两题呢?刚面完第二轮只写完了一题。。好忐忑
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-4-14 07:28:02 | 显示全部楼层
第二题我和LZ想法一样。。呵呵。。
回复 支持 反对

使用道具 举报

 楼主| williamwangz 发表于 2015-4-14 07:31:23 | 显示全部楼层
marthew777 发表于 2015-4-14 07:26
第二轮的bar是不是要至少完成两题呢?刚面完第二轮只写完了一题。。好忐忑
. 1point 3acres 论坛
不是吧,应该看题的难度了,莫担心
回复 支持 反对

使用道具 举报

 楼主| williamwangz 发表于 2015-4-15 13:01:57 | 显示全部楼层
emersonxsu 发表于 2015-4-15 10:42
你一算permutation,就已经O(n!) time 了吧? 题目要求返回的是true or false, 我觉得没必要把序列排好再找. ...

这样reset其实也比较麻烦,反而不如用两个hashmap去track。而且还有个问题就是,reset hashmap以后下一轮循环从哪里开始?
回复 支持 反对

使用道具 举报

lihao814386741 发表于 2015-4-15 13:06:45 | 显示全部楼层
emersonxsu 发表于 2015-4-15 10:42
你一算permutation,就已经O(n!) time 了吧? 题目要求返回的是true or false, 我觉得没必要把序列排好再找. ...

正解,受教了。。。。。。字数字数。。
回复 支持 反对

使用道具 举报

lihao814386741 发表于 2015-4-15 13:08:08 | 显示全部楼层
emersonxsu 发表于 2015-4-15 10:42
你一算permutation,就已经O(n!) time 了吧? 题目要求返回的是true or false, 我觉得没必要把序列排好再找. ...

正解,受教了。。。。。。字数字数。。
回复 支持 反对

使用道具 举报

lihao814386741 发表于 2015-4-15 13:19:52 | 显示全部楼层
emersonxsu 发表于 2015-4-15 10:42
你一算permutation,就已经O(n!) time 了吧? 题目要求返回的是true or false, 我觉得没必要把序列排好再找. ...

不过怎么把这个和KMP联系起来呢?
回复 支持 反对

使用道具 举报

lihao814386741 发表于 2015-4-19 06:29:04 | 显示全部楼层
emersonxsu 发表于 2015-4-15 10:42
你一算permutation,就已经O(n!) time 了吧? 题目要求返回的是true or false, 我觉得没必要把序列排好再找. ...

我突然想到这种方法的一个反例,比如a= elel,  b= ell, 如果采用你的方法的话结果是这样滴:
hashtable[e] = 1 hashtable[l] = 2;
e: 运行后 hashtable[e] = 0 hashtable[l] = 2;
-google 1point3acresl: 运行后 hashtable[e] = 0 hashtable[l] = 1;
e:运行后 发现e不在hashtable中, 重置, hashtable[e] = 0, hashtable[l] = 2;
l:运行后 hashtable[e] = 0, hashtable[l] = 1;
程序的结果是a串里没有b串。 但是实际上a中有lel。
回复 支持 反对

使用道具 举报

lihao814386741 发表于 2015-4-19 06:32:32 | 显示全部楼层
yyboyz 发表于 2015-4-16 05:03
要nmlogm,  n 是a长度 m是b长度。  在a的每个位置截取a.substring(i,i+m) 排序,跟排序后的b相比 一样就返 ...

那个再好点的方法的时间不是O(m), 应该是sigma, sigma是字符数量,如果要是ascii字符的话应该是256,可以看成常量。
回复 支持 反对

使用道具 举报

emersonxsu 发表于 2015-4-20 07:24:59 | 显示全部楼层
lihao814386741 发表于 2015-4-19 06:29
我突然想到这种方法的一个反例,比如a= elel,  b= ell, 如果采用你的方法的话结果是这样滴:
hashtable[ ...
.本文原创自1point3acres论坛
你重置hashtable的时候, e的counter应该恢复为起始的1, 而不是0. . 1point 3acres 论坛
所以发现 ele 不满足的话, i++, 就从 lel 开始了.
这个算法明显还可以用类似kmp的想法优化, 因为 le我们已经考虑过了,不需要再重新check. anyway,面试这样应该就够了把.
回复 支持 反对

使用道具 举报

lihao814386741 发表于 2015-4-20 07:34:59 | 显示全部楼层
emersonxsu 发表于 2015-4-20 07:24.1point3acres网
你重置hashtable的时候, e的counter应该恢复为起始的1, 而不是0.
所以发现 ele 不满足的话, i++, 就从  ...

是的,重置完了之后需要再减一的, 所以就变成0了。
回复 支持 反对

使用道具 举报

lihao814386741 发表于 2015-4-20 07:37:44 | 显示全部楼层
emersonxsu 发表于 2015-4-20 07:24. 1point3acres
你重置hashtable的时候, e的counter应该恢复为起始的1, 而不是0.
所以发现 ele 不满足的话, i++, 就从  ...
.留学论坛-一亩-三分地
明白你的朴素算法了。
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-26 06:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表