Frontend School

Delivery Route Optimization with Retrace

DSA
medium

Delivery Route Optimization with Retrace

Medium
Stack
Simulation
History

Overview

Bigbasket delivery executives follow dynamic routes to fulfill orders. Due to various real-world factors like traffic, customer availability, or last-minute order changes, drivers often need to modify their planned routes. This problem simulates a simplified route management system that allows adding new stops, marking stops as delivered, and crucially, retracing previous actions. This functionality is essential for drivers to adapt quickly and maintain an efficient delivery flow.

What you need to do / Task

You are tasked with implementing a function that processes a sequence of route management operations and returns the final state of the delivery route.

Your function should handle the following operations:

  1. ADD <locationId>: Adds a new stop identified by locationId to the end of the current route. locationId will be a string.
  2. DELIVER: Marks the last stop in the current route as delivered. If the route is empty, this operation has no effect.
  3. RETRACE <k>: Undoes the last k successful ADD or DELIVER operations.
    • If an ADD <locationId> operation is undone, locationId is removed from the route.
    • If a DELIVER operation is undone, the locationId that was previously delivered is added back to the route.
    • If k is greater than the number of available operations to undo, retrace all available operations.

The final route should be returned as an array of locationId strings, ordered from the first stop to the last.

Input & output

Input: operations: An array of strings, where each string represents a single operation. * ADD <locationId>: e.g., "ADD Bengaluru" * DELIVER: e.g., "DELIVER" * RETRACE <k>: e.g., "RETRACE 2" (where k is an integer string)

Output: An array of strings (string[]) representing the locationIds in the final route, ordered from start to end.

Clarifications

  • locationId strings will consist of alphanumeric characters and spaces.
  • k in RETRACE <k> will always be a positive integer.
  • Operations are processed sequentially.
  • The system should maintain the order of stops in the route.

Examples

1

Example 1

Input:

operations = ["ADD A", "ADD B", "DELIVER", "ADD C"]

Output:

["A","C"]

Note:

  1. ADD A: Route = [A]. History = [ADD A]
  2. ADD B: Route = [A, B]. History = [ADD A, ADD B]
  3. DELIVER: Route = [A]. History = [ADD A, ADD B, DELIVER B] (B was delivered)
  4. ADD C: Route = [A, C]. History = [ADD A, ADD B, DELIVER B, ADD C] Final route: [A, C]
2

Example 2

Input:

operations = ["ADD P", "ADD Q", "DELIVER", "ADD R", "RETRACE 2", "ADD S"]

Output:

["P","Q","S"]

Note:

  1. ADD P: Route = [P]. History = [ADD P]
  2. ADD Q: Route = [P, Q]. History = [ADD P, ADD Q]
  3. DELIVER: Route = [P]. History = [ADD P, ADD Q, DELIVER Q]
  4. ADD R: Route = [P, R]. History = [ADD P, ADD Q, DELIVER Q, ADD R]
  5. RETRACE 2:
    • Pop ADD R from history: Route becomes [P] (R removed).
    • Pop DELIVER Q from history: Route becomes [P, Q] (Q added back). History is now [ADD P, ADD Q]
  6. ADD S: Route = [P, Q, S]. History = [ADD P, ADD Q, ADD S] Final route: [P, Q, S]
3

Example 3

Input:

operations = ["ADD X", "DELIVER", "DELIVER", "RETRACE 5", "ADD Y"]

Output:

["Y"]

Note:

  1. ADD X: Route = [X]. History = [ADD X]
  2. DELIVER: Route = []. History = [ADD X, DELIVER X]
  3. DELIVER: Route = []. History unchanged (route was empty, no effect).
  4. RETRACE 5:
    • Pop DELIVER X from history: Route becomes [X] (X added back).
    • Pop ADD X from history: Route becomes [] (X removed). History is now []. k=5 was reduced to 2 as only 2 operations were available.
  5. ADD Y: Route = [Y]. History = [ADD Y] Final route: [Y]

Constraints

Constraints & assumptions

  • operations array length: 0 <= operations.length <= 10^5
  • locationId string length: 1 <= locationId.length <= 20
  • k in RETRACE <k>: 1 <= k <= 10^5
  • The total number of ADD operations will not exceed 10^5.
  • Memory usage should be efficient, proportional to the number of active stops and recorded history.
  • Time complexity should be optimal, aiming for O(N) where N is the total number of operations, or O(N + M) where M is the total number of items pushed/popped across all operations.

What interviewers evaluate

  • Correctness: The solution accurately processes all operation types, including edge cases for DELIVER and RETRACE.
  • Data Structures: Appropriate use of stacks to manage the current route and operation history.
  • Efficiency: The solution demonstrates optimal time and space complexity for the given constraints.
  • Code Quality: Clean, readable, and well-structured code with appropriate variable names and comments where necessary.

Loading editor...