一亩三分地论坛

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

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

Google 8-24电面

[复制链接] |试试Instant~ |关注本帖
sssztq 发表于 2016-8-25 03:20:07 | 显示全部楼层 |阅读模式

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

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

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

x
新鲜出炉8-24电面,题目是:
How many 1-bits are there in a 2^20 sized array with numbers in sequence from 0 to 2^20 - 1?

刚开始学java一个多月,申请的太早了。根本没想到能过oa,之后还有电面,结果准备的不好,做的也不好,肯定没戏啦。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
面试阿三哥还挺nice的,鼓励了我一大堆,说如果觉得coding能找到fun就继续学习。. visit 1point3acres.com for more.
我要继续学习了。。。

祝大家能成功!

评分

1

查看全部评分

llatjob 发表于 2016-8-26 21:31:06 | 显示全部楼层
这些数字总共2^20*20个bit,一半是0,一半是1,所以2^19*20
回复 支持 5 反对 0

使用道具 举报

Josh 发表于 2016-8-25 05:56:23 | 显示全部楼层
用dynamic programming。0~2^20-1就是从0到11111111111111111111(20个1),用数组dp记录从0到i个1中1bit的个数。. from: 1point3acres.com/bbs
dp = dp[i-1]*2+1.
因为对于i个1来说,最高位为0时的个数是dp[i-1],最高位为1时的个数是1+dp[i-1],加起来就是dp[i-1]*2+1

补充内容 (2016-8-25 07:14):
抱歉写错了,应该是dp = dp[i-1]*2+(1<<(i-1)) (备注:1<<(i-1) == 2^(i-1)). 当最高位为1时的个数是dp[i-1] + 2^(i-1)
回复 支持 1 反对 1

使用道具 举报

aangel 发表于 2016-8-26 03:38:33 | 显示全部楼层


n为从0到20之间的整数,.1point3acres缃
.鐣欏璁哄潧-涓浜-涓夊垎鍦
规律: f(n) = 2*f(n-1) + 2^(n-1)

用DP写一下code就可以了
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-8-25 03:30:16 | 显示全部楼层
How many 1 bits in the number represented by this array or sum of 1 bits of each position of this array ?
回复 支持 反对

使用道具 举报

dimi 发表于 2016-8-25 04:48:11 | 显示全部楼层
hamming weight?
回复 支持 反对

使用道具 举报

zqzwxec 发表于 2016-8-25 06:11:18 | 显示全部楼层
if the number of digits is N, then it will be (2^(N-1)) * N.
回复 支持 反对

使用道具 举报

haobotao000 发表于 2016-8-25 08:55:14 | 显示全部楼层
能问下题主什么时候做的OA吗?
回复 支持 反对

使用道具 举报

Josh 发表于 2016-8-25 09:00:02 | 显示全部楼层
zqzwxec 发表于 2016-8-25 06:11
if the number of digits is N, then it will be (2^(N-1)) * N.

can you explain it?
回复 支持 反对

使用道具 举报

dashuaiding 发表于 2016-8-25 09:34:26 | 显示全部楼层
start from small to large

n = 2.
00   每一列有一半是1,当
01
10
11

n = 3.
000
001.1point3acres缃
010
011
100
101-google 1point3acres
110. 1point3acres.com/bbs
111 还是每一列有一半是1

低一位变化到高一位其实就是复制一遍自己,然后前一半第一位是0,后一半第一位是1

所以根据n 的大小,以及这一列有多少个就可以知道对某一个数n有多少个1的bit是n * (2^(n) / 2) = n * (2^(n - 1))
回复 支持 反对

使用道具 举报

pandaneedsjob 发表于 2016-8-25 10:36:25 | 显示全部楼层
这根本就不是考coding, 考数学啊
回复 支持 反对

使用道具 举报

youlixiang 发表于 2016-8-25 11:09:22 | 显示全部楼层
其实是一道排列组合题。 用r的话很好写, 用java话因为阶乘和除法可能没有优化就需要采取别的办法

补充内容 (2016-8-25 11:33):
3194869
回复 支持 反对

使用道具 举报

Ridingstar01 发表于 2016-8-25 11:48:43 | 显示全部楼层
楼主可能面试时间短遇到这样的题不太有思路,其实越是乍一看没思路的题往往静下心来把k=1,2,3 写出来就很容易看出规律了。继续加油!
回复 支持 反对

使用道具 举报

llatjob 发表于 2016-8-27 03:36:17 | 显示全部楼层
There are 2 ^ 20 * 20 bits in total
half of them are 1, the other half is 0. from: 1point3acres.com/bbs
so it is 2 ^ 19 * 20
回复 支持 反对

使用道具 举报

lll_2013 发表于 2016-8-27 04:06:52 | 显示全部楼层
aangel 发表于 2016-8-25 14:38
n为从0到20之间的整数,

规律: f(n) = 2*f(n-1) + 2^(n-1)

感觉上应该是
i = 0 ~ 2^20
dp = dp[i - 1] * 2 + 2 ^ (i - 1)
回复 支持 反对

使用道具 举报

constancelee 发表于 2016-8-27 08:17:27 | 显示全部楼层
请问楼主什么时候拿到电面结果?
回复 支持 反对

使用道具 举报

liu298871369 发表于 2016-8-27 11:15:51 | 显示全部楼层
lll_2013 发表于 2016-8-27 04:06
感觉上应该是
i = 0 ~ 2^20.鏈枃鍘熷垱鑷1point3acres璁哄潧
dp = dp * 2 + 2 ^ (i - 1)

你的感觉是错的
回复 支持 反对

使用道具 举报

lll_2013 发表于 2016-8-27 11:55:11 | 显示全部楼层
liu298871369 发表于 2016-8-26 22:15. visit 1point3acres.com for more.
你的感觉是错的

恩恩,我错了,应该是20bit,我看成2^20bit
回复 支持 反对

使用道具 举报

 楼主| sssztq 发表于 2016-8-28 02:03:00 | 显示全部楼层
haobotao000 发表于 2016-8-25 08:55
能问下题主什么时候做的OA吗?

7月5号,然后7月20来的电话,我约的8月24电面
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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