推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 563|回复: 4
收起左侧

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也算. 鍥磋鎴戜滑@1point 3 acres
简单做法是暴力循环所有100000 - 999999检查每个数的前三位和后三位的和是否相等,Time = 6*900000
高级做法是前三位的和只有可能在1-27之间(100-999), 所以建两个长度27的数组(first3digits[27], last3digits[27]),index + 1表示sum, value表示可能的组合数。第一个数组存储前三位每个sum的可能组合数,第二个数组存后三位的。
循环100-999在两个数组存前三位和后三位所有包含相同digits的组合数。. visit 1point3acres.com for more.
e.g. 100的话后三位可能有100, 010, 001, 所以first3digits[0] += 1,  last3digits[0] += 3。.1point3acres缃
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...
.鏈枃鍘熷垱鑷1point3acres璁哄潧


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

评分

2

查看全部评分

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

使用道具 举报

 楼主| boy27910230 发表于 2017-7-4 05:42:34 | 显示全部楼层
关注一亩三分地微博:
Warald
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组,面之前一定要看这道。。。

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

使用道具 举报

 楼主| boy27910230 发表于 2017-8-4 23:58:21 | 显示全部楼层
def solution1():
  first_3_digits = [0]*27
  last_3_digits = [0]*27
  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. visit 1point3acres.com for more.
      else:
        single_sero_set.add(non_zero_num)
        last_3_combo = 3
    elif zero_count == 2: last_3_combo = 3. From 1point 3acres bbs
    . from: 1point3acres.com/bbs
    first_3_digits[first_sum - 1] += 1. From 1point 3acres bbs
    last_3_digits[first_sum - 1] += last_3_combo
  
  result = 0.1point3acres缃
  for i in xrange(27):
    result += first_3_digits[i]*last_3_digits[i]
   
  return result
  
def sum_count_zero(input):
  result = 0
  zero_count = 0
  non_zero_digits = [0,0]. 1point 3acres 璁哄潧
  non_zero_digits_idx = 1
  while input:
    cur_digit = input%10
    result += cur_digit
    if cur_digit == 0:
      zero_count += 1. more info on 1point3acres.com
    else:
      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:.1point3acres缃
    non_zero_num = non_zero_num*10 + i
  
鏉ユ簮涓浜.涓夊垎鍦拌鍧.   return result, zero_count, non_zero_num
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-17 10:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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