На что обратишь внимание при решении алгоритмической задачи?

Подход к решению алгоритмических задач

При решении алгоритмической задачи я обращаю внимание на несколько ключевых аспектов, которые часто упускают начинающие разработчики. Это структурированный подход с 10+ лет опыта.

1. Понимание требований (САМОЕ ВАЖНОЕ)

Первым делом я тщательно анализирую задачу:

Вопросы, которые я задаю:

• Какой вход? (Диапазон чисел? Строки? Типы данных?)
• Какой ожидаемый выход?
• Есть ли ограничения по памяти и времени?
• Могут ли быть граничные случаи? (пустой ввод, отрицательные числа, null)
• Нужна ли оптимальность или просто рабочее решение?

Пример анализа:

Задача: "Найти два числа в массиве, которые дают сумму target"

Вопросы:
- Размер массива? (100 элементов или 1M?)
- Все ли числа уникальны?
- Может быть несколько пар?
- Массив отсортирован или нет?
- Что возвращать: индексы или сами числа?

2. Анализ сложности ПЕРЕД кодированием

Я ВСЕГДА начинаю с анализа сложности, а не с кода:

// Задача: найти две суммы
// Ввод: [2, 7, 11, 15], target = 9

// Вариант 1: Brute Force O(n²)
// Два вложенных цикла
// ❌ Медленный для больших массивов

private int[] twoSumBruteForce(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return new int[]{};
}

// Вариант 2: Hash Map O(n)
// Один проход, проверка в HashMap
// ✅ Оптимально

private int[] twoSumOptimal(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        
        if (seen.containsKey(complement)) {
            return new int[]{seen.get(complement), i};
        }
        
        seen.put(nums[i], i);
    }
    
    return new int[]{};
}

Анализ Big O:

3. Граничные случаи (Edge Cases)

Я ВСЕГДА проверяю граничные случаи до кодирования:

// Для любой задачи:
// 1. Пустой ввод
// 2. Один элемент
// 3. Дублирующиеся элементы
// 4. Максимальные/минимальные значения
// 5. Отрицательные числа
// 6. Нулевые значения
// 7. Уже отсортированные/обратные порядки

public class TwoSumTest {
    @Test
    public void testEmptyArray() {
        int[] result = twoSum(new int[]{}, 9);
        assertEquals(0, result.length);
    }
    
    @Test
    public void testSingleElement() {
        int[] result = twoSum(new int[]{5}, 10);
        assertEquals(0, result.length);
    }
    
    @Test
    public void testDuplicates() {
        int[] result = twoSum(new int[]{2, 2, 2}, 4);
        assertEquals(2, result.length);
    }
    
    @Test
    public void testNegativeNumbers() {
        int[] result = twoSum(new int[]{-1, -2, 3}, 1);
        assertEquals(2, result.length);
    }
}

4. Выбор структур данных

Я выбираю подходящие структуры в зависимости от задачи:

Частые выборы:

// 1. HashMap/HashSet — быстрый поиск O(1)
Set<Integer> seen = new HashSet<>();

// 2. TreeMap — отсортированные данные, O(log n) операции
TreeMap<Integer, Integer> map = new TreeMap<>();

// 3. Deque — очередь или стек (используется часто)
Deque<Integer> stack = new ArrayDeque<>();
stack.push(5);
int top = stack.pop();

// 4. PriorityQueue — для k largest/smallest
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 5. Arrays.sort() или TreeSet — если нужна сортировка
Arrays.sort(nums);

5. Стратегия решения

Я выбираю правильную парадигму:

Поиск:

• Binary Search (отсортированные массивы) → O(log n)
• Linear Search → O(n)

Сортировка:

• Quick Sort / Merge Sort → O(n log n)
• Counting Sort (если малый диапазон) → O(n + k)

Динамическое программирование:

• Есть оптимальная подструктура?
• Есть перекрывающиеся подзадачи?

// DP пример: Fibonacci с memoization
public class Fibonacci {
    private Map<Integer, Long> memo = new HashMap<>();
    
    public long fib(int n) {
        if (n <= 1) return n;
        
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        long result = fib(n - 1) + fib(n - 2);
        memo.put(n, result);
        return result;
    }
}

Graphs:

• DFS / BFS для поиска пути
• Dijkstra для кратчайшего пути
• Topological Sort для зависимостей

// BFS для поиска в ширину
public void bfs(Node start) {
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();
    
    queue.add(start);
    visited.add(start);
    
    while (!queue.isEmpty()) {
        Node current = queue.poll();
        System.out.println(current);
        
        for (Node neighbor : current.getNeighbors()) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.add(neighbor);
            }
        }
    }
}

6. Реализация с учётом best practices

public class AlgorithmSolution {
    // 1. Используй типизацию (не Object)
    public <T extends Comparable<T>> int binarySearch(
        List<T> list, T target) {
        
        int left = 0, right = list.size() - 1;
        
        // 2. Проверяй граничные условия
        while (left <= right) {
            // 3. Избегай integer overflow
            int mid = left + (right - left) / 2;
            // Не: int mid = (left + right) / 2;
            
            int cmp = list.get(mid).compareTo(target);
            
            if (cmp == 0) return mid;
            else if (cmp < 0) left = mid + 1;
            else right = mid - 1;
        }
        
        return -1;  // Not found
    }
    
    // 4. Документируй сложность
    /**
     * Поиск элемента в отсортированном массиве.
     * 
     * @param list отсортированный список
     * @param target элемент для поиска
     * @return индекс элемента или -1 если не найден
     * @throws NullPointerException если list или target == null
     * @complexity Time: O(log n), Space: O(1)
     */
    public <T extends Comparable<T>> int search(
        List<T> list, T target) {
        // ...
    }
}

7. Тестирование на ошибки

После реализации я тестирую:

// 1. Обычные случаи
assertEquals(1, solution.search(Arrays.asList(1, 2, 3), 2));

// 2. Граничные случаи
assertEquals(-1, solution.search(Arrays.asList(), 1));
assertEquals(0, solution.search(Arrays.asList(1), 1));

// 3. Производительность
long start = System.nanoTime();
for (int i = 0; i < 100_000; i++) {
    solution.search(largeList, target);
}
long duration = System.nanoTime() - start;
assertTrue("Слишком медленно", duration < 1_000_000_000L);

8. Оптимизация если нужна

// Если первое решение работает но медленно:

// ДО: Наивное решение O(n²)
long count = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (condition(i, j)) count++;
    }
}

// ПОСЛЕ: Оптимизировано O(n log n)
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
    freq.put(num, freq.getOrDefault(num, 0) + 1);
}

for (int num : nums) {
    int complement = target - num;
    if (freq.containsKey(complement)) {
        count += freq.get(complement);
    }
}

9. Чек-лист перед сдачей

✓ Понимаю задачу полностью
✓ Анализ сложности сделан
✓ Все граничные случаи проверены
✓ Нет integer/long overflow ошибок
✓ Нет NullPointerException
✓ Код читаемый с хорошими именами переменных
✓ Нет нежелательных сторонних эффектов
✓ Нет бесконечных циклов
✓ Память используется оптимально
✓ Тесты написаны и проходят
✓ Документация есть (если нужна)

10. Пример полного решения

/**
 * Найти все уникальные тройки в массиве, которые дают сумму нулю.
 * 
 * Complexity: Time O(n²), Space O(n)
 */
public class ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        // 1. Граничный случай
        if (nums == null || nums.length < 3) {
            return Collections.emptyList();
        }
        
        List<List<Integer>> result = new ArrayList<>();
        
        // 2. Сортировка для two-pointer подхода
        Arrays.sort(nums);  // O(n log n)
        
        // 3. Основной цикл O(n²)
        for (int i = 0; i < nums.length - 2; i++) {
            // 4. Оптимизация: если число положительное, сумма не может быть 0
            if (nums[i] > 0) break;
            
            // 5. Пропускаем дубликаты
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            // 6. Two-pointer approach для оставшихся элементов
            int left = i + 1, right = nums.length - 1;
            
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                
                if (sum == 0) {
                    result.add(Arrays.asList(
                        nums[i], nums[left], nums[right]
                    ));
                    
                    // 7. Пропускаем дубликаты для left
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    // 8. Пропускаем дубликаты для right
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return result;
    }
}

Итоговый ответ

При решении алгоритмической задачи я обращаю внимание на:

1. Понимание требований — уточняю все детали
2. Анализ сложности — Time и Space ПЕРЕД кодированием
3. Граничные случаи — пустой ввод, дубликаты, отрицательные числа
4. Выбор структур данных — HashMap, TreeMap, PriorityQueue, Deque
5. Правильная стратегия — BFS, DP, Binary Search, Sorting
6. Best practices — типизация, без overflow, читаемость
7. Тестирование — обычные и граничные случаи
8. Оптимизация — если первое решение недостаточно быстро
9. Документация — сложность и параметры
10. Финальная проверка — все ли работает корректно