谈谈Rice MCS18fall入学+找实习感受

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

科技公司如何
用数据分析驱动产品开发
Coupon code: best
深入浅出AB Test
从入门到精通
Coupon code: best
码农求职神器Triplebyte:
不用海投
内推多家公司面试
E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 2301|回复: 12
收起左侧

Akuna Capital OA,求加大米

[复制链接] |试试Instant~
我的人缘0
木华黎_Reid 发表于 2017-10-28 07:13:20 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  97% (75)
 
 
2% (2)  踩

2017(10-12月) 分析|数据科学类 博士 全职@AkunaCapital - 网上海投 - 在线笔试  | Pass | fresh grad应届毕业生

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

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

x
楼主上周六做了Akuna OA
第一题:染色问题,比较难,在线没有做出来,之前也看了地里的面经,也是没有人给出答案,具体题目可以见附件
楼主大概有一天上课想出来了,把code分享给大家:
# coloring problem
def color(m, n, k):
        # nums_polygon = m
        # nums_sides = n = 2p
        # nums_color = k
        p = n/2
        return 1*k + 2*(k**2-k)+ p*(k**p-k)+(2*p)*(k**(2p)-k**p-k**2+k)


问题本质上涉及到欧拉数,用到一些数论,等同于项链珠子染色问题。
当然求解本题暂时可以不用,以上是总结了最后答案想出来的比较容易理解的方法:
对于多边形,想要rotate n次之后,如果颜色分布不均匀,其实可以得到n种在旋转上等同的染色方案。
那么,什么时候不会这样呢?这也是问题的关键,如果把这个多边形打开看成一个链条,如果这个链条上存在重复单元unit,比如123|123 染色方案就有3个,如果是12|12|12 染色方案就有2两个
接下来就容易联想到边长数n的因子分解,这题的题设告诉我们是2*p,p是质数
那么染色方案只有四种:
1. 颜色全一样,重复了2p个unit, 染色方案为1。由于unit个数为1,染色数目可以为k,所以是1*k**1
2. unit为2,重复了p次,染色方案为2。计算染色数目要减去全部颜色的情况,染色数目是k**2-k,所以是2*(k**2 - k)
3. unit为p,重复了2次,染色方案为p。注意到这里不可能和unit=2情况重复,因为2和p公约数只有1。染色数目同样要减去颜色同样的,所以是k**p-k,最终是p*(k**p-k)
4. unit为2p,就是多边形不存在重复的单元,我们可以转2n次,得到2n个在旋转上等价的方案。对于每个边去染色,要出去1, 2, 3以上的情况,由于减去k**2和k**p多减了k一次,所以最后
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
n_x1,y+conn_y1) not in record:
            queue.append((x+conn_x1,y+conn_y1))
            record.add((x+conn_x1,y+conn_y1))
        if 0<=x+conn_x2<n and 0<=y+conn_y2<m and (x+conn_x2,y+conn_y2) not in record:
            queue.append((x+conn_x2,y+conn_y2))
            record.add((x+conn_x2,y+conn_y2))  

    return m*n-len(record)-baidu 1point3acres

Capture.zip

110.59 KB, 下载次数: 74, 下载积分: 大米 -1 升

染色问题截图

评分

参与人数 4大米 +10 收起 理由
phenix997 + 3 给你点个赞!
benben4 + 3 很有用的信息!
zy53012127 + 1 给你点个赞!
helenaqa + 3 很有用的信息!

查看全部评分


上一篇:Capital one coding challenge
下一篇:Akuna 两轮店面 (Quant Researcher)
我的人缘0
绿毛龟太郎 发表于 2017-10-28 11:42:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (7)
 
 
12% (1)  踩
弱问楼主
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
啊?
回复

使用道具 举报

我的人缘0
 楼主| 木华黎_Reid 发表于 2017-10-30 01:20:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (75)
 
 
2% (2)  踩
绿毛龟太郎 发表于 2017-10-28 11:42
弱问楼主投的什么岗位啊?

data analysis
回复

使用道具 举报

我的人缘0
horry0409 发表于 2017-10-30 05:44:46 | 显示全部楼层
谢楼主分享!!!
回复

使用道具 举报

我的人缘0
zhongdewei 发表于 2017-11-1 09:47:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (11)
 
 
8% (1)  踩
请问这个是
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
几啊
回复

使用道具 举报

我的人缘0
zzh007zp 发表于 2017-11-11 12:43:39 | 显示全部楼层
这个题我也做出了你的解法, 但是有几个testcase并没
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
4,仍然没法全部通过。
回复

使用道具 举报

我的人缘0
 楼主| 木华黎_Reid 发表于 2017-11-11 13:21:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (75)
 
 
2% (2)  踩
zzh007zp 发表于 2017-11-11 12:43
这个题我也做出了你的解法, 但是有几个testcase并没法通过。我找出的特殊情况是coler=1 以及side=4,仍然 ...

LZ电话面试两次 问的都挺简单的,等来了据信,祝大家好运!
回复

使用道具 举报

我的人缘0
DavidLi210 发表于 2017-11-28 00:35:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  89% (186)
 
 
10% (21)  踩
可否问下lz
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
t几
回复

使用道具 举报

我的人缘0
yixing98 发表于 2017-12-3 04:14:13 | 显示全部楼层
请问楼主是t
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
几呀?
回复

使用道具 举报

我的人缘0
qingshan412 发表于 2017-12-13 11:17:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (30)
 
 
0% (0)  踩
lz应该是想说分母是(k**p)**2,打错成了(k**n)**2?
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
退化成了和2相同的情况。
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地留学网

GMT+8, 2018-12-19 07:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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