Find number of customers who could not get any computer
Given an integer representing the capacity of a cyber cafe and a sequence representing entry/exit logs of customers, find the total number of customers who could not get any computer.
The first occurrence in the given sequence indicates the arrival, and the second occurrence indicates the departure for a customer. A customer cannot be serviced when the cafe capacity is full (when all computers are allocated).
For example,
sequence = “ABCDDCEFFEBGAG”
capacity = 3
Output: 2 (Customers ‘D’ and ‘F’ left unattended)
Input:
sequence = “ABCDDCBEFFEGAG”
capacity = 2
Output: 3 (Customers ‘C’, ‘D’, and ‘F’ left unattended)
The idea is to traverse the given sequence and keep track of customers who are currently inside the cyber cafe, irrespective of whether they have been allocated computers or not. We also keep track of the customers who were allocated computers. Now, two cases arise for each record:
- When a customer arrives at the cyber cafe, mark the customer as visited and allocate a computer if available; if no computer is available, increment the count of unattended customers.
- When a customer leaves the cafe, mark the customer as unvisited and deallocate the computer.
Finally, after every record is processed, return the unattended customers count. Following is the implementation in C++, Java, and Python based on the above idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <iostream> #include <string> #include <unordered_set> using namespace std; // Given entry/exit logs of customers and a cyber cafe's capacity, // find the total number of customers who could not get any computer int process(string sequence, int capacity) { // to store the count of unattended customers int unattended = 0; // keep track of the customers who were allocated computers unordered_set<char> allocated; // keep track of customers who are currently inside the cyber cafe // (irrespective of whether they are attended or not) unordered_set<char> visited; // traverse the given sequence for (char c: sequence) { // If a customer arrives at the cyber cafe if (visited.find(c) == visited.end()) { // mark customer as visited visited.insert(c); // if a computer is available, allocate it to the customer if (allocated.size() < capacity) { allocated.insert(c); } // if no computer is available, increment the unattended customer's count else { unattended++; } } // if a customer is leaving the cyber cafe, mark the customer as unvisited // and deallocate the computer else { visited.erase(c); allocated.erase(c); } } return unattended; } int main() { string sequence = "ABCDDCEFFEBGAG"; int capacity = 3; cout << process(sequence, capacity) << endl; return 0; } |
Output:
2
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
import java.util.HashSet; import java.util.Set; class Main { // Given entry/exit logs of customers and a cyber cafe's capacity, // find the total number of customers who could not get any computer public static int process(String sequence, int capacity) { // base case if (sequence == null || sequence.length() == 0) { return 0; } // to store the count of unattended customers int unattended = 0; // keep track of the customers who were allocated computers Set<Character> allocated = new HashSet<>(); // keep track of customers who are currently inside the cyber cafe // (irrespective of whether they are attended or not) Set<Character> visited = new HashSet<>(); // traverse the given sequence for (char c: sequence.toCharArray()) { // If a customer arrives at the cyber cafe if (!visited.contains(c)) { // mark customer as visited visited.add(c); // if a computer is available, allocate it to the customer if (allocated.size() < capacity) { allocated.add(c); } // if no computer is available, increment the unattended // customer's count else { unattended++; } } // if a customer is leaving the cyber cafe, mark the customer as // unvisited and deallocate the computer else { visited.remove(c); allocated.remove(c); } } return unattended; } public static void main(String[] args) { String sequence = "ABCDDCEFFEBGAG"; int capacity = 3; System.out.println(process(sequence, capacity)); } } |
Output:
2
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
# Given entry/exit logs of customers and a cyber cafe's capacity, # find the total number of customers who could not get any computer def process(sequence, capacity): # base case if not sequence: return 0 # to store the count of unattended customers unattended = 0 # keep track of the customers who were allocated computers allocated = set() # keep track of customers who are currently inside the cyber cafe # (irrespective of whether they are attended or not) visited = set() # traverse the given sequence for c in sequence: # If a customer arrives at the cyber cafe if c not in visited: # mark customer as visited visited.add(c) # if a computer is available, allocate it to the customer if len(allocated) < capacity: allocated.add(c) # if no computer is available, increment the unattended customer's count else: unattended += 1 # if a customer is leaving the cyber cafe, mark the customer as unvisited # and deallocate the computer else: visited.remove(c) if c in allocated: allocated.remove(c) return unattended if __name__ == '__main__': sequence = 'ABCDDCEFFEBGAG' capacity = 3 print(process(sequence, capacity)) |
Output:
2
The time complexity of the above solution is O(n), and requires O(n) extra space, where n is the total number of customers.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)