一亩三分地论坛

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

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

谷歌foo.bar的level3

[复制链接] |试试Instant~ |关注本帖
carter13466 发表于 2015-1-15 05:16:40 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类 硕士 实习@Google - Other - 其他 |Other

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

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

x
昨天用google搜java的doc的时候突然网页从中间裂开然后出现一行话问要不要来个coding challenge,点了yes就进到了一个类似linux的terminal的地方,地里也有小伙伴遇到这种情况:http://www.1point3acres.com/bbs/thread-111844-1-1.html


我的题和他差不多,level 1是一道integer palindrome的题,就是给你一个数x(0 <= x <=1000),返回让这个数为palindrome的最小进制b (b>=2).
直接把这个数依次转化成2,3,4……进制再判断是否回文就好了。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
level 2有两道题,第一道和http://www.1point3acres.com/bbs/thread-111844-1-1.html的level 3的题一样。

第二道:题目是关于平衡兔子的数量的,大概题意如下:给你一个int数组x[](每个元素都非负),你可以任意平衡数组内的元素的值,. 1point 3acres 璁哄潧
问在若干次平衡之后,数组内最多能有多少个相同的元素。
举个例子:   输入一个有两个元素的数组x[], x[0] = 2, x[1] = 4, 让x[1]减1,x[0]加1就可以使得两个元素相等,这种情况下返回值为2;
如果数组有4个元素: 比如x[0] = 1, x[1] = 2, x[2] = 3, x[3] = 4,那最多可以让3个元素相等(等于3,剩下的一个等于1),此时返回值应为3;
这题比较简单,直接sum一下然后除以数组的length再做若干判断就好了。


现在卡在level3了,题目是:
给你2个String,a和b,
b的长度小于等于a,a中含有若干个b (可以nested),可以nested就是说有可能在去除a中的某一个b后另一个b才出现,比如a = "aabb", b = "ab"。
去除b的顺序不同就能得到不同的结果,现在让你在去除了所有b的candidates里面找最短的(优先级最高),按照字典顺序最靠前的(lexicographically earliest)那一个String。
我用的bruteforce,就是把所有去掉b的顺序都过一遍,然后找最短的,字典顺序最靠前的那一个String。
但是这样写提交的时候就超时了,大家有啥更高效的解法? 欢迎讨论交流哈哈


补充内容 (2015-1-15 05:21):
level3的那道题输入都会是小写字母,且a的长度不会超过20. 鍥磋鎴戜滑@1point 3 acres

补充内容 (2015-1-15 05:26):. Waral 鍗氬鏈夋洿澶氭枃绔,
再给level3那道题补充个test cases:
Inputs:
    (string) chunk = "lololololo"
    (string) word = "lol"
Output:
    (string) "looo"

评分

2

查看全部评分

twosum 发表于 2015-6-4 00:40:17 | 显示全部楼层
level 三如果超时的话可能需要剪枝
可以做类似于 level traverse,把每一level的结果放在hashmap里,避免重复计算
比如
chunk: ababababc .鏈枃鍘熷垱鑷1point3acres璁哄潧
word: ab
无论你减去哪一个ab,结果都是一样的,这样可以避免重复计算

但是如果. Waral 鍗氬鏈夋洿澶氭枃绔,
(string) chunk = "lololololo"
(string) word = "lol"
好像就不太能剪枝。。。
回复 支持 1 反对 0

使用道具 举报

funkboy 发表于 2015-3-5 01:30:17 | 显示全部楼层
level3想了一个办法,不过不知道是否是通解

先判断b,如果b的第一个字符不等于最后一个字符,就不会因去除b的顺序不同造成不同结果,就去除所有a中的b即可

如果b的第一个字符等于最后一个字符,就判断b的第二个字符是在字母顺序表中早于第一字符还是晚于第一个字符,如果是早于第一个字符,就从a中从前往后扫的去除b,每去除一个b,重新从新得到的a的开头扫;如果b的第二个字符晚于第一个字符,就从a的结尾反相往前扫去除b. 1point3acres.com/bbs

没有经过验证证明此方法的正确性,还需大神验证
回复 支持 反对

使用道具 举报

ww55201 发表于 2015-5-31 05:30:37 | 显示全部楼层

楼主我最近也收到这个,很好奇楼主当时做了几道?真的有下文被联系吗?
回复 支持 反对

使用道具 举报

 楼主| carter13466 发表于 2015-6-1 14:26:11 | 显示全部楼层
ww55201 发表于 2015-5-31 05:30
楼主我最近也收到这个,很好奇楼主当时做了几道?真的有下文被联系吗?

做到level 3就没做了,level 3过了会问你要简历
回复 支持 反对

使用道具 举报

ww55201 发表于 2015-6-2 00:16:26 | 显示全部楼层
carter13466 发表于 2015-6-1 14:26
做到level 3就没做了,level 3过了会问你要简历
. 鍥磋鎴戜滑@1point 3 acres
是之后要简历,能得到电面之类的吗?我level3过了填了个人信息,也不想做了
回复 支持 反对

使用道具 举报

 楼主| carter13466 发表于 2015-6-2 11:42:56 | 显示全部楼层
ww55201 发表于 2015-6-2 00:16
是之后要简历,能得到电面之类的吗?我level3过了填了个人信息,也不想做了
.鐣欏璁哄潧-涓浜-涓夊垎鍦
这个就不知道了,感觉网上关于foobar的讨论也比较少,这玩意比较稀有哈哈
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-10-23 13:25:59 | 显示全部楼层
twosum 发表于 2015-6-4 00:40
level 三如果超时的话可能需要剪枝
可以做类似于 level traverse,把每一level的结果放在hashmap里,避免 ...

为hashmap点赞。。
回复 支持 反对

使用道具 举报

熊亮亮111 发表于 2015-11-9 03:13:06 | 显示全部楼层
楼主,我也刚刚做完foo.bar的level4,有谷歌的人联系了我,我提交了简历。请问你当时做完这个有什么后续吗
回复 支持 反对

使用道具 举报

 楼主| carter13466 发表于 2015-11-9 06:10:50 | 显示全部楼层
熊亮亮111 发表于 2015-11-9 03:13. 1point 3acres 璁哄潧
楼主,我也刚刚做完foo.bar的level4,有谷歌的人联系了我,我提交了简历。请问你当时做完这个有什么后续吗

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 我也不知道呢,我当时只做到level 3就没再继续了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 05:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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