传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 902|回复: 7
收起左侧

bloomberg 电面

[复制链接] |试试Instant~ |关注本帖
boy27910230 发表于 2017-6-16 01:09:13 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Bloomberg - 猎头 - 技术电面 在线笔试 |Other在职跳槽

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
刚挂的电话。面试官国人大哥,人很好一直给我提示,可是本人太水第二道还是没做出来

1. 在一个先上升后下降的数组里找target, 要求 speed < O(n)
e.g. 在数组 [1,2,3,4,5,19,18,17,16,15] 中找16,
做法是先O(log(n)) 找到peak, 然后if peak == target, return peak index; else if target < peak, 在peak的左边binary search; else 在peak的右边binary search。总时间O(log(n))

2. 找出所有6位整数中有多少前三位的和等于后三位的和。有leading zero的不算。
e.g. 012012 不算, 102012算, 123213也算
简单做法是暴力循环所有100000 - 999999检查每个数的前三位和后三位的和是否相等,Time = 6*900000
高级做法是前三位的和只有可能在1-27之间(100-999), 所以建两个长度27的数组(first3digits[27], last3digits[27]),index + 1表示sum, value表示可能的组合数。第一个数组存储前三位每个sum的可能组合数,第二个数组存后三位的。. 1point3acres.com/bbs
循环100-999在两个数组存前三位和后三位所有包含相同digits的组合数。
e.g. 100的话后三位可能有100, 010, 001, 所以first3digits[0] += 1,  last3digits[0] += 3。. from: 1point3acres.com/bbs
123的话后三位有可能是123,132,213,231,312,321, 所以first3digits[5] += 1,  last3digits[5] += 6
result = first3digits[0]*last3digits[0] + first3digits[1]*last3digits[1] + ..... + first3digits[26]*last3digits[26]


估计是挂了,move on...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


补充内容 (2017-8-4 09:41):
不好意思刚复习第二题时发现做法是错的,因为如果每次都把前三位的所有组合算进后三位的组合数里的话会出现重复。比如123的话如果把六个组合都加到后三位里,循环到321的时候又会放一遍。字数不够了解决办法放回复

评分

2

查看全部评分

chaseqi 发表于 2017-7-4 04:56:11 | 显示全部楼层
谢谢 楼主分享啦 感觉第二题比一般的BB onsite的题都要难一点 楼主加油
回复 支持 反对

使用道具 举报

 楼主| boy27910230 发表于 2017-7-4 05:42:34 | 显示全部楼层
chaseqi 发表于 2017-7-3 14:56
谢谢 楼主分享啦 感觉第二题比一般的BB onsite的题都要难一点 楼主加油

那道题是BB的高频题,很多组都用,尤其是MARS组,面之前一定要看这道。。。
回复 支持 反对

使用道具 举报

chaseqi 发表于 2017-7-4 05:48:08 | 显示全部楼层
boy27910230 发表于 2017-7-4 05:42
那道题是BB的高频题,很多组都用,尤其是MARS组,面之前一定要看这道。。。
. visit 1point3acres.com for more.
恩恩 谢谢楼主! 刚才做了下
回复 支持 反对

使用道具 举报

 楼主| boy27910230 发表于 2017-8-4 23:58:21 | 显示全部楼层
def solution1():
  first_3_digits = [0]*27
  last_3_digits = [0]*27-google 1point3acres
  single_sero_set = set()
  for i in xrange(100, 1000):
    first_sum, zero_count, non_zero_num = sum_count_zero(i)
    last_3_combo = 1
    if zero_count == 1:
      if non_zero_num in single_sero_set:
        last_3_combo = 0. Waral 鍗氬鏈夋洿澶氭枃绔,
      else:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        single_sero_set.add(non_zero_num). from: 1point3acres.com/bbs
        last_3_combo = 3
    elif zero_count == 2: last_3_combo = 3
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    first_3_digits[first_sum - 1] += 1
    last_3_digits[first_sum - 1] += last_3_combo
  
  result = 0
  for i in xrange(27):
    result += first_3_digits[i]*last_3_digits[i]
   
  return result
  
def sum_count_zero(input):
  result = 0. 鍥磋鎴戜滑@1point 3 acres
  zero_count = 0
  non_zero_digits = [0,0]. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  non_zero_digits_idx = 1
  while input:
    cur_digit = input%10
    result += cur_digit. 1point3acres.com/bbs
    if cur_digit == 0:
      zero_count += 1
    else:.1point3acres缃
      non_zero_digits[non_zero_digits_idx] = cur_digit
      non_zero_digits_idx -= 1
    input /= 10
  . 1point3acres.com/bbs
  non_zero_num = 0
  for i in non_zero_digits:
    non_zero_num = non_zero_num*10 + i
  
  return result, zero_count, non_zero_num
回复 支持 反对

使用道具 举报

shannyhe 发表于 2017-8-22 10:24:12 | 显示全部楼层
请问下这个题目leetcode上有原题么?
回复 支持 反对

使用道具 举报

codemonk 发表于 2017-8-22 14:13:45 | 显示全部楼层
可以用dp做,生成两个dp matrix, 一个记前3位,一个记后3位。dp[j] 就是前i位digit 和为j的方案数。  两个dp matrix 初始化稍微不一样。
时间复杂度O(3*28*10)

  1. #include <iostream>-google 1point3acres
  2. #include <vector>

  3. using namespace std;

  4. int sumDigit(int x) {
  5.     int ans = 0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  6.     while(x != 0) {
  7.         ans += x % 10;
  8.         x /= 10;
  9.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  10.     return ans;
  11. }

  12. int brutalForce() {
  13.     int ans = 0;-google 1point3acres
  14.     for(int i = 100; i <= 999; i++) {
  15.         for(int j = 1; j <= 999; j++) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  16.             if(sumDigit(i) == sumDigit(j)) {
  17.                 ans++;
  18.             }
  19.         }
  20.     }
  21.     return ans;
  22. }

  23. int betterSoln() {
  24.     vector<vector<int>> firstHalf(3, vector<int>(28, 0)), secondHalf(3, vector<int>(28, 0)); // firstHalf[i][j], 前i位digit 和为j的方案
  25.     for(int j = 0; j <= 9; j++) {. 1point 3acres 璁哄潧
  26.         if(j > 0) firstHalf[0][j] = 1;. more info on 1point3acres.com
  27.         secondHalf[0][j] = 1;
  28.     }
  29.     for(int i = 1; i < 3; i++) {
  30.         for(int j = 0; j <= 27; j++) {
  31.             for(int d = 0; d <= 9; d++) {
  32.                 if(j-d >= 0) {
  33.                     firstHalf[i][j] += firstHalf[i-1][j-d];
  34.                     secondHalf[i][j] += secondHalf[i-1][j-d];
  35.                 }. 鍥磋鎴戜滑@1point 3 acres
  36.             }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  37.         }
  38.     }
  39.     int ans = 0;
  40.     for(int s = 1; s <= 27; s++) {
  41.         ans += firstHalf[2][s] * secondHalf[2][s];
  42.     }
  43.     return ans;
  44. }
  45. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  46. int main(int argc, const char * argv[]) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  47.     // insert code here...
  48.     cout << brutalForce() << endl;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  49.     cout << betterSoln() << endl;
  50.     return 0;
  51. }
复制代码
回复 支持 反对

使用道具 举报

Darkduke68 发表于 7 天前 | 显示全部楼层
codemonk 发表于 2017-8-22 14:13. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
可以用dp做,生成两个dp matrix, 一个记前3位,一个记后3位。dp[j] 就是前i位digit 和为j的方案数。  两个d ...

1) 找出所有3个数字combination, 放进map里面, key是sum, value是list. from: 1point3acres.com/bbs
2)foreach sum in map:
         pick two lists from the map[key]:
             calculate # of permutations for each list (careful about leading 0, or duplicates)
     return total sum

O(10^3 + sum_count * avg_map_value_length^2)
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-25 14:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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