Entrevistas técnicas geralmente apresentam perguntas que testam sua compreensão de coleções, especialmente HashMaps. Um desafio comum envolve contar as ocorrências de elementos dentro de uma lista. Esta pergunta ajuda os entrevistadores a avaliar sua capacidade de lidar com a agregação de dados de forma eficiente e evitar armadilhas como NullPointerException.

Se você é novo no HashMaps, pode dar uma olhada em meu Decifrando os princípios básicos do HashMap: conceitos-chave para desenvolvedores Java para obter conhecimentos básicos antes de mergulhar nesta postagem.

Nesta postagem, iremos:

• Explore a declaração do problema em detalhes.
• Resolva-o com duas abordagens: uma solução if-else tradicional e o método getOrDefault().
• Discuta a complexidade de tempo e espaço de ambas as implementações.
• Uma comparação de ambas as soluções, incluindo quando usar cada uma.

Declaração do problema

Você recebe uma lista de números inteiros e sua tarefa é retornar cada número único junto com a contagem de suas ocorrências na lista. Este é um problema típico que testa sua compreensão da estrutura de dados HashMap e sua capacidade de implementá-la com eficiência.

Aqui está um exemplo:

Entrada:

[1, 2, 3, 5, 2, 1]

Saída:

{1=2, 2=2, 3=1, 5=1}

Se a lista de entrada for nula ou vazia, o resultado deverá retornar um HashMap vazio.

Solução 1: abordagem tradicional usando if-else

Nesta solução, verificamos manualmente se o HashMap já contém o número como chave. Se isso acontecer, incrementamos o valor; caso contrário, inserimos a chave com valor 1.

Código

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class CountNumbers {

    private HashMap getCount(List list) {
        // Initialize HashMap to store number counts
        HashMap map = new HashMap();

        // To avoid NullPointerException in case of a null list
        if (list != null) {
           // Iterate through each number in the list
            for (int num : list) {
                // If first occurrence, add number with count 1
                if (!map.containsKey(num)) {
                    map.put(num, 1);
                } else { // If the number already exists, increment its count by 1
                    map.put(num, map.get(num)   1);
                }
            }
        }
        return map;
    }

    public static void main(String[] args) {
        // Using ArrayList Parameterized Constructor with Collection as argument
        List numbers = new ArrayList(Arrays.asList(1, 2, 3, 5, 2, 1));

        CountNumbers nums = new CountNumbers();
        System.out.println(nums.getCount(null)); // Result -> {}
        System.out.println(nums.getCount(numbers)); // Result -> {1=2, 2=2, 3=1, 5=1}
    }
}

Explicação

1. Se a lista for nula: evitamos uma NullPointerException verificando se a lista é nula antes da iteração.
2. Iterando sobre a lista: Para cada número, se já existir no HashMap, incrementamos seu valor. Caso contrário, inserimos o valor 1.

Complexidade de tempo e espaço

• Complexidade de tempo:

  • O(n) – Percorremos a lista uma vez, onde n é o número de elementos.
  • Cada operação HashMap (put e get) leva O(1) em média, tornando a complexidade de tempo geral O(n).

• Complexidade Espacial: O(n) – Na pior das hipóteses, todos os números são únicos e armazenados no HashMap.

Solução 2: abordagem otimizada usando o método getOrDefault()

A classe Java HashMap fornece uma maneira mais limpa e concisa de lidar com esse problema com o método getOrDefault(). Ele elimina a necessidade da lógica if-else, retornando um valor padrão se a chave não for encontrada no mapa.

Definição de método

V getOrDefault(Object key, V defaultValue)

• Parâmetros:

  • key: A chave cujo valor associado deve ser retornado.
  • defaultValue: o valor a ser retornado se o mapa não contiver nenhum mapeamento para a chave.

• Retorna: o valor para o qual a chave especificada é mapeada ou defaultValue se o mapa não contiver nenhum mapeamento para a chave.

Para mais informações, você pode verificar o Javadoc oficial para HashMap.

Código

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class CountNumbers {

    private HashMap getCount(List list) {
        // Initialize HashMap to store number counts
        HashMap map = new HashMap();

        // To avoid NullPointerException in case of a null list
        if (list != null) {
            // Iterate through each number in the list
            for (int num : list) {
                // Cleaner solution using getOrDefault()
                map.put(num, map.getOrDefault(num, 0)   1);
            }
        }
        return map;
    }

    public static void main(String[] args) {
        // Using ArrayList Parameterized Constructor with Collection as argument
        List numbers = new ArrayList(Arrays.asList(1, 2, 3, 5, 2, 1));

        CountNumbers nums = new CountNumbers();
        System.out.println(nums.getCount(null)); // Result -> {}
        System.out.println(nums.getCount(numbers)); // Result -> {1=2, 2=2, 3=1, 5=1}
    }
}

Explicação

1. Usando getOrDefault(): Este método retorna o valor da chave, se ela existir. Caso contrário, ele retorna o valor padrão fornecido (neste caso, 0).
2. Inserção e incremento: O código adiciona 1 diretamente ao valor padrão, eliminando a necessidade da lógica if-else.

Vantagens de getOrDefault()

• Código mais limpo: Reduz o padrão, eliminando a necessidade de if-else.
• Mesma complexidade: O(n) para tempo e espaço.

Comparação de ambas as abordagens

Conclusão

Ambas as soluções produzirão o mesmo resultado, mas usar getOrDefault() torna o código mais conciso e legível. Esta pergunta é uma das favoritas comuns das entrevistas porque avalia sua compreensão de HashMaps, iteração e tratamento de valores nulos. Também está intimamente relacionado a problemas envolvendo contagem de frequência e agregação de dados.

Se você achou esta postagem útil, não deixe de conferir também outras postagens da série Collections Framework Essentials!

Postagens relacionadas

• Fundamentos de Java

• Fundamentos da entrevista de matriz

• Fundamentos da memória Java

Boa codificação!