一亩三分地论坛

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

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

10钟前google电面

[复制链接] |试试Instant~ |关注本帖
zchang3 发表于 2015-8-29 02:16:45 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 网上海投 - HR筛选 |Otherfresh grad应届毕业生

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

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

x
刚刚面完,目测已跪,发面经攒人品。
string题,第一问和leetcode上的shortest palindrome 基本一样,换成了插在结尾,问题不大,讨论了下时间复杂度。
follow up问如果插字符在任何地方,看到过dp解法,但是想不起来也没推出来。搜了一下,类似 pku1159, 大家可以参考下。. from: 1point3acres.com/bbs
面试官印度小哥,人不错,给的建议都很中肯,没觉得有刁难~(平常心平常心)。

毕业季刚刚开始找工作,水平和准备都不足,地里的各种经验和内推帮助很大,以后有面经会继续回馈地里。
祝各位找工作顺利~走过路过打赏点米啊!

评分

5

查看全部评分

本帖被以下淘专辑推荐:

laurie洁 发表于 2015-8-29 03:28:41 | 显示全部楼层
尝试了一下dp解法:dp[j]存从s到s[j]的substring能够组成的最短palindrome
  1. public static String shortestPalindrome2(String s) {-google 1point3acres
  2.         if (s == null || s.length() <= 1) {. 鍥磋鎴戜滑@1point 3 acres
  3.             return s;
  4.         }. 鍥磋鎴戜滑@1point 3 acres
  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.     }
复制代码
回复 支持 1 反对 0

使用道具 举报

宝贝忆彼岸 发表于 2015-8-29 03:05:14 | 显示全部楼层
请问lz是用KMP算法么?感觉店面就考KMP算法好难。。。。
回复 支持 反对

使用道具 举报

 楼主| zchang3 发表于 2015-8-29 03:46:18 | 显示全部楼层
宝贝忆彼岸 发表于 2015-8-29 03:05
请问lz是用KMP算法么?感觉店面就考KMP算法好难。。。。
. From 1point 3acres bbs
一开始写了暴力,问优化的时候写了KMP,因为刷过才记得,所以当时还觉得很走运。。。
回复 支持 反对

使用道具 举报

 楼主| zchang3 发表于 2015-8-29 03:47:35 | 显示全部楼层
laurie洁 发表于 2015-8-29 03:28
尝试了一下dp解法:dp[j]存从s到s[j]的substring能够组成的最短palindrome

谢谢!学习了!
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-8-29 03:55:17 | 显示全部楼层
这还不是叼难。 这难的题。 楼主是面哪个office?
回复 支持 反对

使用道具 举报

laurie洁 发表于 2015-8-29 04:02:01 | 显示全部楼层
zchang3 发表于 2015-8-29 03:46
一开始写了暴力,问优化的时候写了KMP,因为刷过才记得,所以当时还觉得很走运。。。
. 1point 3acres 璁哄潧
可以问问KMP怎么写吗?想学习一下~~
回复 支持 反对

使用道具 举报

donghao 发表于 2015-8-29 04:26:38 | 显示全部楼层
第二个题目 任何 位置应该可以dp接, geeksforgeeks有原题
回复 支持 反对

使用道具 举报

 楼主| zchang3 发表于 2015-8-29 05:15:26 | 显示全部楼层
laurie洁 发表于 2015-8-29 04:02. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
可以问问KMP怎么写吗?想学习一下~~

  1. string solver(string a){
  2.     string re=a;
  3.     reverse(re.begin(),re.end());
  4.     string t=re+"#"+a;
  5.     vector<int> p(t.size(),0);
  6.     for (int i = 1; i < t.size(); ++i) {
  7.         int j = p[i - 1];
  8.         while (j > 0 && t[i] != t[j]). 鍥磋鎴戜滑@1point 3 acres
  9.             j = p[j - 1];
  10.         j+=(t[i]==t[j]);
  11.         p[i] = j;. 1point 3acres 璁哄潧
  12.     }
  13.     for(int i=0;i<p.size();i++). more info on 1point3acres.com
  14.         cout<<p[i]<<' ';
  15.     cout<<endl;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  16.     return a.substr(0,a.size()-p[t.size() - 1]) + re;
  17. }
复制代码

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

使用道具 举报

 楼主| zchang3 发表于 2015-8-29 05:19:55 | 显示全部楼层
hulahu 发表于 2015-8-29 03:55
这还不是叼难。 这难的题。 楼主是面哪个office?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
小哥说google now,前几天看新闻说已经全体离职了?记不清了一开始挺紧张,杂音也大听不很清
回复 支持 反对

使用道具 举报

 楼主| zchang3 发表于 2015-8-29 07:33:38 | 显示全部楼层
donghao 发表于 2015-8-29 04:26
第二个题目 任何 位置应该可以dp接, geeksforgeeks有原题

dp可以,以前学习过但面试时候没有解出来...
回复 支持 反对

使用道具 举报

blactangeri 发表于 2015-8-29 07:36:07 | 显示全部楼层
请问只有一道题吗
回复 支持 反对

使用道具 举报

sevenwonder 发表于 2015-8-29 11:26:43 | 显示全部楼层
laurie洁 发表于 2015-8-29 03:28. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
尝试了一下dp解法:dp[j]存从s到s[j]的substring能够组成的最短palindrome
. more info on 1point3acres.com
dp[i + len - 1] = dp[i + 1][i + len - 1].length() < dp[i + len - 2].length() ?
                                s.charAt(i) + dp[i + 1][i + len - 1] + s.charAt(i) : s.charAt(i + len - 1) + dp[i + len - 2] + s.charAt(i + len - 1);

这块是不是在字符串前面也插了啊,不是只能在后面插么?
回复 支持 反对

使用道具 举报

laurie洁 发表于 2015-8-29 12:58:42 | 显示全部楼层
sevenwonder 发表于 2015-8-29 11:26
dp = dp.length() < dp.length() ?-google 1point3acres
                                s.charAt(i) + dp + s.charAt(i) : ...

这是follow-up的解答
回复 支持 反对

使用道具 举报

冬季恋歌 发表于 2015-8-29 14:13:58 | 显示全部楼层
follow up有点难啊
回复 支持 反对

使用道具 举报

sevenwonder 发表于 2015-8-29 22:40:00 | 显示全部楼层
laurie洁 发表于 2015-8-29 12:58
这是follow-up的解答

哦。大牛dp用的很熟练啊,看你很多题dp很快就解出来了膜拜啊!
回复 支持 反对

使用道具 举报

laurie洁 发表于 2015-8-30 01:02:37 | 显示全部楼层
sevenwonder 发表于 2015-8-29 22:40
哦。大牛dp用的很熟练啊,看你很多题dp很快就解出来了膜拜啊!

绝对不是大牛,小牛都不是~哈哈
参考了网上的解法啦~
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-30 05:52:43 | 显示全部楼层
follow up怎么这么难。。。。。
回复 支持 反对

使用道具 举报

hzshuai 发表于 2015-8-30 21:24:32 | 显示全部楼层
laurie洁 发表于 2015-8-29 03:28. 1point3acres.com/bbs
尝试了一下dp解法:dp[j]存从s到s[j]的substring能够组成的最短palindrome

代码不错,还可以考虑follow up进行空间压缩(滚动数组)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 20:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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