一亩三分地论坛

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

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

狗家电面

[复制链接] |试试Instant~ |关注本帖
lzlmike 发表于 2016-11-22 12:32:53 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 本科 全职@Google - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
新人分享一下,应该是个烙印,他迟到5分钟,一上来直接上题,题目网上有,给2个字符串,求find number of discontinous matches of first string in second one. 你们查一下,可以查到的。一开始看了下画个图发现是个树,然后和他说用dfs,他同意是个树,但让我用recursion,我就愣了一下。。能用iteration为啥要recursion....最后想了好久搞出个recursion的解法,跑了下testcase,. visit 1point3acres.com for more.
他看了一下,问了复杂度就说有meeting走人了,差不多45分钟吧。

. 鍥磋鎴戜滑@1point 3 acres后来发现这棵树有些节点是重复的,所以是个图,应该用dp,但是他竟然同意我是个树。。还让我写recursion....

一周后hr发邮件说要约我谈feedback.以为挂了。。然后他说good news 加面一轮电面。。。估计是我只写了一道题吧。。电面还真麻烦哈哈哈。
希望下轮可以进!



评分

1

查看全部评分

小A要当码农 发表于 2016-11-24 06:41:02 | 显示全部楼层
楼主,discontinuous match的意思是subsequence?
回复 支持 反对

使用道具 举报

忆梦前尘 发表于 2016-11-24 07:28:59 | 显示全部楼层
小A要当码农 发表于 2016-11-23 14:41
楼主,discontinuous match的意思是subsequence?
. 1point3acres.com/bbs
应该是吧。。。这道题用iteration写。。想了半天没想出来。。。。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-24 07:55:52 | 显示全部楼层
忆梦前尘 发表于 2016-11-24 07:28
应该是吧。。。这道题用iteration写。。想了半天没想出来。。。。

LC 原题呀?
回复 支持 反对

使用道具 举报

maston14 发表于 2016-11-24 08:13:39 | 显示全部楼层
21号面的。。也是个烙印。。也是这道题。。也写了dfs。。
回复 支持 反对

使用道具 举报

忆梦前尘 发表于 2016-11-24 08:52:27 | 显示全部楼层

是啊。。我也觉得是LC原题。。。就是死活想不出来怎么写了。。。求题号指点。
回复 支持 反对

使用道具 举报

 楼主| lzlmike 发表于 2016-11-24 09:02:51 | 显示全部楼层
maston14 发表于 2016-11-24 08:13.1point3acres缃
21号面的。。也是个烙印。。也是这道题。。也写了dfs。。

我说DFS结果被强行写了一个recursion的backtracking。。
回复 支持 反对

使用道具 举报

 楼主| lzlmike 发表于 2016-11-24 09:04:13 | 显示全部楼层

卧槽哪道0.0
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-24 23:23:50 | 显示全部楼层
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-24 23:24:36 | 显示全部楼层
忆梦前尘 发表于 2016-11-24 08:52. visit 1point3acres.com for more.
是啊。。我也觉得是LC原题。。。就是死活想不出来怎么写了。。。求题号指点。

LC115?
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-24 23:58:01 | 显示全部楼层
请问这个“discontinous matches”是一定要排除substring (i.e., continuous match)的意思吗?若不需要的话就是LC115         Distinct Subsequences。直接对s.substr(0,i)和t.substr(0,j)二维DP。若一定要排除substring的情况就是把LC115结果中减去KMP substring match的个数?
这个是一个LC115的DP解:
  1.     int numDistinct(string s, string t) {
  2.         int ns = s.length(), nt = t.length();
  3.         if (ns < nt) return 0; else if (nt == 0) return 1; else if (ns == 0) return 0;        . visit 1point3acres.com for more.
  4.         vector<int> prev(nt+1),cur(nt+1); prev[0] = 1;
  5.         for (int j = 1; j <= nt; ++j) prev[j] = 0;        
  6.         for (int i = 1; i <= ns; ++i) {
  7.             cur[0] = 1;. 1point3acres.com/bbs
  8.             for (int j = 1; j <= nt; ++j)
  9.             { if (s[i-1] == t[j-1]) cur[j] = prev[j-1] + prev[j]; else cur[j] = prev[j]; }
  10.             for (int j = 0; j <= nt; ++j) prev[j] = cur[j];. visit 1point3acres.com for more.
  11.         }
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  12.         return cur[nt];
  13.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| lzlmike 发表于 2016-11-25 04:50:06 | 显示全部楼层
zzgzzm 发表于 2016-11-24 23:58. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
请问这个“discontinous matches”是一定要排除substring (i.e., continuous match)的意思吗?若不需要的话 ...

substring在长的string里面的每个字母不能相邻,career cup上有原题
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-25 09:34:41 | 显示全部楼层
lzlmike 发表于 2016-11-25 04:50. visit 1point3acres.com for more.
substring在长的string里面的每个字母不能相邻,career cup上有原题

我就找到: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
https://www.careercup.com/question?id=5757597581836288
这个好像就是LC115。

我想了一下若限制subsequence在长string s的每个字母不能相邻的话那么DP在s[i-1] == t[j-1]的情况加上一个修改就可以了吧:
if (s[i-1] == t[j-1]) dp(i, j) = dp(i-2, j-1) + dp(i-1, j);
else dp(i, j) = dp(i-1, j);
  1. int numDistinct(string s, string t) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  2.         int ns = s.length(), nt = t.length();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  3.        if (nt == 0) return 1; else if (ns == 0) return 0;        
  4.         vector<int> prev1(nt+1),prev2[nt+1], cur(nt+1);
  5.         prev2[0] = prev1[0] = 1; if (s[0] == t[0]) prev1[1] = 1;        
  6.         for (int i = 2; i <= ns; ++i) {
  7.             cur[0] = 1;
  8.             for (int j = 1; j <= nt; ++j)
  9.             { if (s[i-1] == t[j-1]) cur[j] = prev2[j-1] + prev1[j]; else cur[j] = prev1[j]; }
  10.             for (int j = 0; j <= nt; ++j) { prev2[j] = prev1[j];  prev1[j] = cur[j]; }   
  11.         }. more info on 1point3acres.com
  12.         return cur[nt];
复制代码
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-12-1 04:30:15 | 显示全部楼层
zzgzzm 发表于 2016-11-25 09:34
我就找到:
https://www.careercup.com/question?id=5757597581836288
这个好像就是LC115。

这个赞。 我就没想出这么简单的改动来。。。
回复 支持 反对

使用道具 举报

cgxy1991 发表于 7 天前 | 显示全部楼层
hard题。。。楼主运气也是不好啊
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 18:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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