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


一亩三分地论坛

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

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

一个bb悲惨两轮游

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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

. 1point 3acres 璁哄潧. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第一轮: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
印度小哥+白人小哥,都工作一年半,他俩似乎是同期生关系都还不错,人都很好。

behavioral: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1. 介绍你自己
2. 最有挑战性的项目

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


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

behavioral: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1. 介绍你自己-google 1point3acres
2. 为何转向financial area找工
——以上两题是国人大哥问的,很正常的behavioral,国人大哥谢谢你
3. 你吃午饭了么……. 1point 3acres 璁哄潧
4. 你喜欢啥颜色,为什么…….鏈枃鍘熷垱鑷1point3acres璁哄潧
5. 你当TA觉得有意思吧?喜欢TA哪几点?. 1point 3acres 璁哄潧
——工作40年的人的关注点果然和我们不一样了………………

technical:
国人打个先出题,因为老妖精一直在打岔问我C++问题,所以这一轮只做了这一道,不知道这一点是不是成为了两轮游的主因。
变形BST Search:有指向parent的指针,入口节点可以是树的任何一个节点
说思路:通过和parent node value的比对,决定在此点开始普通BST search还是移到parent node再进行比对。.鏈枃鍘熷垱鑷1point3acres璁哄潧
国人大哥和老妖精均表示可以,然后开写。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
然后噩梦就开始了。
刚想定义TreeNode,写下struct之后老妖精立即打断我:为什么不用class。然后就struct和class的异同点展开了深入的交谈。-google 1point3acres
交谈了10多分钟,只记得最后扯到virtual function的实现。我说什么提到了function pointer,然后老妖精说"Yes, that's virtual table."。这一波终于过去了。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
刚写上node里面的left pointer,老妖精又问我为什么要用pointer。。。。
随后又对pointer和reference的区别和特点做了深入交谈。。。。
定义结束,我说我给指针默认设置成null吧。落笔,老妖精又和我就默认值和constructor展开了交谈。。。

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


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

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

感觉老头是超叼的人,但是可能工作久了对fresh grad的期望过高了吧. 鍥磋鎴戜滑@1point 3 acres
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

2

查看全部评分

本帖被以下淘专辑推荐:

fyh8238865 发表于 2016-4-7 03:22:04 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
patpatpat,加油咯
回复 支持 反对

使用道具 举报

 楼主| krrk 发表于 2016-4-7 03:23:49 | 显示全部楼层
关注一亩三分地微博:
Warald

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 终于对上你的论坛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.鏈枃鍘熷垱鑷1point3acres璁哄潧
然后以这个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. Waral 鍗氬鏈夋洿澶氭枃绔,
top 10% stock 这个问题 可以这么解:
suppose there is a totoal number of X stocks. more info on 1point3acres.com
先找到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:
    .1point3acres缃
  4.   void setPrice(string id, double p) { _prices[id] = p; }
  5. . Waral 鍗氬鏈夋洿澶氭枃绔,
  6.   vector<string> getTop10Percent() {
  7.     int n = _prices.size() / 10;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  8.     priority_queue<pair<string, double>, vector<pair<string, double>>, Comp > top10;
  9.     for (auto& x : _prices) {
  10.       if (top10.size() < n) top10.emplace(x.first, x.second);
  11.       else if (top10.top().second < x.second) {
  12.         top10.pop(); top10.emplace(x.first, x.second);
  13.       }
  14.     }
  15.     vector<string> res;
  16.     while (!top10.empty()) {
  17.       res.push_back(top10.top().first); top10.pop();
  18.     }
  19.     return res;
  20.   }
  21. };
复制代码


. Waral 鍗氬鏈夋洿澶氭枃绔,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).. more info on 1point3acres.com
  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.   }. visit 1point3acres.com for more.

  10.   vector<string> getTop10Percent() {
  11.     int n = _prices.size() / 10;. From 1point 3acres bbs
  12.     vector<string> res;
  13.     for (auto& x : _prices) {. From 1point 3acres bbs
  14.       if (res.size() == n) break;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  15.       res.push_back(x.first);
  16.     }
  17.     return res;
  18.   }
  19. };
复制代码
. from: 1point3acres.com/bbs

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. };
复制代码
回复 支持 反对

使用道具 举报

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应 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
两个方法中的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
两个方法中的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, ...
. visit 1point3acres.com for more.
Set::insert 只需要将新元素加入已排序的N个元素中,并不是将所有元素重新排序(相当于binary search)。复杂度可以搜索cpluplus.com 关于set::insert的条目。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-24 05:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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