10钟前google电面

刚刚面完，目测已跪，发面经攒人品。
string题，第一问和leetcode上的shortest palindrome 基本一样，换成了插在结尾，问题不大，讨论了

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

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

帮助很大，以后有面经会继续回馈地里。
祝各位找工作顺利~走过路过打赏点米啊！

尝试了一下dp解法：dp[i][j]存从s[i]到s[j]的substring能够组成的最短palindrome

1. public static String shortestPalindrome2(String s) {
   
2.         if (s == null || s.length() <= 1) {
   
3.             return s;
   
4.         }
   
5.         String[][] dp = new String[s.length()][s.length()];
   
6.         for (int i = 0; i < s.length(); i++) {
   
7.             dp[i][i] = String.valueOf(s.charAt(i));
   
8.         }
   
9.         for (int len = 2; len <= s.length(); len++) {
   
10.             for (int i = 0; i <= s.length() - len; i++) {
    
11.                 if (s.charAt(i) == s.charAt(i + len - 1)) {
    
12.                     if (len == 2) {
    
13.                         dp[i][i + 1] = s.substring(i, i + 2);
    
14.                     } else {
    
15.                         dp[i][i + len - 1] = s.charAt(i) + dp[i + 1][i + len - 2] + s.charAt(i + len - 1);
    
16.                     }
    
17.                 } else {
    
18.                     if (len == 2) {
    
19.                         dp[i][i + 1] = s.substring(i, i + 2) + s.charAt(i);
    
20.                     } else {
    
21.                         dp[i][i + len - 1] = dp[i + 1][i + len - 1].length() < dp[i][i + len - 2].length() ?
    
22.                                 s.charAt(i) + dp[i + 1][i + len - 1] + s.charAt(i) : s.charAt(i + len - 1) + dp[i][i + len - 2] + s.charAt(i + len - 1);
    
23.                     }
    
24.                 }
    
25.             }
    
26.         }
    
27.         return dp[0][s.length() - 1];
    
28.     }

复制代码

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

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

请问lz是用KMP算法么？感觉店面就考KMP算法好难。。。。

宝贝忆彼岸 发表于 2015-8-29 03:05
请问lz是用KMP算法么？感觉店面就考KMP算法好难。。。。

一开始写了暴力，问优化的时候写了KMP，因为刷过才记得，所以当时还觉得很走运。。。

laurie洁 发表于 2015-8-29 03:28
尝试了一下dp解法：dp[j]存从s到s[j]的substring能够组成的最短palindrome

谢谢！学习了！

这还不是叼难。 这难的题。 楼主是面哪个office?

zchang3 发表于 2015-8-29 03:46
一开始写了暴力，问优化的时候写了KMP，因为刷过才记得，所以当时还觉得很走运。。。

可以问问KMP怎么写吗？想学习一下~~

第二个题目 任何 位置应该可以dp接， geeksforgeeks有原题

laurie洁 发表于 2015-8-29 04:02
可以问问KMP怎么写吗？想学习一下~~

1. 
   
2. string solver(string a){
   
3.     string re=a;
   
4.     reverse(re.begin(),re.end());
   
5.     string t=re+"#"+a;
   
6.     vector<int> p(t.size(),0);
   
7.     for (int i = 1; i < t.size(); ++i) {
   
8.         int j = p[i - 1];
   
9.         while (j > 0 && t[i] != t[j])
   
10.             j = p[j - 1];
    
11.         j+=(t[i]==t[j]);
    
12.         p[i] = j;
    
13.     }
    
14.     for(int i=0;i<p.size();i++)
    
15.         cout<<p[i]<<' ';
    
16.     cout<<endl;
    
17.     return a.substr(0,a.size()-p[t.size() - 1]) + re;
    
18. }

复制代码

补充内容 (2015-8-29 05:17):
中间的cout忘删了...原题是在 https://leetcode.com/problems/shortest-palindrome/

hulahu 发表于 2015-8-29 03:55
这还不是叼难。 这难的题。 楼主是面哪个office?

小哥说google now，前几天看新闻说已经全体离职了？记不清了一开始挺紧张，杂音也大听不很清