详谈如何最大化利用career fair

一亩三分地论坛

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

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 1739|回复: 12
收起左侧

Akuna Capital OA,求加大米

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

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

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

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

x
楼主上周六做了Akuna OA
第一题:染色问题,比较难,在线没有做出来,之前也看了地里的面经,也是没有人给出答案,具体题目可以见附件.1point3acres网
楼主大概有一天上课想出来了,把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两个. from: 1point3acres
接下来就容易联想到边长数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一次,所以最后在加上k
所以染色数目是k**(2p)-k**p-k**2+k,总的结果是(2*p)*(k**(2p)-k**p-k**2+k)

把以上结果加起来就是 1*k + 2*(k**2-k)+ p*(k**p-k)+(2*p)*(k**(2p)-k**p-k**2+k)
题目没有让除以分母,所以到此就行了, 当然分母是 (k**n)**2

第二题:求方差,注意最后除以(总数-1)
第三题:Lamp问题,地理有面经,我贴一下别人的code

def  num_illuminated(grid_width, grid_height, conn_x1, conn_y1, conn_x2, conn_y2, start_x, start_y):
    """
    grid_width - the width of the room grid
    grid_height - the height of the room grid 来源一亩.三分地论坛.
    conn_x1 - the x-coordinate of the first lamp connection
    conn_y1 - the y-coordinate of the first lamp connection. from: 1point3acres
    conn_x2 - the x-coordinate of the second lamp connection
    conn_y2 - the y-coordinate of the second lamp connection
    start_x - the x-coordinate of the first lamp turned off
    start_y - the y-coordinate of the first lamp turned off.本文原创自1point3acres论坛
    """
    n=grid_width
    m=grid_height.留学论坛-一亩-三分地
    if start_x<0 or start_x>=n or start_y<0 or start_y>=m: return m*n

    queue=[(start_x,start_y)]   
    record={(start_x,start_y)}

    while queue:
        x,y=queue.pop(). 一亩-三分-地,独家发布
        if 0<=x+conn_x1<n and 0<=y+conn_y1<m and (x+conn_x1,y+conn_y1) not in record:. more info on 1point3acres
            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)

Capture.zip

110.59 KB, 下载次数: 63, 下载积分: 大米 -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)   【踩】
全局: 顶  85% (6)
 
 
14% (1)  踩
弱问楼主投的什么岗位啊?
回复

使用道具 举报

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

data analysis
回复

使用道具 举报

我的人缘0
horry0409 发表于 2017-10-30 05:44:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
谢楼主分享!!!
回复

使用道具 举报

我的人缘0
zhongdewei 发表于 2017-11-1 09:47:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
请问这个是dev 几啊

Complexity Quiz: Test your understanding of Data Structure
来自于网课《Data Structures for Coding Interview in Python》

回复

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

我的人缘0
DavidLi210 发表于 2017-11-28 00:35:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (113)
 
 
7% (9)  踩
可否问下lz这是test几
回复

使用道具 举报

我的人缘0
yixing98 发表于 2017-12-3 04:14:13 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
请问楼主是test # 几呀?
回复

使用道具 举报

我的人缘0
qingshan412 发表于 2017-12-13 11:17:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (25)
 
 
0% (0)  踩
lz应该是想说分母是(k**p)**2,打错成了(k**n)**2?
另外,p = 2的时候应该需要单独讨论?因为这个时候p退化成了和2相同的情况。
回复

使用道具 举报

我的人缘0
zy53012127 发表于 2017-12-19 07:24:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
木华黎_Reid 发表于 2017-11-11 13:21
LZ电话面试两次 问的都挺简单的,等来了据信,祝大家好运!

请问楼主可以分享一下后面的电面经验和题目吗?
回复

使用道具 举报

我的人缘0
zhangyangseu 发表于 2018-1-4 18:54:10 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
请问楼主您发布的关于 Akuna Capital OA 的文章,编程第三题lamp问题, 能问您一下您如何理解为什么要给 conn_x1, conn_y1, conn_x2, conn_y2吗?如果是想给出关灯的方向,那code您感觉有没有问题呢? 谢谢您!我正在准备这套题,但感觉跟您贴的code理解不太一样
回复

使用道具 举报

我的人缘0
XinrongMeng 发表于 2018-2-2 01:11:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
谢谢楼主~
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-9-25 05:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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