一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 730|回复: 11
收起左侧

Akuna Capital OA,求加大米

[复制链接] |试试Instant~ |关注本帖
木华黎_Reid 发表于 2017-10-28 07:13:20 | 显示全部楼层 |阅读模式

2017(10-12月) 分析|数据科学类 博士 全职@Akuna Capital - 网上海投 - 在线笔试 |Passfresh 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)
. Waral 鍗氬鏈夋洿澶氭枃绔,

问题本质上涉及到欧拉数,用到一些数论,等同于项链珠子染色问题。
当然求解本题暂时可以不用,以上是总结了最后答案想出来的比较容易理解的方法:
对于多边形,想要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一次,所以最后在加上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
.鏈枃鍘熷垱鑷1point3acres璁哄潧
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
    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
    """
    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.1point3acres缃

    queue=[(start_x,start_y)]   
-google 1point3acres    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:
            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))  
. visit 1point3acres.com for more.
    return m*n-len(record)

Capture.zip

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

染色问题截图

评分

2

查看全部评分

绿毛龟太郎 发表于 2017-10-28 11:42:40 | 显示全部楼层
弱问楼主投的什么岗位啊?
回复 支持 反对

使用道具 举报

 楼主| 木华黎_Reid 发表于 2017-10-30 01:20:47 | 显示全部楼层
绿毛龟太郎 发表于 2017-10-28 11:42
弱问楼主投的什么岗位啊?

data analysis
回复 支持 反对

使用道具 举报

horry0409 发表于 2017-10-30 05:44:46 | 显示全部楼层
谢楼主分享!!!
回复 支持 反对

使用道具 举报

zhongdewei 发表于 2017-11-1 09:47:39 | 显示全部楼层
请问这个是dev 几啊
回复 支持 反对

使用道具 举报

zzh007zp 发表于 2017-11-11 12:43:39 | 显示全部楼层
这个题我也做出了你的解法, 但是有几个testcase并没法通过。我找出的特殊情况是coler=1 以及side=4,仍然没法全部通过。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

DavidLi210 发表于 2017-11-28 00:35:21 | 显示全部楼层
可否问下lz这是test几
回复 支持 反对

使用道具 举报

yixing98 发表于 2017-12-3 04:14:13 | 显示全部楼层
请问楼主是test # 几呀?
回复 支持 反对

使用道具 举报

qingshan412 发表于 2017-12-13 11:17:43 | 显示全部楼层
lz应该是想说分母是(k**p)**2,打错成了(k**n)**2?
另外,p = 2的时候应该需要单独讨论?因为这个时候p退化成了和2相同的情况。
回复 支持 反对

使用道具 举报

zy53012127 发表于 2017-12-19 07:24:53 | 显示全部楼层
木华黎_Reid 发表于 2017-11-11 13:21
LZ电话面试两次 问的都挺简单的,等来了据信,祝大家好运!
. 1point3acres.com/bbs
请问楼主可以分享一下后面的电面经验和题目吗?
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2018-1-20 09:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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