📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: GreenIceTea
跳转到指定楼层
上一主题 下一主题
收起左侧

Bloomberg 1.17 new grad onsite

🔗
primbo 2017-1-23 05:09:37 | 只看该作者
全局:
ffcc 发表于 2017-1-23 04:52
楼主,想问一下manger的那道设计题,是要把N个数组进行排序?

我感觉就是divide and conquer的思想。一部分放进去排序,排好了以后,再放另一部分进去。
回复

使用道具 举报

🔗
qwert1234567 2017-1-23 06:04:48 | 只看该作者
全局:
primbo 发表于 2017-1-23 05:09
我感觉就是divide and conquer的思想。一部分放进去排序,排好了以后,再放另一部分进去。

N个数组,每个数组代表一个数?
回复

使用道具 举报

🔗
xiaojunji 2017-1-23 07:23:26 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
anna1 2017-1-24 02:18:59 | 只看该作者
全局:
ffcc 发表于 2017-1-23 04:43
你好,请问你是在职跳槽么?

失业找工作。
回复

使用道具 举报

🔗
primbo 2017-1-24 04:33:59 | 只看该作者
全局:
xiaojunji 发表于 2017-1-23 07:23
楼主能仔细讲讲这道题吗?题目都没看懂
给K个绳子, 每个绳子有两个端点, 先在给一个rand(X), X是任意的,  ...

这题就是经典的 union find. 就像number of island 2那样。
  1. //connect rope. 给K个绳子, 每个绳子有两个端点, 先在给一个rand(X), X是任意的, 每次可以随机从2K个端点中取一个, 相邻两次去的端点练成可以相接, 不能重复取端点, 问最后这些绳子可以有多少个环. 这个题的意义就是, 有了我的设计方法, 可以重复N多次, 然后算出平均的有多少个环. 这个题说起来有些复杂, 因为具体模拟都是自己设计, 最后楼主提出了union-find的解法, 小哥表示满意, 说这个算是解法之一, 没让code.
  2. int rand(int x) {
  3.     return rand()%x;
  4. }
  5. int findRoot(vector<int> &roots, int id) {
  6.     while(roots[id] != id) {
  7.         //route compression
  8.         roots[id] = roots[roots[id]];
  9.         id = roots[id];
  10.     }
  11.     return id;
  12. }
  13. void unite(vector<int> &roots, vector<int> &sz, int root1, int root2) {
  14.     if(sz[root1] >= sz[root2]) {
  15.         roots[root2] = root1;
  16.         sz[root1] += sz[root2];
  17.     }else {
  18.         roots[root1] = root2;
  19.         sz[root2] += sz[root1];
  20.     }
  21. }
  22. int ropeConnection(int k, vector<pair<int,int>> connections) {
  23.     vector<int> roots(2*k, -1);
  24.     vector<int> sz(2*k, 1);
  25.     //each end of rope could only be connected once
  26.     vector<bool> connected(2*k, false);
  27.     int res = 0;
  28.     //we suppose 0--1, 2--3, 4--5 ... are the original rope
  29.     for(int i = 0; i < 2*k; i += 2) {
  30.         roots[i] = i;
  31.     }
  32.     for(int i = 1; i < 2*k; i+= 2) {
  33.         roots[i] = i-1;
  34.         sz[i-1]++;
  35.     }
  36.     for(int i = 0; i < connections.size(); i++) {
  37.         int fir = connections[i].first;
  38.         int sec = connections[i].second;
  39.         //these two node should not be connected
  40.         if(!connected[fir] && !connected[sec]) {
  41.             connected[fir] = true;
  42.             connected[sec] = true;
  43.             int root1 = findRoot(roots, fir);
  44.             int root2 = findRoot(roots, sec);
  45.             //if root is not the same, just connect them
  46.             if(root1 != root2) {
  47.                 unite(roots, sz, root1, root2);
  48.             }else {
  49.             //this means these two point is in the same side, and if connected form a circle
  50.                 res++;
  51.             }
  52.         }
  53.     }
  54.     return res;
  55. }
复制代码
回复

使用道具 举报

🔗
春山寒 2017-1-24 04:46:45 | 只看该作者
全局:
big cong 楼主 我也收到了bb的offer discoveryday 倒是觉得他们有的技术还是非常牛的 不知道楼主觉得bb技术老是不是每个组都这样
回复

使用道具 举报

🔗
LeoJY 2017-1-24 07:29:55 | 只看该作者
全局:
lz问一下,你面试的时候是在纸上写的代码吗? 还有就是除了写代码的那张纸之外有提供草稿纸/白板用来可以写思路打草稿之类的么?
回复

使用道具 举报

🔗
primbo 2017-1-24 08:12:02 | 只看该作者
全局:
LeoJY 发表于 2017-1-24 07:29
lz问一下,你面试的时候是在纸上写的代码吗? 还有就是除了写代码的那张纸之外有提供草稿纸/白板用来可以写 ...

应该是有好多张纸吧。
回复

使用道具 举报

🔗
LeoJY 2017-1-24 08:17:27 | 只看该作者
全局:
primbo 发表于 2017-1-23 19:12
应该是有好多张纸吧。

哦哦哦,谢谢~
回复

使用道具 举报

🔗
 楼主| GreenIceTea 2017-1-24 13:44:30 | 只看该作者
全局:
春山寒 发表于 2017-1-24 04:46
big cong 楼主 我也收到了bb的offer discoveryday 倒是觉得他们有的技术还是非常牛的 不知道楼主觉得bb技术 ...

这个我具体其实也不好说, 不过ddl挺久的, 所以可以再好好研究一下~
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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