Frontend School

Maximize Delivery Earnings

DSA
easy

Maximize Delivery Earnings

Easy
Dynamic Programming
Arrays
1D DP

Overview

At Shiprocket, optimizing delivery routes and courier efficiency is paramount. Couriers are assigned to various zones, each offering a certain earning potential. However, to prevent burnout and ensure sufficient rest/travel time between active delivery zones, a courier cannot take deliveries in two immediately consecutive zones. This problem aims to help us calculate the maximum possible earnings a courier can achieve under this constraint, which directly impacts route planning and incentive structures.

What you need to do / Task

You are tasked with implementing a function maxDeliveryEarnings that calculates the maximum total earnings a courier can achieve from a sequence of zones, given the constraint that no two consecutive zones can be chosen for delivery.

Input & output

Function Signature:

function maxDeliveryEarnings(earnings: number[]): number

Parameters:

  • earnings: number[] - An array where earnings[i] represents the potential earnings from making deliveries in zone i.

Return Value:

  • number - The maximum total earnings a courier can achieve following the given constraint.

Clarifications

  • Empty or single-zone list: If the earnings array is empty, the maximum earnings should be 0. If it contains only one zone, the maximum earnings will be the earning from that single zone.
  • Non-negative earnings: All earnings earnings[i] will be non-negative.

Examples

1

Example 1

Input:

earnings = [1, 2, 3, 1]

Output:

4

Note:

The courier can choose zones with earnings 1 and 3 (total 1+3=4). Choosing 2 and 1 (total 2+1=3) is also valid but yields less. Choosing 1,2,3,1 is not valid as 1,2 are consecutive.

2

Example 2

Input:

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

Output:

12

Note:

The courier can choose zones with earnings 2, 9, and 1 (total 2+9+1=12).

3

Example 3

Input:

earnings = [5]

Output:

5

Note:

Only one zone is available, so the courier takes it.

4

Example 4

Input:

earnings = []

Output:

0

Note:

No zones are available, so earnings are 0.

Constraints

Constraints & assumptions

  • 0 <= earnings.length <= 10^4
  • 0 <= earnings[i] <= 1000
  • The solution should aim for optimal time complexity, ideally O(N) where N is the number of zones.
  • The solution should aim for optimal space complexity, ideally O(1) beyond input storage.

Out of scope

  • Handling negative earnings: All earnings[i] are guaranteed to be non-negative.
  • Input validation beyond specified constraints (e.g., non-numeric values, non-array input).

What interviewers evaluate

  • Algorithmic Correctness: The solution correctly applies dynamic programming principles to solve the problem.
  • Time and Space Efficiency: The solution demonstrates an understanding of optimal time (O(N)) and space (O(1) or O(N) with justification) complexity.
  • Edge Case Handling: Correctly handles scenarios like empty or single-element input arrays.
  • Code Quality: The code is clean, readable, well-structured, and easy to understand.

Loading editor...