一亩三分地论坛

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

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

Bloomberg 新鲜面经

[复制链接] |试试Instant~ |关注本帖
flex 发表于 2016-8-4 00:05:23 | 显示全部楼层 |阅读模式

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

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

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

x
昨天收到两个Bloomberg的电面,其中一个感觉有些坑,题目难度都还OK。直接上题:

. from: 1point3acres.com/bbs
第一个电面:
1. 贴上来一个题目让改错:
// 错误1
char test[30];
int elementSize = sizeof(test); // 明显要写成 sizeof(test)/sizeof(test[0]);
// 错误2,这个经过他提示在发现= = ||
class Base{}
class Child:Base{ini a};. 鍥磋鎴戜滑@1point 3 acres
void visit(Base* arr, int len) {
  for (int i = 0; i < len; i++) {
    Base a = arr; // 如果Pass进来的是Child实例,内存地址会有问题. Waral 鍗氬鏈夋洿澶氭枃绔,
  }.1point3acres缃
}
2. 让我实现vector class
要求实现push_back, [], size()
我用一个malloc的数组,如果size到了threshold,就double
要求好多细节,copy constructor, = operator, destructor, 这个vector作为function argument pass的时候会有什么问题
还让我写个程序,用这个vector,让stack爆掉 O_o,这个无能了...
3. 实现一个函数,打印100000到999999所有前三位Sum等于后三位Sum的数
5分钟不到Bug Free实现出来,于是说怎么优化,我说计算三位数Sum的SubRoutine可以cache结果到hashmap,下次遇到一样的不用再算,他似乎不满意。
问我现在的算法复杂度,我说O(n) (n个数字, 每个数字要遍历6次digit,6n),他说还能优化,我问有LogN?他死活不说...我想过用BST,似乎不行。大家想想有啥办法?.1point3acres缃

第二个电面:. 1point 3acres 璁哄潧
面试官上来问我名字,然后发现自己简历拿错了。说自己题目都准备错了,当场调出我简历现读,汗 O_o. visit 1point3acres.com for more.
1. 给我说下C++里map的实现,unordered_map和map有什么区别,里面的实现有什么区别
2. 然后来了一道坑题,键盘敲打了半天画出了一个图,还不停的自语:我恨这个键盘...。
然后解释了半天他要我求的问题,搞了半天我感觉就是要我求最大深度及最小到Leaf深度的绝对值差,我问了一下是不是这个意思,他说这样就可以做...大哥,那你就直说吧。虽然都是LC原题,已经被搞慌了,GetMinDepth写得磕磕碰碰,都能被他抓出Bug,唉,心理素质有待提高啊。. visit 1point3acres.com for more.
然后他让我One Pass做完,我说Traverse,写了一遍居然有严重愚昧Bug,指出后改正。这种错误在平时刷题的时候都不会出现的,总结来说还是心态!脑子里面没有具体想好,不要轻易开写!
面试60分钟,45分钟就结束了。

希望对大家有用!. Waral 鍗氬鏈夋洿澶氭枃绔,
大伙可以看看这个6位数题,有啥好办法吗?看不了地里的包裹贴,另求积分,求大米。。。

评分

1

查看全部评分

 楼主| flex 发表于 2016-8-15 01:21:29 | 显示全部楼层
何打发123 发表于 2016-8-15 00:36
写了一个 求斧正~~~

第二段的逻辑会遍历100到999并重复计算getSum,遍历HashMap应该会更好些,因为总共27个Entry,每个Entry也就几个做全排列,复杂度会好一些。我写了一个版本,和暴力法的结果验证一致,供50412种情况:
  1. int getSum(int num) {
  2.     int sum = 0;. 1point3acres.com/bbs
  3.     while (num != 0) {
  4.         sum += num % 10;
  5.         num = num / 10;
  6.     }
  7.     return sum;
  8. }

  9. vector<int> getNum() {
  10.     vector<int> result;
  11.     unordered_map<int, vector<int>> parts;. from: 1point3acres.com/bbs
  12.     for (int i = 1 ; i <= 999; i++) {
  13.         int sum = getSum(i);
  14.         parts[sum].push_back(i);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  15.     }
  16.     . 1point3acres.com/bbs
  17.     // 遍历Hash表
  18.     for (auto entry : parts) {.1point3acres缃
  19.         vector<int>& elements = entry.second;
  20.         // 得到Entry中一对元素的全排列
  21.         for (int i = 0; i < elements.size(); i++) {. 1point3acres.com/bbs
  22.             for (int j = 0; j < elements.size(); j++) {
  23.                 int num = elements[i] * 1000 + elements[j];
  24.                
  25.                 // 去除0开头的数字
  26.                 if (num >= 100000) {
  27.                     result.push_back(num);
  28.                 }
  29.             }
  30.         }
  31.     }
  32.    
  33.     return result;
  34. }
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| flex 发表于 2016-8-14 22:29:23 | 显示全部楼层
何打发123 发表于 2016-8-14 09:31
大神 没太看懂 能仔细说说嘛?

思路是这样的:
遍历一遍100到999的数字,对每个数字分别求三位数的和,比如100的和就是1,101的和是2,999的和是27,将这些结果放入一个表里面:
1:100
2:101,110
3:111
...
26: 998, 989, 899
27: 999
然后遍历表的每一行,对每一行中的每一个元素进行组合,比如行26,就会有这样的组合998-989, 998-899, 989-899,把结果都放到一个vector里面最后return。
回复 支持 1 反对 0

使用道具 举报

xihaokai1 发表于 2016-8-4 00:24:12 | 显示全部楼层
compute a[1...27] such that a is the list of numbers 100-999 whose digit sum equals i; concatenate every number whose first digit is nonzero in a with every number in a.

补充内容 (2016-8-4 00:24):
*numbers 001-999
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (2016-8-4 00:27):
a 怎么显示不出来

补充内容 (2016-8-4 00:27):
a [ i ]
回复 支持 反对

使用道具 举报

 楼主| flex 发表于 2016-8-4 00:24:34 | 显示全部楼层
不知道为啥帖子都是斜体字,地里新手弱弱地问一句,帖子还能编辑吗?
回复 支持 反对

使用道具 举报

z165153 发表于 2016-8-4 00:32:40 | 显示全部楼层
lz你好。

请问他们家,电面时候,在哪里写程序呀。-google 1point3acres
是打开一个网页写吗?

谢谢。祝offer
回复 支持 反对

使用道具 举报

 楼主| flex 发表于 2016-8-4 00:41:29 | 显示全部楼层
xihaokai1 发表于 2016-8-4 00:24
compute a[1...27] such that a is the list of numbers 100-999 whose digit sum equals i; concatenate e ...

嗯,是个方法~,这样的话还是要存一个unrodered_map<int, vector<int>>的数组呢,hashmap key是1-27,然后最后要对每个entry中的vector<int>做一次n^2的组合。复杂度应该你这个方法好,我那个是(999999 - 100000) * 6
回复 支持 反对

使用道具 举报

 楼主| flex 发表于 2016-8-4 00:43:27 | 显示全部楼层
z165153 发表于 2016-8-4 00:32
lz你好。

请问他们家,电面时候,在哪里写程序呀。
. 鍥磋鎴戜滑@1point 3 acres
是啊,面试前猎头会发给你一个link,在hackerank上写的。还看面试官,据说有的当场还要给test case run,必须能编译通过。
回复 支持 反对

使用道具 举报

z165153 发表于 2016-8-4 01:12:37 | 显示全部楼层
flex 发表于 2016-8-4 00:43
是啊,面试前猎头会发给你一个link,在hackerank上写的。还看面试官,据说有的当场还要给test case run, ...

好多家都用hackerank呀。谢谢。
回复 支持 反对

使用道具 举报

 楼主| flex 发表于 2016-8-4 02:15:11 | 显示全部楼层
z165153 发表于 2016-8-4 01:12. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
好多家都用hackerank呀。谢谢。

嗯,以前用Collabedit,Hackerrank因为可以在线编译,现在确实好多家用呢!也祝你Offer!
回复 支持 反对

使用道具 举报

期末求过 发表于 2016-8-6 12:31:21 | 显示全部楼层
让stack爆掉的话,一直递归可以么?
回复 支持 反对

使用道具 举报

 楼主| flex 发表于 2016-8-6 22:44:43 | 显示全部楼层
期末求过 发表于 2016-8-6 12:31
让stack爆掉的话,一直递归可以么?

有道理啊!确实是个是个方法!
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-8-14 09:31:05 | 显示全部楼层
xihaokai1 发表于 2016-8-4 00:24
compute a[1...27] such that a is the list of numbers 100-999 whose digit sum equals i; concatenate e ...

大神 没太看懂 能仔细说说嘛?
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-8-14 23:39:21 | 显示全部楼层
flex 发表于 2016-8-14 22:29
思路是这样的:
遍历一遍100到999的数字,对每个数字分别求三位数的和,比如100的和就是1,101的和是2, ...

机智!!  如果有n位的话 9^n 个数字分类 然后再对前面的9^n配对 这里是o(1)? 然后整体复杂度就是9^n 这样分析对吗~
回复 支持 反对

使用道具 举报

 楼主| flex 发表于 2016-8-14 23:54:34 | 显示全部楼层
何打发123 发表于 2016-8-14 23:39
机智!!  如果有n位的话 9^n 个数字分类 然后再对前面的9^n配对 这里是o(1)? 然后整体复杂 ...

如果题目是n位的话,要求前n/2个数字和与后n/2个数字和相等,那么遍历一半的复杂度就是n/2 * 10^(n/2),然后总共有n/2 * 10个entry,假设每个entry最多会有m个元素(理论上m会很小),则整体复杂度为O(n / 2 * 10^(n/2) * n/2 * 10 * m ^2),当n = 6的case:3*1000*30*m^2,小于暴力解法 (999999-100000) * 6
这道题有一个tricky的地方就是组合的时候,前半部的数字不能以0开头。
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-8-15 00:36:18 | 显示全部楼层
写了一个 求斧正~~~

  1. //把1 ~999分成27组
  2.         public void print3(){
  3.                 HashMap<Integer, ArrayList<String>> map = new HashMap<Integer, ArrayList<String>>();
  4.                 for(int i = 1; i <= 999; i++){
  5.                         int sum = getSum(i);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  6.                         ArrayList<String> arr = map.get(sum);
  7.                         if(arr == null){
  8.                                 arr = new ArrayList<String>();
  9.                                 map.put(sum, arr);
  10.                         }
  11.                        
  12.                         String cur = i + "";
  13.                         //统一往前加0 否则前后都加有重复
  14.                         while(cur.length() < 3){
  15.                                 cur = '0' + cur;
  16.                         }
  17.                         arr.add(cur);
  18.                 }
  19.                
  20.                 int m = 0;
  21.                 for(int i = 100; i <= 999; i++){
  22.                         int sum = getSum(i);
  23.                         ArrayList<String> list = map.get(sum);
  24.                         for(String str : list){
  25.                                 String temp = i + str;
  26.                                 m++;
  27.                                 System.out.println(m + "  " + temp);
  28.                                
  29.                         }
  30.                 }
  31.         }

  32. private int getSum(int k){. From 1point 3acres bbs
  33.                 int sum = 0;
  34.                 while(k > 0){
  35.                         sum = sum + k%10;
  36.                         k = k/10;
  37.                 }
  38.                 return sum;
  39.         }
复制代码
回复 支持 反对

使用道具 举报

cicean 发表于 2016-9-13 03:03:47 | 显示全部楼层
flex 发表于 2016-8-14 22:29.1point3acres缃
思路是这样的:
遍历一遍100到999的数字,对每个数字分别求三位数的和,比如100的和就是1,101的和是2, ...

感觉是不是可以bucket select 啊?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷List<Integer>[]

这题好难啊。。。怎么这么难,45分钟写一道就差不多了。
回复 支持 反对

使用道具 举报

cicean 发表于 2016-9-13 03:58:19 | 显示全部楼层
flex 发表于 2016-8-14 22:29
思路是这样的:
遍历一遍100到999的数字,对每个数字分别求三位数的和,比如100的和就是1,101的和是2, ...

100010 这个种情况怎么办呢?
回复 支持 反对

使用道具 举报

 楼主| flex 发表于 2016-9-13 15:27:37 | 显示全部楼层
cicean 发表于 2016-9-13 03:58
100010 这个种情况怎么办呢?

恩,不好意思之前有笔误,应该遍历1到999的数字,具体实现请看我之前贴的程序。
没有想到这个最优解不用担心,我当时就是暴力解,也闯到Onsite拿到Offer了。毕竟电话面试还有其他的题目,这道题的最优解算是Bonus吧。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 21:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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