Obtenha 100 números mais altos de uma lista infinita

Digamos que k é o número de números mais altos que você deseja conhecer (100 no seu exemplo). Em seguida, você pode adicionar um novo número em O(k) , que também é O(1) . Porque O(k*g) = O(g) if k is not zero and constant .

Mantenha a lista não classificada. Descobrir se deve ou não inserir um novo número demorará mais tempo, mas a inserção será O (1).

Isso é fácil. O tamanho da lista de constante, portanto, o tempo de classificação da lista é constante. Uma operação que é executada em tempo constante é dita como O (1). Portanto, classificar a lista é O (1) para uma lista de tamanho fixo.

Depois de passar 100 números, o custo máximo que você incorrerá no próximo número é o custo para verificar se o número está nos 100 números mais altos (digamos que CheckTime ) mais o número custo para inseri-lo nesse conjunto e ejetar o menor (vamos chamar isso de EnterTime ), que é o tempo constante (pelo menos para números limitados), ou O (1) .

Worst = CheckTime + EnterTime

Em seguida, se a distribuição dos números for aleatória, o custo médio diminui quanto mais números você tiver. Por exemplo, a chance que você terá de inserir o 101º número no conjunto máximo é 100/101, as chances para o 1000º número seriam de 1/10, e as chances para o enésimo número seriam de 100 / n. Assim, nossa equação para custo médio será:

Average = CheckTime + EnterTime / n

Assim, como n se aproxima do infinito, somente CheckTime é importante:

Average = CheckTime

Se os números estiverem ligados, CheckTime será constante e, portanto, será O (1) tempo.

Se os números não estiverem vinculados, o tempo de verificação aumentará com mais números. Teoricamente, isso ocorre porque, se o menor número no conjunto máximo for grande o suficiente, o tempo de verificação será maior porque você terá que considerar mais bits. Isso faz parecer que será um pouco maior que o tempo constante. No entanto, você também pode argumentar que a chance de que o próximo número esteja no conjunto mais alto se aproxima de zero, à medida que n se aproxima do infinito e, portanto, você precisará considerar mais bits. um argumento para o tempo O (1) .

Não tenho certeza, mas meu instinto diz que é O (log (log (n))) tempo. Isso ocorre porque a chance de o número mais baixo aumentar é logarítmica e a chance de que o número de bits que você precisa considerar para cada verificação também seja logarítmico. Estou interessado em outros povos assume isso, porque eu não tenho certeza ...

Este é fácil se você souber árvores de heap binário . Os heaps binários suportam a inserção em tempo constante médio, O (1). E você tem acesso fácil aos primeiros elementos x.

Se pela pergunta que o entrevistador realmente queria perguntar “podemos ter certeza de que cada número recebido é processado em tempo constante”, então, como muitos já apontaram (por exemplo, ver a resposta de @doedl0r), a solução do seu amigo já é O (1 ), e seria assim mesmo se ele tivesse usado uma lista não classificada, ou usado bubble sort, ou qualquer outra coisa. Nesse caso, a pergunta não faz muito sentido, a menos que seja uma pergunta complicada ou você se lembre dela errado.

Eu assumo que a pergunta do entrevistador foi significativa, que ele não estava perguntando como fazer algo para ser O (1), o que já é muito óbvio.

Como a complexidade do algoritmo de questionamento só faz sentido quando o tamanho da entrada cresce indefinidamente, e a única entrada que pode crescer aqui é 100 - o tamanho da lista; Eu assumo que a verdadeira questão era “podemos nos certificar de que o Top N gasta O (1) tempo por número (não O (N) como na solução do seu amigo), é possível?”.

A primeira coisa que vem à mente é a contagem sort, que comprará complexidade de O (1) tempo por número para o Top-N-problem pelo preço de usar O (m) espaço, onde m é o comprimento do intervalo de números recebidos. Então sim, é possível.

Use uma fila com prioridade mínima implementada com um heap Fibonacci , que possui tempo de inserção constante:

1. Insert first 100 elements into PQ
2. loop forever
       n = getNextNumber();
       if n > PQ.findMin() then
           PQ.deleteMin()
           PQ.insert(n)

A tarefa é claramente encontrar um algoritmo que seja O (1) no comprimento N da lista de números requerida. Portanto, não importa se você precisa do número 100 ou 10000, o tempo de inserção deve ser O (1).

O truque aqui é que, embora o requisito O (1) seja mencionado para a inserção da lista, a pergunta não diz nada sobre a ordem do tempo de busca no espaço numérico inteiro, mas acontece que isso pode ser feito. (1) também. A solução é a seguinte:

1. Organize uma hashtable com números para chaves e pares de ponteiros de lista vinculados para valores. Cada par de ponteiros é o início e o fim de uma sequência de lista vinculada. Isso normalmente será apenas um elemento e depois o próximo. Cada elemento na lista encadeada vai ao lado do elemento com o próximo número mais alto. A lista encadeada contém, assim, a sequência classificada dos números necessários. Mantenha um registro do menor número.

2. Pegue um novo número x do fluxo aleatório.

3. É maior que o último número mais baixo registrado? Sim = > Etapa 4, No = > Etapa 2

4. Acerte a tabela de hash com o número que acabou de ser obtido. Existe uma entrada? Sim = > Etapa 5. Não = > Pegue um novo número x-1 e repita este passo (esta é uma simples busca linear descendente, apenas tenha comigo aqui, isso pode ser melhorado e eu explicarei como)

5. Com o elemento list apenas obtido da tabela de hash, insira o novo número logo após o elemento na lista vinculada (e atualize o hash)

6. Pegue o menor número l gravado (e remova-o do hash / lista).

7. Acerte a tabela de hash com o número que acabou de ser obtido. Existe uma entrada? Sim = > Etapa 8. Não = > Pegue um novo número l + 1 e repita este passo (esta é uma simples pesquisa linear ascendente)

8. Com um resultado positivo, o número se torna o novo número mais baixo. Vá para o passo 2

Para permitir valores duplicados, o hash precisa manter o início e o fim da sequência da lista vinculada de elementos que são duplicados. Adicionar ou remover um elemento em uma determinada chave aumenta ou diminui o alcance apontado.

A inserção aqui é O (1). As buscas mencionadas são, eu acho que algo como, O (diferença média entre os números). A diferença média aumenta com o tamanho do espaço numérico, mas diminui com o tamanho necessário da lista de números.

Portanto, a estratégia de pesquisa linear é muito ruim, se o espaço numérico for grande (por exemplo, para um tipo int de 4 bytes, 0 para 2 ^ 32-1) e N = 100. Para contornar este problema de desempenho, você pode manter conjuntos paralelos de hashtabables, onde os números são arredondados para magnitudes mais altas (por exemplo, 1s, 10s, 100s, 1000s) para criar chaves adequadas. Dessa forma, você pode aumentar ou diminuir as marchas para realizar as pesquisas necessárias mais rapidamente. O desempenho então se torna um O (log numberrange), eu acho, que é constante, ou seja, O (1) também.

Para tornar isso mais claro, imagine que você tenha o número 197 à mão. Você acerta a tabela de hash 10s, com '190', é arredondado para os dez mais próximos. Qualquer coisa? Não. Então você desce em 10s até que você acertar dizer 120. Então você pode começar em 129 no hashtable 1s, em seguida, tente 128, 127 até que você acerte alguma coisa. Você agora encontrou onde na lista encadeada para inserir o número 197. Ao colocá-lo, você também deve atualizar a hashtable 1s com a entrada 197, a 10s com o número 190, 100s com 100, etc. você já tem que fazer aqui são 10 vezes o log do intervalo de números.

Eu poderia ter alguns dos detalhes errados, mas como essa é a troca de programadores, e o contexto era entrevistas, espero que o texto acima seja uma resposta suficientemente convincente para essa situação.

EDIT Eu adicionei alguns detalhes extras aqui para explicar o esquema hashtable paralelo e como isso significa que as pesquisas lineares pobres que mencionei podem ser substituídas por uma pesquisa O (1). Eu também percebi que é claro que não há necessidade de procurar o próximo número mais baixo, porque você pode ir direto para ele, olhando no hashtable com o número mais baixo e progredindo para o próximo elemento.

Podemos presumir que os números são de um tipo de dados fixo, como Integer? Nesse caso, mantenha um registro de cada número adicionado. Esta é uma operação O (1).

1. Declare uma matriz com tantos elementos quantos forem possíveis:
2. Leia cada número enquanto ele é transmitido.
3. Registre o número. Ignore se esse número já tiver sido computado 100 vezes, pois você nunca precisará dele. Isso evita que os transbordamentos sejam computados em um número infinito de vezes.
4. Repita a partir do passo 2.

Código VB.Net:

Const Capacity As Integer = 100

Dim Tally(Integer.MaxValue) As Integer ' Assume all elements = 0
Do
    Value = ReadValue()
    If Tally(Value) < Capacity Then Tally(Value) += 1
Loop

Quando você retornar a lista, poderá demorar o tempo que quiser. Basta iterar a partir do final da lista e criar uma nova lista dos 100 valores mais altos registrados. Esta é uma operação O (n), mas isso é irrelevante.

Dim List(Capacity) As Integer
Dim ListCount As Integer = 0
Dim Value As Integer = Tally.Length - 1
Dim ValueCount As Integer = 0
Do Until ListCount = List.Length OrElse Value < 0
    If Tally(Value) > ValueCount Then
        List(ListCount) = Value
        ValueCount += 1
        ListCount += 1
    Else
        Value -= 1
        ValueCount = 0
    End If
Loop
Return List

Editar: Na verdade, não importa se é um tipo de dados fixo. Dado que não há limites impostos sobre o consumo de memória (ou disco rígido), você poderia fazer este trabalho para qualquer intervalo de inteiros positivos.

Cem números são facilmente armazenados em uma matriz, tamanho 100. Qualquer árvore, lista ou conjunto é um exagero, dada a tarefa em mãos.

Se o número de entrada for maior que o menor (= último) na matriz, execute todas as entradas. Depois de encontrar o primeiro que é menor que o seu novo número (você pode usar pesquisas sofisticadas para fazer isso), percorra o restante do array, empurrando cada entrada "para baixo" em um.

Como você mantém a lista ordenada desde o início, não precisa executar nenhum algoritmo de classificação. Este é O (1).

Você pode usar um heap binário máximo. Você teria que manter o controle de um ponteiro para o nó mínimo (que poderia ser desconhecido / nulo).

Você começa inserindo os primeiros 100 números no heap. O máximo será no topo. Depois disso, você sempre manterá 100 números.

Então, quando você recebe um novo número:

if(minimumNode == null)
{
    minimumNode = findMinimumNode();
}
if(newNumber > minimumNode.Value)
{
    heap.Remove(minimumNode);
    minimumNode = null;
    heap.Insert(newNumber);
}

Infelizmente, findMinimumNode é O (n), e você incorrerá nesse custo uma vez por inserção (mas não durante a inserção :). Remover o nó mínimo e inserir o novo nó é, em média, O (1) porque eles tenderão para a parte inferior do heap.

Indo para o outro lado com um Binary Min-Heap, o min está no topo, o que é ótimo para encontrar o min para comparação, mas é péssimo quando você precisa substituir o mínimo por um novo número que é > min. Isso porque você precisa remover o nó min (sempre O (logN)) e, em seguida, inserir o novo nó (média O (1)). Então, você ainda tem O (logN), que é melhor que Max-Heap, mas não O (1).

Claro, se N é constante, então você sempre tem O (1). :)