资讯专栏INFORMATION COLUMN

京东实习生招聘题目解析(二)

UnixAgain / 3571人阅读

摘要:买糖果题目来源京东实习生招聘原题链接可在线提交赛码网问题描述某糖果公司专门生产儿童糖果,它最受儿童欢迎的糖果有两个序列,均采用盒式包装。小东希望你能帮她解决这一问题。

最近比较忙,又有一段时间没写题目了,终于在前几天把赛码网上,JD的2016秋招和2017实习生招聘剩下的4星难度题目做了,至此所有4星难度题目都解决了,5星难度题目还剩下一个应该是计算几何学的题目,因为这块我不熟悉,后面找时间再处理。
鉴于赛码网的难度分类不是特别准确,接下里我把1-3星难度的题目过一次,如果有价值的就和大家一起分享。
这次的解析包含了4个题目,相对比较简单,但需要考虑全面,否则容易掉坑。


买糖果

<题目来源: 京东2016实习生招聘 原题链接-可在线提交(赛码网)>

问题描述

某糖果公司专门生产儿童糖果,它最受儿童欢迎的糖果有A1、A2两个序列,均采用盒式包装。包装好的A1类糖果体积为一个存储单位,而包装好的A2类糖果体积正好是A1类的两倍。

这两类糖果之所以广受儿童欢迎,是因为糖果中含有公司独家研发的魔幻因子。A1或A2序列中的糖果,看起来包装可能是一样的,但因为其中的魔幻因子含量不同被细分为不同的产品。

临近传统节日,公司的糖果供不应求。作为一个精明的糖果分销商,小东希望能够借此大赚一笔,于是带着现金开着货车来公司提货。货车的容量是确定的,小东希望采购的糖果能够尽可能装满货车,且糖果的魔幻因子总含量最高。只要不超出货车容量,糖果总可以装入货车中。

小东希望你能帮她解决这一问题。

这个题目的描述似乎不是太准确,其实题目就是说有n个糖果,每个糖果有个体积(1或者2),此外,有个魔幻因子。最后我们需要解决是在体积不超过v的情况下,选择若干糖果并且尽可能的获得最大的魔幻因子总量。

这看起来是个01背包问题*[1],观察数据规模后发现,n <= 10^5,v <= 10^9这个用于状态转移的枚举量实在太大,而且单就一个v的上限就足以撑爆空间。看来问题似乎不是直接使用01背包的动态规划可以解决的,再观察题目条件,一个比较特别的地方是糖果的体积只有1和2的两种情况,我们从这个比较特殊的条件来解决问题。

a.考虑一种最简单的情况:只有体积为1的糖果。
显然我们只需要对所有的糖果按照魔幻因子从大到小排序,从魔幻因子最大的糖果开始选择,由于体积都是1,那么给定的v一定可以达到。这些选择出来的糖果的魔幻因子的和就是我们的求解目标。

b.再考虑另外一种罪简单的情况,只有体积为2的糖果。
同样我们需要按魔幻因子的大小进行排序,然后从魔幻因子最大的糖果开始选择,但是不同于a,由于是每个糖果的体积是2,那么选出来糖果的体积和不一定可以刚好为v,如果刚好为v则问题已经解决。如果超过v,显然是总体积比v大了1,那么最后选择的这一种糖果就不要了。这时我们选择的糖果的总体积为v-1,尽管浪费了1,但是我们没有任何办法再放入糖果了。

c.考虑题目既有体积1和2的情况。
基于上述两种基本情况的分析,我们仍然需要安排魔幻因子大小进行排序,尽可能选择魔幻因子高的优先选择,再考虑临界情况的处理。需要注意到,对于体积为2的糖果,我们不应该直接按照其魔幻因子的总量进行排序,而是按照单位体积的魔幻因子含量进行排序。这是因为,尽管可能体积为2的糖果魔幻因子可能很高,但是他占用2个体积,如果两个体积为1的糖果魔幻因子没有其高,但是两个加起来就超过了,并且最终占用的体积都是2.

排序之后我们按照从大的开始选择,如果可以刚好取到v,那么问题就得到解决。如果得不到,那么显然当前取的是体积2的糖果,并且是超过1。这个时候,明显我们可以有多种选择,我们既可以在已经选择的糖果中去掉一个体积为1的且魔幻因子最小的糖果,也可以是在还没有选择的糖果中选择一个体积为1的且魔幻因子最大的一个糖果。至于具体选择哪种就看哪种方案可以获得更高的魔幻因子总和了。

那么问题似乎已经解决了,然后我们并没有考虑到选择的和没选择的中都可能不存在体积为1的糖果。
...已选择部分...| 体积为2的糖果| ...未选择部分...

 ^已获得的魔幻因子pm ^体积限制v

设已选择的最小的体积为1的糖果的魔幻因子为l
设未选择的最小的体积为1的糖果的魔幻因子为r
当前体积2的糖果魔幻因子为p,体积不超过v获得最大的魔幻因子总和为pm
i.l和r都不存在

= v
ii.l存在,r不存在

= max(pm, pm - l + p)

iii.l不存在,r存在

= pm + r
iv.l和r都存在

= max(pm + r, pm - l + p)

最后一个需要解决的问题是输出选择糖果的序列问题,这并不难,我们排序后依次记录选择了的糖果即可。pm - l + p的情况,删除记录中的l即可。但是,由于存在多种方案要得失编号尽可能的小,那么对与ii, iv中存在相等的情况时的处理原则时,选择编号较小的即可。

排序时间复杂度为O(nlogn),由于每个糖果只需要处理一次,计算部分时间复杂度为O(n),非常理想。

import sys

const_n = 0
const_v = 1
const_p = 2


def main():
    while True:
        line = map(int, sys.stdin.readline().strip().split())
        n, vm = line[0], line[1]

        candies = []
        for i in range(n):
            line = map(int, sys.stdin.readline().strip().split())
            if len(line) < 2:
                break
            candies.append((i + 1, line[0], line[1]))

        candies = sorted(candies, key=lambda s: float(s[const_p]) / float(s[const_v]), reverse=True)
        # print candies

        seq = set([])
        v = p = 0
        l = r = -1
        for i, candy in enumerate(candies):
            if v + candy[const_v] >= vm:
                if v + candy[const_v] == vm:
                    seq.add(candy[const_n])
                    p += candy[const_p]
                else:
                    for j in range(i + 1, n):
                        if candies[j][const_v] == 1:
                            r = j
                            break

                    if l == -1 and r == -1:
                        pass
                    elif l == -1 and r != -1:
                        p += candies[r][const_p]
                        seq.append(candies[r][const_n])
                    elif l != -1 and r == -1:
                        if candy[const_p] - candies[l][const_p] > 0:
                            p = p - candies[l][const_p] + candy[const_p]
                            seq.remove(candies[l][const_n])
                            seq.add(candy[const_n])
                    else:
                        if candy[const_p] - candies[l][const_p] > candies[r][const_p]:
                            p = p - candies[l][const_p] + candy[const_p]
                            seq.remove(candies[l][const_n])
                            seq.add(candy[const_n])
                        else:
                            p += candies[r][const_p]
                            seq.add(candies[r][const_n])
                break

            seq.add(candy[const_n])
            v += candy[const_v]
            p += candy[const_p]

            if candy[const_v] == 1:
                l = i

        print p
        if p > 0:
            seq = sorted(seq)
            for s in seq:
                print s,
        else:
            print "No"
        print

if __name__ == "__main__":
    main()
终结者C

<题目来源: 京东2017实习生招聘 原题链接-可在线提交(赛码网)>

问题描述

收到情报,有批新造的机器人要运输到前线。小C将去破坏机器人的运输。小C将激光炮放置在公路的一旁,等运输车经过的时候发射(假设激光炮一定可以射穿车辆)。由于能源有限,激光炮只能发射两次。可以认为激光炮放在坐标轴的原点处,并向y轴正方向发射。每辆运输车可以看作是一个矩形,起始的x轴坐标为Xi ,所有的车均位于第一象限,长度为Li,速度为1,朝x轴负方向运动。即经过t时间后,该车车头的x坐标为Xi-t,车尾坐标为Xi-t+Li 。只要打中车的任何一个部分就算击中。
请你算算,他在哪两个时刻发射,才能摧毁最多的运输车。

先简化下题目的意思,由于每个车辆的前进速度是统一的,那么实际上我们就不用考虑车子移动的情况了,只需要在x轴上选择两个点发射激光炮即可。此外,这个题目的数据规模是X、L<= 10^9 而不是109。

需要注意,第2次发射的激光炮不会击毁被第一次发射的激光炮已经击毁的车子。也就是1辆车不能被击毁两次。我们就不能单纯在按某个点上的车辆最多和次多来选择x轴上发射激光炮的位置了。考虑到只能发射两枚激光炮,那么我们只需要枚举这2个位置就可以了

但是观察X和L 10^9的限时,直接枚举x轴上的两个点显然不可以。

我们考虑两个车有重叠的情况,要判断有没有办法一炮机会这两个车子,实际上我们只需要判断两个位置即可,即某个车头的点是在另外一个车的范围内即可。这是一种对于极限情况的考虑,如果该情况成立,就还会有若干其他的点可能满足,但这部分点就不需要再判断。换句话说,两个车如果有重叠,那么其中有个车的车头一定在另外一个车的车身范围内

扩展到一般情况,根据上面的讨论,对于所有的车,我们激光炮的发射位置只需要选择每个车车头的位置即可。枚举之后再判断哪些车子被击毁,做上标记。最后记录一个最大的击毁数目即可。由于车辆总数n仅仅200,先两重循环枚举2个车头位置,再用一层循环检查击毁数目,算法的时间复杂度为O(n^3)是可以接受的。

import sys


def calc(f, s, c, n):
    destroy = [False for i in range(n)]
    res = 0

    for i, elem in enumerate(c):
        if elem[0] <= f <= elem[1] or elem[0] <= s <= elem[1]:
            if not destroy[i]:
                res += 1
            destroy[i] = True

    return res


def main():
    n = map(int, sys.stdin.readline().strip().split())[0]
    cars = []
    segments = []

    for i in range(0, n):
        line = map(int, sys.stdin.readline().strip().split())
        cars.append((line[0], line[0] + line[1]))
        segments.append(line[0])

    r = 0
    for i in range(len(segments)):
        for j in range(i):
            r = max(r, calc(segments[i], segments[j], cars, n))

    print r


if __name__ == "__main__":
    main()
幸运数

<题目来源: 京东2017秋招 原题链接-可在线提交(赛码网)>

问题描述

小明同学学习了不同的进制之后,拿起了一些数字做起了游戏。小明同学知道,在日常生活中我们最常用的是十进制数,而在计算机中,二进制数也很常用。现在对于一个数字x,小明同学定义出了两个函数f(x)和g(x)。
f(x)表示把x这个数用十进制写出后各个数位上的数字之和。如f(123)=1+2+3=6。
g(x)表示把x这个数用二进制写出后各个数位上的数字之和。如123的二进制表示为1111011,那么g(123)=1+1+1+1+0+1+1=6。
小明同学发现对于一些正整数x满足f(x)=g(x),他把这种数字称为幸运数,现在他想知道,小于等于n的幸运数有多少个。

接下来的这两个题目相对比较简单,数据范围也不大,这个题目可以直接按照题目意思模拟即可。
注意以下两点问题:
1.这类题目都要采用离线的计算方式,一次性先把数据规模内的数据全部计算到出来并保存,然后根据输出直接输出结果即可。
2.相对来说这个题目的数据规模较弱,注意到在当次计算时,如果个位没有发生进位的话,结果就是上次计算的结果+1,如果发生了进位再全部计算一次即可。这样可以节约非常大的一个计算量。

提交后我大致看了下运行时间,我使用的python耗时369ms,而其他python和java耗时接近或者超过1000ms,其中一个C++的运行时间为623ms。有时候一个很小的优化带来的性能提升是很显著的。

import sys

const_max_n = 100000 + 1


def _next(bits, last_sum, base):
    next_add = 0
    bits[0] += 1
    last_sum += 1

    if bits[0] >= base:
        last_sum = 0
        for i in range(len(bits)):
            bits[i] += next_add
            if bits[i] >= base:
                bits[i] = 0
                next_add = 1
            else:
                next_add = 0
            last_sum += bits[i]

        if next_add == 1:
            bits.append(1)
            last_sum += 1

    return last_sum


def main():
    r = [0 for i in range(0, const_max_n)]
    _dec = [0]
    _bin = [0]
    last_bin_sum = last_dec_sum = 0

    for i in range(1, const_max_n):
        last_bin_sum = _next(_dec, last_bin_sum, 2)
        last_dec_sum = _next(_bin, last_dec_sum, 10)

        r[i] = r[i - 1]
        if last_bin_sum == last_dec_sum:
            r[i] += 1

    t_case = map(int, sys.stdin.readline().strip().split())[0]
    for i in range(0, t_case):
        n = map(int, sys.stdin.readline().strip().split())[0]
        print r[n]


if __name__ == "__main__":
    main()
三子棋

<题目来源: 京东2016实习生招聘 原题链接-可在线提交(赛码网)>

问题描述

三子棋是一种大家熟知的游戏,几乎所有人都会玩。游戏规则相当简单,两人依次在一个3X3棋盘格上下棋,一个人画叉,另一个人画圈。任何一个人画的三个记号如果形成构成一条水平、垂直或对角的直线则获胜,游戏结束。画叉的人先开始游戏,如果所有的棋盘格都画满了但两人都不能获胜,则游戏平局结束。

游戏在一个3X3的棋盘上进行,每个棋盘格单元处于空白、画叉或画圈状态中的一种,你的任务是确定下一轮由谁下棋:
1:轮到先手下棋;
2:轮到后手下棋;

或者是判定游戏的状态:
x:给定的棋局不是合法的棋局;
1 won:先手获胜;
2 won:后手获胜;
Draw:平局;

小东对棋类游戏很有研究,这一次三子棋比赛中,她被邀请作为评判,为了提携后进,她请你帮忙判定。


本题看似简单,其实要注意的地方还比较多,包括如何比较优雅的完成代码的编写(这我代码也写不太好)。

注意到本题的条件具有先后顺序。应该是下列顺序:
1.给定的棋局是否合法;
2.是否有获胜方;
3.平局
4.该谁下棋

这类题目建议使用一个方向向量,方向向量可以指示要判断的方向。比如,要判断一个从上到下的对角线情况,我们可以设置一个(1,1)的方向向量,当从(0,0)开始后:

= (0, 0)

sx = 0, sy = 0
for i <- 0 to 2:
sx += d[0]
sy += d[1]
即可,对于本题,设置一个判断8个方向的起始位置后,再对应设置8个方向向量即可。这样对于我们编写代码十分有利。可以最大限度的减少代码量,便于阅读。

import sys

start = [(2, 0), (1, 0), (0, 0), (0, 0), (0, 0), (0, 1), (0, 2), (2, 0)]
vector = [(0, 1), (0, 1), (0, 1), (1, 1), (1, 0), (1, 0), (1, 0), (-1, 1)]

def main():

while True:
    x = o = 0
    board = []
    for i in range(3):
        line = map(str, sys.stdin.readline().strip().split())
        if len(line[0]) < 3:
            return
        for l in line[0]:
            if l == "X":
                x += 1
            elif l == "0":
                o += 1
        board.append(list(line[0]))

    legal = True
    w1 = w2 = False

    if 0 <= x - o <= 1:
        for i in range(8):
            d = {"0": 0, "X": 0, ".": 0}
            dx, dy = start[i][0], start[i][1]
            for j in range(3):
                t = d.get(board[dx][dy])
                d[board[dx][dy]] = t + 1
                dx += vector[i][0]
                dy += vector[i][1]

            if d.get("X") == 3:
                w1 = True
            if d.get("0") == 3:
                w2 = True

        if w1 and w2 or x > o and w2 or x == o and w1:
            legal = False

    else:
        legal = False

    if legal:
        if w1:
            print "1 won"
        elif w2:
            print "2 won"
        else:
            if x + o == 9:
                print "draw"
            elif x == o:
                print "1"
            else:
                print "2"
    else:
        print "x"

if name == "__main__":

main()


*[1] 关于01背包问题及其扩展可以参考下列文章:
http://blog.csdn.net/mu399/ar...
http://blog.csdn.net/insistgo...

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/40720.html

相关文章

  • 从一个京东习生招聘题目讨论算法的选择

    摘要:生日礼物题目来源京东实习生招聘原题链接可在线提交赛码网题目描述的生日快到了,这一次,小东决定为送一份特别的生日礼物为其庆生。小东计划送一个生日卡片,并通过特别的包装让永远难忘。 最近2个月时间都比较忙,另外还有些其他的事情,几乎没有怎么做题和写文章了,害怕自己又开始懒散起来了,所以还是督促自己不断地学习和练习编码。最近还需要好好学下python面向对象的一些知识了。今天我们来分析一个J...

    894974231 评论0 收藏0
  • 从简历被拒到收割今日头条 offer,我用一年时间破茧成蝶!

    摘要:正如我标题所说,简历被拒。看了我简历之后说头条竞争激烈,我背景不够,点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收,也不过个月的时间,但这都是建立在我过去一年的积累啊。 本文是 无精疯 同学投稿的面试经历 关注微信公众号:进击的java程序员K,即可获取最新BAT面试资料一份 在此感谢 无精疯 同学的分享 目录: 印象中的头条 面试背景 准备面试 ...

    tracymac7 评论0 收藏0
  • 从简历被拒到收割今日头条 offer,我用一年时间破茧成蝶!

    摘要:正如我标题所说,简历被拒。看了我简历之后说头条竞争激烈,我背景不够,点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收,也不过个月的时间,但这都是建立在我过去一年的积累啊。 本文是 无精疯 同学投稿的面试经历 关注微信公众号:进击的java程序员K,即可获取最新BAT面试资料一份 在此感谢 无精疯 同学的分享目录:印象中的头条面试背景准备面试头条一面(Java+项目)头条...

    wdzgege 评论0 收藏0
  • 记录一下自己的春招,唯品会、360、京东offer已收、腾讯offer_call已达!!!

    摘要:春招结果五月份了,春招已经接近尾声,因为到了周五晚上刚好有空,所以简单地记录一下自己的春招过程。我的春招从二月初一直持续到四月底,截止今天,已经斩获唯品会电商前端研发部大数据与威胁分析事业部京东精锐暑假实习生的腾讯的是早上打过来的。 春招结果 五月份了,春招已经接近尾声,因为到了周五晚上刚好有空,所以简单地记录一下自己的春招过程。我的春招从二月初一直持续到四月底,截止今天,已经斩获唯品...

    freewolf 评论0 收藏1
  • 前端开发应届生面试指南(含各大公司具体指南及面试真题)

    摘要:先介绍一下本人应届前端开发一枚,非科班出身,专业是化学,大学期间开始自学前端开发,在今年春招实习和秋招的时候投了一些公司,拿到一些京东拼多多虎牙等,总体来说还算满意,特地写一篇文章来总结一下面试的那些套路。 showImg(https://segmentfault.com/img/remote/1460000011897700); 先介绍一下本人应届前端开发一枚,非科班出身,专业是化学...

    sunnyxd 评论0 收藏0

发表评论

0条评论

UnixAgain

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<