一亩三分地论坛

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

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

Google onsite 新鲜面经 9/10

[复制链接] |试试Instant~ |关注本帖
dm37537 发表于 2015-9-15 00:23:55 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 本科 全职@Google - 猎头 - Onsite |Otherfresh grad应届毕业生

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

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

x
前四轮都好好的,感觉就这么搞定了?结果最后一轮是阿三,于是就跪了,目测没啥希望了。

1. 印度女生,虽然是印度的,但女生还是比较友善的。题目大致是BACCBBAAA -> ABABACABC,就是输出相邻字母不能相同的string,这题要用到heap

2. 用尽量短的string生成4位数密码的所有组合

3. 生成palindrome number, 然后寻找最相近的palindrome number,最简单的了,不过要注意奇数个digits和偶数个digits, 本以为就这么水过,结果最后遇到阿三

4. 黑白2D array表示的image。边长是2^n。设计一个class来存它,用尽量少的space。提示是可以不断把图形分割成四块,分完继续分。如果其中一块里面所有格都是黑,那一块就是黑。. more info on 1point3acres.com
   然后连个相同大小的的image相交生产第三个image,遵循黑黑得黑,其他都白的规则。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

人生第一个onsite。准备也不是很充分。就让它随风而去吧。



. from: 1point3acres.com/bbs
补充内容 (2015-9-15 12:41):. from: 1point3acres.com/bbs
同志们给分呐~

评分

8

查看全部评分

本帖被以下淘专辑推荐:

edly 发表于 2015-9-15 14:48:18 | 显示全部楼层
hbsophia 发表于 2015-9-15 14:38
lz,好厉害啊,第二题应该就是这个,能不能麻烦lz贴一下代码或者私信一下代码?实在是不会做啊,我这周五on ...

把所有的3个数字看成1个节点,点与点之间连有向边当且仅当第一个节点的后两个数字等于第二个节点的前两个数字,每一条边就表示一个4位数字,如1234表示成123->234这条边-google 1point3acres

节点的移动表示新加了一个char,遍历所有边即包含所有串,该图显然满足有向图欧尔回路存在条件,求一遍欧拉回路即可

欧拉回路代码就几行 网上随便找
回复 支持 2 反对 0

使用道具 举报

TerrenceLi 发表于 2015-9-15 00:53:29 | 显示全部楼层
第四题是用quadtree么?
bless 楼主
回复 支持 反对

使用道具 举报

TerrenceLi 发表于 2015-9-15 00:57:22 | 显示全部楼层
顺带能问下lz第二题的细节么,没看懂
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-15 01:14:26 | 显示全部楼层
问题2, 和4 能不能细说下, 楼主。
回复 支持 反对

使用道具 举报

 楼主| dm37537 发表于 2015-9-15 02:09:43 | 显示全部楼层
第二题:就是把所有4位数字的密码存在一个string里面,比如123456 = 1234和2345和3456. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第四题:我还真没想到还有quadtree这种东西.. 我最后用map和数列推导做了一个东西,现在想想和quadtree是一个意思,我相当于用map把tree给表示出来了.. 准备还是不充分啊
回复 支持 反对

使用道具 举报

TerrenceLi 发表于 2015-9-15 02:24:36 | 显示全部楼层
dm37537 发表于 2015-9-15 02:09
第二题:就是把所有4位数字的密码存在一个string里面,比如123456 = 1234和2345和3456
第四题:我还真没想 ...

所以第二题就是用一个尽可能短的string来包含所有给定的substring么
回复 支持 反对

使用道具 举报

baobozo 发表于 2015-9-15 02:52:44 | 显示全部楼层
how to solve problem no.2? Anyone?
回复 支持 反对

使用道具 举报

baobozo 发表于 2015-9-15 02:52:50 | 显示全部楼层
how to solve problem no.2? Anyone?
回复 支持 反对

使用道具 举报

storm_hair 发表于 2015-9-15 03:42:57 | 显示全部楼层
最相近的Palindrome number是什么意思
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-15 04:00:44 | 显示全部楼层
baobozo 发表于 2015-9-15 02:52
how to solve problem no.2? Anyone?

http://technology.manyask.com/viewtopic.php?t=1431525
貌似 这个。。。不会吧, 好难哦。。
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-9-15 10:42:52 | 显示全部楼层
dm37537 发表于 2015-9-15 02:09. 鍥磋鎴戜滑@1point 3 acres
第二题:就是把所有4位数字的密码存在一个string里面,比如123456 = 1234和2345和3456
第四题:我还真没想 ...

四位数字的密码有10000种可能对吧,那这个string要包含这10000种可能?
你举的这个123456 的例子里只有1234, 2345, 3456三个密码, 还有9999, 9998,9997...0001,0000这么多种可能呢。. 1point 3acres 璁哄潧
求解释啊,或者楼主可以讲讲自己是咋么做的么?
回复 支持 反对

使用道具 举报

 楼主| dm37537 发表于 2015-9-15 12:43:06 | 显示全部楼层
handsomecool 发表于 2015-9-15 10:42.鐣欏璁哄潧-涓浜-涓夊垎鍦
四位数字的密码有10000种可能对吧,那这个string要包含这10000种可能?
你举的这个123456 的例子里只有1 ...

比如...难道你要我把string全写出来?
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-9-15 13:14:20 | 显示全部楼层
dm37537 发表于 2015-9-15 12:43
比如...难道你要我把string全写出来?
. From 1point 3acres bbs
哈哈,当然不用。。我只是想确定一下我有没理解错题意。。

那这题要怎么做呀? 我能想到的就只有暴力的生成这个10000个密码,一边生成一边在我的解里面查是否已经contain了,不contain才append上去。 这样既慢,又不能保证得到最小的解。。。
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-15 14:24:36 | 显示全部楼层
lz很厉害啊,这些题我都不会。。。请问lz,第一题是啥意思。。。
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-15 14:38:02 | 显示全部楼层
lz,好厉害啊,第二题应该就是这个,能不能麻烦lz贴一下代码或者私信一下代码?实在是不会做啊,我这周五onsite,怎么感觉要跪。。。

http://www.mitbbs.com/article_t1/JobHunting/32604357_0_1.html
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-9-15 15:28:48 | 显示全部楼层
hbsophia 发表于 2015-9-15 14:24
lz很厉害啊,这些题我都不会。。。请问lz,第一题是啥意思。。。

第一题估计是用贪心法,每次把出现最多的字母解决,我试着用priority_queue写了下:
  1. unordered_map<char, int> map;. more info on 1point3acres.com
  2. string noSameNeighbor(string & s){
  3.         string ans = "";
  4.         for (char c : s)
  5.                 map[c]++;               
  6.         . 1point 3acres 璁哄潧
  7.         auto comp = [](char char1, char char2){return map[char1] < map[char2]; };. visit 1point3acres.com for more.
  8.         priority_queue <char, vector<char>, decltype(comp)> pq(comp);
  9.         for (pair<char, int> p : map). 1point3acres.com/bbs
  10.                 pq.push(p.first);

  11.         while (!pq.empty()){
  12.                 char c = pq.top();
  13.                 pq.pop();
  14.                 if (pq.empty()){
  15.                         ans += c;
  16.                         break;
  17.                 }
  18.                 char d = pq.top();
  19.                 pq.pop();
  20.                 ans += c;
  21.                 ans += d;
  22.                 map[c]--;
  23.                 map[d]--;
  24.                 if (map[c] > 0) pq.push(c);
  25.                 if (map[d] > 0) pq.push(d);
  26.         }. From 1point 3acres bbs

  27.         return ans;
  28. }
复制代码
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-17 01:32:58 | 显示全部楼层
handsomecool 发表于 2015-9-15 15:28. 鍥磋鎴戜滑@1point 3 acres
第一题估计是用贪心法,每次把出现最多的字母解决,我试着用priority_queue写了下:

请问大牛,这个你是用minHeap? 为啥不用max heap?
多谢
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-17 02:21:25 | 显示全部楼层
handsomecool 发表于 2015-9-15 15:28
第一题估计是用贪心法,每次把出现最多的字母解决,我试着用priority_queue写了下:
.鐣欏璁哄潧-涓浜-涓夊垎鍦
试了下这个代码,works well。 但是不知道为啥minheap works 但是, max heap不work?

啥意思呢,多谢多谢!
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-17 02:34:30 | 显示全部楼层
为什么第一题需要heap?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 02:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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