Problem Description

The "Immediate Food Delivery II" problem involves analyzing a list of food delivery orders to determine the percentage of customers who received their first order immediately (i.e., with a delivery time of zero minutes). Each order is represented by a set of attributes, typically including customer_id, order_date, order_id, and delivery_time. The key constraint is to consider only each customer's first order chronologically and check if it was delivered immediately. The output should be the percentage (rounded to two decimal places) of such customers relative to all customers who have placed at least one order.

The problem requires careful handling of:

• Selecting only the first order per customer (by order_date or order_id if dates are the same).
• Checking if delivery_time equals zero for that order.
• Calculating the correct percentage and formatting the result.

Thought Process

At first glance, the problem seems to require checking every order, but the focus is solely on each customer's first order. A brute-force approach would be to sort all orders for each customer, find the earliest, and then check if it was delivered immediately. However, this can be optimized.

Instead of scanning all orders repeatedly, we can:

• Group orders by customer_id.
• For each group, identify the minimum order_date (and order_id as a tiebreaker if needed).
• Count how many of these first orders have delivery_time == 0.
• Divide by the total number of unique customers to get the percentage.

Solution Approach

Let's break down the solution into clear steps:

1. Group Orders by Customer:
   • Use a hash map (dictionary) where the key is customer_id and the value is a list of that customer's orders.
2. Find First Order Per Customer:
   • For each customer, sort their orders by order_date (and order_id if needed).
   • Select the first (earliest) order.
3. Check Immediate Delivery:
   • If the first order's delivery_time is zero, increment a counter for immediate deliveries.
4. Calculate Percentage:
   • Divide the count of immediate first deliveries by the total number of unique customers.
   • Multiply by 100 and round to two decimal places (as required).

We use a hash map for efficient grouping and lookup, and a simple iteration for counting, ensuring the solution is both clear and performant.

Example Walkthrough

Suppose we have the following orders:

• Order 1: customer_id=1, order_date=2021-01-01, delivery_time=0
• Order 2: customer_id=1, order_date=2021-01-02, delivery_time=5
• Order 3: customer_id=2, order_date=2021-01-01, delivery_time=10
• Order 4: customer_id=3, order_date=2021-01-02, delivery_time=0

1. Group orders by customer:
   • Customer 1: [Order 1, Order 2]
   • Customer 2: [Order 3]
   • Customer 3: [Order 4]
2. Find the first order for each customer:
   • Customer 1: Order 1 (delivery_time=0)
   • Customer 2: Order 3 (delivery_time=10)
   • Customer 3: Order 4 (delivery_time=0)
3. Count immediate deliveries: Customers 1 and 3 had immediate delivery (2 out of 3 customers).
4. Percentage: (2 / 3) * 100 = 66.67%

The output would be 66.67.

Time and Space Complexity

Brute-Force Approach:

• For each customer, scan all orders to find the first order. If there are n orders and m customers, this is O(mn).

• Grouping orders by customer: O(n)
• Sorting each customer's orders: O(k log k) per customer, where k is the number of their orders. But typically, customers have few orders, so it's close to O(n).
• Overall: O(n) time and O(n) space, since we store all orders in the hash map.

The optimized approach is much more efficient, especially when the number of customers is much less than the number of orders.

Summary

The solution to "Immediate Food Delivery II" centers on efficiently determining, for each customer, whether their first order was delivered immediately. By grouping orders by customer and focusing only on the earliest order for each, we avoid unnecessary computation. Using hash maps and simple counting, we achieve an elegant and performant solution that is easy to implement and understand. The key insight is to focus on the first order per customer and count how many were delivered with zero delay.

Code Implementation

from typing import List, Dict

def immediate_food_delivery_percentage(orders: List[Dict]) -> float:
    from collections import defaultdict

    # Group orders by customer_id
    customer_orders = defaultdict(list)
    for order in orders:
        customer_orders[order['customer_id']].append(order)

    immediate = 0
    total = len(customer_orders)

    for order_list in customer_orders.values():
        # Sort orders by order_date, then order_id
        order_list.sort(key=lambda x: (x['order_date'], x['order_id']))
        first_order = order_list[0]
        if first_order['delivery_time'] == 0:
            immediate += 1

    if total == 0:
        return 0.00

    return round(immediate * 100 / total, 2)
    

#include <vector>
#include <unordered_map>
#include <algorithm>
#include <string>

using namespace std;

struct Order {
    int customer_id;
    string order_date;
    int order_id;
    int delivery_time;
};

double immediateFoodDeliveryPercentage(const vector<Order>& orders) {
    unordered_map<int, vector<Order>> customerOrders;
    for (const auto& order : orders) {
        customerOrders[order.customer_id].push_back(order);
    }
    int immediate = 0;
    int total = customerOrders.size();
    for (auto& kv : customerOrders) {
        auto& orderList = kv.second;
        sort(orderList.begin(), orderList.end(), [](const Order& a, const Order& b) {
            if (a.order_date != b.order_date)
                return a.order_date < b.order_date;
            return a.order_id < b.order_id;
        });
        if (orderList[0].delivery_time == 0) {
            immediate++;
        }
    }
    if (total == 0) return 0.0;
    return round(immediate * 10000.0 / total) / 100.0;
}
    

import java.util.*;

class Order {
    int customer_id;
    String order_date;
    int order_id;
    int delivery_time;
    public Order(int customer_id, String order_date, int order_id, int delivery_time) {
        this.customer_id = customer_id;
        this.order_date = order_date;
        this.order_id = order_id;
        this.delivery_time = delivery_time;
    }
}

public class Solution {
    public double immediateFoodDeliveryPercentage(List<Order> orders) {
        Map<Integer, List<Order>> customerOrders = new HashMap<>();
        for (Order order : orders) {
            customerOrders.computeIfAbsent(order.customer_id, k -> new ArrayList<>()).add(order);
        }
        int immediate = 0;
        int total = customerOrders.size();
        for (List<Order> orderList : customerOrders.values()) {
            orderList.sort((a, b) -> {
                int cmp = a.order_date.compareTo(b.order_date);
                if (cmp != 0) return cmp;
                return Integer.compare(a.order_id, b.order_id);
            });
            if (orderList.get(0).delivery_time == 0) {
                immediate++;
            }
        }
        if (total == 0) return 0.0;
        return Math.round(immediate * 10000.0 / total) / 100.0;
    }
}
    

function immediateFoodDeliveryPercentage(orders) {
    const customerOrders = new Map();
    for (const order of orders) {
        if (!customerOrders.has(order.customer_id)) {
            customerOrders.set(order.customer_id, []);
        }
        customerOrders.get(order.customer_id).push(order);
    }
    let immediate = 0;
    const total = customerOrders.size;
    for (const orderList of customerOrders.values()) {
        orderList.sort((a, b) => {
            if (a.order_date !== b.order_date) {
                return a.order_date < b.order_date ? -1 : 1;
            }
            return a.order_id - b.order_id;
        });
        if (orderList[0].delivery_time === 0) {
            immediate++;
        }
    }
    if (total === 0) return 0.00;
    return Math.round(immediate * 10000 / total) / 100;
}