Python · задача 2 из 10

Топ-N самых частых слов

Начальный 10–15 минут Counterheapqнормализация текста

Условие

Дан текст. Верните N самых частых слов с их количеством, от частых к редким. Слова сравниваются без учёта регистра, знаки препинания не считаются частью слова.

Что требуется

Регистр не важен: «Python» и «python» — одно слово
При равной частоте порядок — алфавитный
N больше числа уникальных слов — вернуть всё, что есть

Пример

text = "Python is great. python IS fast, and Python is simple!"

top_words(text, 2)
# [("python", 3), ("is", 3)]  -> при равной частоте сначала "is"
# правильный ответ: [("is", 3), ("python", 3)]

Сначала уточните

Вопросы до кода — половина оценки. Молча начать печатать хуже, чем задать два вопроса.

Что считать словом: только буквы, или дефисы и апострофы тоже (don-t, кто-то)?
Нужно ли выбрасывать стоп-слова вроде «и», «the»?
Как разрешать равные частоты — по алфавиту или порядок не важен?

Показать решение Скрыть решение

Решение

import re
from collections import Counter

WORD_RE = re.compile(r"[a-zа-яё0-9]+(?:-[a-zа-яё0-9]+)*", re.IGNORECASE)


def top_words(text, n):
    words = WORD_RE.findall(text.lower())
    counts = Counter(words)

    # сортируем по убыванию частоты, при равной частоте — по алфавиту
    return sorted(counts.items(), key=lambda kv: (-kv[1], kv[0]))[:n]


# Если уникальных слов очень много, а N маленькое:
import heapq


def top_words_heap(text, n):
    counts = Counter(WORD_RE.findall(text.lower()))
    return heapq.nsmallest(n, counts.items(), key=lambda kv: (-kv[1], kv[0]))

Почему так

Почему Counter, а не ручной словарь

Counter — это тот же dict, но написанный за вас и на C: короче и быстрее ручного цикла
У него есть most_common(n), но он не решает вопрос равных частот — порядок будет «как легло», поэтому в решении явный sorted
Знание most_common и его ограничения — ровно то, что проверяет интервьюер

Почему ключ сортировки (-count, word)

Один проход сортировки вместо двух: минус перед количеством даёт убывание, слово следом — алфавит при равенстве
Так результат детерминирован: на одних и тех же данных всегда один ответ, что важно и для тестов
reverse=True здесь не подходит: он развернул бы и алфавитный порядок тоже

Когда heapq лучше sorted

sorted — O(u log u) по числу уникальных слов, heapq.nsmallest — O(u log n), и при n=10 против миллиона уникальных это заметно
На тексте из задачи разницы нет — говорите об этом как об оптимизации «если данных станет много»
Преждевременно писать heapq сразу — минус: сначала простое решение, потом обсуждение

Что спросят дальше

text.split() вместо регулярки — тогда «great.» и «great» станут разными словами; это первое, что проверят на примере
Спросят про огромный файл: читать построчно и обновлять Counter, а не грузить текст целиком
Могут попросить без Counter — покажите тот же цикл с dict.get(word, 0) + 1

Следующая задача

Разложить вложенный словарь в плоский — Живая задача из интеграций: конфиг или JSON от чужого API нужно превратить в плоские ключи.

Перейти