一亩三分地论坛

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

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

Google Intern 面经 20150112

[复制链接] |试试Instant~ |关注本帖
eval 发表于 2015-2-19 14:14:56 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Other

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

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

x
. more info on 1point3acres.com

本想有了match再发个总结帖,现在感觉怕是淹没在pool里了。

先分享一下时间点,2014.12.01 内推,很快有recuiter联系,但当时available的时间窗只有一月的了,于是选了三个一月的日期,recuiter挑了个最晚的,于是就到一月12号了。通知进入host match是在9天之后。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
---
第一轮,

国人大哥,很nice,就上了merge sorted list和另一个也超简单的二叉树的题。

第二轮,

白人,听语气感觉上年纪了。整个过程对方爱答不理,也就做了一个题。问题是想要shuffle一个string,使得最终没有相同的character相邻。
. From 1point 3acres bbs
第三轮,
.鏈枃鍘熷垱鑷1point3acres璁哄潧
听不出那里口音,最可能是印度小哥。也只问了一个问题。就是求子矩阵的sum,其中子矩阵左上角一定是从(0, 0)开始。问题很弱,就是最简单的DP吧。

---

总体来讲题很简单,运气不错,换了难题还真未必能进host match。。

Hope for the best.

评分

1

查看全部评分

houqingniao 发表于 2015-2-19 14:57:54 | 显示全部楼层
子矩阵是啥问题?咋dp?
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-2-19 15:16:53 | 显示全部楼层
houqingniao 发表于 2015-2-19 14:57. 1point3acres.com/bbs
子矩阵是啥问题?咋dp?

其实就是部分和。容斥原理啥的。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

will_ym 发表于 2015-2-20 04:29:54 | 显示全部楼层
请教一下第二题怎么解的?
回复 支持 反对

使用道具 举报

 楼主| eval 发表于 2015-2-20 11:12:12 | 显示全部楼层
will_ym 发表于 2015-2-20 04:29
请教一下第二题怎么解的?

hint:是否能shuffle成valid的字符串可以由每个字符出现的次数的关系确定。
回复 支持 反对

使用道具 举报

will_ym 发表于 2015-2-21 01:33:52 | 显示全部楼层
eval 发表于 2015-2-20 11:12
hint:是否能shuffle成valid的字符串可以由每个字符出现的次数的关系确定。

搞定了,但是是O(n squre). 你当时做得是O(n) 么?
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-2-21 01:49:26 | 显示全部楼层
子矩阵的题可以用容斥,也可以维护一个一维的数组
回复 支持 反对

使用道具 举报

tinalxj12 发表于 2015-2-21 15:01:46 | 显示全部楼层
  1. public static void shuffle(String input){
  2.         List<Character> characters = new ArrayList<Character>();
  3.         for(char c:input.toCharArray()){
  4.             characters.add(c);
  5.         }
  6.         StringBuilder output = new StringBuilder(input.length());
  7.         while(characters.size()!=0){
  8.             int rand = (int)(Math.random()*characters.size());. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  9.             . 鍥磋鎴戜滑@1point 3 acres
  10.             output.append(characters.remove(rand));. visit 1point3acres.com for more.
  11.         }
  12.         
  13.         
  14.         String res = output.toString();
  15.         for (int i=0; i<res.length()-1;i++) {
  16.                 if (res.charAt(i) ==res.charAt(i+1)) {
  17.                         System.out.println("not valid");
  18.                         break;-google 1point3acres
  19.                 }
  20.         }
  21.         System.out.println(res);
  22.     }
复制代码
回复 支持 反对

使用道具 举报

中庸人90 发表于 2015-2-23 06:09:24 | 显示全部楼层
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这个感觉不太对呢,会产生相同的char相邻的情况吧
回复 支持 反对

使用道具 举报

中庸人90 发表于 2015-2-23 06:11:32 | 显示全部楼层
will_ym 发表于 2015-2-21 01:33
搞定了,但是是O(n squre). 你当时做得是O(n) 么?

先统计每个char的个数,如果有count > (size+1)/2, 那就是invalid的。然后剩下的就不会了。。求问怎么做的?
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-2-23 08:19:46 | 显示全部楼层
gg的Host match真心拖啊拖
回复 支持 反对

使用道具 举报

kurtwang 发表于 2015-2-23 08:27:28 | 显示全部楼层
进pool11周了
回复 支持 反对

使用道具 举报

 楼主| eval 发表于 2015-2-23 12:32:14 | 显示全部楼层

哎 。。。 还没有一个host来联系
回复 支持 反对

使用道具 举报

yourway 发表于 2015-2-24 01:37:08 | 显示全部楼层
eval 发表于 2015-2-22 23:32
哎 。。。 还没有一个host来联系

我是1月15日电面的,也是到现在还没有host matching interview。同等待中,,,
回复 支持 反对

使用道具 举报

will_ym 发表于 2015-2-24 03:09:43 | 显示全部楼层
中庸人90 发表于 2015-2-23 06:11
先统计每个char的个数,如果有count > (size+1)/2, 那就是invalid的。然后剩下的就不会了。。求问怎么做 ...

就是先构造一个符合要求的字符串,然后再随机化。随机化的过程和普通随机化的一样,扫一遍就行。构造符合要求的字符串可以对每个元素都扫一遍整个数组然后找到合适的switch, 然后处理下一个。这样的话是O(n square)。其实可以做到O(n). 统计出来每种的个数之后两两配对产生合理的字符串, 这样应该就是线性的了。
回复 支持 反对

使用道具 举报

中庸人90 发表于 2015-2-24 04:01:41 | 显示全部楼层
will_ym 发表于 2015-2-24 03:09
就是先构造一个符合要求的字符串,然后再随机化。随机化的过程和普通随机化的一样,扫一遍就行。构造符合 ...

我之前想的是用一个数组(size 26)保存每个字符和该字符出现的次数,求下一个字符就是对刚插入的字符以外的所有字符random select一个,然后插入,并且次数减一,如此迭代直到所有字符插入完毕。这样是O(n),但是貌似不满足randomly shuffle,因为random select 是对26种字符,而不是对所有字符。不知道这样对不对?
回复 支持 反对

使用道具 举报

中庸人90 发表于 2015-2-24 04:02:26 | 显示全部楼层
will_ym 发表于 2015-2-24 03:09
就是先构造一个符合要求的字符串,然后再随机化。随机化的过程和普通随机化的一样,扫一遍就行。构造符合 ...

多谢!!紫薯紫薯紫薯。。
回复 支持 反对

使用道具 举报

yhzn 发表于 2015-2-26 03:23:51 | 显示全部楼层
第二题是不是可以用贪心做?
先记录每个字符出现的次数,即该字符需要被填入生成字符串的次数 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
然后从第一位开始填空. 1point3acres.com/bbs
然后每次从剩下的字母堆中选取剩余待填入次数最多、且与前一位字符不冲突的字符填入,这样可以确保剩余可填写的不同字符种类是最多的. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
如果没有其他不冲突的待填写字符就报错
最多是O(26n)或O(256n)
回复 支持 反对

使用道具 举报

samantha_kr 发表于 2015-2-27 02:53:07 | 显示全部楼层
yhzn 发表于 2015-2-26 03:23
第二题是不是可以用贪心做?
先记录每个字符出现的次数,即该字符需要被填入生成字符串的次数.1point3acres缃
然后从第一 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
感觉很对!
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-4-6 06:24:46 | 显示全部楼层
will_ym 发表于 2015-2-24 03:09. visit 1point3acres.com for more.
就是先构造一个符合要求的字符串,然后再随机化。随机化的过程和普通随机化的一样,扫一遍就行。构造符合 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
就是先构造一个符合要求的字符串,然后再随机化.随机化怎么保证相邻字母不等?比如, 符合要求的字符串为“abab”,怎么随机化?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 08:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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