一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2183|回复: 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就继续学习。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我要继续学习了。。。
-google 1point3acres
祝大家能成功!

评分

1

查看全部评分

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

使用道具 举报

Josh 发表于 2016-8-25 05:56:23 | 显示全部楼层
关注一亩三分地微博:
Warald
用dynamic programming。0~2^20-1就是从0到11111111111111111111(20个1),用数组dp记录从0到i个1中1bit的个数。
dp = dp[i-1]*2+1.
因为对于i个1来说,最高位为0时的个数是dp[i-1],最高位为1时的个数是1+dp[i-1],加起来就是dp[i-1]*2+1. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. From 1point 3acres bbs
补充内容 (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之间的整数,

. 1point 3acres 璁哄潧规律: 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 ?
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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,当. more info on 1point3acres.com
01
10
11

n = 3.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
000. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
001. 鍥磋鎴戜滑@1point 3 acres
010.鐣欏璁哄潧-涓浜-涓夊垎鍦
011
100
101. from: 1point3acres.com/bbs
110
111 还是每一列有一半是1

低一位变化到高一位其实就是复制一遍自己,然后前一半第一位是0,后一半第一位是1
.1point3acres缃
所以根据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. 1point 3acres 璁哄潧
so it is 2 ^ 19 * 20
回复 支持 反对

使用道具 举报

头像被屏蔽
lll_2013 发表于 2016-8-27 04:06:52 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

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
dp = dp * 2 + 2 ^ (i - 1)

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

使用道具 举报

头像被屏蔽
lll_2013 发表于 2016-8-27 11:55:11 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| 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, 2017-3-26 05:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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