Order Shopping Cart Items for Pickup: Frozen Last, Minimum Walking Distance

Return the items in a customer's shopping cart in the order a shopper should pick them up in the store. Frozen items must come after all other items, and the order should also keep the aisles of consecutive picks close together, so that the shopper's total walking distance is as small as possible. The report describes this as the third part of a multi-part shopping cart coding exercise; the earlier parts were not described. The input format was not reported; the illustration below is an assumption to make the task concrete. ```text items (name, aisle, frozen) illustrative bread 2 no peas 3 yes rice 5 no eggs 7 no ice cream 9 yes the shopper starts at the entrance, next to aisle 0 ``` ```hint Two phases The frozen rule splits the trip into two phases. Think about where the first phase should end so that the second phase starts in a good place. ``` ### Constraints and Clarifications - Reported: frozen items go last, and the order should reduce the total distance the shopper walks between aisles. - Inputs are guaranteed to be valid, and the tests are provided, so there is no need to validate input or write test cases. - Not given: the store layout and how distance between aisles is measured, where the shopper starts, and whether the walk to the checkout counts. A common model treats aisles as numbered positions along one walkway, with a walk from aisle $a$ to aisle $b$ costing $\lvert a - b \rvert$. Confirm the model with the interviewer. ### Clarifying Questions - How is the distance between two aisles measured: by the difference of their numbers, or from a store map? - Where does the shopper start, and does the walk from the last item to the checkout count? - Must every frozen item be picked after every non-frozen item, or only last within its own aisle? - How should several items in the same aisle be ordered? ### What a Strong Answer Covers - Pins down the distance model, the start and the end of the trip before optimizing - Recognizes the two phases forced by the frozen rule, and why sorting by aisle alone does not minimize the distance - Chooses the walking direction of each phase correctly, and handles empty phases, shared aisles and ties - Computes the distance of the returned order and states the complexity - Discusses what changes, and what becomes hard, with a realistic two-dimensional store layout ### Follow-up Questions - The store map is a grid of parallel aisles joined by cross-aisles at both ends. How does the distance model change, and what does that do to your algorithm? - Frozen items only need to be picked in the last part of the trip rather than strictly after everything else. What changes? - A large order is split between two shoppers. How would you divide the items? - How would you test that your order really minimizes the distance?