一亩三分地论坛

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

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

Google onsite

[复制链接] |试试Instant~ |关注本帖
lea82 发表于 2016-7-1 08:44:42 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 内推 - Onsite |Fail在职跳槽

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

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

x
1. Longest substring with at most M distinct charactersHave a rand(N) to return an integer from 0 to N-1 with 1/N probability evenly, design a rand to return a number from 0 to N-1 but not any from a given sorted list such as {2, 4, 9}. require uniform distribution
. more info on 1point3acres.com
2. all combinations of phone number representation, with restriction that the words can only be from a dictionary, with possible digits at front/end, such as 800 TARGET 234.. Waral 鍗氬鏈夋洿澶氭枃绔,
3. one string has only one extra character than the other string, find it out.

follow up: better performance (binary, what if s[i-1] == s[i])
4. find the Kth smallest element in the union of two sorted array
unique abbreviation
5. design Youtube upload.
if the uploading video is against the copyright (as from any of the copyrighted videos in the DB), do not allow it upload.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

评分

1

查看全部评分

本帖被以下淘专辑推荐:

ppirate 发表于 2016-7-1 10:18:05 | 显示全部楼层
看坛子里好多码农面试的经历,怎么没有Google管理类的面经呢...
回复 支持 反对

使用道具 举报

ccrjohn8787 发表于 2016-7-1 11:19:20 | 显示全部楼层
楼主能解释一下第二题吗? 不是很明白最后digit at front/end 那一块。如果是letter combination的话怎么会有digits 呢?
回复 支持 反对

使用道具 举报

mkcing 发表于 2016-7-1 12:33:52 | 显示全部楼层
one string has only one extra character than the other string, find it out.   
能解释下这道题吗?
回复 支持 反对

使用道具 举报

say543 发表于 2016-7-1 14:45:00 | 显示全部楼层
第一题的randN 是说不能用一个array with all values​​ 每个random 然后取第一个是吗? 如果是怎么做呢? 设计题是考察说如何判断duplication 吗因为DB 一定要先有store 才能有机率判断new video 是不是against copy right?
回复 支持 反对

使用道具 举报

lajiwushi 发表于 2016-7-5 04:34:45 | 显示全部楼层
请问下随机数那题 。 因为0到N每个数等概率, 应该每个数都可能被生成, 那么如果产生了一个属于given sorted list应该怎么处理?

补充内容 (2016-7-5 04:47):
感谢题主!
回复 支持 反对

使用道具 举报

 楼主| lea82 发表于 2016-7-9 06:28:16 | 显示全部楼层
ccrjohn8787 发表于 2016-7-1 11:19
楼主能解释一下第二题吗? 不是很明白最后digit at front/end 那一块。如果是letter combination的话怎么会 ...

allow digits at front or the very end,
could be HOMEDEPOT or 800TARGET234 (234 words as extension number).
回复 支持 反对

使用道具 举报

 楼主| lea82 发表于 2016-7-9 06:28:38 | 显示全部楼层
mkcing 发表于 2016-7-1 12:33
one string has only one extra character than the other string, find it out.   
能解释下这道题吗?

cxcc
ccc
output: x
回复 支持 反对

使用道具 举报

 楼主| lea82 发表于 2016-7-9 06:30:14 | 显示全部楼层
lajiwushi 发表于 2016-7-5 04:34
请问下随机数那题 。 因为0到N每个数等概率, 应该每个数都可能被生成, 那么如果产生了一个属于given sort ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
you could ignore this output,. from: 1point3acres.com/bbs
and only output the result when it's not in the given sort.

The drawback is that it could take forever to give out one output, but the good part is that it's uniformly distributed.
回复 支持 反对

使用道具 举报

 楼主| lea82 发表于 2016-7-9 06:30:39 | 显示全部楼层
in the design question, got asked to implement the load balancer.
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-7-10 10:15:09 | 显示全部楼层
话说第一题 rand 只能是从一到一个特定的值么? 还是说可以使用从一到一个任意值的随机数生成器?
回复 支持 反对

使用道具 举报

greentrail 发表于 2016-7-10 13:03:10 | 显示全部楼层
lea82 发表于 2016-7-9 06:30. more info on 1point3acres.com
you could ignore this output,
and only output the result when it's not in the given sort.

对于给出的例子,是不是要求结果是从[0, N-1]但除去{2,4,9},每个结果的概率是1/(N-3)。

补充内容 (2016-7-10 13:08):
还是要求[0, N-1]除去{2,4,9}, 每个结果的概率还是1/N ?
注意到,题目说那个集合是排序的,所以O(logN)就可以找到。为啥take forever呢?
回复 支持 反对

使用道具 举报

fanyy 发表于 2016-7-10 15:41:04 | 显示全部楼层
感觉好难啊啊啊啊
回复 支持 反对

使用道具 举报

edyyy 发表于 2016-7-11 01:14:27 | 显示全部楼层
5. design Youtube upload.
这个怎么弄?no idea
回复 支持 反对

使用道具 举报

lajiwushi 发表于 2016-7-11 21:22:30 | 显示全部楼层
lea82 发表于 2016-7-9 06:30
you could ignore this output,. more info on 1point3acres.com
and only output the result when it's not in the given sort.
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
非常感谢
回复 支持 反对

使用道具 举报

 楼主| lea82 发表于 2016-7-12 08:20:24 | 显示全部楼层
greentrail 发表于 2016-7-10 13:03
对于给出的例子,是不是要求结果是从[0, N-1]但除去{2,4,9},每个结果的概率是1/(N-3)。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2016 ...
-google 1point3acres
每个结果的概率是1/(N-3)

that's correct.
回复 支持 反对

使用道具 举报

chen6145 发表于 2016-7-12 15:05:06 | 显示全部楼层
第四题的union是合并还是合集(去重)啊?这题是merge再quick selection吗?
回复 支持 反对

使用道具 举报

edyyy 发表于 2016-7-13 03:05:38 | 显示全部楼层
fanyy 发表于 2016-7-10 15:41
感觉好难啊啊啊啊

你刷过题了就不觉得难了
回复 支持 反对

使用道具 举报

pengpengche 发表于 2016-7-13 23:50:13 | 显示全部楼层
楼主能不能解释下第二题,完全不明白什么意思,给个例子可以么?
回复 支持 反对

使用道具 举报

greentrail 发表于 2016-7-17 03:45:43 | 显示全部楼层
lea82 发表于 2016-7-12 08:20
每个结果的概率是1/(N-3)

that's correct.

多谢! 楼主怎么解的这题?

我的想法是先用一个N-3长度的数组,存[1-N-1] 除去{2,4,9}, 然后Knuth shuffle. 每一轮用完后,重新shuffle。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

另外,这个集合{2,4,9} 会动态变化吗?

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 14:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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