Problema
O Join do LINQ combina itens de duas sequências por uma chave em comum, como um join de banco de dados. Aqui os clientes são combinados com seus pedidos pelo id do cliente.
O cliente i tem id customer_ids[i] e nome customer_names[i]. Cada pedido é [customer_id, amount].
Junte os dois: para cada cliente com pelo menos um pedido, some os valores dos pedidos. Clientes sem pedidos ficam de fora, e pedidos com id desconhecido são ignorados.
Implemente join_customers_orders(customer_ids, customer_names, orders).
Entrada
customer_ids, customer_names: Os clientes (ids distintos).
orders: Pares [customer_id, amount].
Saída
Retorne "<name>:<total>" para cada cliente com pedidos, ordenados pelo total do maior para o menor e pelo nome (ordem ordinal) em caso de empate.
Restrições
1 ≤ número de clientes ≤ 10,000
0 ≤ número de pedidos ≤ 100,000; 1 ≤ amount ≤ 10^6
Exemplos
Entrada:
orders = [
[1, 50],
[2, 30],
[1, 20]
]
customer_ids = [1, 2, 3]
customer_names = ["Ada", "Lin", "Bo"]
Saída esperada:
expected = ["Ada:70", "Lin:30"]Entrada:
std::vector<std::vector<long long>> orders = {
{1, 50},
{2, 30},
{1, 20}
};
std::vector<long long> customer_ids = {1, 2, 3};
std::vector<std::string> customer_names = {"Ada", "Lin", "Bo"};
Saída esperada:
std::vector<std::string> expected = {"Ada:70", "Lin:30"};Entrada:
long[][] orders = new long[][] {
new long[] {1, 50},
new long[] {2, 30},
new long[] {1, 20}
};
long[] customer_ids = new long[] {1, 2, 3};
string[] customer_names = new string[] {"Ada", "Lin", "Bo"};
Saída esperada:
string[] expected = new string[] {"Ada:70", "Lin:30"};Explicação
Ada tem dois pedidos (50 + 20 = 70) e Lin um (30); Bo não tem nenhum e fica de fora: ["Ada:70", "Lin:30"].
Entrada:
orders = [
[8, 40],
[7, 40],
[9, 99]
]
customer_ids = [7, 8]
customer_names = ["Zoe", "Max"]
Saída esperada:
expected = ["Max:40", "Zoe:40"]Entrada:
std::vector<std::vector<long long>> orders = {
{8, 40},
{7, 40},
{9, 99}
};
std::vector<long long> customer_ids = {7, 8};
std::vector<std::string> customer_names = {"Zoe", "Max"};
Saída esperada:
std::vector<std::string> expected = {"Max:40", "Zoe:40"};Entrada:
long[][] orders = new long[][] {
new long[] {8, 40},
new long[] {7, 40},
new long[] {9, 99}
};
long[] customer_ids = new long[] {7, 8};
string[] customer_names = new string[] {"Zoe", "Max"};
Saída esperada:
string[] expected = new string[] {"Max:40", "Zoe:40"};Explicação
Os dois somam 40, então são ordenados pelo nome; o pedido do id desconhecido 9 é ignorado: ["Max:40", "Zoe:40"].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Primeiro some os valores dos pedidos por id de cliente.
Dica 2
Depois percorra os clientes e fique com os que têm total.
Dica 3
Ordene pelo total decrescente e depois pelo nome em ordem ordinal.
Complexidade esperada
tempo O(n log n), espaço extra O(n)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.