Migratory Birds - Hacker Rank

📝 Descrição

Given an array of bird sightings where every element represents a bird type id, determine the id of the most frequently sighted type. If more than 1 type has been spotted that maximum amount, return the smallest of their ids.

📌 Exemplos

Exemplo 1

$arr=[1,1,2,2,3]$

Há dois avistamentos dos passáros 1 e do tipo 2, e apenas um do tipo 3. Dado o enunciado devemos pegar o menor tipo entre os candidados de maior frequência.

✅ Casos de teste

Caso 1

Entrada

$arr=[1,4,4,4,5,3]$

Saída

$result=4$

🚀 Como resolvi?

Primeiro temos de nos atentar a regra, à qual, de início, não me atentei:

Se mais de um tipo tiver a mesma frequência de avistamento, então devemos retornar o de menor id.

Beleza, depois que notamos essa regra, temos de fazer:

1. Criar um índice de frequência. Para isso, utilizaremos um dict do tipo {id: freq}
2. Iremos percorrer os valores do dict e aplicaremos a regra:

A frequência atual é maior do que a frequência máxima ou a frequência atual é igual a frequência máxima e o id do passáro é menor do que o resultado?

Se for, então temos nosso resultado.

🛠️ Implementação

def migratoryBirds(birds: list[int]) -> int:
    freq = {}
    result = sys.maxsize
    max_freq = 0
 
    for bird in birds:
        if freq.get(bird) is None:
            freq[bird] = 1
        else:
            freq[bird] += 1
 
    for bird_id, count in freq.items():
        if count > max_freq or (count == max_freq and bird_id < result):
            max_freq = count
            result = bird_id
 
    return result

🧠 O que aprendemos?

Hashes, por possuírem um tempo de busca $O(1)$ (quando não há colisão), são uma boa forma de fazermos um “lookup”. Sempre é válido lembrar que ao adotarmos esse tipo de abordagem, estamos trocando espaço por tempo, utilizando mais memória para ganhar eficiência.