9月2日Google电面

上周五电面的，今天下午刚刚接到电话说可以约onsite了，之前面完还觉得药丸的没想到过了哈哈= =
一共两道题，都很简单，感觉电面可能主要还是看解题的速度和细节？
1.限定1~99的自然数，给出一列数，比如[2,3,5,6,7,14]，输出一个字符串概括剩下的所有数，例如之前的例子就输出“1,4,8-13,15-99”。也就是说用"x-y"概括连续两

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

了一下改对了。

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

第二题 ...我想不出来＝ ＝请问楼主怎么做的？

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.     }  
    
14.   }
    
15.   return dp[ns][nt];
    
16. }

复制代码

zzgzzm 发表于 2016-10-27 13:22
第二题：用对于s和s'的prefix substring做DP就可以了：定义dp(i, j)为s.substr(0, i)和s'.substr(0, j)的 ...

明白了，感谢！🙏