一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 5117|回复: 41
收起左侧

facebook 第二轮电面

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

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

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

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

x
上周四面了f家电面的第二轮,一共两题。
第一题是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.-google 1point3acres
e.g.
strstrp("hello", ''ell") returns 1
strstrp("hello",  "lle") returns 1
strstrp("hello",  "wor") returns -1

我面试的时候是用解决minimum window那道题的思路考虑的,但面试的小哥说虽然work但实现起来太麻烦,有个简单的方法,也是用hash table,时间复杂度O(n), 不过没想出来,就用minimum window的方法做的,还没写完。。

以上

评分

2

查看全部评分

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出来也会耗时吧。我也不知道正确答案。。。
回复 支持 反对

使用道具 举报

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

你这个头像的意思是 吃掉一切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是不是要至少完成两题呢?刚面完第二轮只写完了一题。。好忐忑

不是吧,应该看题的难度了,莫担心
回复 支持 反对

使用道具 举报

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.
回复 支持 反对

使用道具 举报

 楼主| 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
. 1point3acres.com/bbs你一算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, 我觉得没必要把序列排好再找. ...

. From 1point 3acres bbs不过怎么把这个和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;. 鍥磋鎴戜滑@1point 3 acres
l: 运行后 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[ ...

你重置hashtable的时候, e的counter应该恢复为起始的1, 而不是0.
所以发现 ele 不满足的话, i++, 就从 lel 开始了.
这个算法明显还可以用类似kmp的想法优化, 因为 le我们已经考虑过了,不需要再重新check. anyway,面试这样应该就够了把.
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 19:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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