📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 31
跳转到指定楼层
上一主题 下一主题
收起左侧

GOOGLE ONSITE9/29

全局:

2015(10-12月) 码农类General 硕士 全职@google - 网上海投 - Onsite  | | Other | 应届毕业生

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
没有电面直接ONSITE。

1. 忘了

2.给一个STR,删除最少的任何char,使它变成palindrome.听说是经典的DP,反正我
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
一个没遇到。第二轮遇到那个毛子真是日了狗了。一个月后要我参加residency program,没理。

评分

参与人数 2大米 +13 收起 理由
djjkobe + 3 感谢分享!
love1point + 10

查看全部评分


上一篇:Bloomreach面经
下一篇:Zenefits面经

本帖被以下淘专辑推荐:

推荐
maomaoxiong 2015-11-12 14:03:30 | 只看该作者
全局:
bill701 发表于 2015-11-12 12:48
第四题可不可以利用数学的思想呢?char的话就把他映射到1-256上。分别对两个str算出他们各自的乘积和相加的 ...

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

使用道具 举报

推荐
bill701 2015-11-12 12:48:47 | 只看该作者
全局:
第四题可不可以利用数学的思想呢?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.         public static int getLongestPalindromicSubsequence(String str) {
  13.                 if (str == null || str.length() == 0) {
  14.                         return 0;
  15.                 }
  16.                 int len = str.length();
  17.                 int[][] dp = new int[len][len];
  18.                 for (int i = 0; i < len; i++) {
  19.                         dp[i][i] = 1;
  20.                 }
  21.                 for (int cl = 2; cl <= len; cl++) {
  22.                         for (int i = 0; i < len - cl + 1; i++) {
  23.                                 int j = i + cl - 1;
  24.                                 if (str.charAt(i) == str.charAt(j) && cl == 2) {
  25.                                         dp[i][j] = 2;
  26.                                 } else if (str.charAt(i) == str.charAt(j)) {
  27.                                         dp[i][j] = dp[i + 1][j - 1] + 2;
  28.                                 } else {
  29.                                         dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
  30.                                 }
  31.                         }
  32.                 }
  33.                
  34.                 return dp[0][len - 1];
  35.         }
  36. }
复制代码
回复

使用道具 举报

🔗
sonicgu 2015-11-11 11:21:21 | 只看该作者
全局:
感谢lz分享,这个第四轮的follow up可不可以详细说下
回复

使用道具 举报

🔗
kidzlike 2015-11-11 11:32:04 | 只看该作者
全局:
sonicgu 发表于 2015-11-11 11:21
感谢lz分享,这个第四轮的follow up可不可以详细说下

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

使用道具 举报

🔗
kidzlike 2015-11-11 11:33:21 | 只看该作者
全局:
第三题取钱是基本dp 但是o1 space记路径怎么做? bit op?
回复

使用道具 举报

🔗
maomaoxiong 2015-11-11 11:34:30 | 只看该作者
全局:
第三题这么会是O(n)?

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

使用道具 举报

🔗
 楼主| kennynoodlehous 2015-11-11 11:37:05 | 只看该作者
全局:
kidzlike 发表于 2015-11-11 11:33
第三题取钱是基本dp 但是o1 space记路径怎么做? bit op?

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

使用道具 举报

🔗
maomaoxiong 2015-11-11 11:37:51 | 只看该作者
全局:
maomaoxiong 发表于 2015-11-11 11:34
第三题这么会是O(n)?

敲错了。这个空间复杂度应该是O(n)
回复

使用道具 举报

🔗
fatalme 2015-11-11 13:39:45 | 只看该作者
全局:
第二题,返回最长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];
回复

使用道具 举报

🔗
yx1232287 2015-11-12 03:19:30 | 只看该作者
全局:
第四题char不同可以异或,相同char怎么找?
回复

使用道具 举报

🔗
 楼主| kennynoodlehous 2015-11-12 03:26:37 | 只看该作者
全局:
yx1232287 发表于 2015-11-12 03:19
第四题char不同可以异或,相同char怎么找?

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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