编程马拉松试题_发布版

1/16招商银行第一届编程马拉松试题2015年12月21日–12月28日算法类1、可变数组求和（30分）给定一个整数数组，sum_range(m,n)函数给出指定下标m,n之间的数值之和（m=n）update(idx,value)函数修改第idx位的数值为value要求：•你的代码需要定义一个NumArray类，它包括以上两个函数•数组只能通过update函数更新nums=[2,5,8,9]sum_range(1,3)-22update(2,1)sum_range(1,3)-152/162、给出数组计数结果（30分）给定一个整数数组nums，你需要返回一个等长的counts数组，count[i]的取值是nums[i]右侧比它小的数值的个数。因此，counts数组为[2,0,2,1,0]3、字符串求值运算（40分）给定一个由数字0-9组成的字符串S，给定一个数值N，请找出该字串内所含数字的所有组成N的可能组合。注意：只能使用加、减、乘三种操作符号。nums=[3,1,8,4,2]3的右侧有2个数字比它小（1，2）1的右侧有0个数字比它小8的右侧有2个比它小（4，2）4的右侧有1个比它小（2）2的右侧有0个比它小123,6-[1+2+3,1*2*3]232,8-[2*3+2,2+3*2]105,5-[1*0+5,10-5]00,0-[0+0,0-0,0*0]“3456237490”,9191-?3/164、获得最多奖金（40分）给定n个小球，balls[n]，位置从0到n-1标定，每个球上都标定了一个正整数，用数组nums[n]表示。现在，你需要选定一个小球将它移除，于此同时，你将获得以它为中心、相邻三个小球的数值的乘积值所对应的奖金。假设你选定的是第k个位置的小球，那么你获得的奖金为num[k-1]*num[k]*num[k+1]。你的任务是，找出可能获得的最多的奖金值。约束：•0≤n≤500,0≤nums[i]≤100•nums[-1]=nums[n]=1。这些特殊位置的球不存在，也不能被移除。给定数组[3,1,5,8]返回值167nums=[3,1,5,8]--[3,5,8]--[3,8]--[8]--[]coins=3*1*5+3*5*8+1*3*8+1*8*1=1674/165、移除无效括号（40分）给定一个字符串，它包含了小括号字符。请你移除最少的小括号字符，使得剩余的小括号字符能够成对匹配。注意，字符串中可能包含其他的字符。“()())()-[“()()(),“(())()]“(a)())()-[“(a)()(),“(a())()]“)(-[]5/166、搜寻单词（50分）给定一个二维的字母表，再给定一个单词数组，请在二维字母表里找到单词数组里可能出现的组合。构成单词的字母必须在二维表中相邻，或者水平，或者垂直。在同一个单词里，每个字母仅能被使用一次。例如，给定单词组words=[“oath”,pea,eat,rain]，二维字母表为board=[‘oaan’,’etae’,’ihkr’,’iflv’]：输出值为[“eat,oath]board=[['o','a','a','n'],[‘e','t','a','e'],[‘i','h','k','r'],[‘i',‘f',‘l','v']]6/167、正则表达式匹配（50分）请实现正则表达式中的‘.’与‘*’功能。在正则表达式中，’.’代表匹配一个字符，’*’代表匹配零个或多个字符。要求：•匹配须贯穿整个字符串•不能直接使用Python，JAVA等的正则表达式类库•实现的函数要求为boolisMatch(constchar*s,constchar*p)•注意是广义匹配，最后一个例子是正确的isMatch(aa,a)→falseisMatch(aa,aa)→trueisMatch(aaa,aa)→falseisMatch(aa,a*)→trueisMatch(aa,.*)→trueisMatch(ab,.*)→trueisMatch(aab,c*a*b)→true部分匹配也为true7/168、求得中位数（50分）给定两个整数型数组A1和A2，对应的大小分别是m和n，假设这两个数组都是排好序的，请你找到两个数组的中位数。要求：•时间复杂度为O(log(m+n))假设：A1=[1,5,12,23,36]A2=[3,4,17,21,31,48]返回值为：17假设：A1=[1,12,15,26,37]A2=[2,13,17,30,45]返回值为：168/169、纽约街道清扫路径（70分）问题描述：假定你是纽约市负责街道清扫的长官。你需要在保持街道清洁的同时降低开销，所以你需要在交通规则的同时把重复清扫的街道数量减到最少。这个问题的目标是保证所有街道至少清扫一次的同时把重复清扫的街道减到最少。（在输入的地图上就是每条线段至少走一次）。请为清洁工司机找出一条最佳路径。输入约束：用户会在一行输入两个整数（h和w）到你的程序，这两个整数分别告诉你输入的街道地图行数和列数。下一行是一个大写字母，告诉你从哪里开始。接着就是一个有h行和w列的ASCII地图。你的路径应该在开始点结束。你会被给出一个ASCII的图。路口会用大写字母A-Z命名。线段（街道）把路口连接起来。街道可能是双向的（用-或者|表示）或者是单向的（向上用^表示，向下用v表示，向左用表示，向右用表示），你不能违反交通规则的指示反向行驶。双向街道（-或者|）只需要走一次。输出描述你的程序应该输出路口走过的顺序和你清扫的街道数量。输入33FA-B-C||vDE-F^vvG-HI输出（仅供参考）9/16人工观察输入的地图，所有街道至少走一次的最短路径可能是F-I-H-G-D-E-H-G-D-A-B-C-F-E-B-C-F，但可能有其他更短的路径。10/16综合类10、证书格式转换工具。参见附件。（200分）注：1)11-14题为开放性试题，总分为400分封顶，即每道题分数为200，任意选做2题，多于2题不会获得额外分数。2)你的解答里，应当包含设计方案，以及至少一个核心模块的原型源代码。方案里应当描述实现原理，所需组件，以及具体的接口设计。代码可以进行演示验证。评委对两者分别评定分数，即，如果仅提交设计方案，也能获得相应部分的评分，但相对完整的回答而言得分较少。3)由于时间的限制，允许你对所依赖的基础组件以及调用接口进行假设，但你需要在方案里描述清楚。评委根据你的设计的合理性与简洁度进行评分。4)鼓励各位以Markdown格式提交设计方案，有加分。5)建议您的代码在RHEL6.4或7.1版本下运行通过，如有特殊要求，请在README文件中描述清楚6)Python语言的版本要求是2.7大版本下运行通过，其他语言没有强制要求，请在REDAME文件中描述清楚11/1611、设计一个监控系统。对它的要求为：A.获取实时数据（延迟控制在秒级，N秒）B.用户能够快速定义所需数据C.用户能够在界面上快速定义所需报表或视图请给出你的设计方案，要求为：A.可以使用任何能够实现目标的开源工具。B.方案需要描述清楚实现原理、所需组件与接口C.需要给出至少一个核心模块的原型代码，并能够有输入输出进行验证12/1612、请设计一个并发调度工具。这个工具的作用是帮助用户实现快速调度，例如，用户需要在2000个目标机器上运行一个脚本，或者，用户需要启动10个相同或者不同的作业，调度工具能够让用户以最大的效率完成所需工作。你需要考虑的问题：A.方案需要描述清楚实现原理、所需组件与接口。B.请尽量考虑到各种异常情况。C.该工具需要帮助用户记录数据输出，方便用户汇总。D.该工具需要记录详细的调度日志输出，方便用户排障。E.请给出原型代码，并能够进行实际演示。13/1613、请给出一个实现弹性伸缩的调度框架。参考AmazonEC2的功能，请设计一个调度框架，根据应用负载情况，实现计算资源的弹性伸缩。例如，双十一活动时，你的web应用服务器能够根据访问压力进行水平扩展，当访问负载超过阈值时，调度框架计算所需资源，并自动部署。要求：A.方案需要描述清楚实现原理、所需组件与接口。B.你可以自由设定所依赖的必要组件与调用接口。评委根据你的设计的合理性与简洁度进行评分。C.你的方案里需要考虑数据中心的容量限制D.你的方案里需要考虑到多中心部署E.请给出至少一个核心组件的原型代码14/1614、请设计一个自动化发布系统Apollo是亚马逊内部在2003年上线的自动化部署系统，它是将开发机、测试机、预发机、生产机进行统一部署的工具，确保所有的环境一致，涉及集群上内千台服务器。2014年，Apollo处理了5万次部署，平均每秒大于一次。Apollo让用户通过自助服务的形式自定义发布任务、进行配置变更，并记录跟踪整个变化过程。Apollo支持多中心、在线、批次、滚动部署，用户能够实时、可视化的看到部署的进度状况，如果发布异常，并且问题节点数达到阈值，则系统自动进行回滚处理，将影响降到最低，以保障系统的可用性。现在，请你参考Apollo的功能，设计一个自动化发布系统。请考虑以下几点：A.请在方案中描述实现原理、所需组件与接口B.可以利用开源组件实现你的目标C.你可以自由设定所依赖的必要组件与调用接口。评委根据你的设计的合理性与简洁度进行评分。D.该系统要能够对配置变更进行管理E.处于简化考虑，设定该发布系统单纯在Linux平台上部署，以RHEL7.1版本为标准模板F.请给出一个或多个核心模块的原型代码15/16其他说明1.请登录的项目，namespace为自己的用户名，项目的权限应该设为Private。招行的同事请直接登录code网站，用域账号即可登录；厂商工程师则请联系李建强（[e-mail]）申请账号。如果因网络访问权限问题无法访问，因git本身是分布式版本控制系统，也可以离线进行版本控制，最终提交一个离线的git仓库。项目创建示例：16/162.所有题目请按题号分类放在marathon项目中，比如第一道题放在文件夹01，第二道题放在文件夹02，以此类推。每道题具体的实现，其文件名不限。3.总分为1000，为期一周。代码提交截止时间为2015年12月28日中午12点。4.对试题有任何疑问的地方，请发送邮件给吴陶和李建强，我们将统一进行解答，所有问题公开回复给所有参赛人员。评委列表：（吴陶）[e-mail]（李建强）[e-mail]（林耘毅）[e-mail]（郑少忠）[e-mail]（李旬保）[e-mail]（陈进芬）[e-mail]