pocket gems 口袋宝石 新的Intern OA(有design)

口袋宝石新版oa，一共80分钟，50 minutes 两道coding，加上30 minutes 的一道design实习和全职是不一样的，实习有design全职没有 why。。。

1. movie rating：给一个数组，选最高分，可以连着选，也可以跳着选（最多跳一次）比如【1，2，-3，-2，4】 --> 应该选【1，2，-2，4】结果就是5
2. select and delete: 从一个数组里选出一个数字x，删掉，得到x分，但是同时会删除这个数组中所有的(x-1)和(x+1)，可以无限重复操作直到数组空，问最大能得几分？会有duplicates
比如【2，3，3，4，4】答案就是10，删除两个4和一个2
两道题都是dp做的


design是code review的题，给出十几行代码，求改进意见，原代码用了三个Lists装物品，物品分为装备和普通物品，有几个方法，捡物品，删除物品，找最后捡的物品

参考附件

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

风不清 发表于 2018-1-7 01:06
楼主请问下movie rating能再解释下题意啊，我太笨了没看懂，你能多给几个input, output解释下吗？谢谢楼主

抱歉回复的太晚了
用DP做
评分最多隔⼀一个选 e.g. [-5，9，-1，-3，4，5]-> 选择[9,-1,-3,4,5] 隔了了第⼀一个-5
再举几个例子～
a) [1,2,-3,2,1] , 选择[1,2,2,1] output: 6
b) [1,2,-1,-3,2,1], 选择[1,2,-1,2,1] output:6
c) [-1,-2,-3,-4], 选择[-1,-3] output: -4

wfei26 发表于 2017-12-21 16:25
Han大神，感觉第一题就是maximum subarray的变形啊，就是再加一个跳一次的case？

是挺像的，也很像house robber那道题；我是用dp数组保存了到第i位数的时候，如果一定要选第i位，最大的和是多少；但是和maximum subarray不同的地方是最后结果一定是dp数组最后两个中较大的那个

RogerChu 发表于 2017-12-17 11:53
可否请楼主分享一下movie rating的思路

dp数组保存了到第i位数的时候，如果一定要选第i位，最大的和是多少；对于每一位来说，只有两种情况，跳或者不跳。最后结果一定是dp数组最后两个中较大的那个

刚刚都已经发了～

已发私信 谢谢！

joker123 发表于 2017-12-10 07:44
已发私信 谢谢！

已发～～～

已加米 求分享 感謝樓主！

已经加米， 已私信。