一亩三分地论坛

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

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

狗家5月电面经历

[复制链接] |试试Instant~ |关注本帖
dianhua1560 发表于 2016-6-10 13:26:00 | 显示全部楼层 |阅读模式

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

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

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

x
刷题刷累了,上来攒人品!.鏈枃鍘熷垱鑷1point3acres璁哄潧
搞了两次电面,可能是第一次面的不好又给了第二次机会。还好后来过了,明天onsite。。。Finger crossed!

第一次电面:假设除了用1和0表示数字的binary方式,还可以用2来表示,给一个数字,求有多少种表达方式。
                   例子:4 = 100, 20 所以答案是2。 8 = 1000, 200, 120, 112 所以答案是4。
这题想了半天没想出来,后来给了提示用dp写出来了。

第二次电面:两题都是lc原题,lc298 (Longest consecutive sequence in BT) 和lc128 (longest consecutive sequence in array)。各位自己去看解法吧!

祝大家找工作顺利!!!
. 1point 3acres 璁哄潧


补充内容 (2016-6-11 16:04):
Update:第一题的4应该是100,20,12,答案是3而不是2。谢谢楼下同学提醒!

评分

1

查看全部评分

本帖被以下淘专辑推荐:

handsomecool 发表于 2016-6-11 17:14:00 | 显示全部楼层
瞪了半天我才终于看出第一次电面那题的规律,感觉面试时现想真挺难的。。
我先列一下0-8的表示形式:

0:    0                                    
1:    1                                    
2:    10,2                           
3:    11
4:    100, 20, 12
5:    101, 21
6:    110, 22, 102
7:    111. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
8:    1000, 200, 120, 112

我们可以分别讨论奇数偶数。
如果n是奇数, 那么他的binary表示方式的最右位必然是1, 所以我们只要考虑除去最后一位剩下左边几位的表现形式,即dp[n] = dp[(n-1)/2]
如果n是偶数,那么他的binary表示方式的最右位必然是0或2,我们分情况讨论:
. more info on 1point3acres.com     如果最右位是0,那么只要把n/2的每种表示方式后面加个0即可, 即dp[n] = dp[n/2]. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
     如果最右位是2,类似的可以得到dp[n] = dp[(n-2)/2]

最后的代码如下:

  1. int countWays(int n){. Waral 鍗氬鏈夋洿澶氭枃绔,
  2.     .鏈枃鍘熷垱鑷1point3acres璁哄潧
  3.     vector<int> dp = {1, 1}; // 1 way when n = 0, 1 way when n = 1
  4.    
  5.     for(int i = 2; i<=n; i++) {
  6.         
  7.         int ways = 0;. from: 1point3acres.com/bbs
  8.         
  9.         if(i%2) {
  10.             // i is odd number, right most bit must be one
  11.             ways = dp[(i-1)/2];
  12.             . 鍥磋鎴戜滑@1point 3 acres
  13.         }else {. from: 1point3acres.com/bbs
  14.             // i is even number, right most bit can be 0 or 2
  15.             
  16.             // when right most bit is 0 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  17.             ways = dp[i/2];
  18.             
  19.             // when right most bit is 2
  20.             ways += dp[(i-2)/2];
  21.         }
  22.         dp.push_back(ways);
  23.         
  24.     }
  25.     return dp[n];
  26. }
复制代码
回复 支持 6 反对 0

使用道具 举报

 楼主| dianhua1560 发表于 2016-6-10 17:05:41 | 显示全部楼层
Altynai 发表于 2016-6-10 16:35
第一题是不是这样,dp[j]表示用i位表示j的个数,枚举第i位放k(取值为0,1,2),dp[j] += dp[j-k *(1

不太确定你的答案对不对。。。不过我当时写的是用一个dimension的dp,然后dp的size是n+1,n就是给的那个数。然后算dp从左到右,根据i是奇数还是偶数来决定怎养算dp。具体公式是什么忘了。。。等我明天面完试在回来写出来吧。。。先睡了。。。
回复 支持 0 反对 2

使用道具 举报

Altynai 发表于 2016-6-10 16:35:43 | 显示全部楼层
第一题是不是这样,dp[i][j]表示用i位表示j的个数,枚举第i位放k(取值为0,1,2),dp[i][j] += dp[i-1][j-k *(1<<i)];
回复 支持 反对

使用道具 举报

nevets 发表于 2016-6-11 13:46:15 | 显示全部楼层
第一面其实直接背包就可以:dp[i][j] += dp[i - 1][j] + dp[i - 1][j - (1 << i)] + dp[i - 1][j - (1 << (i + 1))],分别对应i位为0,1,2的情况,写起来和正常背包一样循环就可以。
回复 支持 反对

使用道具 举报

nevets 发表于 2016-6-11 13:46:56 | 显示全部楼层
Altynai 发表于 2016-6-10 16:35
第一题是不是这样,dp[j]表示用i位表示j的个数,枚举第i位放k(取值为0,1,2),dp[j] += dp[j-k *(1
-google 1point3acres
应该没错,看细节了
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-6-11 14:13:45 | 显示全部楼层
咦?    4的话不是应该可以100,20还有12吗? 一个三种吧?
回复 支持 反对

使用道具 举报

 楼主| dianhua1560 发表于 2016-6-11 16:02:52 | 显示全部楼层
handsomecool 发表于 2016-6-11 14:13
. visit 1point3acres.com for more.咦?    4的话不是应该可以100,20还有12吗? 一个三种吧?

对对,我改一下
回复 支持 反对

使用道具 举报

dydcfg 发表于 2016-6-11 16:57:38 | 显示全部楼层
nevets 发表于 2016-6-11 13:46. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一面其实直接背包就可以:dp[j] += dp[j] + dp[j - (1

i这一维可以压缩掉: )
回复 支持 反对

使用道具 举报

 楼主| dianhua1560 发表于 2016-6-12 02:12:02 | 显示全部楼层
handsomecool 发表于 2016-6-11 17:14
瞪了半天我才终于看出第一次电面那题的规律,感觉面试时现想真挺难的。。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我先列一下0-8的表示形式:

看了一下,跟我当时写的一样,只是我是用java写的。赞一个!
回复 支持 反对

使用道具 举报

nevets 发表于 2016-6-13 02:25:11 | 显示全部楼层
dydcfg 发表于 2016-6-11 16:57
i这一维可以压缩掉: )

是的,这就我说的正常背包处理
回复 支持 反对

使用道具 举报

claireyangyang 发表于 2016-8-28 17:37:18 | 显示全部楼层
4 为什么可以是“100,20,12”?20 &12怎么算出来的啊
具体规律还是没怎么懂啊。。谁能告知哦???
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 04:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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