Last active
January 8, 2026 21:17
-
-
Save zr0n/fc88a5bd03bc3b6904661017e75d9f14 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """ | |
| TESTE - Top K itens mais frequentes em uma lista de strings | |
| Objetivo: | |
| Dada uma lista de strings `items` e um inteiro `k`, retornar os K itens mais frequentes. | |
| Regras: | |
| - Retorne uma lista de tuplas (item, contagem). | |
| - Ordenação: | |
| 1) contagem DESC | |
| 2) item ASC (lexicográfico) em caso de empate | |
| - Se k <= 0 -> retornar [] | |
| - Se k > quantidade de itens distintos -> retornar todos os distintos (respeitando ordenação) | |
| - A função deve ser determinística. | |
| Exemplo: | |
| items = ["a","b","a","c","b","a"], k=3 | |
| -> [("a",3), ("b",2), ("c",1)] | |
| Dica: collections.Counter pode ser usado, mas cuidado com os critérios de ordenação. | |
| """ | |
| from __future__ import annotations | |
| from typing import List, Tuple | |
| def top_k_frequent(items: List[str], k: int) -> List[Tuple[str, int]]: | |
| """ | |
| Implemente aqui. | |
| Complexidade esperada (para a versão simples): | |
| - O(n) para contar | |
| - O(m log m) para ordenar (m = número de distintos) | |
| Bônus (não obrigatório): | |
| - Melhorar para O(n log k) com heap | |
| """ | |
| raise NotImplementedError | |
| # ========================= | |
| # TESTES (pytest) | |
| # ========================= | |
| def test_basic(): | |
| items = ["a", "b", "a", "c", "b", "a"] | |
| assert top_k_frequent(items, 3) == [("a", 3), ("b", 2), ("c", 1)] | |
| def test_k_bigger_than_distinct(): | |
| items = ["x", "y", "x"] | |
| assert top_k_frequent(items, 10) == [("x", 2), ("y", 1)] | |
| def test_k_zero_and_negative(): | |
| items = ["a", "a", "b"] | |
| assert top_k_frequent(items, 0) == [] | |
| assert top_k_frequent(items, -5) == [] | |
| def test_empty_list(): | |
| assert top_k_frequent([], 3) == [] | |
| def test_tie_break_lexicographic(): | |
| # a e b empatam com 2, mas "a" vem antes | |
| items = ["b", "a", "b", "a", "c"] | |
| assert top_k_frequent(items, 2) == [("a", 2), ("b", 2)] | |
| def test_more_ties(): | |
| # todos com 1, então retorna em ordem lexicográfica | |
| items = ["delta", "alpha", "charlie", "bravo"] | |
| assert top_k_frequent(items, 3) == [("alpha", 1), ("bravo", 1), ("charlie", 1)] | |
| def test_determinism(): | |
| items = ["z", "z", "y", "x", "y", "y"] | |
| r1 = top_k_frequent(items, 2) | |
| r2 = top_k_frequent(items, 2) | |
| assert r1 == r2 == [("y", 3), ("z", 2)] | |
| test_basic() | |
| test_k_bigger_than_distinct() | |
| test_k_zero_and_negative() | |
| test_empty_list() | |
| test_tie_break_lexicographic() | |
| test_more_ties() | |
| test_determinism() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment