一亩三分地论坛

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

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

Twitter OA

[复制链接] |试试Instant~ |关注本帖
newbiee 发表于 2016-3-22 02:18:55 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Twitter - 网上海投 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
昨天的OA, 我和朋友暂时都没有好的思路, 各位有好的思路么?
. 1point 3acres 璁哄潧
. from: 1point3acres.com/bbs
-google 1point3acres
补充内容 (2016-3-22 02:23):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
基本意思就是: 从1到n选择尽可能多的数,使得任意两个数不为倍数关系,问你最大能取多少个数(或者如题目所说的,至少多少个必然存在冲突)

prune:  isPrime() 数质数的个数不对,我们开始没想明白,撞这枪口上了
Screen Shot 2016-03-21 at 2.15.43 PM.png

评分

2

查看全部评分

本帖被以下淘专辑推荐:

sheepmiemies 发表于 2016-3-22 03:27:18 | 显示全部楼层
第一反应也是找primes,结果举了个1~10的例子检验就发现不对了。。。
提供个思路不知道对不对:继续找规律发现 [n/2 + 1, n]这个范围内的数是互相无法整除的,因为一个数是另一个数的倍数最少是两倍及其以上。所以如果有n/2 + 1个以上的数,就会有冲突了。

请问LZ最近是多久投的twitter,最近twitter又开始招人啦?
回复 支持 反对

使用道具 举报

白丁117 发表于 2016-3-23 08:15:23 | 显示全部楼层
请教lz为啥例子output是3...? 可以选1吗? but任何数都是1的倍数...?
回复 支持 反对

使用道具 举报

sac7e 发表于 2016-3-23 10:32:54 | 显示全部楼层
白丁117 发表于 2016-3-23 08:15
请教lz为啥例子output是3...? 可以选1吗? but任何数都是1的倍数...?

我觉得应该evenly divide应该是2倍关系,这样可以是1,3,4. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

补充内容 (2016-3-23 10:45):
额,我理解错了,题目问的是minimum K,那valid的最大数目就是2,
回复 支持 反对

使用道具 举报

白丁117 发表于 2016-3-23 10:41:26 | 显示全部楼层
sac7e 发表于 2016-3-23 10:32
我觉得应该evenly divide应该是2倍关系,这样可以是1,3,4

谢了,Btw lz用的啥 java or C++? 可以跑test case吗?
回复 支持 反对

使用道具 举报

sac7e 发表于 2016-3-23 10:46:32 | 显示全部楼层
白丁117 发表于 2016-3-23 10:41
谢了,Btw lz用的啥 java or C++? 可以跑test case吗?

我不是lz,你再看下楼上,我理解错了
回复 支持 反对

使用道具 举报

sac7e 发表于 2016-3-23 11:07:00 | 显示全部楼层
白丁117 发表于 2016-3-23 10:41
谢了,Btw lz用的啥 java or C++? 可以跑test case吗?
. Waral 鍗氬鏈夋洿澶氭枃绔,
我给一个solution, python的: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

def solution(n):.鐣欏璁哄潧-涓浜-涓夊垎鍦

    arr = [1]*n. From 1point 3acres bbs
    for i in range(n-1, -1, -1):
        if arr==1 and i%2:
            arr[i//2] = 0

    return sum(arr)
回复 支持 反对

使用道具 举报

acming 发表于 2016-3-23 12:11:09 | 显示全部楼层
把1-n数字列出来,有整除关系的数之间加一条边,问题就转换成为找最大的集合使得集合里的数互相没有边,答案就是集合里数的个数+1,枚举几个n之后,我觉的答案就是n/2+1,因为n是偶数,所以[n/2 + 1, n]之间不能互相整除,n/2之前的数必然能整除[n/2 + 1, n]之间的某个数,因为将其乘2得到的结果必然在[n / 2 + 1, n]直接,所以我认为答案应该就是n/2 + 1
回复 支持 反对

使用道具 举报

sac7e 发表于 2016-3-23 19:21:34 | 显示全部楼层
acming 发表于 2016-3-23 12:11. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
把1-n数字列出来,有整除关系的数之间加一条边,问题就转换成为找最大的集合使得集合里的数互相没有边,答 ...

嗯,你的是对的,我楼上的代码是不存在2倍关系的最小K
回复 支持 反对

使用道具 举报

penenda 发表于 2016-3-23 22:09:02 | 显示全部楼层
我3月20号坐了OA,然后昨天同时来了两份邮件,,一个是让我3月24之前做完OA,一个是Next step,我都不知道怎么搞了 OA还做不做呢
回复 支持 反对

使用道具 举报

白丁117 发表于 2016-3-24 00:02:18 | 显示全部楼层
acming 发表于 2016-3-23 12:11
把1-n数字列出来,有整除关系的数之间加一条边,问题就转换成为找最大的集合使得集合里的数互相没有边,答 ...

so 直接return n/2+1(感觉是这个),那还写啥...就像n lines divide plane那个题,直接return 1+(1+n)*n/2不就可以...But那个lz跑test case跑不过...? 不懂,求解答,多谢
回复 支持 反对

使用道具 举报

lxy16555 发表于 2016-3-24 00:20:24 | 显示全部楼层
penenda 发表于 2016-3-23 22:09
我3月20号坐了OA,然后昨天同时来了两份邮件,,一个是让我3月24之前做完OA,一个是Next step,我都不知道 ...

twitter就是好奇怪,放oa全部一起放,放完之后也不看就先让人填next step,这万一要是oa没过不是白填。。。
回复 支持 反对

使用道具 举报

penenda 发表于 2016-3-24 00:28:16 | 显示全部楼层
lxy16555 发表于 2016-3-24 00:20
twitter就是好奇怪,放oa全部一起放,放完之后也不看就先让人填next step,这万一要是oa没过不是白填。。 ...

那就是我的第二个OA还是要做吗?  他邮件给我写的是 Thank you for completing our code challenge. Next step....但是这封邮件5分钟之前却给了我第二个OA
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-3-24 01:43:41 | 显示全部楼层
白丁117 发表于 2016-3-24 00:02
so 直接return n/2+1(感觉是这个),那还写啥...就像n lines divide plane那个题,直接return 1+(1+n)*n ...

这题明显是证明分析大于编写代码,所以感觉代码短还是情有可原的,如果面试遇到这题,十有八九是要你证明的。
回复 支持 反对

使用道具 举报

白丁117 发表于 2016-3-24 01:48:16 | 显示全部楼层
hison7463 发表于 2016-3-24 01:43
这题明显是证明分析大于编写代码,所以感觉代码短还是情有可原的,如果面试遇到这题,十有八九是要你证明 ...

请问证明写哪里?.....写注释...?怎么写证明才能算过?
回复 支持 反对

使用道具 举报

lxy16555 发表于 2016-3-24 02:20:56 | 显示全部楼层
penenda 发表于 2016-3-24 00:28
那就是我的第二个OA还是要做吗?  他邮件给我写的是 Thank you for completing our code challenge. Next ...

我觉得这个是单纯它发错了,没听说t家有两轮OA,不过你做了,做得好可能有加分?
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-3-24 02:53:28 | 显示全部楼层
白丁117 发表于 2016-3-24 01:48
请问证明写哪里?.....写注释...?怎么写证明才能算过?

我说的是onsite,OA我觉得能跑过就行了
回复 支持 反对

使用道具 举报

1peter 发表于 2016-3-24 03:23:48 | 显示全部楼层
hison7463 发表于 2016-3-24 02:53
. From 1point 3acres bbs我说的是onsite,OA我觉得能跑过就行了

我觉得证明不难啊,用contradiction证,假设大于(n+1)/2,那么肯定有一些数落在(0,n/2),假设有x个,那么这些数的2倍就不可以出现在(n/2,n)中,所以(n/2,n)至多有n/2-x个,所以总数至多有(n+1)/2个,得出矛盾。

大概是这个意思,边界我就没细分析了
回复 支持 反对

使用道具 举报

acming 发表于 2016-3-24 04:17:12 | 显示全部楼层
1peter 发表于 2016-3-24 03:23
我觉得证明不难啊,用contradiction证,假设大于(n+1)/2,那么肯定有一些数落在(0,n/2),假设有x个, ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
嗯,对,每从前面拿出一个,必定要从后面至少减去一个
回复 支持 反对

使用道具 举报

lfy249 发表于 2016-4-19 12:57:13 | 显示全部楼层
『prune:  isPrime() 数质数的个数不对,我们开始没想明白,撞这枪口上了』 . from: 1point3acres.com/bbs
"我们"... LOL
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 05:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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