Escriba una función «runCustomerSimulation» que tome las siguientes dos entradas
- Un entero ‘n’: número total de computadoras en un café y una string:
- Una secuencia de letras mayúsculas ‘seq’: Las letras en la secuencia aparecen en pares. La primera ocurrencia indica la llegada de un cliente; el segundo indica la salida de ese mismo cliente.
Se atenderá a un cliente si hay una computadora desocupada. Ninguna letra aparecerá más de dos veces.
Los clientes que se van sin usar una computadora siempre salen antes que los clientes que actualmente están usando las computadoras. Hay como máximo 20 computadoras por café.
Para cada conjunto de entradas, la función debe generar un número que indique cuántos clientes, si es que alguno se fue sin usar una computadora. Devuelva 0 si todos los clientes pudieron usar una computadora.
runCustomerSimulation (2, “ABBAJJKZKZ”) debería devolver 0
runCustomerSimulation (3, “GACCBDDBAGEE”) debería devolver 1 ya que ‘D’ no pudo obtener ninguna computadora
runCustomerSimulation (3, “GACCBGDDBAEE”) debería devolver 0
runCustomerSimulation (1, “ABCBCA ”) debería devolver 2 ya que ‘B’ y ‘C’ no pudieron obtener ninguna computadora.
runCustomerSimulation(1, “ABCBCADEED”) debería devolver 3 ya que ‘B’, ‘C’ y ‘E’ no pudieron obtener ninguna computadora.
Fuente: Fiberlink (maas360) Entrevista
Recomendamos encarecidamente minimizar su navegador y probarlo usted mismo primero.
A continuación se presentan pasos simples para encontrar el número de clientes que no pudieron obtener ninguna computadora.
- Inicializa el resultado como 0.
- Recorre la secuencia dada. Mientras atraviesa, realice un seguimiento de las computadoras ocupadas (esto se puede hacer al realizar un seguimiento de los caracteres que han aparecido solo una vez y una computadora estaba disponible cuando aparecieron). En cualquier momento, si el conteo de computadoras ocupadas es igual a ‘n’ y hay un nuevo cliente, incremente el resultado en 1.
Lo importante es realizar un seguimiento de los clientes existentes en el café de una manera que pueda indicar si el cliente tiene una computadora o no. Tenga en cuenta que en la secuencia «ABCBCADEED», el cliente ‘B’ no obtuvo un asiento, pero aún está en el café ya que un nuevo cliente ‘C’ es el siguiente en la secuencia.
A continuación se muestran implementaciones de la idea anterior.
C++
// C++ program to find number of customers who couldn't get a resource.
#include<iostream>
#include<cstring>
using namespace std;
#define MAX_CHAR 26
// n is number of computers in cafe.
// 'seq' is given sequence of customer entry, exit events
int runCustomerSimulation(int n, const char *seq)
{
// seen[i] = 0, indicates that customer 'i' is not in cafe
// seen[1] = 1, indicates that customer 'i' is in cafe but
// computer is not assigned yet.
// seen[2] = 2, indicates that customer 'i' is in cafe and
// has occupied a computer.
char seen[MAX_CHAR] = {0};
// Initialize result which is number of customers who could
// not get any computer.
int res = 0;
int occupied = 0; // To keep track of occupied computers
// Traverse the input sequence
for (int i=0; seq[i]; i++)
{
// Find index of current character in seen[0...25]
int ind = seq[i] - 'A';
// If First occurrence of 'seq[i]'
if (seen[ind] == 0)
{
// set the current character as seen
seen[ind] = 1;
// If number of occupied computers is less than
// n, then assign a computer to new customer
if (occupied < n)
{
occupied++;
// Set the current character as occupying a computer
seen[ind] = 2;
}
// Else this customer cannot get a computer,
// increment result
else
res++;
}
// If this is second occurrence of 'seq[i]'
else
{
// Decrement occupied only if this customer
// was using a computer
if (seen[ind] == 2)
occupied--;
seen[ind] = 0;
}
}
return res;
}
// Driver program
int main()
{
cout << runCustomerSimulation(2, "ABBAJJKZKZ") << endl;
cout << runCustomerSimulation(3, "GACCBDDBAGEE") << endl;
cout << runCustomerSimulation(3, "GACCBGDDBAEE") << endl;
cout << runCustomerSimulation(1, "ABCBCA") << endl;
cout << runCustomerSimulation(1, "ABCBCADEED") << endl;
return 0;
}
Java
// JAVA program to find number of
//customers who couldn't get a resource.
class GFG
{
static int MAX_CHAR = 26;
// n is number of computers in cafe.
// 'seq' is given sequence of customer entry, exit events
static int runCustomerSimulation(int n, char []seq)
{
// seen[i] = 0, indicates that customer 'i' is not in cafe
// seen[1] = 1, indicates that customer 'i' is in cafe but
// computer is not assigned yet.
// seen[2] = 2, indicates that customer 'i' is in cafe and
// has occupied a computer.
char []seen = new char[MAX_CHAR];
// Initialize result which is number of customers who could
// not get any computer.
int res = 0;
int occupied = 0; // To keep track of occupied computers
// Traverse the input sequence
for (int i=0; i< seq.length; i++)
{
// Find index of current character in seen[0...25]
int ind = seq[i] - 'A';
// If First occurrence of 'seq[i]'
if (seen[ind] == 0)
{
// set the current character as seen
seen[ind] = 1;
// If number of occupied computers is less than
// n, then assign a computer to new customer
if (occupied < n)
{
occupied++;
// Set the current character as occupying a computer
seen[ind] = 2;
}
// Else this customer cannot get a computer,
// increment result
else
res++;
}
// If this is second occurrence of 'seq[i]'
else
{
// Decrement occupied only if this customer
// was using a computer
if (seen[ind] == 2)
occupied--;
seen[ind] = 0;
}
}
return res;
}
// Driver program
public static void main(String[] args)
{
System.out.println(runCustomerSimulation(2, "ABBAJJKZKZ".toCharArray()));
System.out.println(runCustomerSimulation(3, "GACCBDDBAGEE".toCharArray()));
System.out.println(runCustomerSimulation(3, "GACCBGDDBAEE".toCharArray()));
System.out.println(runCustomerSimulation(1, "ABCBCA".toCharArray()));
System.out.println(runCustomerSimulation(1, "ABCBCADEED".toCharArray()));
}
}
// This code is contributed by Princi Singh
Python3
# Python program function to find Number of customers who
# could not get a computer
MAX_CHAR = 26
# n is number of computers in cafe.
# 'seq' is given sequence of customer entry, exit events
def runCustomerSimulation(n, seq):
# seen[i] = 0, indicates that customer 'i' is not in cafe
# seen[1] = 1, indicates that customer 'i' is in cafe but
# computer is not assigned yet.
# seen[2] = 2, indicates that customer 'i' is in cafe and
# has occupied a computer.
seen = [0] * MAX_CHAR
# Initialize result which is number of customers who could
# not get any computer.
res = 0
occupied = 0 # To keep track of occupied
# Traverse the input sequence
for i in range(len(seq)):
# Find index of current character in seen[0...25]
ind = ord(seq[i]) - ord('A')
# If first occurrence of 'seq[i]'
if seen[ind] == 0:
# set the current character as seen
seen[ind] = 1
# If number of occupied computers is less than
# n, then assign a computer to new customer
if occupied < n:
occupied+=1
# Set the current character as occupying a computer
seen[ind] = 2
# Else this customer cannot get a computer,
# increment
else:
res+=1
# If this is second occurrence of 'seq[i]'
else:
# Decrement occupied only if this customer
# was using a computer
if seen[ind] == 2:
occupied-=1
seen[ind] = 0
return res
# Driver program
print (runCustomerSimulation(2, "ABBAJJKZKZ"))
print (runCustomerSimulation(3, "GACCBDDBAGEE"))
print (runCustomerSimulation(3, "GACCBGDDBAEE"))
print (runCustomerSimulation(1, "ABCBCA"))
print (runCustomerSimulation(1, "ABCBCADEED"))
# This code is contributed BHAVYA JAIN
C#
// C# program to find number of
// customers who couldn't get a resource.
using System;
class GFG
{
static int MAX_CHAR = 26;
// n is number of computers in cafe.
// 'seq' is given sequence of customer entry,
// exit events
static int runCustomerSimulation(int n, char []seq)
{
// seen[i] = 0, indicates that customer 'i' is not in cafe
// seen[1] = 1, indicates that customer 'i' is in cafe but
// computer is not assigned yet.
// seen[2] = 2, indicates that customer 'i' is in cafe and
// has occupied a computer.
char []seen = new char[MAX_CHAR];
// Initialize result which is number of customers
// who could not get any computer.
int res = 0;
int occupied = 0; // To keep track of occupied computers
// Traverse the input sequence
for (int i = 0; i < seq.Length; i++)
{
// Find index of current character in seen[0...25]
int ind = seq[i] - 'A';
// If First occurrence of 'seq[i]'
if (seen[ind] == 0)
{
// set the current character as seen
seen[ind] = (char)1;
// If number of occupied computers is less than
// n, then assign a computer to new customer
if (occupied < n)
{
occupied++;
// Set the current character as
// occupying a computer
seen[ind] = (char)2;
}
// Else this customer cannot get a computer,
// increment result
else
res++;
}
// If this is second occurrence of 'seq[i]'
else
{
// Decrement occupied only if this customer
// was using a computer
if (seen[ind] == 2)
occupied--;
seen[ind] = (char)0;
}
}
return res;
}
// Driver Code
public static void Main(String[] args)
{
Console.WriteLine(runCustomerSimulation(2,
"ABBAJJKZKZ".ToCharArray()));
Console.WriteLine(runCustomerSimulation(3,
"GACCBDDBAGEE".ToCharArray()));
Console.WriteLine(runCustomerSimulation(3,
"GACCBGDDBAEE".ToCharArray()));
Console.WriteLine(runCustomerSimulation(1,
"ABCBCA".ToCharArray()));
Console.WriteLine(runCustomerSimulation(1,
"ABCBCADEED".ToCharArray()));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript Program for the above approach
let MAX_CHAR = 26;
// n is number of computers in cafe.
// 'seq' is given sequence of customer entry, exit events
function runCustomerSimulation(n, seq) {
// seen[i] = 0, indicates that customer 'i' is not in cafe
// seen[1] = 1, indicates that customer 'i' is in cafe but
// computer is not assigned yet.
// seen[2] = 2, indicates that customer 'i' is in cafe and
// has occupied a computer.
let seen = new Array(MAX_CHAR).fill(0);
// Initialize result which is number of customers who could
// not get any computer.
let res = 0;
let occupied = 0; // To keep track of occupied computers
// Traverse the input sequence
for (let i = 0; i < seq.length; i++) {
// Find index of current character in seen[0...25]
let ind = seq[i].charCodeAt(0) - 'A'.charCodeAt(0);
// If First occurrence of 'seq[i]'
if (seen[ind] == 0) {
// set the current character as seen
seen[ind] = 1;
// If number of occupied computers is less than
// n, then assign a computer to new customer
if (occupied < n) {
occupied++;
// Set the current character as occupying a computer
seen[ind] = 2;
}
// Else this customer cannot get a computer,
// increment result
else
res++;
}
// If this is second occurrence of 'seq[i]'
else {
// Decrement occupied only if this customer
// was using a computer
if (seen[ind] == 2) {
occupied--;
}
seen[ind] = 0;
}
}
return res;
}
// Driver program
document.write(runCustomerSimulation(2, "ABBAJJKZKZ") + "<br>");
document.write(runCustomerSimulation(3, "GACCBDDBAGEE") + "<br>");
document.write(runCustomerSimulation(3, "GACCBGDDBAEE") + "<br>");
document.write(runCustomerSimulation(1, "ABCBCA") + "<br>");
document.write(runCustomerSimulation(1, "ABCBCADEED") + "<br>");
// This code is contributed by Potta Lokesh
</script>
Producción
0 1 0 2 3
La complejidad de tiempo de la solución anterior es O(n) y el espacio extra requerido es O(CHAR_MAX) donde CHAR_MAX es el número total de caracteres posibles en una secuencia determinada.
Este artículo es una contribución de Lokesh . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA