Las entrevistas técnicas a menudo incluyen preguntas que ponen a prueba tu comprensión de las colecciones, especialmente HashMaps. Un desafío común implica contar las apariciones de elementos dentro de una lista . Esta pregunta ayuda a los entrevistadores a evaluar su capacidad para manejar la agregación de datos de manera eficiente y evitar errores como NullPointerException.

Si eres nuevo en HashMaps, quizás quieras consultar mi Descifrando los conceptos básicos de HashMap: conceptos clave para desarrolladores de Java para obtener conocimientos básicos antes de sumergirte en esta publicación.

En esta publicación, vamos a:

• Explore la enunciado del problema en detalle.
• Resuélvelo con dos enfoques: una solución tradicional if-else y el método getOrDefault().
• Discute la complejidad temporal y espacial de ambas implementaciones.
• Una comparación de ambas soluciones, incluido cuándo usar cada una.

Declaración del problema

Se le proporciona una lista de números enteros y su tarea es devolver cada número único junto con el recuento de sus apariciones en la lista. Este es un problema típico que pone a prueba su comprensión de la estructura de datos de HashMap y su capacidad para implementarla de manera eficiente.

Aquí tienes un ejemplo:

Aporte:

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

Producción:

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

Si la lista de entrada es nula o está vacía, el resultado debería devolver un HashMap vacío.

Solución 1: enfoque tradicional usando if-else

En esta solución, verificamos manualmente si el HashMap ya contiene el número como clave. Si es así, incrementamos el valor; si no es así, insertamos la clave con un valor de 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}
    }
}

Explicación

1. Si la lista es nula: evitamos una NullPointerException comprobando si la lista es nula antes de iterar.
2. Iterando sobre la lista: Para cada número, si ya existe en el HashMap, incrementamos su valor. En caso contrario lo insertamos con un valor de 1.

Complejidad del tiempo y el espacio

• Complejidad del tiempo:

  • O(n) – Recorremos la lista una vez, donde n es el número de elementos.
  • Cada operación de HashMap (poner y obtener) toma O(1) en promedio, lo que hace que la complejidad del tiempo general sea O(n).

• Complejidad espacial: O(n) – En el peor de los casos, todos los números son únicos y se almacenan en HashMap.

Solución 2: enfoque optimizado utilizando el método getOrDefault()

La clase Java HashMap proporciona una forma más limpia y concisa de manejar este problema con el método getOrDefault(). Elimina la necesidad de la lógica if-else al devolver un valor predeterminado si la clave no se encuentra en el mapa.

Definición del método

V getOrDefault(Object key, V defaultValue)

• Parámetros:

  • clave: la clave cuyo valor asociado se devolverá.
  • defaultValue: el valor que se devolverá si el mapa no contiene ningún mapeo para la clave.

• Devuelve: el valor al que se asigna la clave especificada, o valor predeterminado si el mapa no contiene ninguna asignación para la clave.

Para obtener más información, puedes consultar el Javadoc oficial de 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}
    }
}

Explicación

1. Usando getOrDefault(): Este método devuelve el valor de la clave si existe. De lo contrario, devuelve el valor predeterminado proporcionado (en este caso, 0).
2. Insertar e incrementar: el código agrega directamente 1 al valor predeterminado, eliminando la necesidad de la lógica if-else.

Ventajas de getOrDefault()

• Código más limpio: Reduce el texto repetitivo al eliminar la necesidad de if-else.
• Misma complejidad: O(n) tanto para tiempo como para espacio.

Comparación de ambos enfoques

Conclusión

Ambas soluciones producirán el mismo resultado, pero usar getOrDefault() hace que el código sea más conciso y legible. Esta pregunta es una de las favoritas de las entrevistas porque evalúa su comprensión de HashMaps, iteración y manejo de valores nulos. También está estrechamente relacionado con problemas que involucran conteo de frecuencias y agregación de datos.

Si esta publicación te resultó útil, ¡asegúrate de consultar también otras publicaciones de la serie Collections Framework Essentials!

Publicaciones relacionadas

• Fundamentos de Java

• Conceptos básicos de la entrevista de matriz

• Conceptos básicos de la memoria Java

¡Feliz codificación!