空气床电面 1。28

我是朋友内推的，hr非常拖拉，从开始聊到电面时间隔了快20天，面试官是一位中国大叔，问的是一个类似backtracking的题，好像有更好的解法但是我没想出来。
例如给一个list[0.2,0.9,1.3,4.5] 这个list的sum是6.9，取整是6. 每个数字都可以round up/down。比如0.2可以变成0也可以变成1.

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

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

望的是时间复杂度降低，所以这里答得不算很好。大叔说it's good to me.后来就结束了。大家有idea的可以share一下。

过了三天hr说还需要加一轮电面，可能觉得我写的不够流畅或者followup答的不够好。希望对大家有帮助。

这题是面经题. 你可以O（nlogn） 先把所有都当做down 这时候肯定偏小  
然后尝试把差值最小的变成up 也就是对total来说是更优的

直到等于target

zhangzitong001 发表于 2019-2-1 13:16
这题是面经题. 你可以O（nlogn） 先把所有都当做down 这时候肯定偏小  
然后尝试把差值最小的变成up 也就是 ...

为啥要nlogn把所有都当做DOWN? 不是直接扫一遍就行了吗？

hpplayer 发表于 2019/02/01 13:29:22


为啥要nlogn把所有都当做DOWN? 不是直接扫一遍就行了吗？

i mean 最终overall.  你要根据difference 排序 排序需要nlogn.

请问楼主是要取整一样还是round一样，深秋面经里是round price。如果是round price，你的例子应该sum算7吧。

tangvictor 发表于 2019-2-12 11:52
请问楼主是要取整一样还是round一样，深秋面经里是round price。如果是round price，你的例子应该sum算7吧 ...

不好意思过了一周多我有点不记得具体是哪种了，但bt做法应该是类似的。仅供参考~