《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1384|回复: 11
收起左侧

bloomberg 电面

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

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

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

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

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的可能组合数,第二个数组存后三位的。. 1point 3acres 璁哄潧
循环100-999在两个数组存前三位和后三位所有包含相同digits的组合数。
e.g. 100的话后三位可能有100, 010, 001, 所以first3digits[0] += 1,  last3digits[0] += 3。
123的话后三位有可能是123,132,213,231,312,321, 所以first3digits[5] += 1,  last3digits[5] += 6.1point3acres缃
result = first3digits[0]*last3digits[0] + first3digits[1]*last3digits[1] + ..... + first3digits[26]*last3digits[26]


估计是挂了,move on...



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

评分

2

查看全部评分

bigteemo 发表于 2017-11-4 04:14:35 | 显示全部楼层
第一题似乎如果peak != target, 需要两边各自跑一个binary search,而不是if else
回复 支持 2 反对 0

使用道具 举报

yuranrobin 发表于 2017-10-18 13:52:43 | 显示全部楼层
  1. private static int getSameSum() {
  2.         int[] mapLeft = new int[27];
  3.         int[] mapRight = new int[27];

  4.         int seed = 1;
  5.         while (seed < 1000) {
  6.             int sum = seed / 100 + seed / 10 % 10 + seed % 10;
  7.             if (seed >= 100) mapLeft[sum - 1]++;-google 1point3acres
  8.             mapRight[sum - 1]++;
  9.             seed++;
  10.         }

  11.         int res = 0;
  12.         for (int i = 0; i < 27; i++) {
  13.             res += mapLeft[i] * mapRight[i];
  14.         }
  15.         return res;
  16.     }
复制代码

回复 支持 1 反对 0

使用道具 举报

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

  1. #include <iostream>
  2. #include <vector>
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  3. using namespace std;

  4. int sumDigit(int x) {
  5.     int ans = 0;
  6.     while(x != 0) {
  7.         ans += x % 10;
  8.         x /= 10;
  9.     }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  10.     return ans;
  11. }
  12. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  13. int brutalForce() {
  14.     int ans = 0;
  15.     for(int i = 100; i <= 999; i++) {
  16.         for(int j = 1; j <= 999; j++) {
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  17.             if(sumDigit(i) == sumDigit(j)) {
  18.                 ans++;
  19.             }
  20.         }
  21.     }
  22.     return ans;
  23. }. more info on 1point3acres.com
  24. -google 1point3acres
  25. int betterSoln() {
  26.     vector<vector<int>> firstHalf(3, vector<int>(28, 0)), secondHalf(3, vector<int>(28, 0)); // firstHalf[i][j], 前i位digit 和为j的方案
  27.     for(int j = 0; j <= 9; j++) {
  28.         if(j > 0) firstHalf[0][j] = 1;
  29.         secondHalf[0][j] = 1;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  30.     }
  31.     for(int i = 1; i < 3; i++) {
  32.         for(int j = 0; j <= 27; j++) {
  33.             for(int d = 0; d <= 9; d++) {
  34.                 if(j-d >= 0) {
  35.                     firstHalf[i][j] += firstHalf[i-1][j-d];
  36.                     secondHalf[i][j] += secondHalf[i-1][j-d];
  37.                 }
  38.             }
  39.         }
  40.     }
  41.     int ans = 0;
  42.     for(int s = 1; s <= 27; s++) {
  43.         ans += firstHalf[2][s] * secondHalf[2][s];
  44.     }
  45.     return ans;
  46. }

  47. int main(int argc, const char * argv[]) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  48.     // insert code here...
  49.     cout << brutalForce() << endl;. more info on 1point3acres.com
  50.     cout << betterSoln() << endl;
  51.     return 0;
  52. }. 1point 3acres 璁哄潧
复制代码
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

 楼主| boy27910230 发表于 2017-7-4 05:42:34 | 显示全部楼层
chaseqi 发表于 2017-7-3 14:56
谢谢 楼主分享啦 感觉第二题比一般的BB onsite的题都要难一点 楼主加油
.鏈枃鍘熷垱鑷1point3acres璁哄潧
那道题是BB的高频题,很多组都用,尤其是MARS组,面之前一定要看这道。。。
回复 支持 反对

使用道具 举报

chaseqi 发表于 2017-7-4 05:48:08 | 显示全部楼层
boy27910230 发表于 2017-7-4 05:42. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
那道题是BB的高频题,很多组都用,尤其是MARS组,面之前一定要看这道。。。

恩恩 谢谢楼主! 刚才做了下
回复 支持 反对

使用道具 举报

 楼主| 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). Waral 鍗氬鏈夋洿澶氭枃绔,
    last_3_combo = 1
    if zero_count == 1:
      if non_zero_num in single_sero_set:. From 1point 3acres bbs
        last_3_combo = 0
      else:
. Waral 鍗氬鏈夋洿澶氭枃绔,        single_sero_set.add(non_zero_num) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        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]
    . From 1point 3acres bbs
  return result
  
def sum_count_zero(input):.鐣欏璁哄潧-涓浜-涓夊垎鍦
  result = 0
  zero_count = 0
  non_zero_digits = [0,0]
  non_zero_digits_idx = 1
  while input:. 鍥磋鎴戜滑@1point 3 acres
    cur_digit = input%10. 1point 3acres 璁哄潧
    result += cur_digit
    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
  
  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上有原题么?
回复 支持 反对

使用道具 举报

Darkduke68 发表于 2017-9-18 06:53:45 | 显示全部楼层
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
2)foreach sum in map:
         pick two lists from the map[key]:. from: 1point3acres.com/bbs
             calculate # of permutations for each list (careful about leading 0, or duplicates)
     return total sum. From 1point 3acres bbs

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

使用道具 举报

北极猪一只 发表于 2017-10-19 22:34:42 | 显示全部楼层
请问楼主bb不同的组,可以连续面没有冷冻期的吗?
回复 支持 反对

使用道具 举报

路怒路怒路怒 发表于 2017-11-9 09:44:47 | 显示全部楼层
想问楼主第一题 怎么用O(log(n)) 找到peak?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-23 15:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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