Frontend School

Warehouse Robot Path Optimization

DSA
medium

Warehouse Robot Path Optimization

Medium
Dynamic Programming
Arrays

Overview

Amazon's fulfillment centers rely heavily on automated robots for efficient inventory management. One critical task is optimizing the path for robots collecting items from storage bins arranged in a linear fashion. Maximizing the number of items collected directly impacts throughput and operational efficiency.

What you need to do / Task

Your task is to implement a function that calculates the maximum total number of items a robot can collect from a series of bins, given a specific movement constraint:

  1. The robot is given a list of items where items[i] represents the number of items in bin i.
  2. If the robot chooses to collect items from bin i, it must skip the immediately next bin (i+1) and can only proceed to consider bin i+2 or beyond.
  3. If the robot chooses to skip bin i (i.e., not collect items from it), it can then proceed to consider bin i+1.
  4. The robot starts before the first bin (index 0) and wants to maximize the total items collected.

Input & output

  • Input: items: number[] - An array of non-negative integers where items[i] is the number of items in the i-th bin.
  • Output: number - The maximum total number of items the robot can collect.

Clarifications

  • An empty items array should result in 0 items collected.
  • An items array with a single element [x] means the robot can only collect x items.
  • All item counts items[i] are non-negative.

Examples

1

Example 1

Input:

items = [2, 7, 9, 3, 1]

Output:

12

Note:

To maximize items, the robot collects from bins at indices 0 (2 items), 2 (9 items), and 4 (1 item). Total: 2 + 9 + 1 = 12. If it collected from 1 (7 items), it would skip 2, then collect from 3 (3 items). Total: 7 + 3 = 10. This is less than 12.

2

Example 2

Input:

items = [1, 2, 3, 1]

Output:

4

Note:

The optimal path is to collect from bins at indices 0 (1 item) and 2 (3 items). Total: 1 + 3 = 4. Collecting from 1 (2 items) and 3 (1 item) would yield 2 + 1 = 3.

3

Example 3

Input:

items = [10]

Output:

10

Note:

With only one bin, the robot collects all 10 items.

Constraints

Constraints & assumptions

  • 1 <= items.length <= 10^4
  • 0 <= items[i] <= 1000

Out of scope

  • Error handling for invalid input types (e.g., items not an array, non-numeric values).
  • Real-world robot navigation complexities beyond the described movement rule.

What interviewers evaluate

  • Correct application of dynamic programming principles.
  • Accurate handling of base cases and edge conditions for the given constraints.
  • Optimal time and space complexity for the solution.
  • Clarity and readability of the code, demonstrating good software engineering practices.

Loading editor...