一亩三分地论坛

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

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

Twitter 新鲜OA

[复制链接] |试试Instant~ |关注本帖
什么都有 发表于 2015-11-7 10:09:51 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Twitter - 内推 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
今天刚做的Twitter OA,HackerRank上面一小时两题。.鏈枃鍘熷垱鑷1point3acres璁哄潧

1. 给你一个等差数列的首项和差值,再给你一个等比数列的首项和公比,再给一个上限,让你找出两个数列在上限内的共有的项的个数。例子 1, 2, 3, 4 首项1差值1等差数列 和 1, 2, 4 首项1公比2等比数列,共有项个数是3
一个注意点就是如果存下来一个数列的所有数然后暴力搜另一个数列会有三个case超时,所以可以利用mod来算每一个等比数列的项是否在等差数列里,再然后提醒一下Java的mod对于负数来说有问题,记得另外处理一下。. From 1point 3acres bbs
2. 给你一个数组里面有几个棍子的长度,每次可以从每个棍子上砍掉“最短的那个棍子的长度”(比如最短棍子是2,那就所有棍子砍掉2,如果不到2的就全部砍掉),然后输出每次能砍的棍子的数量。举个例子
3 2 3 4 5 2  (最短是2,所有棍子都砍2,一共能砍6个棍子)
1 _ 1 2 3 _  (最短是1,所有棍子都砍1,一共能砍4个棍子)
_ _ _ 1 2 _  (最短是1,所有棍子都砍1,一共能砍2个棍子)
_ _ _ _ 1 _  (最短是1,所有棍子都砍1,一共能砍1个棍子)
_ _ _ _ _ _ (没了)-google 1point3acres

所以输出 6 4 2 1

有不懂的留言提问,然后有帮上忙的加加米,谢谢~

评分

12

查看全部评分

八月 发表于 2015-11-8 04:41:56 | 显示全部楼层
谢楼主,我也准备做,先看看,不懂来问!
回复 支持 反对

使用道具 举报

 楼主| 什么都有 发表于 2015-11-8 06:28:50 | 显示全部楼层
八月 发表于 2015-11-8 04:41
谢楼主,我也准备做,先看看,不懂来问!

好的 加油哈
回复 支持 反对

使用道具 举报

八月 发表于 2015-11-8 08:23:58 | 显示全部楼层
请问楼主,第一题的mod方法是什么意思
回复 支持 反对

使用道具 举报

 楼主| 什么都有 发表于 2015-11-8 08:26:25 | 显示全部楼层
八月 发表于 2015-11-8 08:23
请问楼主,第一题的mod方法是什么意思

我是用来算等比数列中某一项是否在等差数列里,只要mod等差后等于0就说明在,你写一下就知道了
回复 支持 反对

使用道具 举报

william_gong 发表于 2015-11-8 08:29:27 | 显示全部楼层
问下哈,第二题用什么思路做?
回复 支持 反对

使用道具 举报

八月 发表于 2015-11-8 08:31:30 | 显示全部楼层
什么都有 发表于 2015-11-8 08:26
我是用来算等比数列中某一项是否在等差数列里,只要mod等差后等于0就说明在,你写一下就知道了

比如说一个等差数列1 3 5 等差是2,然后一个等比数列1 2 4,是等比数列的每一个mod2嘛,或者说我理解错了。。
回复 支持 反对

使用道具 举报

 楼主| 什么都有 发表于 2015-11-8 08:52:57 | 显示全部楼层
八月 发表于 2015-11-8 08:31
比如说一个等差数列1 3 5 等差是2,然后一个等比数列1 2 4,是等比数列的每一个mod2嘛,或者说我理解错了 ...

你理解的没错,但是要减去等差数列的首项。因为等差数列的公式就是an = a1 + (n - 1) * d 所以你用an - a1 % d 如果能得到0 就说明他存在等差数列里  
回复 支持 反对

使用道具 举报

 楼主| 什么都有 发表于 2015-11-8 08:53:41 | 显示全部楼层
william_gong 发表于 2015-11-8 08:29
问下哈,第二题用什么思路做?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第二题我用min heap做的
回复 支持 反对

使用道具 举报

八月 发表于 2015-11-8 09:32:56 | 显示全部楼层
什么都有 发表于 2015-11-8 08:52
你理解的没错,但是要减去等差数列的首项。因为等差数列的公式就是an = a1 + (n - 1) * d 所以你用an - a ...

懂啦 谢谢!
回复 支持 反对

使用道具 举报

 楼主| 什么都有 发表于 2015-11-8 09:52:27 | 显示全部楼层

好的~有空帮我加米哦~
回复 支持 反对

使用道具 举报

ymqytw 发表于 2015-11-17 04:40:17 | 显示全部楼层
请问LZ,第一题用mod判断,只要判断结果是否等于0就行,在java中这样计算对于负数有什么问题?LZ能不能举个例子。谢谢
回复 支持 反对

使用道具 举报

 楼主| 什么都有 发表于 2015-11-17 08:10:14 | 显示全部楼层
ymqytw 发表于 2015-11-17 04:40
请问LZ,第一题用mod判断,只要判断结果是否等于0就行,在java中这样计算对于负数有什么问题?LZ能不能举个 ...

你可以到Lintcode的 Rehashing那一题的题目描述去看一眼,有例子和解决办法。
回复 支持 反对

使用道具 举报

bonnachoven 发表于 2015-11-17 08:19:25 | 显示全部楼层
lz想问下做完oa有收到下一步面试么?
回复 支持 反对

使用道具 举报

ymqytw 发表于 2015-11-17 09:17:36 | 显示全部楼层
什么都有 发表于 2015-11-17 08:10
你可以到Lintcode的 Rehashing那一题的题目描述去看一眼,有例子和解决办法。
. more info on 1point3acres.com
哦哦,多谢楼主啦
回复 支持 反对

使用道具 举报

 楼主| 什么都有 发表于 2015-11-17 12:18:04 | 显示全部楼层
ymqytw 发表于 2015-11-17 09:17. 1point3acres.com/bbs
哦哦,多谢楼主啦

没事 加油加油
回复 支持 反对

使用道具 举报

DreamBoy 发表于 2016-1-24 04:18:47 | 显示全部楼层
觉得第二题用heap会space不是optimal的==这道题最优时间空间应该是O(logN)和O(1),真是题目越容易坑越多的感觉=第一题corner case也好多
回复 支持 反对

使用道具 举报

 楼主| 什么都有 发表于 2016-1-24 09:45:30 | 显示全部楼层
DreamBoy 发表于 2016-1-24 04:18. 鍥磋鎴戜滑@1point 3 acres
觉得第二题用heap会space不是optimal的==这道题最优时间空间应该是O(logN)和O(1),真是题目越容易坑越多的 ...

0 0 我已经忘了诶,不过看起来你的解法很厉害!
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-1-24 09:50:46 | 显示全部楼层
什么都有 发表于 2016-1-24 09:45
0 0 我已经忘了诶,不过看起来你的解法很厉害!

我在想第二题是不是只要sort然后再输出就可以了?
回复 支持 反对

使用道具 举报

 楼主| 什么都有 发表于 2016-1-24 10:57:32 | 显示全部楼层
william_gong 发表于 2016-1-24 09:50
我在想第二题是不是只要sort然后再输出就可以了?
. 1point3acres.com/bbs
没这么简单啊,我记忆里是二分了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 06:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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