GOOGLE ONSITE9/29

没有电面直接ONSITE。

1. 忘了

2.给一个STR，删除最少的任何char,使它变成palindrome.听说是经典的DP，反正我不会，毛子也不给提示，埋头忙自己的。

3.

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

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

一个没遇到。第二轮遇到那个毛子真是日了狗了。一个月后要我参加residency program，没理。

bill701 发表于 2015-11-12 12:48
第四题可不可以利用数学的思想呢？char的话就把他映射到1-256上。分别对两个str算出他们各自的乘积和相加的 ...

这个方法可行。不用乘。直接XOR。如果为0，a = b = (sumb-sumA)/2.

第四题可不可以利用数学的思想呢？char的话就把他映射到1-256上。分别对两个str算出他们各自的乘积和相加的和： sum_a,sum_b,multiply_a,multiply_b。假设多出的两个char 分别是 a和b。 那么 a+b＝sumb-suma, a*b=multyplyb/multiplya; 然后计算应该就可以了，虽然我觉得如果str过长会有溢出。。。

nothingtrouble 发表于 2015-11-13 23:21
第二题确实是面筋题，如果理解没错的话，第二题应该是求longest palindrome subsequence的变形。如果求出su ...

应该是这样的，写了下代码。

1. public class LongestPalindromicSubsequenceByDeleting {
   
2.        
   
3.         public static void main(String[] args) {
   
4.                 String s = "abcdesc";
   
5.                 System.out.println(leastCharacterDeleted(s));
   
6.         }
   
7.        
   
8.         public static int leastCharacterDeleted(String str) {
   
9.                 int len = getLongestPalindromicSubsequence(str);
   
10.                 return str.length() - len;
    
11.         }
    
12. 
    
13.         public static int getLongestPalindromicSubsequence(String str) {
    
14.                 if (str == null || str.length() == 0) {
    
15.                         return 0;
    
16.                 }
    
17.                 int len = str.length();
    
18.                 int[][] dp = new int[len][len];
    
19.                 for (int i = 0; i < len; i++) {
    
20.                         dp[i][i] = 1;
    
21.                 }
    
22.                 for (int cl = 2; cl <= len; cl++) {
    
23.                         for (int i = 0; i < len - cl + 1; i++) {
    
24.                                 int j = i + cl - 1;
    
25.                                 if (str.charAt(i) == str.charAt(j) && cl == 2) {
    
26.                                         dp[i][j] = 2;
    
27.                                 } else if (str.charAt(i) == str.charAt(j)) {
    
28.                                         dp[i][j] = dp[i + 1][j - 1] + 2;
    
29.                                 } else {
    
30.                                         dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
    
31.                                 }
    
32.                         }
    
33.                 }
    
34.                
    
35.                 return dp[0][len - 1];
    
36.         }
    
37. }
    

复制代码

感谢lz分享，这个第四轮的follow up可不可以详细说下

sonicgu 发表于 2015-11-11 11:21
感谢lz分享，这个第四轮的follow up可不可以详细说下

我觉得就是贪心暴力撸吧 遇到不同的就记下来？

第三题取钱是基本dp 但是o1 space记路径怎么做？ bit op?

第三题这么会是O(n)?

补充内容 (2015-11-11 11:40):
敲错了。这个空间复杂度应该是O（n）

kidzlike 发表于 2015-11-11 11:33
第三题取钱是基本dp 但是o1 space记路径怎么做？ bit op?

往左边来的记负数
往右边来的记正数 2B吧

maomaoxiong 发表于 2015-11-11 11:34
第三题这么会是O(n)?

敲错了。这个空间复杂度应该是O（n）

第二题，返回最长plalindrome的长度。

1. public class GetPalindromByRemoval {
   
2.   public static void main(String[] args) {
   
3.     String s = "slk23kllsldf";
   
4.     int[] pre = new int[s.length()];
   
5.     int[] cur = new int[s.length()];
   
6.     for(int w = 0; w < s.length(); ++w){
   
7.       for(int j = w; j >= 0; --j){
   
8.         if(s.charAt(j) == s.charAt(w)){
   
9.           cur[j] = (w - j > 1) ? (2 + pre[j + 1]): (1 + w - j);
   
10.         }else{
    
11.           cur[j] = Math.max(cur[j + 1], pre[j]);
    
12.         }
    
13.       }
    
14.       int[] temp = pre;
    
15.       pre = cur;
    
16.       cur = temp;
    
17.     }
    
18.   }
    
19. }

复制代码

补充内容 (2015-11-11 13:43):
return pre[0];

第四题char不同可以异或，相同char怎么找？

yx1232287 发表于 2015-11-12 03:19
第四题char不同可以异或，相同char怎么找？

我也不知道。。。。。我知道了应该就不会被发配去residency program了