O problema que só 1% dos devs consegue resolver

Поділитися
Вставка
  • Опубліковано 29 жов 2024

КОМЕНТАРІ • 276

  • @russotragik
    @russotragik 7 місяців тому +105

    6:49 isso é um 6 em decimal, 3 decimal em binário seria 11.

    • @JeffersonPires90
      @JeffersonPires90 6 місяців тому +5

      também notei isso e fiquei me perguntado se eu tava louco

    • @JeffersonPires90
      @JeffersonPires90 6 місяців тому +4

      mesmo assim, conteúdo fantástico e bem apresentado

    • @pietriinn
      @pietriinn Місяць тому

      exato, notei isso tb. 0, 1, 10 e 110, estranho

  • @LukitaSukita
    @LukitaSukita 7 місяців тому +162

    Me perguntaram isso em uma entrevista pra uma startup no Texas, nunca tinha visto o problema. Demorei um pouco pra resolver, mas resolvi em O(n). Pediram pra implementar um LRU em O(1) também. Foi desafiador mas atingi o objetivo.
    Infelizmente n fui chamado pra vaga, acho que pela demora pra resolver o problema em primeira instância. Noto que a cultura dos norte americanos é mt forte pra leet code, bem diferente das empresas do Brasil

    • @erikxw
      @erikxw 7 місяців тому +5

      Olá, o que significa O(n) e LRU em O(1), pode me explicar?

    • @LukitaSukita
      @LukitaSukita 7 місяців тому +85

      @@erikxw tudo certo cara? Quando falamos O(n), O(1), O(logn), entre outros, referimos a complexidade algoritmica, ou Big O Notation, que é utilizada para comparar a eficiência de algoritmos. É importante entender pelo menos o básico de estrutura de dados para conseguir determinar a complexidade de algum algoritmo.
      Alguns exemplos:
      O(1) - Chamado de constant time (tempo constante). É chamado assim pois a operação é sempre constante e não depende de N. Acessar um index em um array é feito em tempo constante O(1) por exemplo, pois já temos a referência em memória pronta para ser acessada. Operações simples como um println, atribuir valores a variáveis e etc também são feitas em tempo constante.
      O(n) - Chamado de Linear Time (tempo linear). Diferente do O(1), esse carinha depende de N. Iterar em uma lista é feito em Linear Time, pois iremos iterar em todos os itens da lista, podendo iterar N vezes até que a lista acabe. Outro caso de Linear Time pode ser acessar um valor em uma Linked List. Nesse caso da Linked List, para acharmos um valor específico começamos pelo primeiro valor na linked list, e através da referência ao próximo valor, vamos avançando na lista. Nesse cenário, no pior dos casos, o valor pode estar no final da lista, tornando o algoritmo em O(n). "- Há mas vc pode manter a referência do head e do tail da lista pra ficar mais rápido e etc", Entendo, mas essa explicação é mais simplificada pra cunho de entendimento.
      O(logn) - Chamado de Logarithmic Time (Tempo logaritmico). Esse cara utiliza um conceito bem comum na programação chamdo de Divide & Conquer (dividir e conquistar), pois a abordagem dele é literalmente o número de vezes que “n” pode ser dividido por 2 para encontrar o valor. Um Binary Search (busca binária), ou uma Balanced Sorted Binary Tree (arvore binária ordenada e balanceada) são exemplos de O(logn). Pode ser que, para achar um valor em uma busca binária vc demore log5 ou log7. Para ser mais geral, utiliza-se logn.
      Esses que citei são os mais básicos, comuns e utilizados. Você pode se aprofundar um pouco mais no assunto e com certeza vai se deparar com outras complexidades, como O(nlogn), O(n^2), O(n!), dentre outras.

    • @LukitaSukita
      @LukitaSukita 7 місяців тому

      Agora, falando sobre a LRU (Last Recently Used). Esse é um algoritmo de cache. Basicamente o que ele faz é armazenar um map de valores até uma certa capacidade. Quando existe a necessidade de adicionar um novo valor nesse cache e essa capacidade for atingida, você precisa remover do seu cache o valor que foi menos utilizado para que possa ser possível adicionar um novo valor.
      O problema parece simples, mas vc precisa pensar em como vai lidar com a ordem de acesso, a remoção e adição, o pop do valor mais utilizado.
      Com base na explicação de Big O que dei ali em cima, podemos pensar em alguns approaches pra atingir isso. Geralmente uttiliza-se um HashMap e um DoublyLinkedList. Ou, no meu caso, no Kotlin, tem um LinkedHashMap (mas lógico que vão pedir pra vc implementar ttudo na unha pra ver se vc entende hehe).

    • @LukitaSukita
      @LukitaSukita 7 місяців тому +38

      Portanto, pedir um LRU com Big O de O(1), basicamente estão pedindo para implementar esse algoritmo em tempo constante (que é o algoritmo mais rápido). Suas operações devem ser todas em O(1)

    • @LukitaSukita
      @LukitaSukita 7 місяців тому +45

      Um LRU (Last Recenly Used) é um algoritmo de cache. Basicamente vc precisa armamzenar um map de valores em um cache até uma determinada capacidade. Quando precisar armazenar um novo valor e essa capacidade tiver sido atingida, vc precisa remover do cache a chave que foi menos utilizada dentre as outras.
      Quando vc dá um get em um valor ele se torna o ultimo valor mais utilizado, por exemplo. E quando vc da um put nesse valor, a mesma coisa, mas aqui ele atualiza o valor atrelado a chave que está armazenada em cache.
      Parece um problema simples, vc aqui vc já precisa de preocupar com coisas como:
      - Como manter a ordem de acesso
      - Como remover, adicionar, dar update nos valores
      - O que fazer quando tentar dar um get em um valor que n está em cache
      - Quais esttruturas de dados vou uttilizar para que a Complexidade se mantenha em Big O (1)?
      Muito comum utilizarem HashMap e DoublyLinkedList para solucionar o problema.

  • @pablolacerdaestaffe4888
    @pablolacerdaestaffe4888 7 місяців тому +24

    Eu não sou programador, não sei programar e nunca tentei, eu assisti seu vídeo só pq me prendeu no ínicio, queria te dizer que sua didática foi tão incrível que por mais que eu não tenha entendido mt bem a programação, entendi a lógica, isso foi incrível!!!

    • @thomasthemazzerrunner3615
      @thomasthemazzerrunner3615 6 місяців тому +2

      Exatamente meu amigo! isso é Matemática (Lógica!), códigos qualquer imprestável escreve! Desenvolver um algoritmo eficiente (Possível Solução no mínimo Boa) é que é difícil!

  • @GuilhermePatriota
    @GuilhermePatriota 6 місяців тому +5

    Sugiro fazer o xor e subtrair ele duas vezes da soma do nums. O resultado será o valor único… assim não precisará de nenhuma outra variável de controle.

  • @elciof
    @elciof 7 місяців тому +7

    Fantástico, Augusto! Problema lindo! Solução muito elegante! Obrigado por esse vídeo.

  • @goldentortoisebeetle9741
    @goldentortoisebeetle9741 7 місяців тому +10

    Assim como a operação xor soma os dígitos na representação binária módulo 2 (isto é, soma e vê qual o resto do resultado na divisão por 2), pensei em definir uma outra operação que converte os números na base ternária e soma dígitos módulo 3.

  • @TheThousandDaggers
    @TheThousandDaggers 5 місяців тому

    parabéns! conteúdo incrível, abriu minha mente de como encarar alguns problemas e possíveis soluções

  • @geffteluis7407
    @geffteluis7407 6 місяців тому +1

    é um problema divertido, dps de fazer a matéria de sistemas digitais tudo fica bem claro

  • @renangoncalves2633
    @renangoncalves2633 26 днів тому

    No fim a sacada esta em transferir a compexidade O(N) onde N dependeria do número de elementos da entrada, para uma O(M), onde M é o número maximo de bits dos elementos, ainda sim continua sendo linear porém dependendo de outra variavel, em N fica constante mesmo

  • @civicmugenlxs
    @civicmugenlxs 7 місяців тому +7

    cara gostei bastante desse canal, pois diferentemente dos outros canais que tem hoje em dia que só falam coisas basicas e vendem mentiras (tipo com 6 meses vc conseguir trampo pra ganhar 10k) esse canal aborta leet code e praticas de software que me agregaram, continue assim

  • @ThiagoHenriqueDS
    @ThiagoHenriqueDS Місяць тому +1

    A conclusão que eu tiro desse vídeo é que eu sou um merda em programação

  • @SamueldaCostaAraujoNunes
    @SamueldaCostaAraujoNunes 3 місяці тому +2

    Eu fiz um paralelo com uma maquina de estado, com 3 estados. Cada vez que aparece um numero, vc joga para o próximo estado. 00 -> 01 -> 10 -> 11

  • @MedeirosJoel_
    @MedeirosJoel_ 7 місяців тому +7

    Minha solução seria ordenar o vetor, depois andar por ele verificando o quanto se repete, e se repetir 2x pularia +1 casa desconsiderando a terceira vez que o numero repete

    • @sLokJoNas
      @sLokJoNas 7 місяців тому +6

      os algoritmos de sort mais eficientes são n log n, exceto pelo bucket sort

    • @MedeirosJoel_
      @MedeirosJoel_ 7 місяців тому +1

      @@sLokJoNas então essa seria minha primeira solução, não a ideal

    • @99temporal
      @99temporal 7 місяців тому +4

      Mas a questão fala que tem que ser linear

    • @ykyjohn
      @ykyjohn 7 місяців тому

      o fato de ser linerar sinifica q vc deve percorrer o array apenas uma unica vez. e memoria constante é como foi explicado no video. e a soluçao é realmente o unico jeito de ser linear e memoria constante. q no caso ele usou apenas 2 variaveis. ou seja o uso de memoria escala com o problema em si mas nao com o tamanho do problema. se o problema fosse de forma q os numeros se repetem 4 vezes ao inves de 3, teriamos q adicionar mais uma variavel.

    • @99temporal
      @99temporal 7 місяців тому +19

      @@ykyjohn não, ser linear não significa que você precisa percorrer o array apenas uma vez. Apenas que a quantidade de tempo de vezes que você percorre o array não pode escalar com o tamanho do array
      O(1000x) = O(x)

  • @fdelduquenobre
    @fdelduquenobre 28 днів тому

    Só pela thumb pareceu bem simples, mas no enunciado tem dizendo que precisa ter complexidade linear(não sei o que isso significa). Eu pensei em leia o primeiro numero, count com o valor, incrementar e repetir até encontrar. Poderia já salvar os números testados para reduzir dupla-testagem, mas acho que não pode "only constant extra space". Depois eu vejo o vídeo, eu tenho medo desses que vem com porcentagem baixa.

  • @Lucas94467
    @Lucas94467 7 місяців тому +2

    Tive que assistir 2 vezes pra entender. Fritou muito a cabeça kkkkkkk

  • @amandamachado2818
    @amandamachado2818 2 місяці тому

    Eu não sou muito boa com programação, mas bolei uma solução matemática pro problema:
    Somatório de todos os elementos da array:
    > For x de 0 a n
    > If x/3 = 0; x = x +1
    > somatório += x
    Depois de ter esse somatório:
    > For x de 0 a n
    > If (somatório -(x +1))/3 = 0; x é a resposta
    > Else; continua até achar x
    No final do somatório vc vai ter um número que não é divisível por 3, e se subtrair o número solitário +1, então o somatório vai sim ser divisível por 0.

  • @dudz1978
    @dudz1978 6 місяців тому +11

    A solução é engenhosa, mas seria bem mais fácil rodar 32 vezes _radix sort_ na base 2, uma para cada bit, e depois varrer a lista procurando o que aparece apenas uma vez. Claro que para isso ser considerado constante temos que contar com a limitação da quantidade de bits para cada número, o que poderia não ser verdade em Python ou com uso de algum BigInteger, mas isso já ocorre também no próprio xor, pois se fossem números com bilhões de bits isso de qualquer forma já teria que constar na fórmula do cálculo da complexidade algorítmica. O que nos leva a outro ponto: se precisamos contar com a limitação de bits para considerar como linear na quantidade de elementos, então por que não poderíamos fazer uso da própria limitação dessa quantidade de elementos para dizer que uma lista auxiliar também é limitada?! Dois pesos, duas medidas, de forma que não considero esse problema matematicamente preciso. Tem outra coisa: mesmo o radix sort teria 32 iterações, totalizando 32n operações, mas um simples sort de espaço adicional O(1) (por exemplo, heapsort) e tempo Θ(n log(n)) seria mais rápido, na prática, para n grandes até cerca de 2^30. Como a quantidade de elementos é *muito* menor que isso, um simples sort (até mesmo os prontos das linguagens de programação) passa no teste. Enfim, minha crítica ao problema é que precisa assumir algo (a limitação de bits) para ter solução de forma proposta, mas ao fazer isso abre espaço para fazer o mesmo do outro lado, considerando a limitação do número de elementos como um item necessário para afirmar que uma lista auxiliar ainda usa espaço constante.

    • @MorgaoFreud
      @MorgaoFreud 5 місяців тому

      Se dá pra fazer and not, daria pra fazer uma tabela verdade de 3 elementos também concatenado ?

  • @willianCastilh
    @willianCastilh Місяць тому +1

    No inicio eu nao tava entendendo nada, e no final parecia que eu estava no inicio.....

  • @LucasOliveira-zy6fj
    @LucasOliveira-zy6fj 6 місяців тому

    Caraca, peguei aqui pra resolver e gastei 1 hora, mas consegui fazer sem pesquisar, só com meu conhecimento em Java. Top!

  • @BrunoBafilli1
    @BrunoBafilli1 7 місяців тому +1

    Eu considero esse desafio médio, parabéns pelo vídeo.

  • @andremueller3892
    @andremueller3892 2 місяці тому

    Um outra solução, menos elegante, mas mais simples e que atende às specs do problema, seria iniciar um count: int = 1 e pra cada elemento el do array, multiplicar count por el e, se possível, divido por el ** 3 (cubo). No final, só terá sobrado o elemento único do array.

    • @carloshenrique-ov5nk
      @carloshenrique-ov5nk Місяць тому

      mais fácil ainda e menos elegante ainda é dar um print('1') kkkkk

  • @alexandresoutonogueira7675
    @alexandresoutonogueira7675 7 місяців тому +1

    no leetcode fala pra resolver em tempo linear, O(n). Mas eu implementei em O(nlog(n)) com TreeMap e passou. porém apenas acima de 8.85% dos outros desenvolvedores Java, ou seja, pior do que 91.15% de todos os outros.

  • @wellersondrumond3176
    @wellersondrumond3176 7 місяців тому

    o problema tem uma restrição onde todo numero na array de input aparece exatamente 3 vezes, exceto o número que tentamos encontrar, que aparece apenas uma vez, pra mim é mais facil apenas usar um hashmap que mantém a quantidade de vezes encontramos um número e deletar do hashmap caso foi encontrado mais de 2 vezes, assim o unico numero que sobra no hashmap é o numero que aparece apenas 1 vez, acessar um numero no hashmap sempre será O(1) e dessa forma vc sempre corre pelo array 1 vez, ou seja, no final dá O(n) da mesma forma com um código imensamente mais compreensível

    • @wellersondrumond3176
      @wellersondrumond3176 7 місяців тому

      nem vi que era O(1) space 💀 achei bobo mas me pegou

    • @ZantsuRocks
      @ZantsuRocks 7 місяців тому +1

      Mas não usa alocação constante, usa alocação "dinamica"

  • @mynameisleonardoactually
    @mynameisleonardoactually Місяць тому

    Legal pra carai, mas qual a aplicação prática desses desafios que colocam nas entrevistas? não tenho muita exp com programação (fiz curso introdutório de webdev uns anos atrás e decidi que TI não era pra mim, mas agora que to em logística só mexo ocasionalmente com python por hobby) mas 90% desses negócios parecem muito fora da realidade do dia a dia

  • @nastrimarcello
    @nastrimarcello Місяць тому

    Então tava sem ideia alguma de como resolver em espaço linear até você mostrar a solução do problema anterior.
    Você usou a função XOR que quando aplicada duas vezes com mesmo valor acaba eliminando o valor.
    Eu pensei numa solução praticamente igual so que quando aplica 3 vezes a tal função no mesmo valor.
    Chamei de xor_base_tres.
    Você vai simplesmente usar
    reduce(xor_base_tres, lista)
    E pronto!
    Se quiser posto um código que rabisquei num pedaço de papel. É bem simples mesmo.
    Você precisa converter pra base 3 o número e somar digito a digito sem carry over. Ou seja você tem que fazer 2+1=0 (base 3), 2+2=1 (base 3). O normal seria 2+1=10 (base 3) e 2+2=11 (base 3). As outras somas digito a digito não sofrem alterações (0+0,0+1,0+2,1+0,1+1,etc)
    Assim sempre que for somar 3 vezes algum número você sempre retorna pro zero
    Edit:
    def to_trit(num):
    """
    Retorna o trit de um número
    """
    if num==0: return "0"
    "Criar trit a partir de divisões sucessivas"
    trit,q="",num
    while q>0:
    q,r=divmod(q,3)
    trit+=str(r)
    return "".join(reversed(trit))
    def from_trit(trit):
    """
    Criar número a partir do trit
    """
    "Criar número a partir de multiplicações e adições sucessivas"
    num=0
    for r in trit:
    num*=3
    num+=int(r)
    return num
    def xor_3(a,b):
    """"
    Faz operação similar ao XOR porém na base 3
    """
    "Colocar menor dos números em 'tb' e o outro em 'ta' ''
    if b>a:
    ta,tb=to_trit(b),to_trit(a)
    else:
    ta,tb=to_trit(a),to_trit(b)
    trit=""
    "Iterar sobre o menor trit tb"
    for k in range(len(tb)):
    "Pegar caracteres a comparar nos trits"
    m,n=ta[-k-1],tb[-k-1]
    "Somar caracteres"
    dig=int(m)+int(n)
    "Realizar XOR"
    trit+=str(dig) if dig

    • @nastrimarcello
      @nastrimarcello Місяць тому +1

      def to_trit(num):
      if num==0: return "0"
      trit=""
      q=num
      while q>0:
      q,r=divmod(q,3)
      trit+=str(r)
      return "".join(reversed(trit))
      def from_trit(trit):
      num=0
      for r in trit:
      num*=3
      num+=int(r)
      return num
      def xor_3(a,b):
      if b>a:
      ta,tb=to_trit(b),to_trit(a)
      else:
      ta,tb=to_trit(a),to_trit(b)
      trit=""
      for l in range(len(tb)):
      m,n=ta[-l-1],tb[-l-1]
      dig=int(ta[-l-1])+int(tb[-l-1])
      trit+=str(dig) if dig

    • @nastrimarcello
      @nastrimarcello Місяць тому +2

      Você não sabe o inferno que foi escrever isso pelo celular.

  • @lionbraz
    @lionbraz 7 місяців тому +11

    como brincadeira isso é mto legal mesmo. o foda é usarem essas paradas em entrevistas, ou tipo o caso do primeiro comentário que perdeu o emprego pq não fica fazendo essas porras. dai o cara sabe leetcode e não sabe estruturar um código legível, ou debugar algo complexo, nem entro no mérito de quais arquiteturas de software usar para cada problema. tipo, tu só seleciona gente com tempo e paciência para ficar brincando, que não necessariamente vai adicionar numa empresa.

    • @tiagorafael9872
      @tiagorafael9872 6 місяців тому +3

      Isso nunca será um problema pra big techs. Eles tem dinheiro de sobra pra queimar treinando seus funcionários e tão pouco se importando se você tem habilidades em escrita de código legível e habilidades pra debugar códigos complexos. Eles não precisam disso, eles tem a comunidade open source pra debugar e melhorar o código se for necessário. A regra é que código é descartável, e os projetos que eles desejam manter por muito tempo vira open source, e toda a comunidade que usa código faz esse trampo que você falou.
      "tu só seleciona gente com tempo e paciência para ficar brincando".
      É esses caras que eles precisam. Se alguém surge com uma ideia que vai de algum modo contribuir com o modelo de negócio ou estratégia do conglomerado, é desses caras que tiveram tempo pra ficar brincando com peculiaridades de complexidades e firulas de algoritmos que eles precisam pra fazer o bagulho funcionar.
      De acordo com o livro do Google, a primeira versão do rankeador era um lixo de código. Foi reescrita várias vezes (do zero) durante os primeiros anos do google. Mas ainda assim o valor que esses ranqueador entregava já era anos luz a frente dos concorrentes.

  • @lazaromaganha3803
    @lazaromaganha3803 7 місяців тому

    Seus vídeos são demais mano!

  • @gabrielvieira2054
    @gabrielvieira2054 7 місяців тому

    Incrível esse aula, muito obrigado!

  • @Lucas94467
    @Lucas94467 7 місяців тому +1

    Esses problemas geralmente são para serem resolvidos com a menor complexidade possível, mas a solução em si é facil, só agrupar os valores e pegar o com Count/Length == 1 kkkkkkkk

    • @cristianofelipe9907
      @cristianofelipe9907 7 місяців тому

      Pensei nisso, só um if e um return resolvia, n sei se em python o count é Implementado em c

    • @seveng0th
      @seveng0th 7 місяців тому

      Em c# daria pra resolver fazendo um Array.Sort(nums), e depois um for comparando o nums[i] com o nums [i+1], se for >< pronto, resolveu.

    • @michaelnicholas926
      @michaelnicholas926 7 місяців тому

      @@seveng0th Não daria, a função de sort não é executada em tempo linear, acho que a implementação do C# e de muitas outras linguagens é de O(n log(n))

    • @EdgarEndoJunior
      @EdgarEndoJunior 7 місяців тому +1

      Agrupar os valores faz a complexidade de espaço não ser mais O(1) pois o tamanho desses valores agrupados dependerá do tamanho do array fazendo sua solução ter complexidade espacial O(N) e não O(1) que é um dos requisitos do problema.

  • @TheRageOm
    @TheRageOm 6 місяців тому +6

    Em linguagem Python, a utilização de in pode ser bastante útil para esses problemas.
    Eu não sei se faz parte da regra eliminar a lista principal, ou alterar a numeração dos índices, mas se isso for permitido, uma ideia seria
    while nums:
    vari = nums.pop(0)
    if vari in nums:
    while vari in nums:
    nums.remove(vari)
    else:
    break
    Se a memória da lista precisar ficar intacta, um algoritmo que retorna o número de ocorrências de verificação linear poderia percorrer um a um:
    for i in nums:
    if nums.count(i) == 3:
    continue
    else:
    return i
    Se a lista poder ser semi alterada, você pode fazer uma brincadeira de ir jogando o item da frente para trás, mantendo-os na mesma lista, parando apenas no item único:
    while True:
    vari = nums.pop(0)
    if vari in nums:
    nums.append(vari)
    else:
    nums.append(vari)
    return nums[-1]
    ETC

    • @Renan_PS-zt8lm
      @Renan_PS-zt8lm 6 місяців тому +5

      Todas essas soluções tem complexidade de tempo quadrática e não linear como o exercício pede.
      Na sua primeira solução: O método nums.remove percorre o vetor inteiro para encontrar o número a ser removido, como ele faz isso para cada valor do vetor então é O(n*n) = O(n^2)
      Na sua segunda solução: método nums.count literalmente percorre o vetor inteiro contando quantas vezes o número aparece, logo se ele percorre o vetor 1 vez para cada número no vetor é O(n*n) = O(n^2)
      Na terceira você usa "if vari in nums" para determinar se isso é verdadeiro ou falso ele percorre nums inteiro procurando a variável, logo se ele percorre o vetor uma vez para cada elemento então é O(n*n) = O(n^2)
      Esse é um probleminha do python, usando as funções que ele tem implementado pode ficar difícil de perceber a eficiência do próprio código, por não saber como foi feita a implementação dessas funções.

    • @TheRageOm
      @TheRageOm 6 місяців тому +2

      @@Renan_PS-zt8lm Acredito que estamos tendo um erro de contextualização.
      Por definição, "Linear Complexity" aumenta conforme a quantidade do input (tamanho do iterável lista[int]), a cada elemento. Em outras palavras, se um elemento tem 1 tempo para ser resolvido, se colocar 2 elementos o tempo de execução deve ser 2 tempos.
      Logo, se para analisar 1 item ele leva 0.05 segundos, com 2 itens ele deve levar 0.10 segundos, e assim sucessivamente
      Dentro do conceito de n², se eu aumentar 1 item, esse tempo multiplica. Ou seja, se um programa leva 0.05 segundos, com 2 itens ele leva 0.25 segundos, por causa dos protocolos de percorrimento.
      Nos percorrimentos dos algoritmos apresentados, a execução do programa não se multiplica de n² por cada input a mais, são execuções de percorrimento simples.
      Em outras palavras, se demora 0.10 segundos para encontrar o elemento único em uma lista com 10 elementos, é de complexidade linear que ele demore 1 segundo em uma lista com 100 elementos.
      Um erro dos exemplos do qual eu entenderia a crítica seria "Mas no programa não pode alocar memória para responder, ou seja, criar variáveis", eu entenderia, e responderia algo mais simplório ainda:
      while len(nums.count(nums[0])) == 3: nums.append(nums.pop(0))
      return nums[0]
      E assim nem variável seria utilizada.
      Esse tipo de problema não é sobre agilidade de processamento, mas sim sobre algoritmo que não use muito memória, mesmo que demorado. Não necessariamente um algoritmo de Complexidade Linear é ágil, porém, mais ágil que outros.

    • @Renan_PS-zt8lm
      @Renan_PS-zt8lm 6 місяців тому +3

      @@TheRageOm O exercício específica que a complexidade de memória deve der constante e a complexidade de tempo tem que ser linear. O nums.count não descobre quantas vezes um elemento aparece no vetor magicamente, na implementação da função ele percorre o vetor inteiro e conta quantas vezes aparece. Ou seja, se você chama um nums.count (O(n)) para cada elemento do seu vetor (O(n)) a complexidade de tempo do algoritmo fica O(n^2).
      Quando falamos da complexidade de memória, criar variáveis ou não não impacta na complexidade assintótica, a não ser que o número de variáveis cresça com o tamanho do vetor. Assintótica significa que constantes multiplicativas são desconsideradas, logo O(4627193) = O(1).

    • @TheRageOm
      @TheRageOm 6 місяців тому

      @@Renan_PS-zt8lm O problema é que você está interpretando que o script está lendo a lista. Ler a lista faz parte da subrotina. O conceito de O(n²) não é para scripts, mas sim para as consequências de adicionar mais ou menos elementos ao iterável.
      Desta forma, ao adicionar 1 elemento, ela não aumenta o tempo linearmente, mas de forma exponencial. Isso ocorre com base no código, mas o conceito se aplica aos tamanhos dos iteráveis.
      Vou dar um exemplo:
      - uma str com len == 4
      - cada caractere vai de a até z
      - quantas formações aleatórias são criadas?
      Caso eu aumente essa str para 5, aumenta consideravelmente, se for 6, ainda mais, etc
      Isso não ocorre nos exemplos apresentados.

    • @Renan_PS-zt8lm
      @Renan_PS-zt8lm 6 місяців тому +3

      @@TheRageOm Nos seus exemplos, se a lista tiver 4 elementos vai demorar 16t, sendo t um intervalo de tempo constante arbitrário, agora se tiver 5 elementos vai 25t. Crescimento quadrático.

  • @jorgedemacedo
    @jorgedemacedo 6 місяців тому

    Já dizia um professor meu na universidade: "Olha a sacada dos caras"

    • @thomasthemazzerrunner3615
      @thomasthemazzerrunner3615 6 місяців тому

      o meu falava "Olha esse esquema dos caras", levo esse termo "esquema " pra vida toda

  • @badbass555
    @badbass555 2 місяці тому

    Mano, pensei que era outro Galego, esse cabelo de rockeiro ai parça? Essa realmente deu uma esquentada na cuca

    • @alex123rip2
      @alex123rip2 Місяць тому

      Escreve como gente por favor.

  • @rafael_tg
    @rafael_tg 7 місяців тому

    video sensacional. Quando você postou no twitter fiquei pensando no problema por vários dias.

  • @palmitexx
    @palmitexx Місяць тому

    com javascript eu meti essa: ( só n sei se cumpre TODOS os requisitos de complexidade e etc)
    var singleNumber = function(nums) {
    let excluded = {};
    let stage = {};
    nums.forEach(num => {
    if (excluded[num] !== undefined) {
    return;
    }
    if (stage[num] !== undefined) {
    excluded[num] = num;
    delete stage[num];
    } else {
    stage[num] = num;
    }
    });
    return Object.keys(stage)[0];
    };

  • @danielagostinho8993
    @danielagostinho8993 7 місяців тому

    Rapaz realmente praticamente impossível pensar nessa solução sem ter visto algo parecido antes kkk,

  • @AlexSRSoares
    @AlexSRSoares Місяць тому

    Só pode fazer em python? Com operadores bit a bit sai fácil em c.

  • @occidens6350
    @occidens6350 25 днів тому

    Sou programador de empresa, mais prático e nunca dei muita atenção pra problemas de programação desse tipo. Pode soar como ignorância da minha parte, mas nao daria pra fazer um sort na lista e dps percorrer pra achar o item único usando 3 variáveis de comparação? Não sei se dessa forma o uso de memória iria aumentar

    • @ricardovinicius9015
      @ricardovinicius9015 19 днів тому

      Daria, mas o problema exige solução em tempo linear, isso é, O(n). De forma simples, você não pode percorrer a lista de modo que para cada elemento você percorra ela novamente, ou algo nesse sentido (um for dentro de um for). Nesse caso teríamos um valor constante de espaço de memória a depender do algoritmo de ordenação, um heapsort por exemplo teria complexidade de espaço O(n). Só que o mínimo de complexidade para um algoritmo de ordenação comum é O(nlogn) o que fere o enunciado que pede tempo linear. Esses problemas em geral não são muito comuns de se encontrar no dia a dia de um programador mais comum, mas são uma base muito importante para algoritmos e estrutura de dados, e projeto e análise de algoritmos, que são campos bastante relevantes para otimização, banco de dados, e outras aplicações de ciência da computação. Para nós, meros mortais, que trabalhamos na indústria, servem como aprendizados para entendermos o porquê de nossos códigos estarem lentos, e conseguir analisar matematicamente estes comportamentos; ou simplesmente passar em entrevista de empregos 😂.

  • @codeumdesenvolvimento
    @codeumdesenvolvimento 6 місяців тому

    Cara top de mais, mas se tiver uma sequencia de números aleatório, digamos todos entre 0 e 9, como determinar quais números não se repetem, e se algums números aparecem 2 e outros 3 vezes
    Pelo que entendi o primeiro algoritmo serve para um uso geral e os demais servem para um uso especifico, mas ainda sim é válido, muito obrigado pelo vídeo você é 10

  • @hfsaito
    @hfsaito 6 місяців тому

    Acho que é mais fácil de entender se fazer
    twos ^= num & ones;
    ones ^= num & ~twos;
    Trocando a ordem voce pode verificar o ones anterior para utilizar no twos

  • @jonfer9999
    @jonfer9999 Місяць тому

    Faz um tempo que não vejo sobre programação, mas alguém pode me responder pq não seria possível uma solução na qual você passaria um for checando a presença de números repetidos e removendo-os do array?

    • @victorespeto
      @victorespeto 26 днів тому

      você vai tá alocando uma memória de tamanho variável, armazenando se o cara já apareceu o não, se a lista for gigante sua memória alocada vai ser gigante

  • @williansteinagel
    @williansteinagel 6 місяців тому +1

    4:35 Esse reduce e esse xor aí não vão dar undefined??

  • @Tomagu_
    @Tomagu_ 7 місяців тому +2

    Essa questão ser classificada como "medium" é sacanagem kkkkkkkkkkkkk. E teu áudio tá baixo, tenho que sair do volume 20 pro 50 pra poder escutar bem.

  • @sama_gotec
    @sama_gotec 7 місяців тому +23

    Adoro seus vídeos, porém, sempre o seu áudio está MUITO baixo. :(

  • @styles6788
    @styles6788 Місяць тому +2

    em c++ meti dois for loop e consegui time complextiy O(n^2) e space complexity O(1)

  • @avelhabolachuda
    @avelhabolachuda 7 місяців тому +6

    Faz um radix sort, testa se 2 em sequencia são iguais, se sim soma 3 pro index, se não ou se for o último retorna ele

  • @DaviBohn123
    @DaviBohn123 Місяць тому

    Em python:
    lista = [2,5,4,4,5,2,7,8,8,4]
    for n in lista:
    if lista.count(n) == 1:
    print(n)
    Isso não resolve?

    • @alexandrecaldas9215
      @alexandrecaldas9215 Місяць тому

      "Resolve", mas ele vai ter complexidade O(n^2), porque tem o for loop por todos os itens da lista que custa O(n) e a função lista.count() também passa por todos os itens da lista que custa O(n), tornando a solução O(n^2).

  • @joaofranco3795
    @joaofranco3795 6 місяців тому

    isso não seria meio que fazer soma e subtração sequencialmente até terminar os valores do array?

  • @lucaslugao
    @lucaslugao 6 місяців тому

    Eu resolvi de maneira pais pragmatica... conta os bits numa lista. Faz mod 3 na lista depois reconstroi o numero. A complexidade e identica ja que o tamanho do inteiro e constante, porem nao tem magia nenhuma. O lado bom da solucao por contagem de bits e que da pra fazer pra qualquer numero de repeticoes sem nenhum problema, sei la, 7 repeticoes.

  • @Mexpenses
    @Mexpenses 7 місяців тому

    em javascript pensei dessa forma:
    let nums = [2, 2, 1, 2];
    const findSingleNumber = () => {
    let single;
    nums.forEach(num => {
    const filterLength = nums.filter(itemNum => itemNum === num);
    if (filterLength.length === 1) {
    single = filterLength[0];
    }
    })
    console.log(single)
    }
    findSingleNumber();

    • @maudjito
      @maudjito Місяць тому

      Mas aí com `forEach` e `filter` vira O(n^2). Ele pede pra resolver em "linear runtime complexity", ou seja, O(n), só percorrendo a lista de números uma única vez.

  • @arthurramos1161
    @arthurramos1161 7 місяців тому +60

    mano, vc consegue deixar o audio do video um pouco mais alto?

    • @arturmg2068
      @arturmg2068 7 місяців тому +5

      Não

    • @TheEscuro
      @TheEscuro 7 місяців тому +8

      Aumenta o volume

    • @DjEdu28
      @DjEdu28 7 місяців тому +5

      Eu uso uma extensão chamada soundFixer, recomendo usar ela também. É possível aplicar ganho nos áudios do navegador de até 5 (500%)

    • @GS12.3D
      @GS12.3D 7 місяців тому

      Pra que

    • @quemediga
      @quemediga 7 місяців тому +6

      Foi irônico? Pra mim parecia alto demais kkk

  • @inosuke3626
    @inosuke3626 6 місяців тому

    Pensei e implementei um O(n) e desisti de implementar a O(1) kkkkk

  • @reyynaldo.
    @reyynaldo. 2 місяці тому

    Qual a plataforma o Galego está usando?

  • @guilhermecoelho7012
    @guilhermecoelho7012 7 місяців тому

    po essa solução é matemática computacional puro

  • @petersonfranciscodacostase3099
    @petersonfranciscodacostase3099 Місяць тому

    comecei a fazer em C aqui, realmente é difícil ...

  • @quemediga
    @quemediga 7 місяців тому +1

    Só registrando minha solução de iniciante coda fofo no início do vídeo: criaria um novo array e uma função em loop para verificar o próximo item do array principal, se for diferente dos itens anteriores adicionaria o valor ao novo array, se não, sendo igual a algum anterior excluiria do novo array. Acho que usaria find pra vasculhar o array, e um for loop pra função, mas confesso que nem sei certo de cabeça como implementaria pra funcionar

    • @lPandoraBox
      @lPandoraBox 7 місяців тому +1

      tbm faria assimkkkkkkkkkkkkkk

  • @gabriell4815162342
    @gabriell4815162342 6 місяців тому

    Fiz assim, mas n li direito as regras rs, mas é bem legal o desafio
    const number2 = array.find(i => { if (array.filter(j => j === i).length === 1) return i })
    ou assim
    const number = array.find(i => { if (array.filter(j => j === i).length !== 3) return i })

  • @raphaelninoo
    @raphaelninoo 6 місяців тому +1

    Isso aqui passa no sistema que vc ta usando?
    private static void Main(string[] args)
    {
    int[] lista = { 21, 7, 22, 7, 2, 3, 2, 7, 3, 5, 6, 21, 8, 6 , 10, 5, 17, 10, 11, 12, 200, 11, 200, 12, 17, 22 };
    Array.Sort(lista);
    bool duplicado = false;
    int solucao = lista[0];
    for (int i = 0; i < lista.Length; i++)
    {
    if (lista[i] == lista[i + 1])
    {
    duplicado = true;
    }
    else if (duplicado == false)
    {
    break;
    }
    else
    {
    solucao = lista[i + 1];
    duplicado = false;
    }
    }
    Console.WriteLine(solucao);
    Console.ReadLine();
    }

    • @caiocutrim3596
      @caiocutrim3596 29 днів тому

      passa não, o sort ali pode tá usando o extra-space

  • @libercode9886
    @libercode9886 Місяць тому

    No final, ao invés de fazer o & ~ twos, n seria mais simples (e mais eficiente) só retornar ones ^ twos?

  • @rogercruz1547
    @rogercruz1547 Місяць тому

    Oi Augusto,
    Tentando acompanhar o vídeo só que muitas vezes vejo que no meio da explicação você pára pra reexplicar XOR a cada 10 segundos... então a gente tenta acompanhar o algoritmo mas tem um "intervalo comercial do patrocinador XOR que tornou tudo isso possível" entre cada linha do algoritmo e acaba distraindo muito.

  • @kauedelmonte9432
    @kauedelmonte9432 7 місяців тому

    Alguém pode passar o link do vídeo onde ele resolve a parte 1 do problema? Fiquei com algumas dúvidas.

  • @mattheusspoo
    @mattheusspoo 7 місяців тому

    Não assisti o vídeo (ainda) e resolvi o problema usando o thumbnail com javascript. Não sei as especificações e provavelmente existem formas melhores de se fazer, mas levei uns 3 minutos pra fazer:
    let a = [2,7,7,2,3,2,7]
    let b = [];
    a.forEach(item => {
    if(a.filter(i => i === item).length === 1) b.push(item)
    });
    enfim, com certeza da pra melhorar isso, mas é funcional.

    • @ZantsuRocks
      @ZantsuRocks 7 місяців тому

      Essa solução não utiliza alocação "fixa" pois tem DUAS listas. (uma é a variavel b e a outra é o retorno do metodo filter)

    • @mattheusspoo
      @mattheusspoo 7 місяців тому +1

      @@ZantsuRocks como eu disse, nao tinha visto o video, so o thumbnail.

    • @TalesIagoBatista
      @TalesIagoBatista 6 місяців тому

      @@ZantsuRocks Sim, mas essa soluçao resolve quando tem multiplos itens nao repetidos... Se nao quer, so retornar o item em vez de dar push....

    • @ZantsuRocks
      @ZantsuRocks 6 місяців тому

      @@TalesIagoBatista Na verdade não, o return dentro do metodo forEach "não faz nada", ele vai seguir executando o forEach até o fim

    • @gabriell4815162342
      @gabriell4815162342 6 місяців тому

      Legal a solução pensei em algo bem parecido
      const number = array.find(i => { if (array.filter(j => j === i).length === 1) return i })

  • @marcos-2023
    @marcos-2023 Місяць тому

    Eu aqui vendo esse vídeo vidrado sem nem saber html e css KKKKKJ

  • @danielcampos8986
    @danielcampos8986 7 місяців тому

    Qual o site que você usa para gravar esses vídeos?

  • @levymarquesnunes7128
    @levymarquesnunes7128 2 місяці тому

    49ms
    Beats: 91.69%

  • @GabrielBrisolara-c1t
    @GabrielBrisolara-c1t 7 місяців тому

    Qual aplicativo usa para gravar a tela e mexer a webcam assim

    • @TheDenysabner
      @TheDenysabner 6 місяців тому

      OBS Studio

    • @GabrielBrisolara-c1t
      @GabrielBrisolara-c1t 6 місяців тому

      @@TheDenysabner N tenho certeza, pq ele mexe a camera arrastando com o mouse

    • @rogeriossp
      @rogeriossp 6 місяців тому

      @@GabrielBrisolara-c1t isso é normal no OBS

  • @ignaciosavi7739
    @ignaciosavi7739 Місяць тому

    Eu resolvi. Acho. De uma maneira diferente. Mas eu n tenho certeza se funcionaria pra todos os casos

  • @oscarmadureira3431
    @oscarmadureira3431 7 місяців тому

    Eu usaria um vetor de 31 bits
    E contaria bit a bit
    Sua solução é maneira

    • @oscarmadureira3431
      @oscarmadureira3431 4 місяці тому

      class Solution {
      public:
      int singleNumber(vector& nums) {
      vector vet(32);
      int res = 0;
      for(int i = 0; i < nums.size(); i++){
      for(int j = 0; j < 32; j++){
      if((nums[i] & (1

  • @derkonig7820
    @derkonig7820 7 місяців тому

    `input = [2,2,3,2]
    def single_number(arr):
    if len(arr) == 0:
    return 0
    else:
    if len(arr) == 1:
    return arr[0]
    else:
    return arr[0] if arr[0] not in arr[1:] else single_number(arr[1:])
    print(single_number(input))`quando resolvi sem ver o vídeo fiz assim e nem percebi que era O(1)

    • @michaelnicholas926
      @michaelnicholas926 7 місяців тому +2

      No pior caso, ele vai executar essa operação IN uma vez pra cada elemento do array, ou seja, no final a complexidade não é linear e sim quadrática. E acredito que o uso de slice como arr[1:] também crie uma lista em memória pra fazer a comparação, então acho que também acaba que não fica O(1) a complexidade de espaço

    • @derkonig7820
      @derkonig7820 7 місяців тому +1

      @@michaelnicholas926 isso que quis dizer, nem percebi que a questão queria O(1) o meu caso, no pior seria O(n^2), não?

    • @michaelnicholas926
      @michaelnicholas926 7 місяців тому

      @@derkonig7820 Em relação a espaço, eu acho que a lista que a função slice cria só é usada na operação do IN e depois é excluida então creio que seja O(n) (me corrige se estiver errado kkkk), mas em relação a complexidade de tempo é n^2 sim no pior caso

  • @phillipgallas
    @phillipgallas 2 місяці тому

    Muito legal o conteúdo do canal, Augusto!
    Eu pensei em uma outra ideia. Por que não utilizar um sort() para ordenar o array, e já que cada conjunto de números repetitivos estarão agrupados, podemos usar uma série de variáveis constantes para checar qual número não repete?

    • @LucasSilva-ut7nm
      @LucasSilva-ut7nm Місяць тому +1

      Então porque o desafio é fazer em tempo linear! O sort é O(n log n)

  • @skblink
    @skblink 6 місяців тому

    Não consigo entender a sintaxe de python ainda

  • @marcosfc123
    @marcosfc123 7 місяців тому +3

    Praticamente uma máquina de turing kkkkkkkkk

  • @clebsonsantiago
    @clebsonsantiago 7 місяців тому

    Gosto muito do seu Canal.

  • @Joaobatista-kx3sw
    @Joaobatista-kx3sw Місяць тому

    Muito louco, incrível

  • @wellor1
    @wellor1 6 місяців тому

    Esta solução é sua ou tem outra origem?

  • @zec_s
    @zec_s 7 місяців тому

    meu parcerinho que programa/site é esse do fundo preto??

    • @PintoDonald
      @PintoDonald 7 місяців тому +1

      vscode

    • @zec_s
      @zec_s 7 місяців тому

      ​@@PintoDonald kkkkkkk obg mano, mas me referi a o programa q ele "desenha" a lista, as setas e afins

    • @PintoDonald
      @PintoDonald 7 місяців тому

      @@zec_s ops kkkkk

    • @HIM-br9qy
      @HIM-br9qy 7 місяців тому +1

      ​@@zec_s Não sei se você já chegou a descobrir, mas se caso não o website usado é o Excalidraw.

    • @zec_s
      @zec_s 7 місяців тому

      @@HIM-br9qy obrigado

  • @joaoc4508
    @joaoc4508 6 місяців тому

    youtube premium ótimo vídeo

  • @vitorsilva-or1dj
    @vitorsilva-or1dj 7 місяців тому +1

    ta sussurrando kkkkkkkk

  • @johnniefujita
    @johnniefujita 6 місяців тому

    ?Ha alguma generalizacao pra n repeticoes

    • @GutoGalego
      @GutoGalego  6 місяців тому

      Pior que existe sim. Mas esse já foi difícil de explicar kkk

  • @seveng0th
    @seveng0th 7 місяців тому

    Isso é super facil. Ordena os elementos do array em ordem crescente e faz um for, se array[i] for diferente de array[i+1], fim, achou.

    • @DjEdu28
      @DjEdu28 7 місяців тому

      Pensei nisso, problema de ordenar é que a memória vai ser alterada dinamicamente (vai ser alocado na memória uma nova variável com o mesmo tamanho do input), exceto que fabrique teu próprio código para ordenar manipulando/destruindo a variável de entrada

    • @GutoGalego
      @GutoGalego  7 місяців тому +3

      Eu esqueci de mencionar no vídeo, mas isso quebra outra premissa do problema. Precisa ter linear runtime complexity, ou seja, rodar em O(n). ordenar é n log n

    • @seveng0th
      @seveng0th 7 місяців тому +1

      @@GutoGalego com O(n) acho que dá pra fazer com um for e um while, vou tentar e jaja replico aqui.

    • @cristianomoraes4721
      @cristianomoraes4721 7 місяців тому

      conseguiu?@@seveng0th

    • @rafael.damiani
      @rafael.damiani 2 місяці тому +2

      @@seveng0th aqui jaz um dev, 4 meses depois e o rapaz ainda ta tentando.

  • @victorbarbosa5205
    @victorbarbosa5205 6 місяців тому

    Fiz assim com Js
    const singleNumber = (nums) => {
    const [num] = nums.filter(
    (num) => nums.indexOf(num) === nums.lastIndexOf(num)
    );
    return num;
    }

  • @tauk7975
    @tauk7975 7 місяців тому +1

    dar sorted na lista e fazer um for que pula de 3 em 3, e parar quando achar um item da lista q o proximo dele não seja igual a ele seria uma maneira eficiente?

    • @samon101
      @samon101 7 місяців тому +1

      Não pq a operação sorted é cara, mas talvez o site aceite a resposta

    • @gabrielfreitas4270
      @gabrielfreitas4270 7 місяців тому +1

      Radix sort pode ter tempo linear em casos que a quantidade de dígitos não crescem significativamente com o tamanho da conjunto, que é o caso aqui. Realmente pode ser uma boa! Foda é lembrar como implementar de cabeça kkkkkkkk

    • @gabrielfreitas4270
      @gabrielfreitas4270 7 місяців тому +1

      Fui confirmar e não valeria por que o radix sort tem complexidade de espaço O(N) 😅

  • @seijurouhiko
    @seijurouhiko 7 місяців тому +5

    3 não é 110

    • @AlexandreSenpai
      @AlexandreSenpai 7 місяців тому +2

      Já que o anjo de Deus não se deu ao trabalho de corrigir:
      3 em binário não seria 110 e sim 11.

    • @estenio
      @estenio 7 місяців тому

      #ajudei

  • @G_nono
    @G_nono 6 місяців тому

    Que site é esse aonde você pegou o desafio?

  • @IgorSprovieri
    @IgorSprovieri 6 місяців тому

    Esse problema é bem simples, é só rodar um for na lista e criar outra lista com as frequências de cada elemento na lista principal, depois você saberá quais elementos tem na lista e quantas vezes eles se repetiram

  • @mateusserafim4876
    @mateusserafim4876 7 місяців тому

    Qual o site dos desafios?

  • @pandasoli6581
    @pandasoli6581 6 місяців тому

    Como alguem chega em uma solucao como essa??

  • @toninhoprodesp
    @toninhoprodesp 6 місяців тому +1

    Apenas 1% dos devs "consegue" resolver. Que falta faz o primário!

    • @GutoGalego
      @GutoGalego  6 місяців тому +3

      Está correto utilizar "consegue", pois "1%" é singular. Que falta faz o secundário 🤭🤭

    • @GutoGalego
      @GutoGalego  6 місяців тому +1

      www.tjsc.jus.br/web/servidor/dicas-de-portugues/-/asset_publisher/0rjJEBzj2Oes/content/como-concordar-frases-com-percentual-ou-porcentual-
      De nada amigão, recebeu aula de software, de português e aprendeu a não ser pedante, principalmente quando não sabe do que ta falando.

    • @TheRageOm
      @TheRageOm 6 місяців тому

      Mas ele está correto, pois o consegue se refere ao problema, e não aos desenvolvedores.

    • @felipe.raposo
      @felipe.raposo 6 місяців тому +1

      ​@@TheRageOm tá doido? Consegue concorda com o sujeito, que no caso seria "1%"

    • @GutoGalego
      @GutoGalego  6 місяців тому +1

      @@felipe.raposo eu nem entendi se é meme ou não o que esse cara ta falando KKKKKKK. Só sei que o que fez o comentário original é o tipo de pessoa mais insuportável da internet. O desnecessariamente pedante. No caso agora ele ficou bem quietinho e sumiu pq ele percebeu que ele tava errado e passou altas vergonha.

  • @papalardo
    @papalardo 7 місяців тому

    Não é só criar um map incrementando a quantidade caso já exista? Ou entendi errado?

    • @vulcan4085
      @vulcan4085 7 місяців тому +3

      No início do vídeo ele explica o porquê dessa solução não ser válida para o problema.

  • @sezeki_
    @sezeki_ 6 місяців тому

    isso funcionaria?
    class Solution:
    def singleNumber(self, nums: List[int]) -> int:
    for j in range(len(nums)):
    x = 0
    for i in range(len(nums)):
    if nums[j] == nums[(-i-1)] and ((-i-1)+len(nums)) != j:
    x = 1
    if x == 0:
    y = nums[j]
    return y

    • @TheRageOm
      @TheRageOm 6 місяців тому

      Acredito que não, pois nesse algoritmo a verificação se daria por matriz de ij, sendo que é dito nas restrições que todas as réplicas de int aparecem três vezes, exceto um (que aparece uma única vez).
      Ao longo da análise, y armazenaria apenas o que não apareceu 2 vezes na matriz.
      Mas, e se x == 1? Logo, o código nunca resolveria o valor de y, dando erro de execução. Esse erro, apesar de parecer impossível, deve ser evitado, pois existe uma probabilidade dele acontecer (lista int com apenas um valor).
      Outra restrição é que a análise deve ser feita em tempo O(n), ou seja, o tempo por item deve crescer de forma linear com o tamanho de itens. Nessa execução, seria algo mais parecido O(n²), por se tratar de análise em matriz, deixando o tempo o quadrado de tempo a ser analisado
      Então acredito que sim, pode funcionar, mas para o problema é inviável segundo os requerimentos.

  • @AmodeusR
    @AmodeusR 6 місяців тому

    Qual é o uso prático do conhecimento requisitado por esse desafio?

    • @william.strebe
      @william.strebe 13 днів тому

      passar na entrevista de emprego onde ele for solicitado (:

    • @AmodeusR
      @AmodeusR 13 днів тому

      @@william.strebe Ou seja, é inútil.

    • @william.strebe
      @william.strebe 13 днів тому

      @@AmodeusR se tu n querer o emprego, é kkkk.

    • @william.strebe
      @william.strebe 13 днів тому

      mas fora isso tem algumas coisas que são bem raras de se ter no dia a dia mesmo.

  • @whiskas-1
    @whiskas-1 Місяць тому

    11b = 3 não?

  • @TheRageOm
    @TheRageOm 7 місяців тому

    Primeiro de sort em num.
    crie um loop onde ele caminha nos elementos da lista, e faça uma leitura do próximo item da lista.
    Caso o próximo seja igual, então coloque uma condição que enquanto o número for X é continue.
    Se o ciclo recomeçar e o próximo não for igual, ou chegar ao fim sem duplicatas, então ele é único.

    • @augusto1997
      @augusto1997 7 місяців тому

      de fato funciona ahaha embora nas constraint do problema menciona que a solucao precisa ser em O(N). Como a sua solução requer um "sort" estamos falando de ao menos O(n log n) (para algoritmos que usam comparação como quick, merge) vale ver os que usam a abordagem de contagem mas para isso creio que seria necessario outro array para a "contagem".

    • @thiagovieira8569
      @thiagovieira8569 6 місяців тому

      @@augusto1997 radix sort é linear.

    • @augusto1997
      @augusto1997 6 місяців тому

      @@thiagovieira8569 yep. Embora ele não é O(1) em espaço. Ou seja ele precisa de memoria extra para auxiliar na ordenação.

    • @thomasthemazzerrunner3615
      @thomasthemazzerrunner3615 6 місяців тому

      @@augusto1997 mas essa memória extra cresce com mais dados de entrada? por que se não, não faz diferença alguma assintoticamente!

    • @miguiprytoluk
      @miguiprytoluk 6 місяців тому

      ​@@thomasthemazzerrunner3615 sim essa memória extra cresce com o o input, ou seja, nenhuma solução com sort resolve o problema

  • @keuwey
    @keuwey 6 місяців тому

    Caraca, fritei o cerebelo mas ACHO que entendi. Eu estudo Python a algum tempo, mas as operações que geralmente uso são "not", "and" e "or". É a primeira vez que vejo esses operadores |, ^, ~ sendo usados em um programa. Qual o nome desse assunto pra eu poder estudar?

  • @fabiocasanova6121
    @fabiocasanova6121 7 місяців тому

    Muito elegante!

  • @fidizila
    @fidizila 7 місяців тому

    Achei a parte do FOR com IF meio complicada. Preferi assim:
    nums = [0,1,0,1,0,1,99]
    nums2 = [2,2,3,2]
    x = [n for n in nums if nums.count(n) ==1]
    y = [n for n in nums2 if nums2.count(n) ==1]
    print(*x)
    print(*y)

    • @MrZ1ka
      @MrZ1ka 7 місяців тому +1

      Entao, mas esse é ponto desse video, ele sabe que essa é a solucao mais facil e rapida de se pensar, mas o problema quer que voce resolve em O(1) ou seja ele nao quer que voce percorra o array mais de uma vez, que é o que voce esta fazendo em .count()

    • @samon101
      @samon101 7 місяців тому +1

      ​@@MrZ1kaO problema quer O(1) em espaço, então o problema não é percorrer o array mais de uma vez, o problema é ter um array cujo tamanho depende da entrada

    • @gabrielfreitas4270
      @gabrielfreitas4270 7 місяців тому

      ​@@samon101mas ainda tem que ter tempo linear. Não manjo muito de python, mas essa operação aí não é n^2 por causa do count() dentro de um loop?

  • @ale_ducati
    @ale_ducati 6 місяців тому

    Não vou resolver nem ver o vídeo mas tragoa solução. Ao invés de procurar o unico elemento é só procurar os elementos repetidos pois é muito mais fácil. Depois de encontrar todos é só eliminar e ficar com o restante. se for apenas 1 numero único, você ficará com o único, se forem algums vc ficará com algums.

    • @MateusRodrigues-fx2bw
      @MateusRodrigues-fx2bw Місяць тому

      Mano, não é grosseria tá. Só uma resposta pra tu mesmo. Mas tu devia ter visto oq pede o enunciado. Pq o enunciado pede que sua solução seja O(1). Na tua explicação, a complexidade seria O(n), ou seja, tua solução está meio correta se consideramos oq pede o enunciado. E está meio correta pq ma sua solução a saída escala conforme a entrada. Ainda soluciona o problema, mas com uma complexidade maior do que o solicitado.
      Grande abraço meu caro!

  • @DonManolloz
    @DonManolloz 7 місяців тому

    3 em binário é 11

  • @matheusmoreno8982
    @matheusmoreno8982 2 місяці тому

    eu pensei num radix sort

  • @Cozacsv
    @Cozacsv 6 місяців тому

    cara eu achei na verdade esse exercício nível fácil pra ser sincero com um simples sort e um loop for voce resolve.
    PS: eu sou programador a 9 meses e resolvi em menos de 20 minutos dessa forma.
    Runtime:55ms Beats 67% | JS Users
    Memory:49.77MB Beats 71% | JS Users

    • @Cozacsv
      @Cozacsv 6 місяців тому

      var singleNumber = function(nums) {
      let n = nums.sort((a, b) => a-b);
      var saw=n[0];
      for(let i = 1; i < n.length; i++){
      if(n[i+1] == undefined){
      if(n[i] != saw && n[i] != n[i-1])saw=n[i]
      }else {
      if(n[i] != saw && n[i+1] != n[i] && n[i] != n[i-1])saw=n[i]
      }
      }
      return saw;
      };
      Lembrando que essa estrutura foi feita por um iniciante e mantem a estrutura O(1) e armazena apenas um valor independente do tamanho de nums

    • @GutoGalego
      @GutoGalego  6 місяців тому

      Quebra premissa do problema, tem que resolver em complexidade temporal linear, sort é O n log n. Eu sei que passa no leetcode, mas numa entrevista por exemplo não ia passar

    • @Cozacsv
      @Cozacsv 6 місяців тому

      @@GutoGalego desculpa você está certo pedi ajuda pra um senior pra entender o que você disse vou mexer no código amanha e ver se arrumo obrigado !

    • @Cozacsv
      @Cozacsv 6 місяців тому

      @@GutoGalego bom sábado pra você. eu acordei tem alguns minutos e decidi refazer o código dessa vez levou menos de 10 minutos poderia confirmar pra mim se agora está em O(n)?
      var singleNumber = function(nums) {
      let n = nums.sort((a, b) => a-b);
      var saw=n[0];
      var count=1;
      for(let i = 1; i < n.length; i++){
      if(n[i] == saw){
      count++;
      i++;
      }else if(n[i] != saw){
      if(count > 1){
      count=1;
      saw = n[i];
      }
      }
      }
      return saw;
      };
      eu percorro uma vez e apenas verifico se o numero já foi visto caso sim. eu pulo um a mais e continuo verificando. Se puder me ajudar eu ficaria grato no leetcode passou tambem

  • @xablaurs
    @xablaurs 7 місяців тому

    Bem, li o titulo, me senti meio intrigado, entrei no vs code e criei um script em python...:
    lista = [2, 7, 7, 2, 3, 2, 7]
    counter = {}
    for i in lista:
    if i not in counter:
    counter[i] = 1
    elif i in counter:
    counter[i] += 1
    print(counter)
    Deu certo. Talvez em outra linguagem, tipo C, talvez nao conseguiria implementar desse jeito. Mas enfim, sou um mero aprendiz, hehe.....

    • @EdgarEndoJunior
      @EdgarEndoJunior 7 місяців тому +1

      Nessa solução o seu counter faz o seu algoritmo ter complexidade espacial O(n) em vez de O(1).
      Vc precisa de uma solução que não aloque memória que dependa do tamanho do array inicial.