一亩三分地论坛

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

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

一个bb悲惨两轮游

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

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

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

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

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


第一轮:
印度小哥+白人小哥,都工作一年半,他俩似乎是同期生关系都还不错,人都很好。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
behavioral:. Waral 鍗氬鏈夋洿澶氭枃绔,
1. 介绍你自己. 1point 3acres 璁哄潧
2. 最有挑战性的项目

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


被虐惨的第二轮:
工作5年第一次面fresh grad的国人大哥+40年工龄的白人老妖精,老妖精说他最近已经做了类似律师的职位,我猜是专利之类的吧。
. more info on 1point3acres.com
behavioral:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
1. 介绍你自己
2. 为何转向financial area找工. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
——以上两题是国人大哥问的,很正常的behavioral,国人大哥谢谢你. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
3. 你吃午饭了么……
4. 你喜欢啥颜色,为什么……
5. 你当TA觉得有意思吧?喜欢TA哪几点?
——工作40年的人的关注点果然和我们不一样了………………

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."。这一波终于过去了。
. from: 1point3acres.com/bbs
刚写上node里面的left pointer,老妖精又问我为什么要用pointer。。。。
随后又对pointer和reference的区别和特点做了深入交谈。。。。
定义结束,我说我给指针默认设置成null吧。落笔,老妖精又和我就默认值和constructor展开了交谈。。。

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


最终45分钟写一道题,老妖精说没时间了,他不出题了,我问问题。。。

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

感觉老头是超叼的人,但是可能工作久了对fresh grad的期望过高了吧

评分

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
哈哈哈,你这个头像最近发帖蛮频繁的

因为闲下来了,课不多题也刷两遍半了,弄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-google 1point3acres
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不能看作是常数啊。-google 1point3acres

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:. visit 1point3acres.com for more.
  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) {
  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.       }. more info on 1point3acres.com
  13.     }. 1point3acres.com/bbs
  14.     vector<string> res;-google 1point3acres
  15.     while (!top10.empty()) {
  16.       res.push_back(top10.top().first); top10.pop();. Waral 鍗氬鏈夋洿澶氭枃绔,
  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).
  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.   vector<string> getTop10Percent() {
  11.     int n = _prices.size() / 10;
  12.     vector<string> res;
  13.     for (auto& x : _prices) {
  14.       if (res.size() == n) break;-google 1point3acres
  15.       res.push_back(x.first);
  16.     }
  17.     return res;
  18.   }
  19. };
复制代码


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;. from: 1point3acres.com/bbs
  4.   }
  5. };
复制代码
回复 支持 反对

使用道具 举报

sevenwonder 发表于 2016-12-25 08:11:20 | 显示全部楼层
zzgzzm 发表于 2016-10-15 06:07
top 10% stock 这个问题应该是设计一个类,实现setPrice(string id, double p) and getTop10Percent()两个 ...

it should be n = float(_prices.size()) / 0.1? , 第一个方法set 不是实时的吧?第二方法,gettopto10应该是O(n)吧,还有你加了compare function 在里面,这个sort时间复杂度已经是O(NlogN)了吧,所以set 和gettop只少是 O(NlogN)吧,因为你这两个方法是建立在sort的基础上的。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-12-25 12:22:50 | 显示全部楼层
sevenwonder 发表于 2016-12-25 08:11
it should be n = float(_prices.size()) / 0.1? , 第一个方法set 不是实时的吧?第二方法,gettopto10应 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
两个方法中的set和getTop10percent都是让用户随时调用的API, timing 都是用户自己决定的,返回的结果就是反映当前的状态。
方法1: n就是指当前top 10%股票的个数,所以/10.
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-12-25 12:32:00 | 显示全部楼层
sevenwonder 发表于 2016-12-25 08:11
it should be n = float(_prices.size()) / 0.1? , 第一个方法set 不是实时的吧?第二方法,gettopto10应 ...

方法1的set price 每次调用时并不排序,只有get 时才排,所以只有get花时间。
方法2实时用std::set来存价格,std::set是永远排序的,所以erase/insert 一次的时间都是logN。但换来的好处就是get 时无需再排序了。
其实方法2对于1比较就是把set price的一部分complexity 转移到get了。哪个performance 好得看用户调用set/get哪个更频繁。
回复 支持 反对

使用道具 举报

sevenwonder 发表于 2016-12-26 00:18:02 | 显示全部楼层
zzgzzm 发表于 2016-12-25 12:22. from: 1point3acres.com/bbs
两个方法中的set和getTop10percent都是让用户随时调用的API, timing 都是用户自己决定的,返回的结果就是 ...

不好意思看错了确实是/10
回复 支持 反对

使用道具 举报

sevenwonder 发表于 2016-12-26 00:25:44 | 显示全部楼层
zzgzzm 发表于 2016-12-25 12:32
方法1的set price 每次调用时并不排序,只有get 时才排,所以只有get花时间。
方法2实时用std::set来存价 ...

我是想说,因为是实时的,set里面每次加进东西不是会排个序么,难道这个不耗时么?我知道emplace是logN,但是你加入这个pair后,set自动排序还是要耗时的吧,这个是O(NlogN)吧。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-12-26 13:21:11 | 显示全部楼层
sevenwonder 发表于 2016-12-26 00:25
我是想说,因为是实时的,set里面每次加进东西不是会排个序么,难道这个不耗时么?我知道emplace是logN, ...

Set::insert 只需要将新元素加入已排序的N个元素中,并不是将所有元素重新排序(相当于binary search)。复杂度可以搜索cpluplus.com 关于set::insert的条目。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-17 23:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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