一亩三分地论坛

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

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

Google 电面 二面

[复制链接] |试试Instant~ |关注本帖
y颜慕一 发表于 2016-4-27 05:04:48 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
电面一面的面经在这里.1point3acres缃
http://www.1point3acres.com/bbs/thread-183067-1-1.html
这次是第二面,第一面题好难LZ没答好,二面题目就超简单我也是被这个差距给惊狗带。不求offer,求个onsite体验一把啊哈哈哈
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
大概就是取一个array里的任意n个不同的值,得到一个随机的组合,不能取同一个index的数,但是可以取数值相同的不同index的数

给一个array:[5,1,3,3],
再给一个数字n:2,
求这个array里的任意num个数:比如可以得到[5,1] or [5,3] or [1,3] or [3,3] ,但是不能得到[5,5] 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

再比如[5,1,3,3], 1 ===> [5] or [1] or [3]
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
LZ就是先判断如果n>array.length或者n<=0或者array是空,返回一个空array
否则就是一个loop,每一次生成一个random的index数字,还用了一个hashset来存之前访问过的index,如果生成的random index之前已经get了,就再继续生成一个random index。.鐣欏璁哄潧-涓浜-涓夊垎鍦
loop n次,每次取到的值放进新的结果array里。
然后说了说也可以用一个boolean array存每个值有没有已经取到。。
写完后再写了写unit test什么的,还有问道怎么检测得到的结果比如[5,1]确实是[5,1,3,3]里的

问问大家有没有更优的方法啊

评分

1

查看全部评分

本帖被以下淘专辑推荐:

Altynai 发表于 2016-6-26 20:17:25 | 显示全部楼层
如果能更改原数组的话,不就是shuffle一下取前n个?
回复 支持 1 反对 0

使用道具 举报

ykwwind 发表于 2016-4-27 05:18:39 | 显示全部楼层
排序.... 1point3acres.com/bbs
然后么..permutation....dfs
回复 支持 1 反对 0

使用道具 举报

adiggo 发表于 2016-4-27 07:27:11 | 显示全部楼层
可以优化一下。 要不然 每次random index都得check用过没有。 可以用个array 存 0到n-1 的index, 用一个for loop, 然后每次 rand mod  n-i,每次拿到的random index move到结尾。 这样下次可以保证不会用到之前的index,不知道这样行不行
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-4-27 07:31:20 | 显示全部楼层
是只要一个可行结果还是要输出所有呢?
回复 支持 反对

使用道具 举报

小艾哥 发表于 2016-4-27 10:30:23 | 显示全部楼层
楼主请问你一面过后多久收到二面的通知的啊?
回复 支持 反对

使用道具 举报

jjustc 发表于 2016-6-17 11:15:20 | 显示全部楼层
caiqi8877 发表于 2016-4-27 07:31
是只要一个可行结果还是要输出所有呢?

目测是只需要得到一个结果 。。。。
回复 支持 反对

使用道具 举报

pengpengche 发表于 2016-6-26 04:55:19 | 显示全部楼层
这真的是google的题么。。。。但愿我的电面这个难度
回复 支持 反对

使用道具 举报

WaveRace 发表于 2016-6-27 03:25:08 | 显示全部楼层
ykwwind 发表于 2016-4-27 05:18
排序...
然后么..permutation....dfs

这就是最优解了
回复 支持 反对

使用道具 举报

greentrail 发表于 2016-6-28 07:59:52 | 显示全部楼层
adiggo 发表于 2016-4-27 07:27. Waral 鍗氬鏈夋洿澶氭枃绔,
可以优化一下。 要不然 每次random index都得check用过没有。 可以用个array 存 0到n-1 的index, 用一个fo ...

这个方法好耶
回复 支持 反对

使用道具 举报

fatalme 发表于 2016-6-28 16:35:28 来自手机 | 显示全部楼层
两个电面都挺难的。
回复 支持 反对

使用道具 举报

zhihaosun 发表于 2016-10-24 16:24:10 | 显示全部楼层
用个HashMap记录数组中每个数字的出现次数,然后backtrack生成这些array吧
回复 支持 反对

使用道具 举报

garygao1993 发表于 2016-10-24 23:35:45 | 显示全部楼层
感觉 shuffle 做了前 n 个返回前 n 个就好了...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2016-10-25 07:40):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
不对...要做完全部的 shuffle 返回前 n 个...
回复 支持 反对

使用道具 举报

metalsolid 发表于 2016-11-8 00:27:14 | 显示全部楼层
reservoir sampling?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 08:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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