传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 6112|回复: 10
收起左侧

十分钟前的 Two Sigma OA 题目

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

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

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

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

x
十分钟前刚刚做完的Two Sigma OA 题目,祝各位农友找工作顺利!. from: 1point3acres.com/bbs
走过路过,求大家多赏几个玉米吧 哈哈 . visit 1point3acres.com for more.

一共两道题目,
.鏈枃鍘熷垱鑷1point3acres璁哄潧
题目一:Fibonacci coding, 就是给一个数,求出它的string形式的Fibonacci coding。比如4,它的Fibonacci coding就是“101”。这个wiki上说的非常清楚什么是Fibonacci coding,(也是醉了,地里说我没权限发表站外URL。。。。Google一下Fibonacci coding,wikipedia 第一个就是),就是实现一个函数 string encode(int n);.1point3acres缃
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

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



评分

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){. Waral 鍗氬鏈夋洿澶氭枃绔,
  2.         if(n < 1) return "";. From 1point 3acres bbs
  3.         string res;. From 1point 3acres bbs
  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++;. Waral 鍗氬鏈夋洿澶氭枃绔,
  11.         }
  12.         while(index >= 0){. more info on 1point3acres.com
  13.                 if(digits[index] <= n){
  14.                         res.push_back('1');
  15.                         n -= digits[index];
  16.                 }
  17.                 else{
  18.                         res.push_back('0');. 1point 3acres 璁哄潧
  19.                 }
  20.                 index--;
    . 鍥磋鎴戜滑@1point 3 acres
  21.         }
  22.         return res;
  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上实现的,大牛们如果有更好的方法,欢迎留言

补充内容 (2 ...

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

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-21 15:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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