一亩三分地论坛

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

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

Twitter OA 跪经,他家换题库了?

[复制链接] |试试Instant~ |关注本帖
fanzy 发表于 2016-3-4 07:29:15 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Twitter - 内推 - 在线笔试 |Fail其他

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

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

x

刚做完Twitter OA,做之前听同学说他家OA很简单,然后我就淡定地打开来开始做。

然后一看题,卧槽不对啊,这是简单吗!!

-google 1point3acres第一题:输入一个正整数N,求1<=X<=N中,满足(X-1)!%X==X-1的X的个数。N有个范围,最大大概是到10^6?
第二题:输入一个正整数N,代表在一个平面中划N条线,求最多能被分成几个区域。如果结果大于10^9,取其模。(其实输入是一个list,输出也是一个list,结果一一对应)

乍一看都是数学问题,然而感觉都是越界的问题。。

我都没做出来,然后OA结束时间一到,我的邮箱就出现了一封拒信。被虐的体无完肤啊。。

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴第一题,我目前没思路。第二题,我是想套数学公式的,这样复杂度就是O(1),结果最后没写出来。退一步讲是有一个O(N)的算法的,就是动规一步一步算上去,因为输入是一个list,dp结果是可以重复利用的,所以估计也不会太差,然而我没实现它。。
. 1point3acres.com/bbs

祝大家找工顺利。。

评分

3

查看全部评分

liuyifly06 发表于 2016-3-6 09:31:39 | 显示全部楼层
Only the prime number satisfies this equation:  (X-1)!%X == X-1 . It is actually asking how many prime numbers are there !       If you wanna brute force,  (X-1)!%X  can be calculated by  for(int i = 1; i<X; i++){res = (res*i)%X}.  

补充内容 (2016-3-6 09:34):
By the way, 1 also satisfy the equation although it is not a prime number

补充内容 (2016-3-6 10:01):
About the second question, check here: (Number of Regions N Lines Divide Plane)  http://www.cut-the-knot.org/proofs/LinesDividePlane.shtml
回复 支持 3 反对 0

使用道具 举报

johnjavabean 发表于 2016-3-4 08:18:02 | 显示全部楼层
他家比较随机...总体上都是比较难的
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-3-6 05:39:05 | 显示全部楼层
第一题该怎么做啊。。。我用BigInteger的话,当输入是1,000,000的时候,半天都跑不出结果。。。
回复 支持 反对

使用道具 举报

lucifer_vent 发表于 2016-3-6 05:44:43 | 显示全部楼层
(X-1)!%X==X-1 ??. visit 1point3acres.com for more.
这是什么啊,!%?。。。
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-3-6 07:23:35 | 显示全部楼层
lucifer_vent 发表于 2016-3-6 05:44
(X-1)!%X==X-1 ??
这是什么啊,!%?。。。

X - 1的阶乘对X取模后,等于X - 1
回复 支持 反对

使用道具 举报

ymwang1984 发表于 2016-3-6 09:47:14 | 显示全部楼层
这哪是考编程啊,明明是考数学!

第一道题,典型的数论问题,威尔逊定理(Wilson's Theorom),只有质数和1满足那个条件,所以实际上就是个找质数而已。

第二道题,也是奥数题吧。
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-3-6 10:40:41 | 显示全部楼层
liuyifly06 发表于 2016-3-6 09:31
Only the prime number satisfies this equation:  (X-1)!%X == X-1 . It is actually asking how many pri ...

链接很赞。然后第二题,我发现f(n) = f(n-1) + n; 因为n-1根线的时候,它们相互之间都是相交的,也就是角度最大的两根线的角度是小于180度的,所以这n-1根直线可以把第n根直线分割成n段,因而增加了n个区域。。。
回复 支持 反对

使用道具 举报

 楼主| fanzy 发表于 2016-3-7 21:57:18 | 显示全部楼层
liuyifly06 发表于 2016-3-6 09:31
Only the prime number satisfies this equation:  (X-1)!%X == X-1 . It is actually asking how many pri ...

U r so helpful!!
回复 支持 反对

使用道具 举报

 楼主| fanzy 发表于 2016-3-7 22:06:43 | 显示全部楼层
第二题的数学公式是很明显的,然后问题就转化为,两个数相乘的结果%10^9,我是这样做的,假设这两个数为a,b(a,b<10^8,题目里好像有这个条件)。
1.如果a<b,交换a,b
2.对a二分搜索,找出满足1<a'<a且a'*b>=10^9的a'的最小值,t
3.如果t*b>INT_MAX,递归;否则,temp=(t*b)%10^9
4.递归求temp与x/t的积
5.递归求x%t与b的积
6.将4和5的结果相加,再mod 10^9做最后结果

求拍砖。。

补充内容 (2016-3-7 22:08):
3.应该是:如果t*b>INT_MAX,temp=递归t和b的积;否则,temp=(t*b)%10^9
回复 支持 反对

使用道具 举报

披着马甲的菠菜 发表于 2016-3-8 00:02:37 | 显示全部楼层
请问下楼主是网投还是内推?
回复 支持 反对

使用道具 举报

 楼主| fanzy 发表于 2016-3-8 01:49:30 | 显示全部楼层
披着马甲的菠菜 发表于 2016-3-8 00:02
请问下楼主是网投还是内推?
-google 1point3acres
我是内推的
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-3-8 05:55:59 | 显示全部楼层
fanzy 发表于 2016-3-7 22:06
第二题的数学公式是很明显的,然后问题就转化为,两个数相乘的结果%10^9,我是这样做的,假设这两个数为a,b ...

可以直接用long吗?这是是不是就不用考虑越界了?
回复 支持 反对

使用道具 举报

syftalent 发表于 2016-3-8 07:38:46 | 显示全部楼层
这题以前有出现过
回复 支持 反对

使用道具 举报

 楼主| fanzy 发表于 2016-3-8 10:49:54 | 显示全部楼层
Mark6 发表于 2016-3-8 05:55
可以直接用long吗?这是是不是就不用考虑越界了?

嗯嗯,有道理。。为什么这么直接的方式我没想到囧。。
回复 支持 反对

使用道具 举报

norafang 发表于 2016-3-10 00:08:13 | 显示全部楼层
fanzy 发表于 2016-3-7 22:06
第二题的数学公式是很明显的,然后问题就转化为,两个数相乘的结果%10^9,我是这样做的,假设这两个数为a,b ...

这里a,b指的是什么呢?不是n条线吗?
回复 支持 反对

使用道具 举报

 楼主| fanzy 发表于 2016-3-10 04:19:55 | 显示全部楼层
norafang 发表于 2016-3-10 00:08. 鍥磋鎴戜滑@1point 3 acres
这里a,b指的是什么呢?不是n条线吗?

2+(n+2)(n-1)/2,我说的a和b就是n+2和n-1了
回复 支持 反对

使用道具 举报

norafang 发表于 2016-3-10 06:42:48 | 显示全部楼层
fanzy 发表于 2016-3-10 04:19. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
2+(n+2)(n-1)/2,我说的a和b就是n+2和n-1了

好的!谢谢
回复 支持 反对

使用道具 举报

Enchant 发表于 2016-3-20 05:44:07 | 显示全部楼层
感谢讨论! 这下就稳了!
回复 支持 反对

使用道具 举报

忆梦前尘 发表于 2016-3-20 08:45:00 | 显示全部楼层
唉。。遇到了第二题,但鬼使神差的没有看你这个帖子,就是搜到了,打开了,但是没看。。。真是神了。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 23:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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