在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1879|回复: 11
收起左侧

bloomberg 电面

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

2017(7-9月) 码农类General 硕士 全职@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的可能组合数,第二个数组存后三位的。
循环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
result = first3digits[0]*last3digits[0] + first3digits[1]*last3digits[1] + ..... + first3digits[26]*last3digits[26]. more info on 1point3acres
. 一亩-三分-地,独家发布

估计是挂了,move on....留学论坛-一亩-三分地



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

评分

2

查看全部评分

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

  3. using namespace std;
  4. . 1point3acres
  5. int sumDigit(int x) {
  6.     int ans = 0;
  7.     while(x != 0) {
  8.         ans += x % 10;
  9.         x /= 10;
  10.     }
  11.     return ans;
  12. }

  13. int brutalForce() {
  14.     int ans = 0;
  15.     for(int i = 100; i <= 999; i++) {
  16.         for(int j = 1; j <= 999; j++) {
  17.             if(sumDigit(i) == sumDigit(j)) {
  18.                 ans++;
  19.             }
  20.         }
  21.     }
  22.     return ans; 来源一亩.三分地论坛.
  23. }

  24. int betterSoln() {
  25.     vector<vector<int>> firstHalf(3, vector<int>(28, 0)), secondHalf(3, vector<int>(28, 0)); // firstHalf[i][j], 前i位digit 和为j的方案
  26.     for(int j = 0; j <= 9; j++) {
  27.         if(j > 0) firstHalf[0][j] = 1;
  28.         secondHalf[0][j] = 1;
    -google 1point3acres
  29.     }
  30.     for(int i = 1; i < 3; i++) {
  31.         for(int j = 0; j <= 27; j++) {
  32.             for(int d = 0; d <= 9; d++) {
  33.                 if(j-d >= 0) {
  34.                     firstHalf[i][j] += firstHalf[i-1][j-d];
  35.                     secondHalf[i][j] += secondHalf[i-1][j-d];
  36.                 }-google 1point3acres
  37.             }
  38.         }
  39.     }
  40.     int ans = 0;
  41.     for(int s = 1; s <= 27; s++) {. more info on 1point3acres
  42.         ans += firstHalf[2][s] * secondHalf[2][s];
  43.     }
  44.     return ans;
  45. }

  46. int main(int argc, const char * argv[]) {
  47.     // insert code here...
  48.     cout << brutalForce() << endl;
  49.     cout << betterSoln() << endl;. 牛人云集,一亩三分地
  50.     return 0;-google 1point3acres
  51. }. From 1point 3acres bbs
复制代码
回复 支持 3 反对 0

使用道具 举报

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. 来源一亩.三分地论坛.
  5.         int seed = 1;.1point3acres网
  6.         while (seed < 1000) {
  7.             int sum = seed / 100 + seed / 10 % 10 + seed % 10;
  8.             if (seed >= 100) mapLeft[sum - 1]++;.留学论坛-一亩-三分地
  9.             mapRight[sum - 1]++;
  10.             seed++;
  11.         }
  12. . from: 1point3acres
  13.         int res = 0;
  14.         for (int i = 0; i < 27; i++) {
  15.             res += mapLeft[i] * mapRight[i];. From 1point 3acres bbs
  16.         }. 留学申请论坛-一亩三分地
  17.         return res;
  18.     }
复制代码

回复 支持 2 反对 0

使用道具 举报

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

使用道具 举报

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

那道题是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
  single_sero_set = set(). 1point3acres
  for i in xrange(100, 1000):. 牛人云集,一亩三分地
    first_sum, zero_count, non_zero_num = sum_count_zero(i). from: 1point3acres
    last_3_combo = 1
    if zero_count == 1:
      if non_zero_num in single_sero_set:
        last_3_combo = 0
      else:
        single_sero_set.add(non_zero_num). From 1point 3acres bbs
        last_3_combo = 3. 1point3acres
    elif zero_count == 2: last_3_combo = 3
    . 1point3acres
    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. visit 1point3acres for more.
  zero_count = 0
  non_zero_digits = [0,0]
  non_zero_digits_idx = 1
  while input:
    cur_digit = input%10
    result += cur_digit
    if cur_digit == 0:
      zero_count += 1
    else:
      non_zero_digits[non_zero_digits_idx] = cur_digit
      non_zero_digits_idx -= 1
    input /= 10
  .1point3acres网
  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
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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

使用道具 举报

Darkduke68 发表于 2017-9-18 06:53:45 | 显示全部楼层
codemonk 发表于 2017-8-22 14:13. more info on 1point3acres
可以用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]:. 牛人云集,一亩三分地
             calculate # of permutations for each list (careful about leading 0, or duplicates). 1point3acres
     return total sum

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?
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-23 19:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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