一亩三分地论坛

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

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

G家电面

[复制链接] |试试Instant~ |关注本帖
Boxxxx 发表于 2015-9-28 17:21:43 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
第一次写面经求点赞!
------------------
前几天的电话面试,面试官听口音应该是个白人小哥。。上来先验明lz真身,然后介绍了一下自己。。本来还以为会问一些简历的问题,结果啥也没问直接开始技术面。。。

给一个list,长度未知,里面全是质数,然后给一个k,要求输出前k个正整数,这k个数都能被list里的质数因式分解。。

lz一看到这个题目就闻到了一股递归的气息,然后用大概10分钟blablabla讲怎么用stack存每次分解后的子结果。。谈笑风生了一会儿发现面试官没声音了。。之后他说不如你先写个brute-force,我去研究一下你说的算法。。
然后lz就开始哼哧哼哧地写brute-force(google doc写代码超难用。。),搞一个list存结果,搞一个循环每次check一下能不能被给定的质数分解。。慢慢就搞起来了
写完之后面试官说啊呀你写得很快嘛,但是我草草看过去就发现了至少两个bug啊,姿势水平还需要提高啊。。。当时lz心里一惊开始一边跟他交流一边小心翼翼地debug。。后来感觉差不多了就问他怎么样,他说我看一下应该还行吧(其实我代码都没写完。。个人感觉google更重视你的想法和思维)
之后他followup说如果这个k很大那怎么办。。如果这个list很长怎么办。。。如果这个list是unsorted怎么办。。我说那brute-force肯定不行,要机智地用stack啊,递归找结果啊(纯聊不用写代码). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

然后他就开始说这道题其实有个很好的算法然后blablabla开始讲他的算法。。。讲完之后我说这不就是我刚开始用stack的那个算法的改良版么。。。他说貌似是的。。。之后他说OK,you've done pretty well。。时间也不多了,我就介绍一下Google这个公司吧。。之后就一直说Google有多厉害,公司有多大,员工福利有多好之类。。lz一边听他讲一边附和说哎呀妈呀真屌。。聊了十分钟左右最后就愉快地bye-bye挂电话了。。

挂了电话之后还以为这次要跪了。。没想到过两天之后hr发邮件说可以onsite了。。.鏈枃鍘熷垱鑷1point3acres璁哄潧
. 1point3acres.com/bbs

评分

1

查看全部评分

本帖被以下淘专辑推荐:

stellari 发表于 2015-9-28 21:56:06 | 显示全部楼层

如果要求“N的因子必须在list中,但不一定同时用到list中所有的数”,即第一个满足条件的整数是min(list)。那这题就是LC上的ugly number ii的扩展,DP应该能解。如果是“N的因子集合必须同时包含list中的所有数”的话,那这题其实还是ugly number ii,只不过这k个整数的最小值变成了min(product(list))。解法不变。.1point3acres缃

但是,如果面试官认为的“很好的算法”是递归的话,我想这题的意思或许和我理解的不同。
回复 支持 1 反对 0

使用道具 举报

wenqiang88 发表于 2015-9-28 19:48:27 | 显示全部楼层
请问面试官说的算法是什么?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-9-28 21:04:13 | 显示全部楼层
请问“N能被list里的质数因式分解”指的是“list中所有的质数都必须是N的因子”,还是说“list中有至少一个质数是N的因子”就可以?. 1point3acres.com/bbs
比如:list是{2,3,5}的话。6 = 2 x 3和21 = 3 x 7是否能认为满足条件?
回复 支持 反对

使用道具 举报

rb131108 发表于 2015-9-28 21:05:56 | 显示全部楼层
这题就是ugly number 2 的general版本吧
回复 支持 反对

使用道具 举报

readman 发表于 2015-9-28 21:34:18 | 显示全部楼层
stellari 发表于 2015-9-28 21:04
请问“N能被list里的质数因式分解”指的是“list中所有的质数都必须是N的因子”,还是说“list中有至少一个 ...

应该是"都"能吧
回复 支持 反对

使用道具 举报

readman 发表于 2015-9-28 21:57:15 | 显示全部楼层
stellari 发表于 2015-9-28 21:56
如果要求“N的因子必须在list中,但不一定同时用到list中所有的数”,即第一个满足条件的整数是min(list) ...
只不过这k个整数的最小值变成了min(product(list))


长度不知怎么product. more info on 1point3acres.com

补充内容 (2015-9-28 21:57):
min(product(list)) 是LCM?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-9-28 22:07:32 | 显示全部楼层
readman 发表于 2015-9-28 21:57
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷长度不知怎么product. 1point 3acres 璁哄潧
.1point3acres缃
补充内容 (2015-9-28 21:57):
-google 1point3acres
不好意思,我写错了。我的意思不是min(product(list)),而是product(list),也就是:

list[0]*list[1]*...*list[n-1]
回复 支持 反对

使用道具 举报

readman 发表于 2015-9-28 22:39:02 | 显示全部楼层
stellari 发表于 2015-9-28 22:07
不好意思,我写错了。我的意思不是min(product(list)),而是product(list),也就是:.1point3acres缃

list[0]*list[1] ...

不过楼主不是说list长度未知么......如果未知怎么做...
我估计楼主的"未知"的意思是"任意长度".
回复 支持 反对

使用道具 举报

readman 发表于 2015-9-28 22:43:38 | 显示全部楼层
另外: 为什么list很长, k很大, 反而就能用递归了.....递归不会爆栈么
回复 支持 反对

使用道具 举报

stellari 发表于 2015-9-28 22:54:03 | 显示全部楼层
readman 发表于 2015-9-28 22:39
不过楼主不是说list长度未知么......如果未知怎么做...
我估计楼主的"未知"的意思是"任意长度".

嗯,应该是任意长度。如果连长度都不知道,那list中的数是些什么就更无从得知了。
回复 支持 反对

使用道具 举报

nongminbobo 发表于 2015-9-29 00:04:39 | 显示全部楼层
楼主加油。过两天我也要电面了,攒人品!
回复 支持 反对

使用道具 举报

 楼主| Boxxxx 发表于 2015-9-29 01:53:09 | 显示全部楼层
stellari 发表于 2015-9-28 21:04.1point3acres缃
请问“N能被list里的质数因式分解”指的是“list中所有的质数都必须是N的因子”,还是说“list中有至少一个 ...
. 鍥磋鎴戜滑@1point 3 acres
应该这么说,n的因子都在这个list里面
回复 支持 反对

使用道具 举报

TerrenceLi 发表于 2015-9-29 01:53:15 | 显示全部楼层
请问面试官说的算法是什么?
回复 支持 反对

使用道具 举报

 楼主| Boxxxx 发表于 2015-9-29 01:57:25 | 显示全部楼层
TerrenceLi 发表于 2015-9-29 01:53
请问面试官说的算法是什么?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
就是递归。。假设list里有2,3,5.。。k是5,那么就是  1*2, 1*3, 1*5,1*2*2,1*2*3。。以此类推
回复 支持 反对

使用道具 举报

 楼主| Boxxxx 发表于 2015-9-29 01:57:40 | 显示全部楼层
wenqiang88 发表于 2015-9-28 19:48
请问面试官说的算法是什么?

就是递归。。假设list里有2,3,5.。。k是5,那么就是  1*2, 1*3, 1*5,1*2*2,1*2*3。。以此类推
回复 支持 反对

使用道具 举报

 楼主| Boxxxx 发表于 2015-9-29 01:58:05 | 显示全部楼层
readman 发表于 2015-9-28 22:43
另外: 为什么list很长, k很大, 反而就能用递归了.....递归不会爆栈么
. 鍥磋鎴戜滑@1point 3 acres
我也有这个疑问。。
回复 支持 反对

使用道具 举报

wen587 发表于 2015-9-29 03:20:13 | 显示全部楼层
Boxxxx 发表于 2015-9-29 01:58
我也有这个疑问。。

同疑问, k如果很大 是要用一个数组来存放最小值吗?
比如 list是 2 3 5 7 ——n
回复 支持 反对

使用道具 举报

 楼主| Boxxxx 发表于 2015-9-29 05:18:18 | 显示全部楼层
wen587 发表于 2015-9-29 03:20
同疑问, k如果很大 是要用一个数组来存放最小值吗?
比如 list是 2 3 5 7 ——n

这个没有明确说。。我最后返回了一个list。。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-9-29 10:24:47 | 显示全部楼层
Boxxxx 发表于 2015-9-29 01:57
就是递归。。假设list里有2,3,5.。。k是5,那么就是  1*2, 1*3, 1*5,1*2*2,1*2*3。。以此类推

感谢说明。这样的话,这题就是LC上的ugly number ii了。假设list的长为N的话,那么用DP每找一个满足条件的数,需要做N次乘法,并找出N个数的最小值。所以总时间复杂度是O(NK)。

话说楼主能否简单介绍一下你用的递归算法是如何找到前k个数的呢?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2015-9-29 10:27):-google 1point3acres
主要是想知道lz的方法和面试官给的算法的时间复杂度。多谢!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 12:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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