Hello all,
My friend was asked below question for amazon interview
Delivery Optimization
You are given a list of delivery orders, each represented by a unique order ID, a destination address, and the time required for delivery. Your task is to schedule these deliveries in a way that minimizes the total time taken to complete all deliveries. However, there are constraints:
- Each delivery truck can carry a maximum of k orders at a time.
- A truck can only deliver orders to addresses that are within a certain distance from each other.
Write a function minimizeDeliveryTime(Order[] orders, int k, double maxDistance) that returns the minimum total time required to complete all deliveries.
You can assume that the delivery addresses are represented as (x, y) coordinates on a 2D plane, and the distance between two points is calculated using the Euclidean distance formula.
class Order {
int orderId;
double x; // x-coordinate of destination
double y; // y-coordinate of destination
double deliveryTime; // time required for delivery
public Order(int orderId, double x, double y, double deliveryTime) {
this.orderId = orderId;
this.x = x;
this.y = y;
this.deliveryTime = deliveryTime;
}
}
double minimizeDeliveryTime(Order[] orders, int k, double maxDistance) {
// to be implemented
}
### Sample Inputs
Order[] orders = {
new Order(1, 1.0, 2.0, 5.0),
new Order(2, 3.0, 4.0, 7.0),
new Order(3, 5.0, 6.0, 3.0),
new Order(4, 7.0, 8.0, 6.0),
new Order(5, 9.0, 10.0, 4.0)
};
int k = 2;
double maxDistance = 5.0;
Python solution:
import math
class Order:
def __init__(self, id, x, y, delivery_time) -> None:
self.id = id
self.x = x
self.y = y
self.delivery_time = delivery_time
def __str__(self):
"""
String representation of the Order instance.
"""
return f"Order id: {self.id}, x is: {self.x}, y is: {self.y}, Delivery Time: {self.delivery_time}"
def __repr__(self):
"""
String representation of the Order instance.
"""
return f"Order id: {self.id}, x is: {self.x}, y is: {self.y}, Delivery Time: {self.delivery_time}"
def minimizeDeliveryTime(order_list: list[Order], k: int, max_distance: int):
order_list.sort(key=lambda order: order.delivery_time)
print(order_list)
total_time = 0
max_delivery_time = 0
all_trucks = []
while order_list:
current_truck_orders = []
i = 0
max_delivery_time = 0
while i < len(order_list) and (len(current_truck_orders) < k):
order = order_list[i]
if not current_truck_orders or euclidean_distance(current_truck_orders[0].x,current_truck_orders[0].y , order.x, order.y) <= max_distance:
current_truck_orders.append(order)
max_delivery_time = max(max_delivery_time, order.delivery_time)
order_list.pop(i)
else:
i += 1
if len(current_truck_orders) == k or i >= len(order_list):
all_trucks.append(current_truck_orders)
total_time += max_delivery_time
#if current_truck_orders:
# max_delivery_time = max(order.delivery_time for order in current_truck_orders)
# total_time += max_delivery_time
return total_time, all_trucks
def euclidean_distance(x1,y1,x2,y2):
return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)based on above, time complexity can be broken down to:
- 0(nlong) for sorting
- based on loops O(nk) worst case could be O(n^2) due to pop operation
My question: Is this a correct solution to this problem? Does this fall into dynamic programming paradigm or greedy approach taken above will always give optimized time delivery?