传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 4465|回复: 34
收起左侧

问一道Google面经

[复制链接] |试试Instant~ |关注本帖
neverlandly 发表于 2016-1-20 03:49:21 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Google - Other - 技术电面 |Otherfresh grad应届毕业生

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

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

x
求问一道在网上看到的Google家面经:.1point3acres缃

求string str1中含有string str2 order的 subsequence 的最小长度

举个例子: str1 = "acbacbc"   str2="abc", 那么最小subsequence长度应该是4, 对应的subsequence是“acbc”
. 1point3acres.com/bbs
只想到brute force,有没有其它好办法?

本帖被以下淘专辑推荐:

bobzhang2004 发表于 2016-3-9 12:54:57 | 显示全部楼层
muybienw 发表于 2016-1-20 07:11
上面帖子的代码格式有问题... 重新贴一下

用三个指针就行了,时间复杂度O(n^2),空间复杂度O(1)
  1. public class ShortestSequence {

  2. -google 1point3acres
  3.         public static void main(String[] args) {
  4.                 System.out.println(getShortestSequence("acbacbc", "abc"));
  5.         }
  6.         public static int getShortestSequence(String s1, String s2) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  7.                 if (s1.length() < s2.length()) {
  8.                         return Integer.MAX_VALUE;
  9.                 }
  10.                 int res = Integer.MAX_VALUE;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  11.                 for (int i = 0; i < s1.length(); i++) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  12.                         if (s1.charAt(i) == s2.charAt(0)) {
  13.                                 int j = i;
  14.                                 int k = 0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  15.                                 while (j < s1.length() && k < s2.length()) {
  16.                                         if (s1.charAt(j) == s2.charAt(k)) {
  17.                                                 j++;
  18.                                                 k++;
  19.                                         } else {
  20.                                                 j++;
  21.                                         }
  22.                                 }
  23.                                 if (k == s2.length()) {
  24.                                         res = Math.min(res, j - i);
  25.                                 }
  26.                         }
  27.                 }
  28.                
  29.                
  30.                 return res;
  31.         }. From 1point 3acres bbs
  32. }
复制代码
回复 支持 1 反对 0

使用道具 举报

smallpig1988 发表于 2016-1-20 06:06:16 | 显示全部楼层
类似于 LC 76. Minimum Window Substring。 但需要保持order。
回复 支持 反对

使用道具 举报

kidzlike 发表于 2016-1-20 06:11:09 | 显示全部楼层
我怎么觉得得用dp做?
回复 支持 反对

使用道具 举报

 楼主| neverlandly 发表于 2016-1-20 06:21:27 | 显示全部楼层
smallpig1988 发表于 2016-1-20 06:06
类似于 LC 76. Minimum Window Substring。 但需要保持order。

我也看了那道题,那道题要用array或者hashmap记录char出现次数,找到一个合适窗口后,尝试移动左边缘缩小窗口。这道题找到一个合适窗口倒不难,但是该怎么optimize窗口大小呢
回复 支持 反对

使用道具 举报

 楼主| neverlandly 发表于 2016-1-20 06:25:41 | 显示全部楼层
kidzlike 发表于 2016-1-20 06:11
我怎么觉得得用dp做?
. from: 1point3acres.com/bbs
能详细讲讲么,怎么用dp?
回复 支持 反对

使用道具 举报

muybienw 发表于 2016-1-20 07:09:39 | 显示全部楼层
用dp写了一下,欢迎讨论~
  1. <font size="1">    <span style="color: rgb(204, 120, 50);">public </span>String <span style="color: rgb(255, 198, 109);">findShortest</span>(String a<span style="color: rgb(204, 120, 50);">, </span>String b){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  2.         <span style="color: rgb(204, 120, 50);">if</span>(a==<span style="color: rgb(204, 120, 50);">null </span>|| b==<span style="color: rgb(204, 120, 50);">null </span>|| a.length()==<span style="color: rgb(104, 151, 187);">0 </span>|| b.length()==<span style="color: rgb(104, 151, 187);">0</span>) <span style="color: rgb(204, 120, 50);">throw new </span>IllegalArgumentException()<span style="color: rgb(204, 120, 50);">;
  3. </span><span style="color: rgb(204, 120, 50);">. visit 1point3acres.com for more.
  4. </span><span style="color: rgb(204, 120, 50);">        int </span>lena = a.length()<span style="color: rgb(204, 120, 50);">, </span>lenb = b.length()<span style="color: rgb(204, 120, 50);">;
  5. </span><span style="color: rgb(204, 120, 50);">        int</span>[][] dp = <span style="color: rgb(204, 120, 50);">new int</span>[lenb][lena]<span style="color: rgb(204, 120, 50);">;
  6. </span><span style="color: rgb(204, 120, 50);">
  7. </span><span style="color: rgb(204, 120, 50);">        for</span>(<span style="color: rgb(204, 120, 50);">int </span>i=<span style="color: rgb(104, 151, 187);">0</span><span style="color: rgb(204, 120, 50);">; </span>i<lenb<span style="color: rgb(204, 120, 50);">; </span>i++){
  8.             <span style="color: rgb(204, 120, 50);">char </span>bc = b.charAt(i)<span style="color: rgb(204, 120, 50);">; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  9. </span><span style="color: rgb(204, 120, 50);">            for</span>(<span style="color: rgb(204, 120, 50);">int </span>j=<span style="color: rgb(104, 151, 187);">0</span><span style="color: rgb(204, 120, 50);">; </span>j<lena<span style="color: rgb(204, 120, 50);">; </span>j++){
  10.                 <span style="color: rgb(204, 120, 50);">char </span>ac = a.charAt(j)<span style="color: rgb(204, 120, 50);">;
  11. </span><span style="color: rgb(204, 120, 50);">                </span>dp[i][j] = Integer.<span style="color: rgb(152, 118, 170); font-style: italic;">MAX_VALUE</span><span style="color: rgb(204, 120, 50);">;
  12. </span><span style="color: rgb(204, 120, 50);">
  13. </span><span style="color: rgb(204, 120, 50);">                if</span>(ac==bc){
  14.                     <span style="color: rgb(204, 120, 50);">if</span>(i==<span style="color: rgb(104, 151, 187);">0</span>) dp[i][j] = <span style="color: rgb(104, 151, 187);">1</span><span style="color: rgb(204, 120, 50);">;
  15. </span><span style="color: rgb(204, 120, 50);">                    else </span>{
  16.                         <span style="color: rgb(204, 120, 50);">for </span>(<span style="color: rgb(204, 120, 50);">int </span>t = <span style="color: rgb(104, 151, 187);">0</span><span style="color: rgb(204, 120, 50);">; </span>t < j<span style="color: rgb(204, 120, 50);">; </span>t++) {. From 1point 3acres bbs
  17.                             <span style="color: rgb(204, 120, 50);">if </span>(dp[i - <span style="color: rgb(104, 151, 187);">1</span>][t] == Integer.<span style="color: rgb(152, 118, 170); font-style: italic;">MAX_VALUE</span>) <span style="color: rgb(204, 120, 50);">continue;
  18. </span><span style="color: rgb(204, 120, 50);">                            else </span>dp[i][j] = Math.<span style="font-style: italic;">min</span>(dp[i][j]<span style="color: rgb(204, 120, 50);">, </span>dp[i - <span style="color: rgb(104, 151, 187);">1</span>][t] + j - t)<span style="color: rgb(204, 120, 50);">;
  19. </span><span style="color: rgb(204, 120, 50);">                        </span>}
  20.                     }
  21.                 }
  22.             }
  23.         }

  24.         <span style="color: rgb(204, 120, 50);">int </span>min = Integer.<span style="color: rgb(152, 118, 170); font-style: italic;">MAX_VALUE</span><span style="color: rgb(204, 120, 50);">;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  25. </span><span style="color: rgb(204, 120, 50);">        int </span>end = -<span style="color: rgb(104, 151, 187);">1</span><span style="color: rgb(204, 120, 50);">;
  26. </span><span style="color: rgb(204, 120, 50);">
  27. </span><span style="color: rgb(204, 120, 50);">        for</span>(<span style="color: rgb(204, 120, 50);">int </span>j=<span style="color: rgb(104, 151, 187);">0</span><span style="color: rgb(204, 120, 50);">; </span>j<lena<span style="color: rgb(204, 120, 50);">; </span>j++){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  28.             <span style="color: rgb(204, 120, 50);">if</span>(dp[lenb-<span style="color: rgb(104, 151, 187);">1</span>][j] < min) {
  29.                 min = dp[lenb-<span style="color: rgb(104, 151, 187);">1</span>][j]<span style="color: rgb(204, 120, 50);">;
  30. </span><span style="color: rgb(204, 120, 50);">                </span>end = j<span style="color: rgb(204, 120, 50);">;
  31. </span><span style="color: rgb(204, 120, 50);">            </span>}
  32.         }

  33. <span style="color: rgb(128, 128, 128);">//        System.out.println(end);
  34. </span><span style="color: rgb(128, 128, 128);">//        System.out.println(min);
  35. </span><span style="color: rgb(128, 128, 128);">
  36. </span><span style="color: rgb(128, 128, 128);">        </span><span style="color: rgb(204, 120, 50);">if</span>(end==-<span style="color: rgb(104, 151, 187);">1</span>) <span style="color: rgb(204, 120, 50);">return </span><span style="color: rgb(106, 135, 89);">"no match!"</span><span style="color: rgb(204, 120, 50);">;
  37. </span><span style="color: rgb(204, 120, 50);">        return </span>a.substring(end-min+<span style="color: rgb(104, 151, 187);">1</span><span style="color: rgb(204, 120, 50);">, </span>end+<span style="color: rgb(104, 151, 187);">1</span>)<span style="color: rgb(204, 120, 50);">;. visit 1point3acres.com for more.
  38. </span><span style="color: rgb(204, 120, 50);">    </span>}</font>
复制代码
回复 支持 反对

使用道具 举报

muybienw 发表于 2016-1-20 07:11:11 | 显示全部楼层
上面帖子的代码格式有问题... 重新贴一下

  1.     public String findShortest(String a, String b){
  2.         if(a==null || b==null || a.length()==0 || b.length()==0) throw new IllegalArgumentException();
  3. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  4.         int lena = a.length(), lenb = b.length();
  5.         int[][] dp = new int[lenb][lena];

  6.         for(int i=0; i<lenb; i++){.1point3acres缃
  7.             char bc = b.charAt(i);
  8.             for(int j=0; j<lena; j++){.1point3acres缃
  9.                 char ac = a.charAt(j);
  10.                 dp[i][j] = Integer.MAX_VALUE;

  11.                 if(ac==bc){
  12.                     if(i==0) dp[i][j] = 1;
  13.                     else {
  14.                         for (int t = 0; t < j; t++) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  15.                             if (dp[i - 1][t] == Integer.MAX_VALUE) continue;
  16.                             else dp[i][j] = Math.min(dp[i][j], dp[i - 1][t] + j - t);
  17.                         }
  18.                     }
  19.                 }
  20.             }
  21.         }. 1point3acres.com/bbs

  22.         int min = Integer.MAX_VALUE;
  23.         int end = -1;
  24. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  25.         for(int j=0; j<lena; j++){
  26.             if(dp[lenb-1][j] < min) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  27.                 min = dp[lenb-1][j];
  28.                 end = j;
  29.             }
  30.         }

  31. //        System.out.println(end);
  32. //        System.out.println(min);

  33.         if(end==-1) return "no match!";
  34.         return a.substring(end-min+1, end+1);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  35.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| neverlandly 发表于 2016-1-20 07:40:30 | 显示全部楼层
muybienw 发表于 2016-1-20 07:11
上面帖子的代码格式有问题... 重新贴一下

你的dp[j]的定义是什么呀?
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2016-1-20 07:41):
说错了,dp[j]的定义是什么呀

补充内容 (2016-1-20 07:42):. From 1point 3acres bbs
额。。。打不出来,是dp[ i, j ]
回复 支持 反对

使用道具 举报

muybienw 发表于 2016-1-20 11:04:11 | 显示全部楼层
pattern对应到i位置,string对应到j位置时,shortest substring的长度,Int_Max表示不存在
回复 支持 反对

使用道具 举报

atwoodwang0918 发表于 2016-1-20 11:10:22 | 显示全部楼层
muybienw 发表于 2016-1-20 07:11
上面帖子的代码格式有问题... 重新贴一下

问一下 code怎么贴才会不出现乱码啊 我之前贴code都跟你上面的code一样 显示的格式不对
回复 支持 反对

使用道具 举报

muybienw 发表于 2016-1-20 11:35:26 | 显示全部楼层
atwoodwang0918 发表于 2016-1-20 11:10
问一下 code怎么贴才会不出现乱码啊 我之前贴code都跟你上面的code一样 显示的格式不对
. Waral 鍗氬鏈夋洿澶氭枃绔,
应该是先把贴过来的代码去格式化,变成普通文本,再勾选成代码吧
回复 支持 反对

使用道具 举报

Hotzenplotz 发表于 2016-1-20 13:37:04 | 显示全部楼层
muybienw 发表于 2016-1-20 07:11
上面帖子的代码格式有问题... 重新贴一下

请问你这个dp方法复杂度是多少,你两层循环里面还有一个循环,似乎跟暴力解的复杂度是一样的?
回复 支持 反对

使用道具 举报

mingycool 发表于 2016-1-20 14:17:09 | 显示全部楼层
muybienw 发表于 2016-1-20 07:11. 1point 3acres 璁哄潧
上面帖子的代码格式有问题... 重新贴一下

恕我才疏,我怎么感觉暴力解法貌似也就n*n复杂度,n是str1的长度,你这dp感觉意义不大啊。。
回复 支持 反对

使用道具 举报

snowwolf 发表于 2016-1-20 16:15:40 | 显示全部楼层
你确定是subsequence不是substring?看你的描述是要找substring吧?概念还是要搞清楚的呀
回复 支持 反对

使用道具 举报

muybienw 发表于 2016-1-21 06:32:07 | 显示全部楼层
Hotzenplotz 发表于 2016-1-20 13:37
请问你这个dp方法复杂度是多少,你两层循环里面还有一个循环,似乎跟暴力解的复杂度是一样的?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
对,我写的比较naive的dp,时间复杂度应该可以优化到O(n^2),去掉第三个循环,可以在第二个循环遍历的时候同时记录见到上一次字符最小长度。类似buy and sell stock IV的优化方法。
回复 支持 反对

使用道具 举报

muybienw 发表于 2016-1-21 06:33:26 | 显示全部楼层
Hotzenplotz 发表于 2016-1-20 13:37
请问你这个dp方法复杂度是多少,你两层循环里面还有一个循环,似乎跟暴力解的复杂度是一样的?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
你的暴力解法是怎么做?如果拆下来n^2个substring的话,和另外一个string的比较还需要O(n)的时间。我这个dp是最简单的版本,应该可以优化到O(m*n)
回复 支持 反对

使用道具 举报

Hotzenplotz 发表于 2016-1-21 07:36:30 | 显示全部楼层
muybienw 发表于 2016-1-21 06:33
你的暴力解法是怎么做?如果拆下来n^2个substring的话,和另外一个string的比较还需要O(n)的时间。我这个 ...
. visit 1point3acres.com for more.
暴力就是O(n^2):
遍历str1,如果某个char i和str2的第一个char相同,就从i开始往后遍历所有字符,直到找到str2对应的sequence,或者走完str1,由于这里是同时递增遍历str1,str2,所以时间复杂度是O(n); 然后接着从i + 1开始遍历str1.总的复杂度是O(n^2). 实际跟strStr类似,那个的复杂度是O(mn),现在条件更复杂,谨慎怀疑一般的做法是否能到O(mn)。
回复 支持 反对

使用道具 举报

muybienw 发表于 2016-1-21 08:59:44 | 显示全部楼层
Hotzenplotz 发表于 2016-1-21 07:36
暴力就是O(n^2):
遍历str1,如果某个char i和str2的第一个char相同,就从i开始往后遍历所有字符,直到找 ...

嗯,这样看来没必要dp做。
回复 支持 反对

使用道具 举报

likenisha 发表于 2016-1-22 22:59:52 | 显示全部楼层
two pointers,这个是原题咯
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-26 02:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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