一亩三分地论坛

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

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

十分钟前的 Two Sigma OA 题目

[复制链接] |试试Instant~ |关注本帖
不要说话 发表于 2015-9-21 10:18:31 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 博士 全职@Two Sigma - 内推 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
十分钟前刚刚做完的Two Sigma OA 题目,祝各位农友找工作顺利!
走过路过,求大家多赏几个玉米吧 哈哈

一共两道题目,

题目一:Fibonacci coding, 就是给一个数,求出它的string形式的Fibonacci coding。比如4,它的Fibonacci coding就是“101”。这个wiki上说的非常清楚什么是Fibonacci coding,(也是醉了,地里说我没权限发表站外URL。。。。Google一下Fibonacci coding,wikipedia 第一个就是),就是实现一个函数 string encode(int n);. 鍥磋鎴戜滑@1point 3 acres

.鏈枃鍘熷垱鑷1point3acres璁哄潧
题目二:地里见过,给一个string字典, 对里面的任何一个string,可以删除任意一个字符,删除字符后的string要在字典里,问最长的连接路径。举个例子,给定字典{"abcd", "bcd", "bd", "defgh", "cd", "d"}, 最长路径为 4 {"acbd"->"bcd"->"cd"->"d"}.



评分

5

查看全部评分

 楼主| 不要说话 发表于 2015-9-21 10:21:19 | 显示全部楼层
wikipedia里的Fibonacci coding最末尾始终有一个1,OA里面要求不带1,所以4的code是101,不然就是1011了
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-21 13:31:29 | 显示全部楼层
不要说话 发表于 2015-9-21 10:21
wikipedia里的Fibonacci coding最末尾始终有一个1,OA里面要求不带1,所以4的code是101,不然就是1011了

楼主, 可不可以把第一题code 贴出来。
回复 支持 反对

使用道具 举报

 楼主| 不要说话 发表于 2015-9-21 22:04:25 | 显示全部楼层
hulahu 发表于 2015-9-21 13:31
楼主, 可不可以把第一题code 贴出来。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
没存code,我大概就是这么写的,照着Wikipedia上实现的,大牛们如果有更好的方法,欢迎留言
  1. string encode (int n){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  2.         if(n < 1) return "";. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3.         string res;
  4.         vector<int> digits;
  5.         int index = 1;
  6.         digits.empalce_back(1);
  7.         digits.empalce_back(2);
  8.         while(digits.back() < n){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.                 digits.emplace(digits[i], digits[i-1]);
  10.                 index++;
  11.         }
  12.         while(index >= 0){. 1point3acres.com/bbs
  13.                 if(digits[index] <= n){
  14.                         res.push_back('1');
  15.                         n -= digits[index];
  16.                 }
  17.                 else{
  18.                         res.push_back('0');
  19.                 }
  20.                 index--;. more info on 1point3acres.com
  21.         }
  22.         return res;. From 1point 3acres bbs
  23. }
复制代码

补充内容 (2015-9-21 22:05):
第一个while loop里面应该是 digits.emplace_back(digits+digits[i-1]);。。。。手抖了不好意思

评分

2

查看全部评分

回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-22 00:32:37 | 显示全部楼层
btw, 去新人报到, 有一百分哦。
回复 支持 反对

使用道具 举报

smile~~~~ 发表于 2015-9-24 01:02:29 | 显示全部楼层
请问楼主oa是三个小时的吗?
回复 支持 反对

使用道具 举报

 楼主| 不要说话 发表于 2015-9-24 01:19:44 | 显示全部楼层
smile~~~~ 发表于 2015-9-24 01:02
请问楼主oa是三个小时的吗?

是 一般用不了这么久

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

smile~~~~ 发表于 2015-9-24 01:20:53 | 显示全部楼层
不要说话 发表于 2015-9-23 12:19
是 一般用不了这么久

好的 谢谢啦!
回复 支持 反对

使用道具 举报

yiliaobailiao 发表于 2015-9-28 09:14:45 | 显示全部楼层
不要说话 发表于 2015-9-21 22:04
没存code,我大概就是这么写的,照着Wikipedia上实现的,大牛们如果有更好的方法,欢迎留言
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2 ...

是 digits.emplace_back(digits[index] + digits[index-1]); 吗?
回复 支持 反对

使用道具 举报

yiliaobailiao 发表于 2015-9-28 09:33:27 | 显示全部楼层
还有就是,如果按照Wikipedia的写法的话,最后的顺序应该是要反过来吧,在结果中,越大的F数字对应的标志位(d)应该是越靠右(低位)的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 20:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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