一亩三分地论坛

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

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

BB Onsite

[复制链接] |试试Instant~ |关注本帖
alucardzhou 发表于 2016-9-21 22:53:51 | 显示全部楼层 |阅读模式

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

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

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

x
本来以为两轮游的节奏,结果早上面完后突然被告知,“没有午饭时间,要面另一个组。”
昨天回家已经有点意识模糊了。所以一觉睡到大天亮。.1point3acres缃
有些题目是没头没尾的,直接讨论。就不拿出来说了。就说记得清楚的题。

1.在二维矩阵中完成类似“画板的填色”的功能。矩阵里每个值都代表一个颜色。给你一个坐标,和一个新的颜色。让你把所给坐标中相邻的所有同色改成新颜色。比一个圆形中间全是白的,那么如果坐标在圆形中任意一点的话,圆形内部将全成新的颜色。
2.验证二叉搜索树
3.设计一个系统,系统不断接受股票名和股票价格的Entry。请追踪价格浮动最大的十个股票。价格浮动的意思是,最新价和上一个价格之间,相差值和上一个价格的比例。追加问题要求多保留当日最大值和最小值。
4.给你四个随机个位数字,要求用他们组成两个数字,使其和最接近一百.

1.复制有随机指针的单链. more info on 1point3acres.com
2.一个很奇怪的排序题,给了很多股票,和其最新价格(取代旧价格)。要求先按股票的时间顺序,再按股票的价格顺序排列。
3.输入一堆(序列)管理关系,比如A员工老板是B,B员工老板是C。然后设计储存方式,并写一个方法返回所给员工的所有直接或者间接的老板。. 鍥磋鎴戜滑@1point 3 acres
4.又做了一遍验证二叉树搜索树
5.给了一段喜佳佳代码,产生了四个进程,每个进程都会在一定时间后把一个相应的数字加同到一个静态变量中。由于时间问题,最后这个变量中的值每次打印出来都不一样。但都是由那四个值组成。

遇见了地里描述过的几个考官。感觉很亲切。
然后所有的考官都是一开始严肃一下,后来聊开了都嬉皮笑脸了。
总的来说比几年前第一次面BB感觉好太多了。.鏈枃鍘熷垱鑷1point3acres璁哄潧

穿插地问了很多各种各样的知识点。
求offer。



补充内容 (2016-9-23 16:31):
被拒。 Move on。

评分

1

查看全部评分

zzgzzm 发表于 2016-10-11 03:34:32 | 显示全部楼层
My thoughts on "给你四个随机个位数字,要求用他们组成两个数字,使其和最接近一百."
This problem is actually reduced to the problem of "Two Sum to closest to given target".
Let a, b, c, d be the four given number with each in between 0 and 9. The goal is to minimize E := |10a'+b'+10c'+d'-100|, where a', b', c', d' is a permutation of a, b, c, d. Further calculation shows that 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
E = |9(a'+b')-(100-sum)|, where sum := a'+b'+c'+d' = a+b+c+d which is a constant if the four numbers are given(!!!). So the question is to ask picking any two numbers, i.e., a' and b' from the given four numbers, such that E is minimized. And clearly this is the Two Sum to closest to a fixed target (100-sum).
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Furthermore, I guess this problem can be extended to given 2k single digit numbers and pair them into k of double-digit numbers to sum to to closest to a given target.  . Waral 鍗氬鏈夋洿澶氭枃绔,
. more info on 1point3acres.com
补充内容 (2016-10-11 03:38):
I think the technique for this kind of problems is to try to reformulate the problem into as many constant parameters as possible by eliminating symmetry and permutations.

补充内容 (2016-10-11 03:46):. Waral 鍗氬鏈夋洿澶氭枃绔,
For example, for given 3, 6, 7, 9, the sum = 25, so we want to minimize E:= |9(a+b)-(100-25)|. The target for a+b to match is round(75/9)=8. Best candidate is {a, b}={3, 6}, so we group into {37, 69}.
回复 支持 1 反对 0

使用道具 举报

iPhD 发表于 2016-9-21 23:04:25 | 显示全部楼层
new grad会被问系统设计吗?
回复 支持 反对

使用道具 举报

 楼主| alucardzhou 发表于 2016-9-21 23:06:59 | 显示全部楼层
iPhD 发表于 2016-9-21 10:04
new grad会被问系统设计吗?


我不敢不确定啊。
不过两年前我是New Grad的时候面他们家的时候确实只面了技术题。
回复 支持 反对

使用道具 举报

 楼主| alucardzhou 发表于 2016-9-22 00:35:23 | 显示全部楼层
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

谢谢
回复 支持 反对

使用道具 举报

cicean 发表于 2016-10-7 07:45:52 | 显示全部楼层
为什么,感觉楼主面的不错啊。这拒的也太莫名其妙了。真是random 里的看脸么?
回复 支持 反对

使用道具 举报

 楼主| alucardzhou 发表于 2016-10-7 21:01:03 | 显示全部楼层
cicean 发表于 2016-10-6 18:45
为什么,感觉楼主面的不错啊。这拒的也太莫名其妙了。真是random 里的看脸么?

其实第一轮第四题没做好。而且那一轮是manager,并且主要问的是系统设计。
第二组强调CPP太多了,再加上有个考官交流不通。. visit 1point3acres.com for more.
回复 支持 反对

使用道具 举报

Neil_Acton 发表于 2016-10-7 21:17:54 | 显示全部楼层
多谢楼主分享
5.给了一段喜佳佳代码,产生了四个进程,每个进程都会在一定时间后把一个相应的数字加同到一个静态变量中。由于时间问题,最后这个变量中的值每次打印出来都不一样。但都是由那四个值组成。
这个题目问题是什么?

3.设计一个系统,系统不断接受股票名和股票价格的Entry。请追踪价格浮动最大的十个股票。价格浮动的意思是,最新价和上一个价格之间,相差值和上一个价格的比例。追加问题要求多保留当日最大值和最小值。. more info on 1point3acres.com
这就是一个类设计题把?
回复 支持 反对

使用道具 举报

 楼主| alucardzhou 发表于 2016-10-7 23:55:38 | 显示全部楼层
Neil_Acton 发表于 2016-10-7 08:17.鐣欏璁哄潧-涓浜-涓夊垎鍦
多谢楼主分享
5.给了一段喜佳佳代码,产生了四个进程,每个进程都会在一定时间后把一个相应的数字加同到一 ...

5. 要你看代码,写输出。而输出其实是随机的。要把所有可能的值都写出来。
3. 没错是个数据结构设计题。
回复 支持 反对

使用道具 举报

cicean 发表于 2016-10-8 03:20:01 | 显示全部楼层
alucardzhou 发表于 2016-10-7 23:55
5. 要你看代码,写输出。而输出其实是随机的。要把所有可能的值都写出来。
3. 没错是个数据结构设计题。
-google 1point3acres
楼主paipai, 我觉得考得挺难得。而且除了 valid BST 其他题都不太容易 上来就bug free
尤其是第一轮第四题,是用 dfs 找全解,global 存最接近100 的解么? 如果当前两数加起来 与 100 差 abs 跟小 就更新,如果刚好是一百 就结束了,要是多解情况咋办?
还有设计题,最大值和最小值,是不是用 两个 变量存一下就好了, 浮动最大的 10 是不是可以用 Heap  
回复 支持 反对

使用道具 举报

 楼主| alucardzhou 发表于 2016-10-8 06:03:11 | 显示全部楼层
cicean 发表于 2016-10-7 14:20
楼主paipai, 我觉得考得挺难得。而且除了 valid BST 其他题都不太容易 上来就bug free
.鏈枃鍘熷垱鑷1point3acres璁哄潧尤其是第一轮第 ...

当天的正经系统设计我没写清楚。后来就一心忙别的准备去了。
我上午的第三轮面的是组里的大头(出四个随机数字那位),一位超干练的阿姨。
她上来先告诉我面试安排有变,聊了一会开始讨论多层服务器的设计。
最上层是需求层,需求开始一个任务后,向下面一层服务器发请求,每个服务器层会选出一个特定的服务器处理这个任务,并且接着向更下一层发出请求。层层递进,直到落到最底层的数据库。
设计的目标点是,在整个过程中,如果那一层的特定服务器坏了。数据调不出来了,怎么找那个坏掉的服务器。
我先说了通过完整的log系统查找,然后说实时heart beat反馈(每层都监控),最后提到每次往下递新要求时,也往需求层发一个回馈(类似针对特定任务的heart beat)。这就聊了二三十分钟了。然后阿姨觉得聊的还行,就随便丢了个题(四个数字算100最近)出来让我做,自己写评定。也许她觉得这题很简单,我没处理好让她觉得意外。后来她把题目又简化了一下让我说了些想法就结束了。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-10 06:04:32 | 显示全部楼层
"3.输入一堆(序列)管理关系,比如A员工老板是B,B员工老板是C。然后设计储存方式,并写一个方法返回所给员工的所有直接或者间接的老板". 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这道题看起来就是用一个hash map吗?. Waral 鍗氬鏈夋洿澶氭枃绔,
  1. class Organization {
  2.   private:   
  3.   unordered_map<string, string> manager;
  4.   
  5.   public:
  6.   void setManager(string employee, string mgr) {
  7.       manager[employee] = mgr;
  8.   } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  9.   
  10.   vector<string> getManagers(string employee) {
  11.     vector<string> res;
  12.     while (manager.count(employee)) {
  13.       string mgr = manager[employee];.1point3acres缃
  14.       res.push_back(mgr);
  15.       if (mgr == employee) break;
  16.       else employee = mgr;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  17.     }
  18.     return res;
  19.   }
  20. }
复制代码
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-10 11:20:15 | 显示全部楼层
"1.在二维矩阵中完成类似“画板的填色”的功能。矩阵里每个值都代表一个颜色。给你一个坐标,和一个新的颜色。让你把所给坐标中相邻的所有同色改成新颜色。比一个圆形中间全是白的,那么如果坐标在圆形中任意一点的话,圆形内部将全成新的颜色。"
If using int as color index, DFS, I think
  1. void updateConnectedRegion(vector<vector<int>>& grid, int i, int j, int color) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  2.   int m = grid.size(); if (m == 0) return;
  3.   int n = grid[0].size(); if (n == 0) return;
  4.   if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == color) return;
  5.   grid[i][j] = color;. from: 1point3acres.com/bbs
  6.   updateConnectedRegion(grid, i-1, j, color);
  7.   updateConnectedRegion(grid, i+1, j, color);.1point3acres缃
  8.   updateConnectedRegion(grid, i, j-1, color);. 1point 3acres 璁哄潧
  9.   updateConnectedRegion(grid, i, j+1, color);
  10. }
复制代码
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-10 12:46:41 | 显示全部楼层
"3.设计一个系统,系统不断接受股票名和股票价格的Entry。请追踪价格浮动最大的十个股票。价格浮动的意思是,最新价和上一个价格之间,相差值和上一个价格的比例。追加问题要求多保留当日最大值和最小值。". 1point3acres.com/bbs
I am thinking to use hash map to store the current/min/max prices for each stock. And use a set to store the <stock id, change rate> pair sorted by change rate. Since whenever a new price comes in for a stock, the new change rate could decrease, so just keeping a size = K of heap for top K changing stock doesn't work. So I have to keep the sorted change rate for all stocks. Any better idea?
  1. class Server {
  2.   private:
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  3.   unsigned int _numTrack;. more info on 1point3acres.com
  4.   // _prices index: 0 current, 1 min, 2 max. visit 1point3acres.com for more.
  5.   unordered_map<string, vector<double>> _prices;
    . 1point3acres.com/bbs
  6.   unordered_map<string, double> _changes; // current change. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  7.   set<pair<string, double>, Comp> _topChange; // sorted change
  8.   
  9.   public:
  10.   Server(int numTrack):_numTrack(numTrack) {}  
  11.   double getMaxPrice(string id) { return _prices.count(id)? _prices[id][2] : -1.0; }. 鍥磋鎴戜滑@1point 3 acres
  12.   double getMinPrice(string id) { return _prices.count(id)? _prices[id][1] : -1.0; }
  13.   
  14.   // get stock id of top _numTrack changes.1point3acres缃
  15.   vector<string> getTopChange() {
  16.     vector<string> res;
  17.     for (auto& x:_topChange) { res.push_back(x.first); if (res.size() == _numTrack) break; }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  18.     return res;
  19.   }
  20.   
  21.   void setPrice(string id, double price) {
  22.     if (price <= 0.0) { cout << "invalid price\n"; return; }
  23.     double change = _prices.count(id)? abs(price-_prices[id][0])/_prices[id][0] : 0.0;
  24.     if (_prices.count(id)) {
  25.         _prices[id] = {price, min(_prices[id][1], price), max(_prices[id][2], price)};
  26.         _topChange.erase(make_pair(id, _changes[id]));
  27.     }
  28.     else _prices[id] = vector<double>(3, price);  
  29.     _changes[id] = change;
  30.     _topChange.emplace(id, change);
  31.   }
  32. };
复制代码
回复 支持 反对

使用道具 举报

Neil_Acton 发表于 2016-10-11 00:52:52 | 显示全部楼层
谁有好方法

给你四个随机个位数字,要求用他们组成两个数字,使其和最接近一百.

这个题感觉类似 brainstorm 是一道取巧的题。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-11 10:12:43 | 显示全部楼层
cicean 发表于 2016-10-8 03:20. 1point3acres.com/bbs
楼主paipai, 我觉得考得挺难得。而且除了 valid BST 其他题都不太容易 上来就bug free. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
尤其是第一轮第 ...

第一轮第四题(4个随机各位数字):其实可以转化为给定4个数字,求最接近round((100 - sum)/9)的TwoSum问题.
Given a0, a1, a2, a3 (0 <= ai <= 9), let target :=round((100-sum)/9), where sum:=a0+a1+a2+a3, find all pairs (ai, aj) such that ai+aj is closest to target. Then ai and aj will be the 10th digits for the two 2-digit numbers.
回复 支持 反对

使用道具 举报

ffcc 发表于 2016-12-1 09:54:59 | 显示全部楼层
你好,想问下你是通过猎头获得面试的么?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 15:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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