一亩三分地论坛

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

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

GOOGLE ONSITE9/29

[复制链接] |试试Instant~ |关注本帖
majiamajia 发表于 2015-11-11 10:51:46 | 显示全部楼层 |阅读模式

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

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

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

x
没有电面直接ONSITE。. 1point3acres.com/bbs

1. 忘了

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

3.SYstem DESIGN, BLOOMFILTER; 2-D ARRAY, 上面放了不同的钱,找条路(0,0)走到(M, N)钱最多。O(1)SPACE记录路径如何做

4.WARM UP题目忘了。FOLLOWUP: 给2个STR A, B。 B比A多2个CHAR,可能是相同的CHAR, 如何找出?O(1) SPACE, <= O(N) TIME。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

感受:
面之前准备了60多个常见面经题,一个没遇到。第二轮遇到那个毛子真是日了狗了。一个月后要我参加residency program,没理。

评分

2

查看全部评分

本帖被以下淘专辑推荐:

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

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

使用道具 举报

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过长会有溢出。。。
回复 支持 1 反对 0

使用道具 举报

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)
回复 支持 反对

使用道具 举报

 楼主| majiamajia 发表于 2015-11-11 11:37:05 | 显示全部楼层
kidzlike 发表于 2015-11-11 11:33
第三题取钱是基本dp 但是o1 space记路径怎么做? bit op?
. Waral 鍗氬鏈夋洿澶氭枃绔,
往左边来的记负数. From 1point 3acres bbs
往右边来的记正数 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的长度。. from: 1point3acres.com/bbs
  1. public class GetPalindromByRemoval {. more info on 1point3acres.com
  2.   public static void main(String[] args) {
  3.     String s = "slk23kllsldf";. 1point3acres.com/bbs
  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):. from: 1point3acres.com/bbs
return pre[0];
回复 支持 反对

使用道具 举报

yx1232287 发表于 2015-11-12 03:19:30 | 显示全部楼层
第四题char不同可以异或,相同char怎么找?
回复 支持 反对

使用道具 举报

 楼主| majiamajia 发表于 2015-11-12 03:26:37 | 显示全部楼层
yx1232287 发表于 2015-11-12 03:19
第四题char不同可以异或,相同char怎么找?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我也不知道。。。。。我知道了应该就不会被发配去residency program了
回复 支持 反对

使用道具 举报

sxh53 发表于 2015-11-12 06:15:50 | 显示全部楼层
第四题难道不是分别读到两个256长度的int array里, 然后顺序比较这俩256的int array? O(1) space 因为256是常数
回复 支持 反对

使用道具 举报

yx1232287 发表于 2015-11-12 06:18:47 | 显示全部楼层
sxh53 发表于 2015-11-12 06:15
第四题难道不是分别读到两个256长度的int array里, 然后顺序比较这俩256的int array? O(1) space 因为256 ...

正解,这个是char....
回复 支持 反对

使用道具 举报

 楼主| majiamajia 发表于 2015-11-12 06:55:08 来自手机 | 显示全部楼层
sxh53 发表于 2015-11-12 06:15
第四题难道不是分别读到两个256长度的int array里, 然后顺序比较这俩256的int array? O(1) space 因为256 ...
. From 1point 3acres bbs
他说这个方法不是他要的亲
回复 支持 反对

使用道具 举报

maomaoxiong 发表于 2015-11-12 07:02:59 | 显示全部楼层
majiamajia 发表于 2015-11-12 06:55
他说这个方法不是他要的亲

那就只有二分或brute force从头比较。
回复 支持 反对

使用道具 举报

 楼主| majiamajia 发表于 2015-11-12 07:05:00 来自手机 | 显示全部楼层
maomaoxiong 发表于 2015-11-12 07:02
那就只有二分或brute force从头比较。

二分…?没有顺序的. from: 1point3acres.com/bbs

brute force不符合复杂度
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-11-12 13:42:35 | 显示全部楼层
majiamajia 发表于 2015-11-12 03:26. Waral 鍗氬鏈夋洿澶氭枃绔,
我也不知道。。。。。我知道了应该就不会被发配去residency program了
. 1point 3acres 璁哄潧
请问什么是residency program
回复 支持 反对

使用道具 举报

 楼主| majiamajia 发表于 2015-11-12 13:43:48 | 显示全部楼层
aiweiwei 发表于 2015-11-12 13:42
请问什么是residency program

上班几个月然后转正。。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-12 15:16:35 | 显示全部楼层
请问lz第三轮第二题是网左边走要减去当前格子的钱数,往右边走是加上钱数吗?那上下怎么看?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 02:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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