May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1341|回复: 3
收起左侧

9月2日Google电面

[复制链接] |试试Instant~ |关注本帖
UpDownDOTA 发表于 2016-9-8 12:17:37 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Passfresh grad应届毕业生

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

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

x
上周五电面的,今天下午刚刚接到电话说可以约onsite了,之前面完还觉得药丸的没想到过了哈哈= =
一共两道题,都很简单,感觉电面可能主要还是看解题的速度和细节?
1.限定1~99的自然数,给出一列数,比如[2,3,5,6,7,14],输出一个字符串概括剩下的所有数,例如之前的例子就输出“1,4,8-13,15-99”。也就是说用"x-y"概括连续两个或多个数,单独列出单个数,然后用逗号连起来。.鐣欏璁哄潧-涓浜-涓夊垎鍦
非常简单的模拟题,但是有一些特殊情况比如空列表,所有数之类的需要特别注意。我当时就漏掉了一些特殊情况,被提醒了之后才加上的。
2.Substring Matching就是给两个字符串s和s',求有多少种方法将s'作为s的子串。例如"catastca", "cat",有三种将"cat"作为"catastca"子串的方法:"catastca", "catastca", "catastca"。
非常简单的DP,写递推式的时候还犯了蠢>_<还好面试官提醒了一下改对了。

最后再吐槽一句,面试官迟到了5分钟,然后把题目copy过来还非常的慢,而且不知道为什么电话全程带超级大的噪音,非常影响交流,不过还好结果不错(说不定是考虑到了噪音的影响所以抬了我一手?^_^). 1point3acres.com/bbs

本帖被以下淘专辑推荐:

  • · google|主题: 68, 订阅: 16
cgq77 发表于 2016-10-27 11:32:41 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第二题 ...我想不出来= =请问楼主怎么做的?
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-27 13:22:48 | 显示全部楼层
关注一亩三分地微博:
Warald
cgq77 发表于 2016-10-27 11:32
第二题 ...我想不出来= =请问楼主怎么做的?

第二题:用对于s和s'的prefix substring做DP就可以了:定义dp(i, j)为s.substr(0, i)和s'.substr(0, j)的match count, 那么就很容易写出转移方程了。
  1. int SubstringMatching(string& s, string& t) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  2.   int ns = s.length(), nt = t.length();
  3.   if (nt > ns || nt == 0) return 0;
  4.   
  5.   // dp[i][j]: matching count for s.subtr(0,i) and t.substr(0,j)
  6.   vector<vector<int>> dp(ns+1, vector<int>(nt+1, 0));
  7.   dp[0][0] = 1;
  8.   for (int i = 1; i <= ns; i++) {
  9.     dp[i][0] = 1;  
  10.     for (int j = 1; j <= nt; j++) {
  11.       dp[i][j] = dp[i-1][j];
  12.       if (s[i-1] == t[j-1]) dp[i][j] += dp[i-1][j-1];
  13.     }  . 1point 3acres 璁哄潧
  14.   }
  15.   return dp[ns][nt];
  16. }
复制代码
回复 支持 反对

使用道具 举报

cgq77 发表于 2016-10-27 21:59:10 | 显示全部楼层
zzgzzm 发表于 2016-10-27 13:22. 鍥磋鎴戜滑@1point 3 acres
第二题:用对于s和s'的prefix substring做DP就可以了:定义dp(i, j)为s.substr(0, i)和s'.substr(0, j)的 ...

明白了,感谢!&#128591;
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-25 12:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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