一亩三分地论坛

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

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

问一道Google面经

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

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

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

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

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

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

举个例子: str1 = "acbacbc"   str2="abc", 那么最小subsequence长度应该是4, 对应的subsequence是“acbc”
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
只想到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.         public static void main(String[] args) {
  3.                 System.out.println(getShortestSequence("acbacbc", "abc"));
  4.         }
  5.         public static int getShortestSequence(String s1, String s2) {
  6.                 if (s1.length() < s2.length()) {
  7.                         return Integer.MAX_VALUE;
  8.                 }
  9.                 int res = Integer.MAX_VALUE;
  10.                 for (int i = 0; i < s1.length(); i++) {
  11.                         if (s1.charAt(i) == s2.charAt(0)) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  12.                                 int j = i;
  13.                                 int k = 0;.1point3acres缃
  14.                                 while (j < s1.length() && k < s2.length()) {
  15.                                         if (s1.charAt(j) == s2.charAt(k)) {
  16.                                                 j++;
  17.                                                 k++;
  18.                                         } else {
  19.                                                 j++;. From 1point 3acres bbs
  20.                                         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  21.                                 }
  22.                                 if (k == s2.length()) {
  23.                                         res = Math.min(res, j - i);
  24.                                 }. more info on 1point3acres.com
  25.                         }
  26.                 }
  27.                
  28.                
  29.                 return res;
  30.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  31. }
复制代码
回复 支持 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做?

能详细讲讲么,怎么用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);">. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  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);">;. from: 1point3acres.com/bbs
  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++) {
  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>}. 鍥磋鎴戜滑@1point 3 acres
  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);">;
    . 1point3acres.com/bbs
  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);">;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  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++){. 1point 3acres 璁哄潧
  7.             char bc = b.charAt(i);
  8.             for(int j=0; j<lena; j++){
  9.                 char ac = a.charAt(j);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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.         }

  22.         int min = Integer.MAX_VALUE;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  23.         int end = -1;
  24. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  25.         for(int j=0; j<lena; j++){
  26.             if(dp[lenb-1][j] < min) {
  27.                 min = dp[lenb-1][j];
  28.                 end = j;. 鍥磋鎴戜滑@1point 3 acres
  29.             }
  30.         }

  31. //        System.out.println(end); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  32. //        System.out.println(min);-google 1point3acres

  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]的定义是什么呀?

补充内容 (2016-1-20 07:41):
说错了,dp[j]的定义是什么呀

补充内容 (2016-1-20 07:42):
额。。。打不出来,是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一样 显示的格式不对

应该是先把贴过来的代码去格式化,变成普通文本,再勾选成代码吧
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

头像被屏蔽
mingycool 发表于 2016-1-20 14:17:09 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

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

使用道具 举报

muybienw 发表于 2016-1-21 06:32:07 | 显示全部楼层
Hotzenplotz 发表于 2016-1-20 13:37. Waral 鍗氬鏈夋洿澶氭枃绔,
请问你这个dp方法复杂度是多少,你两层循环里面还有一个循环,似乎跟暴力解的复杂度是一样的?

对,我写的比较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)的时间。我这个 ...

暴力就是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,这个是原题咯
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 07:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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