Skip to main content

合并箱子重量 —— 亚马逊 2022 面试题

Merge weight (Amazon 2022 OA)

Published 2 min readMarkdown
合并箱子重量 —— 亚马逊 2022 面试题

#leetcode #算法

题目

Consider n packages, where packageWeights[i] represents the weight of the i th package, You can combine i th and i+1 th package if packageWeights[i] <packageWeights[i+1] and then discard the i th package. After this operation number of packages reduces by 1 and weight of i+1 th package increases by packageWeights[i]. You can merge as many times as you want. Find the max possible weight of the package that can be achieved after any sequence of merge operations

Eg packageWeights =[2,9,10,3, 7] optimal order:

  • iteration 1 combine packages at index 2 and 3 ->new packageWeights =[2,19,3,7]
  • iteration 2 combine packages at index 1 and 2 ->new packageWeights =[21,3,7]
  • iteration 3 combine packages at index 2 and 3 ->new packageWeights =[21,10]
  • No more packages can be combined. The weight of the heaviest package is 21 Result:21

分析

其实例子中给出来的分析已经足够。在理解这个问题的时候,可以直接尝试着用程序化的语言来理解,比如:

  1. packageWeights =[2,9,10,3, 7]; var max = 0;
  2. var index = 4; value = 7; current = 7; max = 7;
  3. index = 3; value = 3; value < current; current = 7 + 3; max = 10;
  4. index = 2; value = 10; value !< current; current = value(10); max = 10;
  5. index = 1; value = 9; value < current; current = 10 + 9; max = 19;
  6. index = 0; value = 2; value < current; current = 19 + 2; max = 21;
  7. return max;

代码

var packageCount = packageWeights.Length;
var max = 0;
if (packageCount == 0) { return max; }

var current = packageWeights[^1];
for (int index = packageCount - 1; index >= 0; index--)
{
    var value = packageWeights[index];
    current = value < current
        ? current + value
        : value;
    max = Math.Max(max, current);
}

return max;

有没有发现,在上一步中,当你用程序化的思维去理解这个问题的时候,编程就成了一种自然而然的语言转换了。 时间复杂度:O(n) 空间复杂度:O(1)

测试案例

如果你是在面对面的跟面试官沟通的话,往往面试官会问你要怎么设计测试用例。 其实这个也是考察你对编码的严谨性的。

本题的测试案例可以这样逐步来想:

  1. 只有一条重量数据:[TestCase(new[] { 2 }, ExpectedResult = 2)]
    1. 增加一个大重量的包在前面:[TestCase(new[] { 10, 2 }, ExpectedResult = 10)]
      1. 增加一个相同重量的包在前面:[TestCase(new[] { 10, 10, 2 }, ExpectedResult = 10)]
      2. 增加一个相同重量的包在后面:[TestCase(new[] { 10, 2, 2 }, ExpectedResult = 10)]
    2. 增加一个大重量的包在后面:[TestCase(new[] { 2, 10 }, ExpectedResult = 12)]
  2. 合并之后有两个包:[TestCase(new[] { 2, 9, 10, 3, 7 }, ExpectedResult = 21)]
  3. 合并之后只有一个包:[TestCase(new[] { 2, 9, 10, 3, 8 }, ExpectedResult = 32)]

About the author

  • 一个喜欢写代码的游戏玩家。 做了个原创的益智玩具(迷历),申请到了两个国家专利,玩过上百款游戏。 有个可爱的老婆,希望把日常的生活过成诗。

No comments yet. Be the first to comment.

More from this blog