一亩三分地论坛

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

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

Facebook 电面第二轮,已过

[复制链接] |试试Instant~ |关注本帖
fame 发表于 2016-3-9 02:04:59 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 博士 全职@Facebook - 猎头 - 技术电面 |Pass在职跳槽

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

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

x
第一轮的面筋搜索一下我的id就能找到,很简单的一道print binary tree vertical

第二轮是一个老毛子,迟到了10分钟,但是很礼貌的问我是不是要reschedule,因为需要45分钟,我说不需要,结果面了一个小时
第一个问题,找出两个给出两个string, leetcode, codyabc和一个数字k = 3,问两个string里面存不存在连续的common substring大于等于k.比如这个例子,两个string都有cod,所以返回true。楼主用dp建了一个m*n的table秒了,然后写test case,发现有个小corner case,改了,pass
第二个问题就是LCA in BST.输入是两个value,不是node.瞬秒,无bug. Follow up是统计问题,如果这两个值是随机从这颗树里面sample,问我的算法平均需要几次比较就可以得出结果。这题大家可以想一想,很有意思,涉及到一些统计的分布。答案我过几天公布。

接下来onsite,求祝福!

评分

2

查看全部评分

 楼主| fame 发表于 2016-3-14 13:10:47 | 显示全部楼层
xiaohui5319 发表于 2016-3-13 11:31
是这个意思吗?楼主,十分感谢!!!!

bool check(string& a, string& b) {

不是。在else里面dp[i,j]应该等于0.所以else没有必要
回复 支持 1 反对 0

使用道具 举报

weihe2015 发表于 2016-3-9 02:52:00 | 显示全部楼层
congs,楼主厉害啊。。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-9 03:00:54 | 显示全部楼层
第一个问题,找出两个给出两个string, leetcode, codyabc和一个数字k = 3,问两个string里面存不存在连续的common substring大于等于k.比如这个例子,两个string都有cod,所以返回true。楼主用dp建了一个m*n的table秒了,然后写test case,发现有个小corner case,改了,pass. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. from: 1point3acres.com/bbs
may you tell me the question name in Leetcode ????
回复 支持 反对

使用道具 举报

 楼主| fame 发表于 2016-3-9 03:13:17 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-9 03:00
第一个问题,找出两个给出两个string, leetcode, codyabc和一个数字k = 3,问两个string里面存不存在连续的c ...

不是leetcode的题,很简单的,想想
回复 支持 反对

使用道具 举报

战栗的百香果 发表于 2016-3-9 03:13:46 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-9 03:00
第一个问题,找出两个给出两个string, leetcode, codyabc和一个数字k = 3,问两个string里面存不存在连续的c ...

我不知道leet上有没有,但是好像楼主并没有明显的说leet有啊- -,leetcode只是他说的两个string中一个叫"leetcode"。。。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-9 03:19:38 | 显示全部楼层
fame 发表于 2016-3-9 03:13
不是leetcode的题,很简单的,想想
. Waral 鍗氬鏈夋洿澶氭枃绔,
what is "m*n的table"?????
public void boolean(String A, String B, int k). 鍥磋鎴戜滑@1point 3 acres
{

        for(int i =0;i < A.length()-3;i++)
        {
            if(B.indexof(A.substring(i,i+3))!=-1) return true;
         }

        return false;
}. Waral 鍗氬鏈夋洿澶氭枃绔,



}
回复 支持 反对

使用道具 举报

 楼主| fame 发表于 2016-3-9 03:21:49 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-9 03:19
what is "m*n的table"?????
public void boolean(String A, String B, int k)
{

你这个算法复杂度是多少?如果k很大呢?用indexof是不是很费时间。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-9 03:25:56 | 显示全部楼层
fame 发表于 2016-3-9 03:21. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
你这个算法复杂度是多少?如果k很大呢?用indexof是不是很费时间。
. more info on 1point3acres.com
so what is "dp建了一个m*n的table秒了"

补充内容 (2016-3-9 03:34):. From 1point 3acres bbs
http://algorithms.tutorialhorizo ... t-common-substring/
回复 支持 反对

使用道具 举报

 楼主| fame 发表于 2016-3-9 03:36:08 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-9 03:25
so what is "dp建了一个m*n的table秒了". 1point3acres.com/bbs

补充内容 (2016-3-9 03:34):

这题用hashtable存A里面长度为k的字符,然后用b里面长度为k的字符去匹配也行。
我的方法是 dp[i,j] = dp[i-1,j-1] + 1 if (a == b) else 0,然后每次都check dp[i,j]是否大于等于k就行了
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-9 03:39:58 | 显示全部楼层
fame 发表于 2016-3-9 03:36
这题用hashtable存A里面长度为k的字符,然后用b里面长度为k的字符去匹配也行。
我的方法是 dp = dp + 1  ...

https://www.youtube.com/watch?v=BysNXJHzCEs
回复 支持 反对

使用道具 举报

 楼主| fame 发表于 2016-3-9 06:58:16 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-9 03:39
https://www.youtube.com/watch?v=BysNXJHzCEs

正确。我就是这么解的。很脑残的k=1的时候初始化忘了check,后来改过来了。
回复 支持 反对

使用道具 举报

xiaohui5319 发表于 2016-3-13 11:31:33 | 显示全部楼层
是这个意思吗?楼主,十分感谢!!!!
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
bool check(string& a, string& b) {
    if (a.length() < k || b.length() < k) return false;
    //next dynamic programming
    int m = a.length();. Waral 鍗氬鏈夋洿澶氭枃绔,
    int n = b.length();. 1point 3acres 璁哄潧
    vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));.鐣欏璁哄潧-涓浜-涓夊垎鍦
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i] == b[j]) {
                dp[i][j] = dp[i-1][j-1] + 1;. more info on 1point3acres.com
            } else {. visit 1point3acres.com for more.
                dp[i][j] = max(dp[i-1][j], dp[i], [j-1]);
            } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            if (dp[i][j] >= k) return true;
        }.鐣欏璁哄潧-涓浜-涓夊垎鍦
    }
    return false;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
}
回复 支持 反对

使用道具 举报

tldxk 发表于 2016-3-15 03:06:37 | 显示全部楼层
common substring是这道题吧?
http://www.lintcode.com/zh-cn/problem/longest-common-substring/

另外想问下楼主,两道题瞬秒的话一个小时其他时间还问了啥呢?感觉follow up也不用太久呀
回复 支持 反对

使用道具 举报

 楼主| fame 发表于 2016-3-16 05:32:44 | 显示全部楼层
tldxk 发表于 2016-3-15 03:06
common substring是这道题吧?
http://www.lintcode.com/zh-cn/problem/longest-common-substring/
. more info on 1point3acres.com
楼主是PhD所以闲扯了很多research,问了paper里面的细节。然后花了很多时间写test case.最后是在第二题那个“问算法平均需要几次比较得到结果” 里面想了一会儿。
回复 支持 反对

使用道具 举报

sealove999 发表于 2016-4-18 09:15:53 | 显示全部楼层
撸主你说过几天给followup答案的呢在哪里
回复 支持 反对

使用道具 举报

hello2pig 发表于 2016-8-5 00:43:07 | 显示全部楼层
fame 发表于 2016-3-9 03:21
你这个算法复杂度是多少?如果k很大呢?用indexof是不是很费时间。

用一个hashset保存第一个str的substr(3),再traversal第二个str的substr看是否在hashset中。时间复杂度m+n. 好于dp的m*n
回复 支持 反对

使用道具 举报

null_point_exc 发表于 2016-8-6 09:48:35 | 显示全部楼层
  1.         public boolean commonSub(String s1,String s2,int k){
  2.                 int len=s1.length();
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  3.                 int wid=s2.length();
  4.                 if(k>len || k>wid) return false;
  5.                 char[] arr1=s1.toCharArray();
  6.                 char[] arr2=s2.toCharArray();

  7.                 int[][] dp=new int[wid][len];
  8.                
  9.                 for(int i=1;i<wid;i++){
  10.                         for(int j=1;j<len;j++){
  11.                                 if(arr2[i]==arr1[j]){. visit 1point3acres.com for more.
  12.                                         dp[i][j]=dp[i-1][j-1]+1;
  13.                                 }else{.1point3acres缃
  14.                                         dp[i][j]=0;
  15.                                 }
  16.                                 if(dp[i][j]>=k) return true;. From 1point 3acres bbs
  17.                         }.1point3acres缃
  18.                 }

  19.                 return false;
  20.         }
复制代码
回复 支持 反对

使用道具 举报

lvvvvv 发表于 2016-8-6 11:38:07 | 显示全部楼层
第二题 是不是  0.5*1 + 0.5^2*2 + 0.5^3*3 + 0.5^4*4 + ....
这个等于多少 ??

补充内容 (2016-8-6 11:43):
奥,  乘以 1/2 然后相减,  x-1/2x= 1/2+ 1/4 + 1/8     =》  x = 2.
平均 2 次 。 对不 ?
回复 支持 反对

使用道具 举报

edyyy 发表于 2016-8-6 11:46:21 | 显示全部楼层
楼主好厉害啊,祝onsite 顺利
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 11:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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