Frequência de palavras com pedidos na complexidade O (n)

Durante uma entrevista para uma posição de desenvolvedor Java, me perguntaram o seguinte:

Escreva uma função que use dois parâmetros:

1. uma String representando um documento de texto e
2. um número inteiro fornecendo o número de itens a serem retornados.

Implemente a função para que ela retorne uma lista de Strings ordenadas por frequência de palavra, a palavra que ocorre com mais frequência primeiro. Sua solução deve ser executada em $O(n)$ tempo em que $n$ é o número de caracteres no documento.

A seguir é o que eu respondi (em pseudocódigo), não é mas sim O ( n log n ) tempo por causa da classificação. Não consigo descobrir como fazê-lo O ( n ) tempo. $O(n)$$O(n \log n)$$O(n)$

wordFrequencyMap = new HashMap<String, Integer>();
words = inputString.split(' ');

for (String word : words) {
  count = wordFrequencyMap.get(word);
  count = (count == null) ? 1 : ++count;
  wordFrequencyMap.put(word, count);
}

return wordFrequencyMap.sortByValue.keys

Alguém sabe ou pode me dar algumas dicas?

Sugiro uma variação da contagem de distribuição:

1. Leia o texto e insira toda a palavra encontrada em uma tentativa , mantendo em cada nó uma contagem, com que frequência a palavra representada por esse nó ocorreu. Além disso, mantenha o controle da maior contagem de palavras, digamos maxWordCound. - $O(n)$
2. Inicialize uma matriz de tamanho maxWordCount. Tipo de entrada são listas de strings. - , já que a contagem não pode ser maior.$O(n)$
3. Atravesse o trie e, para cada nó, adicione a sequência correspondente à entrada da matriz indicada pela contagem. - , já que o comprimento total das cadeias é limitado por n .$O(n)$$n$
4. Atravesse a matriz em ordem decrescente e produza o número desejado de strings. - , uma vez que isso é um limite para o tamanho e a quantidade de dados na matriz.$O(n)$

Provavelmente, você pode substituir o teste por outras estruturas de dados na primeira fase.

A coleta de contagens de ocorrências é O (n), portanto, o truque é realmente encontrar apenas as contagens de k principais ocorrências.

Um heap é uma maneira comum de agregar os principais valores de k, embora outros métodos possam ser usados ​​(consulte https://en.wikipedia.org/wiki/Partial_sorting ).

Assumindo que k é o segundo parâmetro acima e que é uma constante na declaração do problema (parece ser):

1. Crie uma série de palavras com a contagem de ocorrências em cada nó.
2. Inicialize um monte de tamanho k.
3. Atravesse a trie e min-probe / insira cada par (folha, número de ocorrências) no heap top-k.
4. Faça a saída das k folhas e contagens superiores (isso é realmente meio complicado, porque você precisa de indicadores pai para mapear cada folha de volta a uma palavra).

Como o tamanho do heap é uma constante, as operações do heap são O (1), portanto, a etapa 3 é O (n).

O heap também pode ser mantido dinamicamente ao criar o trie.

Seu algoritmo nem roda no tempo ; inserir Θ ( n ) coisas em um hashtable custa tempo Ω ( n 2 ) já (na pior das hipóteses).$O(n \log n)$$\Theta(n)$$\Omega(n^2)$

O que se segue está errado ; Estou deixando aqui por enquanto para fins ilustrativos.

O algoritmo a seguir é executado no pior dos casos (assumindo um alfabeto Σ de tamanho constante), n o número de caracteres no texto.$O(n)$$\Sigma$$n$

1. Construa uma árvore de sufixos do texto, por exemplo, com o algoritmo de Ukkonen .

   Se a construção ainda não fizer isso, adicione o número de folhas alcançáveis ​​em cada nó (interno).

2. Atravesse a árvore da raiz e corte todos os galhos no primeiro espaço (branco).

3. Atravesse a árvore e classifique a lista de filhos de cada nó pela contagem de folhas.

4. O rendimento da árvore (folhas da esquerda para a direita) agora é uma lista de todas as palavras, classificadas por frequência.

Em relação ao tempo de execução:

1. O algoritmo de Ukkonen (em sua forma aprimorada) é executado no tempo ; manter a contagem de folhas não aumenta $O(n)$$\Theta$ -Custo do algoritmo.
2. Temos que percorrer um nó por caractere de cada palavra que ocorre no texto. Como existem no máximo pares diferentes de caracteres de palavras, visitamos no máximo n nós.$n$$n$
3. Visitamos no máximo nós (cf. 2.) e gastamos tempo O ( | Σ | ⋅ log | Σ | ) = O ( 1 ) por nó.$n$$O(|\Sigma| \cdot \log |\Sigma|) = O(1)$
4. Podemos obter o rendimento (que obviamente tem tamanho ) por uma simples travessia no tempo O ( n ) (cf. 2.).$O(n)$$O(n)$

Limites mais precisos podem ser obtidos parametrizando o tempo de execução com o número de palavras diferentes; se houver poucos, a árvore será pequena após 2.

HashMap$1..n$$O(n)$$O(n)$

$O(n)$$O(n)$$O(n)$

Ou, se você quiser jogar um pouco mais seguro, antes de dar uma resposta, primeiro pergunte "você se importa com a diferença entre esperado$O(n)$ running time and worst-case $O(n)$ running time?". Then tailor your answer accordingly. Be prepared for the interviewer to ask you how you would choose, in practice. (If so, score! That's a question you should be able to hit out of the ballpark.)

Hashtable based solution

Not sure why hashtable makes the complexity $\Omega(n^2)$ if $n$ is the number of characters (not words).

If you iterate through every character in the document and as you are iterating, calculate the hashcode of the word, you will have gone through $n$ characters. That is, as soon as a letter is encountered, the word begins, so start computing hash until the word ends (there are some special cases for punctuation but those do not affect the complexity). For every word, once the hash is computed, add it to a hashtable. This is to avoid going over every word twice, i.e. first to iterate through the document to find the words and then to insert them in a hashtable, although the complexity in that case could also be $\Omega(n)$.

Collisions in the hashtable are surely a problem, and depending on how big the original hashtable was and how good the hashing algorithm is, one could approach close to $O(1)$ for insertions and keeping counts and thus $O(n)$ for the algorithm, although at the expense of memory. However, I still cannot appreciate how the worst case can be asserted to be $O(n^2)$ if $n$ is the number of characters.

The assumption is that the hashing algorithm is linear in time in relation to the number of characters.

Radix sort based solution

Alternatively, assuming English, since the length of the words is well-known, I would instead create a grid and apply radix sort which is $O(kN)$ where $k$ would be the maximum length of a word in the English language, and $N$ is the total number of words. Given $n$ is the number of characters in the document, and $k$ is a constant, asymptotically this amounts $O(n)$.

Now count the frequency of each word. Since the words are sorted, we will be comparing each word to its preceding word to see if it's the same one or different. If it's the same, we remove the word and add a count to the previous. If different, just make the count 1 and move on. This requires $2n$ comparisons where $n$ is the number of characters, and thus $O(n)$ in complexity as a whole.

The top few longest words in English are ridiculously long, but then one could cap the word length at a reasonable number (such as 30 or smaller) and truncate words accepting the margin of error that might come with it.