一亩三分地论坛

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

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

一个bb悲惨两轮游

[复制链接] |试试Instant~ |关注本帖
krrk 发表于 2016-4-5 04:10:51 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Bloomberg - 校园招聘会 - Onsite |Failfresh grad应届毕业生

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

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

x
3.23的onsite,整理好心情发一下。

. from: 1point3acres.com/bbs
第一轮:
印度小哥+白人小哥,都工作一年半,他俩似乎是同期生关系都还不错,人都很好。

behavioral:. 鍥磋鎴戜滑@1point 3 acres
1. 介绍你自己 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
2. 最有挑战性的项目. 鍥磋鎴戜滑@1point 3 acres

technical:
1. n个人围一圈,每隔k个人删掉一个人,最后剩的那个人是赢家,求赢家。
以前没仔细想过这道题,白人小哥特意提示挑一个合适的data structure,恍然大悟可以用cycled linked list做。做完小哥表示满意,算时间复杂度,经提示得到O(nk)。. visit 1point3acres.com for more.
2. 设计:股票实时更新最高10%
说了好多想法,比如heap,sort,分配不同机器处理,最终都是O(nlgn)的算法。印度小哥似乎知道还有更好的方法,一直在问我如何改进。最终时间到了就没有继续,小哥表示满意。从第二轮来两个面试官来看,应该这结果还算说得过去。


被虐惨的第二轮:. From 1point 3acres bbs
工作5年第一次面fresh grad的国人大哥+40年工龄的白人老妖精,老妖精说他最近已经做了类似律师的职位,我猜是专利之类的吧。

behavioral:
1. 介绍你自己
2. 为何转向financial area找工
——以上两题是国人大哥问的,很正常的behavioral,国人大哥谢谢你
3. 你吃午饭了么……
4. 你喜欢啥颜色,为什么……
5. 你当TA觉得有意思吧?喜欢TA哪几点?. visit 1point3acres.com for more.
——工作40年的人的关注点果然和我们不一样了………………
. visit 1point3acres.com for more.
technical:
国人打个先出题,因为老妖精一直在打岔问我C++问题,所以这一轮只做了这一道,不知道这一点是不是成为了两轮游的主因。
变形BST Search:有指向parent的指针,入口节点可以是树的任何一个节点
说思路:通过和parent node value的比对,决定在此点开始普通BST search还是移到parent node再进行比对。
国人大哥和老妖精均表示可以,然后开写。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
.鐣欏璁哄潧-涓浜-涓夊垎鍦
然后噩梦就开始了。
刚想定义TreeNode,写下struct之后老妖精立即打断我:为什么不用class。然后就struct和class的异同点展开了深入的交谈。
交谈了10多分钟,只记得最后扯到virtual function的实现。我说什么提到了function pointer,然后老妖精说"Yes, that's virtual table."。这一波终于过去了。

刚写上node里面的left pointer,老妖精又问我为什么要用pointer。。。。
随后又对pointer和reference的区别和特点做了深入交谈。。。。
定义结束,我说我给指针默认设置成null吧。落笔,老妖精又和我就默认值和constructor展开了交谈。。。

至此,我写完一个node定义已经花了接近半小时。。。。
这可是国人大哥出的题,老妖精如此频繁插话他也不太满意了,后面老妖精也就没怎么打岔。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
和老妖精交谈的过程中,国人大哥还是帮我说的很多好话的,还有适当的表现出不满才能让老妖怪有所收敛吧,国人大哥再次谢谢你。

. 1point 3acres 璁哄潧
最终45分钟写一道题,老妖精说没时间了,他不出题了,我问问题。。。

临走前他说不是他们做决定,他们也不知道接下来是谁来接我,还跟我good luck。。。。
你good luck根本就是不管我拍拍屁股走人,我两轮游的节奏啊。。。
最后果不其然就被hr送走了……

感觉老头是超叼的人,但是可能工作久了对fresh grad的期望过高了吧. visit 1point3acres.com for more.

评分

2

查看全部评分

fyh8238865 发表于 2016-4-7 03:22:04 | 显示全部楼层
patpatpat,加油咯
回复 支持 反对

使用道具 举报

 楼主| krrk 发表于 2016-4-7 03:23:49 | 显示全部楼层

终于对上你的论坛id了
回复 支持 反对

使用道具 举报

fyh8238865 发表于 2016-4-7 03:26:15 | 显示全部楼层
krrk 发表于 2016-4-7 03:23
终于对上你的论坛id了

哈哈哈,你这个头像最近发帖蛮频繁的
回复 支持 反对

使用道具 举报

 楼主| krrk 发表于 2016-4-7 03:28:45 | 显示全部楼层
fyh8238865 发表于 2016-4-7 03:26
哈哈哈,你这个头像最近发帖蛮频繁的
.鏈枃鍘熷垱鑷1point3acres璁哄潧
因为闲下来了,课不多题也刷两遍半了,弄side project做做看
回复 支持 反对

使用道具 举报

billyli8866 发表于 2016-4-7 04:30:08 | 显示全部楼层
我和你差不多,第二轮题目非常简单,但是非出题的那个人各种问,废话太多时间,最后只做了一道题,就被请了出去。。。不知道是不是所有人都被问了这么多,或者过了面试的人都是一两句话就回答了问题,没有耽误做题的时间
回复 支持 反对

使用道具 举报

yfang0663 发表于 2016-6-10 10:25:54 | 显示全部楼层
top 10% stock 这个问题 可以这么解:
suppose there is a totoal number of X stocks
先找到the X/10-th most expensive stock. can be done in O(N) time using quick-select
然后以这个stock value做pivot  then move all element smaller to left, move all element larger to right in O(N) time
so can be done in O(N) time.
回复 支持 反对

使用道具 举报

aifer 发表于 2016-6-23 05:04:46 | 显示全部楼层
第二轮的题目实际上先走到root,然后做正常的BST search写起来代码最干净。复杂度也是O(logN)
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-15 04:21:17 | 显示全部楼层
"1. n个人围一圈,每隔k个人删掉一个人,最后剩的那个人是赢家,求赢家。"
这个就是Joseph Ring问题,如果用DP做的话可以时间O(N),空间O(1)。用k%n来计算每次删除的人的编号,无需任何数据结构,但的确用环链表更简明。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-15 05:16:47 | 显示全部楼层
yfang0663 发表于 2016-6-10 10:25
top 10% stock 这个问题 可以这么解:
suppose there is a totoal number of X stocks
先找到the X/10-t ...

请问这里的N是代表什么呢?如果也是Stock总数的话那么X=N,怎样可以O(N)时间来得到X/10-th element? 这里X不能看作是常数啊。

To make a simplified example, given array int arr[N], what is the time complexity to get top N/10 elements? I can only figure out O(N logN) algorithm using priority queue. (in general, if asking for top K element, the complexity is O(N log min(N,N-K))).
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-15 06:07:42 | 显示全部楼层
top 10% stock 这个问题应该是设计一个类,实现setPrice(string id, double p) and getTop10Percent()两个方法。 我想到2个设计,各有优缺点,tradeoff就是看是股票变化和求Top 10%哪个用的频率多。
1. use a single container Hash map store stock id -> price, then setPrice is O(1), getTop10Percent is O(N logN).
  1. class Top10Percent1 {
  2.   unordered_map<string, double> _prices;
  3. public:
  4.   void setPrice(string id, double p) { _prices[id] = p; }

  5.   vector<string> getTop10Percent() {
  6.     int n = _prices.size() / 10;
  7.     priority_queue<pair<string, double>, vector<pair<string, double>>, Comp > top10;
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  8.     for (auto& x : _prices) {. 1point 3acres 璁哄潧
  9.       if (top10.size() < n) top10.emplace(x.first, x.second);
  10.       else if (top10.top().second < x.second) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  11.         top10.pop(); top10.emplace(x.first, x.second);
  12.       }
  13.     }
  14.     vector<string> res;
  15.     while (!top10.empty()) {
  16.       res.push_back(top10.top().first); top10.pop();
  17.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  18.     return res;
  19.   }
  20. };
复制代码


2. Use two containers: use set of pair <id, price> to store stock prices sorted by prices and use hash map to store stock id -> iterator of the price set so we can fast update a stock's price. If so, setPrice is O(log N), getTop10Percent is O(N)..鏈枃鍘熷垱鑷1point3acres璁哄潧
  1. class Top10Percent2 {
  2.   set<pair<string, double>, Comp> _prices;
  3.   unordered_map<string, set<pair<string, double>>::iterator> _pos;

  4. public:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  5.   void setPrice(string id, double p) {
  6.     if (_pos.count(id)) _prices.erase(_pos[id]);
  7.     auto res = _prices.emplace(id, p);
  8.     _pos[id] = res.first;
  9.   }
  10. . from: 1point3acres.com/bbs
  11.   vector<string> getTop10Percent() {
  12.     int n = _prices.size() / 10;
  13.     vector<string> res;
  14.     for (auto& x : _prices) {
  15.       if (res.size() == n) break;
  16.       res.push_back(x.first);. 鍥磋鎴戜滑@1point 3 acres
  17.     }
  18.     return res;. Waral 鍗氬鏈夋洿澶氭枃绔,
  19.   }
  20. };
复制代码

.鏈枃鍘熷垱鑷1point3acres璁哄潧
Here the customized comparator is simply defined as:
  1. struct Comp {
  2.   bool operator()(const pair<string, double>& a, const pair<string, double>& b) {
  3.     return a.second > b.second;
  4.   } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5. };
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 11:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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