Confusão em encontrar a ordem da estrutura de dados

Question

Hoje participei de um teste escrito realizado por uma empresa. O teste geral foi focado nas estruturas de dados. Eu tive um problema que pensei ter resolvido. Mas tive um tempo difícil no cálculo da grande função do O para a estrutura de dados. Vou fornecer a pergunta e a resposta que criei.

Dado um documento que você precisa armazenar e as palavras no documento e deve poder devolver a contagem quando qualquer palavra for inserida. Você recebe char* GetNextWord().

1. Que estrutura de dados você escolherá
2. Dê o algoritmo
3. Qual será a ordem do seu algoritmo

Para a pergunta 1, escrevi que irei para a estrutura de dados trie. Para a pergunta 2, dei um breve algoritmo. Eu escrevi que construiria a estrutura de dados trie como seguinte.

struct TRIE{
 boolean isWord;
 int count;
 Node* myList;
}

struct Node{
 char* character;
 Node *next;
 TRIE *child;
}

Eu tenho métodos constructTrie() que fará um addToTrie() para cada palavra.

Eu escrevi a ordem de addToTrie() seria O (k) Onde k é o comprimento. E a ordem de constructTrie() seria N*O (k) Onde N seria o número de palavras.

Agora, minha pergunta é a seguinte: se as ordens que mencionei estão corretas ou não? Caso contrário, como atacar problemas como esse no futuro (dado um DS encontrando a ordem). Fiquei realmente confuso depois de usar o (k). Isso me faz assumir o (1).

Dicas/dicas/conselhos estão bem abertos !!

Editar : Corrigiu a pergunta mencionando claramente que a contagem de palavras deve ser armazenada para todas as palavras únicas.

Answer 1

Se você realmente quer usar um trie, então addToTrie() seria de fato OK) onde k é a duração da palavra que você está adicionando. constructTrie() levaria O (NK) Onde N é o número de palavras, se você apenas ligar addToTrie() Para cada palavra. No entanto, você não precisa ligar para o addToTrie() função para cada palavra. Depois de terminar de adicionar uma palavra, basta redefinir um ponteiro trie para a raiz do trie e mover o ponteiro à medida que você está se movendo sobre sua palavra atual, adicionando os personagens à medida que avança. Pseudo-código:

trieNode *curr = trieRoot;
for each character c in document
  if it's a word terminator (space etc)
    add a character at curr signaling the end of the current word ('\0' maybe);
    curr = trieRoot;
  else if character is not a separator
    add character c at curr->next->character[c];
    curr = curr->next;

Isso vai te dar O (c) tempo de execução para construir o trie, onde C é o número de caracteres em seu documento.

Agora, isso levanta a pergunta: por que você precisa do Trie? Obviamente, você descobriu uma maneira de detectar quando uma palavra terminou, então por que você deve adicionar suas palavras a um trie? É um exagero. A únicaestrutura de dados que você precisa são algumas variáveis: uma para acompanhar o caractere atual, um para acompanhar o personagem anterior e outro para contar as palavras. Isso é facilmente feito em O (c) assim:

char prev = '\0';
char curr;
int count = 0;

for each character curr
  if curr is a word separator and prev isn't 
    ++count;
  prev = curr;

Eu acho que não faz sentido usar um trie para esse problema, apenas complicando as coisas. Eu acho que se eles quisessem testar seu conhecimento de tentativas, teriam lhe dado um problema em que um trie fazia mais sentido.

Mesmo se eles lhe deram um getNextWord() função (você teve que usá -lo? Porque você pode fazer melhor sem ele), acho que ele retorna " 0" ou algo assim quando não há mais palavras? Então, por que você não pode simplesmente chamá -lo até que ele retorne " 0" e conte as palavras assim? De qualquer forma, um trie não faz sentido aqui.

Answer 2

spservices por nosso próprio tio Marc (Anderson) tem um plugin jquery que faz exatamente isso.Sua função resolve os nomes de exibição, então você pode desejar arrancá-los ou resolver as chaves para os nomes de exibição do usuário manualmente interrogando a lista de informações do usuário.

Aqui estão os documentos para essa função.