На технических собеседованиях часто встречаются вопросы, проверяющие ваше понимание коллекций, особенно HashMaps. Одна из распространенных проблем связана с подсчетом вхождений элементов в список. Этот вопрос помогает интервьюерам оценить вашу способность эффективно обрабатывать агрегацию данных и избежать таких ошибок, как NullPointerException.

Если вы новичок в HashMaps, возможно, вы захотите ознакомиться с моим Cracking the Basics of HashMap: Key Concepts for Java Developers для получения базовых знаний, прежде чем углубляться в этот пост.

В этом посте мы:

• Подробно изучите постановку задачи.
• Решите ее двумя способами: традиционным решением if-else и методом getOrDefault().
• Обсудите временную и пространственную сложность обеих реализаций.
• сравнение обоих решений, включая случаи использования каждого из них.

Постановка задачи

Вам дан список целых чисел, и ваша задача — вернуть каждое уникальное число вместе с количеством его вхождений в список. Это типичная задача, которая проверяет ваше понимание структуры данных HashMap и вашу способность эффективно ее реализовать.

Вот пример:

Вход:

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

Выход:

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

Если входной список имеет значение NULL или пуст, результат должен возвращать пустой HashMap.

Решение 1. Традиционный подход с использованием if-else

В этом решении мы вручную проверяем, содержит ли HashMap число в качестве ключа. Если это так, мы увеличиваем значение; если нет, то вставляем ключ со значением 1.

Код

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}
    }
}

Объяснение

1. Если список имеет значение NULL: мы избегаем исключения NullPointerException, проверяя, имеет ли список значение NULL перед итерацией.
2. Итерация по списку: для каждого числа, если оно уже существует в HashMap, мы увеличиваем его значение. В противном случае мы вставляем его со значением 1.

Пространственно-временная сложность

• Временная сложность:

  • O(n) — мы проходим список один раз, где n — количество элементов.
  • Каждая операция HashMap (помещение и получение) занимает в среднем O(1), что увеличивает общую временную сложность O(n).

• Пространственная сложность: O(n) — в худшем случае все числа уникальны и хранятся в HashMap.

Решение 2. Оптимизированный подход с использованием метода getOrDefault()

Класс Java HashMap предоставляет более чистый и лаконичный способ решения этой проблемы с помощью метода getOrDefault(). Он устраняет необходимость в логике if-else, возвращая значение по умолчанию, если ключ не найден на карте.

Определение метода

V getOrDefault(Object key, V defaultValue)

• Параметры:

  • ключ: ключ, связанное с которым значение должно быть возвращено.
  • defaultValue: значение, возвращаемое, если карта не содержит сопоставления для ключа.

• Возвращает: значение, с которым сопоставлен указанный ключ, или значение по умолчанию, если сопоставление не содержит сопоставления для ключа.

Для получения дополнительной информации вы можете проверить официальную документацию Java для HashMap.

Код

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}
    }
}

Объяснение

1. Использование getOrDefault(): этот метод возвращает значение ключа, если он существует. Если нет, он возвращает предоставленное значение по умолчанию (в данном случае 0).
2. Вставка и увеличение: код напрямую добавляет 1 к значению по умолчанию, устраняя необходимость в логике if-else.

Преимущества getOrDefault()

• Чистый код: сокращает количество шаблонов, устраняя необходимость в if-else.
• Одинаковая сложность: O(n) как для времени, так и для пространства.

Сравнение обоих подходов

Заключение

Оба решения дадут один и тот же результат, но использование getOrDefault() делает код более кратким и читабельным. Этот вопрос является наиболее популярным на собеседованиях, поскольку он оценивает ваше понимание HashMaps, итерации и обработки нулевых значений. Это также тесно связано с проблемами, связанными с подсчетом частоты и агрегированием данных.

Если этот пост оказался для вас полезным, обязательно прочтите и другие посты из серии «Основы Collections Framework»!

Похожие сообщения

• Основы Java

• Основы собеседования с Array

• Основы памяти Java

Удачного программирования!