quora 电面面经

面的是 infra 组. 面试官一个 ML Engineer, 有一个类似国人小哥 shadow, 小哥好像是 data engineer. 简单互相介绍了之后开始出题. 题目没见过. 题目没写对但是还是给约了 HM 面试.  
求加米!!!
题目:

给一个没有 sort 的数列. 找到一个最大和. 不可以有连续的数字. 但是相同数字可以全选.

例子:
[1,1,2,2,2,2,2,3,3] 返回 10
[1,1,2,2,2,2,2,3,3, 4] 返回 14

我的思路先算出所有的 uniq number 的和.存一个 map 里. 例子 1 的 map 会是{(1,2), (2,10), (3, 6)}
然后用 dp求解.

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

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

-1]);
   } else {
      dp1[i] = sum + dp2[i-1];
   }
   dp2[i] = Math.max(dp2[i-1], dp1[i-1]);
}

return Math.max(dp1[map.size()], dp2[map.size()]);

请问 LZ 为什么要用map存unique的和呀？直接用dp就行了吧？

谢谢楼主。确实是跟豪斯萝卜类似的题，挺有意思的。

没有sort的话不该先根据KEY SORT一遍吗？

metrical1 发表于 2019-7-29 14:48
请问 LZ 为什么要用map存unique的和呀？直接用dp就行了吧？

已加米，请问您怎么不存hashmap直接DP呢？