一亩三分地论坛

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

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

8月12号 zenefit OA 3

[复制链接] |试试Instant~ |关注本帖
consciousgaze 发表于 2015-8-13 14:20:37 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@ - 内推 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x

版内朋友内推的zenefits。前天接到的zenefit challange III, 似乎就是OA3。今天做了。第二个test case都没全过……估计要挂了

. 鍥磋鎴戜滑@1point 3 acres
第一题叫sell tickets。火车站有一些买票点(station)。每个买票点有数量不同的存票。而且票的价格和此买票点卖票时的存票量相同。比如:A来点1,有15张票,那么票就卖A 15块。A之后B来了。此时点A只有14张票,就卖B 14块。火车站有个卖票点总指标,卖够了就收摊。问卖完这个指标的最大收益。
输入是如下的两行。
2, 4
5, 2
第一行第一个数是买票点(station)的数量,这里是2个。第二个数是总指标的值。这里是4张。
第二行是各个买票点的最开始的存票数量。这里5张和2张。
最大的收益是14。

这个我觉得还不算难。不过要先想清楚到底是怎么卖票的。首先肯定永远卖票最多那个买票点的票,因为价格最高。而后当票卖到好几个买票点一样多的时候就是这些买票点轮流卖票了。. 1point 3acres 璁哄潧

.鏈枃鍘熷垱鑷1point3acres璁哄潧比如如下情况:

3, 5

10, 8, 5
. 1point 3acres 璁哄潧
买票的次序就是:10, 9, 8, 8, 7

所以最开始就把各买票点sort一下。而后一个价格区间一个价格区间的卖。卖到最后收尾。python代码大概如下:
tmp = raw_input().split()
station_num = int(tmp[0])
m = int(tmp[1])

a = sorted([int(t) for t in raw_input().split()])
revenue = 0
鏉ユ簮涓浜.涓夊垎鍦拌鍧. sold = 0. from: 1point3acres.com/bbs

for window in range(len(a)):
    if window < len(a) - 1:
        next_window = a[window + 1]
    else:
        next_window = 0. Waral 鍗氬鏈夋洿澶氭枃绔,

    stop = (m - sold)/(window + 1) < (a[window] - next_window)
    if stop:
        price_step = (m - sold)/(window + 1)
    else:
        price_step = a[window] - next_window

. more info on 1point3acres.com    # 用等差公式求出revenue的增量
    revenue += (window+1)*(2*a[window] - price_step + 1)/2
. 鍥磋鎴戜滑@1point 3 acres    sold += price_step*(window + 1)
    if stop:
            revenue += (m - sold)*(a[window] - price_step)
            sold = m
. Waral 鍗氬鏈夋洿澶氭枃绔,            break
.1point3acres缃
print revenue

输入是从stdin读入的,输出也是输出到stdout。所以io看起来可能有些怪。不过还是蛮快就过了。





第二题叫word rank。首先题里定义了一个word rank。是说一个词在其所有permutation中的排序。比如‘cab’,所有的permutation排序后是'abc', 'bac', 'bca', 'cab', 'cba'。其中‘cab’在第4个,所有它的word rank就是3(rank的计数从0开始)。
这个题我觉得想起来不太困难不过就是没过全部的test case。也看不到没有过的case到底是什么。所以我也不知道是逻辑有遗漏还是求阶乘的时候数据有溢出。。。明白人帮帮忙啊。、
这个是file io,parsing的code他给好了。我也就只写中间比较重要的code了。也都是python
def word_num(letters):. Waral 鍗氬鏈夋洿澶氭枃绔,
        #求出对于给定字符集合,所有的permutation的数量-google 1point3acres
    total = 0 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    div = 1 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    for c in letters:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        total += letters[c]. from: 1point3acres.com/bbs
        for i in range(letters[c]):. Waral 鍗氬鏈夋洿澶氭枃绔,
            div *= i + 1
    tmp = 1.鏈枃鍘熷垱鑷1point3acres璁哄潧
    for i in range(total):
        tmp *= i+1
    return tmp/div
.鏈枃鍘熷垱鑷1point3acres璁哄潧
def get_rank(word):
    letters = {}
    for c in word:
        if c in letters:.鐣欏璁哄潧-涓浜-涓夊垎鍦
            letters[c] += 1
. more info on 1point3acres.com        else:
            letters[c] = 1. visit 1point3acres.com for more.

    rank = 0. From 1point 3acres bbs
    for c in word:
            #当前位前一样,但当前位比word小的permutation的数量
        for lower in letters:
            if lower < c and letters[lower] > 0:
                letters[lower] -= 1
                rank += word_num(letters). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                letters[lower] += 1. more info on 1point3acres.com
        letters[c] -= 1
    #至当前位都一样,但之后比word小的情况
    return rank

不知道有没有错,有没有可以优化的地方。出身是EE所以coding可能也不太漂亮。高人们多指正啊。小弟多谢了。

评分

1

查看全部评分

 楼主| consciousgaze 发表于 2015-8-14 06:00:10 | 显示全部楼层
好消息是竟然过了OA,准备电面了!
回复 支持 反对

使用道具 举报

weiwuwei 发表于 2015-9-19 15:21:01 | 显示全部楼层
consciousgaze 发表于 2015-8-14 06:00
好消息是竟然过了OA,准备电面了!

请问就两道题吗?
回复 支持 反对

使用道具 举报

 楼主| consciousgaze 发表于 2015-9-20 10:15:06 | 显示全部楼层
weiwuwei 发表于 2015-9-19 15:21. 1point 3acres 璁哄潧
请问就两道题吗?

只有两到
回复 支持 反对

使用道具 举报

Triston 发表于 2015-10-20 05:13:32 | 显示全部楼层
楼主确定是OA3么?今天也收到了OA但是查了一下,似乎还有很多人写OA3是longestchain和 n-queen,想准备妥当在开始,毕竟他家OA还挺难的
回复 支持 反对

使用道具 举报

 楼主| consciousgaze 发表于 2015-10-21 00:59:57 | 显示全部楼层
Triston 发表于 2015-10-20 05:13
楼主确定是OA3么?今天也收到了OA但是查了一下,似乎还有很多人写OA3是longestchain和 n-queen,想准备妥 ...

确定是。我的题和当时我看到的别人的题也不是完全一样。但也有人说遇到了。题库应该不止两道。
回复 支持 反对

使用道具 举报

Triston 发表于 2015-10-21 03:46:02 | 显示全部楼层
consciousgaze 发表于 2015-10-21 00:59
确定是。我的题和当时我看到的别人的题也不是完全一样。但也有人说遇到了。题库应该不止两道。

谢谢楼主!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 00:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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