Amazon Interviews · 1

One of the questions from the OA

Question:

Imagine Amazon warehouses arranged in a circle. You can start at any warehouse and move either clockwise or counterclockwise, but you must stick with your chosen direction for the entire process.

Each warehouse has a different number of items, and the goal is to redistribute them so that every warehouse ends up with the same amount. It’s guaranteed that this is possible.

The distance between neighboring warehouses is 1 unit, and moving an item costs the same as the distance it travels. The goal is to find the best starting point and direction to minimize the total cost.

Example

Let’s say the warehouses have the following counts: 3 -> 4 -> 6 -> 6 -> 6 (looping back to 3).

To balance the items:

1. Start at the third warehouse (with 6 items). Collect 1 item from the 3rd, 4th, and 5th warehouses.

2. Deliver 2 items to the first warehouse (which has 3) and 1 item to the second warehouse (which has 4).

By the end, each warehouse will have 5 items, and the total cost would be 1 + 2 + 4 = 7.

Total Cost Breakdown:

• Moving from the 5th warehouse to the 1st warehouse costs 1.

• Moving from the 4th warehouse to the 1st warehouse costs 2.

• Moving from the 3rd warehouse to the 2nd warehouse costs 4.