Function to find Number of customers who could not get a computer

The problem, simply

A shop has n computers. You get a string of capital letters. Each letter is one customer, and each letter shows up exactly two times. The first time you see a letter, that customer walks in. The second time, that customer walks out.

A customer who walks in sits at a free computer if there is one. If every computer is taken, the customer is sent away. They do not wait. Their letter still shows up a second time later, when they leave the street. Count how many customers were sent away.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep two lists of letters: who is sitting, and who was sent away. For each letter, look through both lists.

1. If the letter is in the sitting list, they are leaving. Remove them, and a computer is free again.
2. Else if the letter is in the sent away list, they are leaving the street. Remove them. No computer changes.
3. Else it is a new customer. If the sitting list is shorter than n, add them. If not, add them to the sent away list and count one.

import java.util.*;

class Solution {
    public int runCustomerSimulation(int n, String seq) {
        List<Character> seated = new ArrayList<>();
        List<Character> away = new ArrayList<>();
        int sentAway = 0;
        for (char ch : seq.toCharArray()) {
            Character c = ch;
            if (seated.contains(c)) {
                seated.remove(c);              // leaving, a computer is free
            } else if (away.contains(c)) {
                away.remove(c);                // was sent away, frees nothing
            } else if (seated.size() < n) {
                seated.add(c);                 // new customer sits down
            } else {
                away.add(c);                   // new customer, no room
                sentAway++;
            }
        }
        return sentAway;
    }
}

How long it takes: each letter may scan both lists, which hold up to k different customers, so O(n * k). Extra room: the two lists, O(k).

Way 2: the clever way

There are only 26 letters, so the notebook can be 26 slots, one per letter. Each slot holds a small number: 0 means not here, 1 means at a computer, 2 means sent away. Looking up a slot is instant. Keep one more number: how many computers are in use.

1. Read the next letter and look at its slot.
2. Slot is 0: a new customer. If fewer than n computers are in use, mark 1 and use one more. Else mark 2 and count one sent away.
3. Slot is 1 or 2: a goodbye. If it was 1, free a computer. Set the slot back to 0.

class Solution {
    public int runCustomerSimulation(int n, String seq) {
        int[] seen = new int[26];   // 0 not here, 1 at a computer, 2 sent away
        int inUse = 0, sentAway = 0;
        for (char ch : seq.toCharArray()) {
            int c = ch - 'A';
            if (seen[c] == 0) {                 // first time: arriving
                if (inUse < n) {
                    inUse++;
                    seen[c] = 1;
                } else {
                    sentAway++;
                    seen[c] = 2;
                }
            } else {                            // second time: leaving
                if (seen[c] == 1) inUse--;      // only a seated customer frees one
                seen[c] = 0;
            }
        }
        return sentAway;
    }
}

How long it takes: one look at each letter, O(n) where n is the length of the string. Extra room: 26 slots, no matter how long the string is, O(1).

Watch out for

• Do not treat the second letter of a sent away customer as a new customer. They would be counted twice.
• Set the slot back to 0 when someone leaves, so the shop can be reused if the same letter is used again in a longer version of the problem.
• n = 0 is legal. Everyone is sent away.
• If n is 26 or more, nobody is ever sent away.

What interviewers ask next

• What if customers waited in a line instead of leaving? Keep a waiting line (a queue). When a computer frees up, the front of the line sits down.
• What if you got arrival times and how long each person stays? Sort by arrival and keep the end times in a min heap. That is the "meeting rooms" problem.
• What is the most computers ever in use at once? Track the biggest value inUse reaches.
• Which customers were sent away? Collect the letters at the moment you count them.

Remember this

Grown-up words: the notebook is a lookup table (a hash map indexed by letter), the three marks are states, and walking the string once while updating counts is a simulation in O(n) time.