Vending Machine Simulator

Problem

Simulate a vending machine. Commands: stock NAME PRICE COUNT (sets the price and the count, prints ok), insert AMOUNT (adds money, prints balance B), buy NAME and refund (prints refunded B and sets the balance to 0). buy checks in this order: unknown item, sold out, need X more (X = price - balance). On success it prints dispensed NAME change C, where C is the money left, and the balance becomes 0.

Constraints

  • 1 <= lines <= 10^4
  • all numbers are non-negative integers

Examples

Input

stock cola 150 1
insert 200
buy cola

Output

ok
balance 200
dispensed cola change 50

Solutions

Best approachTime O(n)Space O(n)

The machine object owns its state (stock and balance), and one method handles every command. The three buy checks run in a fixed order, so the message is always the same for the same situation.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process commands line by line.
 * Input   : Several lines of commands.
 * Output  : One answer per command.
 * Approach: A machine class with state.
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: The machine keeps its stock (price and count for each item) and the money the customer inserted.
        static class VendingMachine {
            private final java.util.Map<String, long[]> items = new java.util.HashMap<>();
            private long balance = 0;

            String process(String[] parts) {
                String command = parts[0];

                if (command.equals("stock")) {
                    items.put(parts[1], new long[] {Long.parseLong(parts[2]), Long.parseLong(parts[3])});
                    return "ok";
                }
                if (command.equals("insert")) {
                    balance += Long.parseLong(parts[1]);
                    return "balance " + balance;
                }
                if (command.equals("refund")) {
                    long refund = balance;
                    balance = 0;
                    return "refunded " + refund;
                }

                // Step 2: Buy. Check the item, the stock and the money, in this order.
                long[] item = items.get(parts[1]);
                if (item == null) {
                    return "unknown item";
                }
                if (item[1] == 0) {
                    return "sold out";
                }
                if (balance < item[0]) {
                    return "need " + (item[0] - balance) + " more";
                }

                // Step 3: Sell the item. The rest of the money is returned as change.
                balance -= item[0];
                item[1]--;
                long change = balance;
                balance = 0;
                return "dispensed " + parts[1] + " change " + change;
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        VendingMachine machine = new VendingMachine();
        String[] output = new String[lines.length];
        for (int i = 0; i < lines.length; i++) {
            // Step 4: Send every command line to the machine and keep its answer.
            output[i] = machine.process(lines[i].split(" "));
        }
        return output;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(String.join("\n", solve(lines)));
    }
}
Hints (1)
  1. Which check comes first when buying?