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 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.
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).
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)
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.
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!!!
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!
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
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.
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.
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.
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
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
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
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.
@@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.
@@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).
@@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.
@@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.
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?
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.
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.
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.
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.
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.
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.
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
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
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
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]; };
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.
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?
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
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
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.
"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).
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
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.
@@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)
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.
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?
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
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
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.
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
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
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
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.
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!
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 })
Em Js é tao simples: const list = [2,1,1,2,2,3,3,4,4,5] let one = false; for (const num of list){ const achou = list.filter((p)=> p===num).length; if(achou === 1)one=num; } // Log to console console.log('One:',one)
cara, é so fazer manipulação de arquivo ue, tu pega um numero e coloca no arquivo e ordena por la ou faz o count la. ele explicitou em memoria e não memoria secundaria/armazem externo
Se vc usar essa forma, vc com certeza adicionará no mínimo Time Complexity pra ler ou ordenar o arquivo. E Space Complexity não depende de onde seus dados estão, o fato de vc usar memória adicional dependente do tamanho do array já viola a complexidade de espaço. A resolução mostrada no vídeo cumpre ambas as soluções de complexidade de tempo e espaço.
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.
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
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
`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)
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 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
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?
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.
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".
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
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.
6:49 isso é um 6 em decimal, 3 decimal em binário seria 11.
também notei isso e fiquei me perguntado se eu tava louco
mesmo assim, conteúdo fantástico e bem apresentado
exato, notei isso tb. 0, 1, 10 e 110, estranho
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
Olá, o que significa O(n) e LRU em O(1), pode me explicar?
@@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.
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).
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)
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.
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!!!
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!
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
Fantástico, Augusto! Problema lindo! Solução muito elegante! Obrigado por esse vídeo.
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.
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.
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.
parabéns! conteúdo incrível, abriu minha mente de como encarar alguns problemas e possíveis soluções
é um problema divertido, dps de fazer a matéria de sistemas digitais tudo fica bem claro
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
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
Verdade esse é um grande diferencial
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
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
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.
@@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.
@@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).
@@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.
@@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.
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?
Então porque o desafio é fazer em tempo linear! O sort é O(n log n)
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.
mais fácil ainda e menos elegante ainda é dar um print('1') kkkkk
Só pode fazer em python? Com operadores bit a bit sai fácil em c.
Tive que assistir 2 vezes pra entender. Fritou muito a cabeça kkkkkkk
No final, ao invés de fazer o & ~ twos, n seria mais simples (e mais eficiente) só retornar ones ^ twos?
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.
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.
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
Incrível esse aula, muito obrigado!
A conclusão que eu tiro desse vídeo é que eu sou um merda em programação
Eu considero esse desafio médio, parabéns pelo vídeo.
Praticamente uma máquina de turing kkkkkkkkk
No inicio eu nao tava entendendo nada, e no final parecia que eu estava no inicio.....
Seus vídeos são demais mano!
Caraca, peguei aqui pra resolver e gastei 1 hora, mas consegui fazer sem pesquisar, só com meu conhecimento em Java. Top!
video sensacional. Quando você postou no twitter fiquei pensando no problema por vários dias.
isso não seria meio que fazer soma e subtração sequencialmente até terminar os valores do array?
em c++ meti dois for loop e consegui time complextiy O(n^2) e space complexity O(1)
mano, vc consegue deixar o audio do video um pouco mais alto?
Não
Aumenta o volume
Eu uso uma extensão chamada soundFixer, recomendo usar ela também. É possível aplicar ganho nos áudios do navegador de até 5 (500%)
Pra que
Foi irônico? Pra mim parecia alto demais kkk
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.
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.
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.
Se dá pra fazer and not, daria pra fazer uma tabela verdade de 3 elementos também concatenado ?
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
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
Você não sabe o inferno que foi escrever isso pelo celular.
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
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];
};
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.
4:35 Esse reduce e esse xor aí não vão dar undefined??
Já dizia um professor meu na universidade: "Olha a sacada dos caras"
o meu falava "Olha esse esquema dos caras", levo esse termo "esquema " pra vida toda
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?
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
Adoro seus vídeos, porém, sempre o seu áudio está MUITO baixo. :(
para mim está tranquilo o audio dele
Tá surdo merda
Pra mim tbm fica bem baixo
Aqui está tranquilo
Rapaz realmente praticamente impossível pensar nessa solução sem ter visto algo parecido antes kkk,
49ms
Beats: 91.69%
Eu resolvi. Acho. De uma maneira diferente. Mas eu n tenho certeza se funcionaria pra todos os casos
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.
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
nem vi que era O(1) space 💀 achei bobo mas me pegou
Mas não usa alocação constante, usa alocação "dinamica"
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();
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.
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?
"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).
comecei a fazer em C aqui, realmente é difícil ...
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
os algoritmos de sort mais eficientes são n log n, exceto pelo bucket sort
@@sLokJoNas então essa seria minha primeira solução, não a ideal
Mas a questão fala que tem que ser linear
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.
@@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)
Mano, pensei que era outro Galego, esse cabelo de rockeiro ai parça? Essa realmente deu uma esquentada na cuca
Escreve como gente por favor.
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.
Qual a plataforma o Galego está usando?
ta sussurrando kkkkkkkk
Pensei e implementei um O(n) e desisti de implementar a O(1) kkkkk
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?
Não pq a operação sorted é cara, mas talvez o site aceite a resposta
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
Fui confirmar e não valeria por que o radix sort tem complexidade de espaço O(N) 😅
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
Pensei nisso, só um if e um return resolvia, n sei se em python o count é Implementado em c
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.
@@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))
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.
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
Qual o site que você usa para gravar esses vídeos?
Provavelmente excalidraw
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
tbm faria assimkkkkkkkkkkkkkk
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
Eu aqui vendo esse vídeo vidrado sem nem saber html e css KKKKKJ
Não consigo entender a sintaxe de python ainda
Qual é o uso prático do conhecimento requisitado por esse desafio?
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.
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!
Qual aplicativo usa para gravar a tela e mexer a webcam assim
OBS Studio
@@TheDenysabner N tenho certeza, pq ele mexe a camera arrastando com o mouse
@@GabrielBrisolara-c1t isso é normal no OBS
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();
}
passa não, o sort ali pode tá usando o extra-space
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 })
11b = 3 não?
Gosto muito do seu Canal.
?Ha alguma generalizacao pra n repeticoes
Pior que existe sim. Mas esse já foi difícil de explicar kkk
Não é só criar um map incrementando a quantidade caso já exista? Ou entendi errado?
No início do vídeo ele explica o porquê dessa solução não ser válida para o problema.
po essa solução é matemática computacional puro
Em Js é tao simples:
const list = [2,1,1,2,2,3,3,4,4,5]
let one = false;
for (const num of list){
const achou = list.filter((p)=> p===num).length;
if(achou === 1)one=num;
}
// Log to console
console.log('One:',one)
@ZantsuRocks a sim, por isso eu indiquei essa soluçao...
Alguém pode passar o link do vídeo onde ele resolve a parte 1 do problema? Fiquei com algumas dúvidas.
Muito louco, incrível
Fiz assim com Js
const singleNumber = (nums) => {
const [num] = nums.filter(
(num) => nums.indexOf(num) === nums.lastIndexOf(num)
);
return num;
}
cara, é so fazer manipulação de arquivo ue, tu pega um numero e coloca no arquivo e ordena por la ou faz o count la.
ele explicitou em memoria e não memoria secundaria/armazem externo
Se vc usar essa forma, vc com certeza adicionará no mínimo Time Complexity pra ler ou ordenar o arquivo. E Space Complexity não depende de onde seus dados estão, o fato de vc usar memória adicional dependente do tamanho do array já viola a complexidade de espaço. A resolução mostrada no vídeo cumpre ambas as soluções de complexidade de tempo e espaço.
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.
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)
@@ZantsuRocks como eu disse, nao tinha visto o video, so o thumbnail.
@@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....
@@TalesIagoBatista Na verdade não, o return dentro do metodo forEach "não faz nada", ele vai seguir executando o forEach até o fim
Legal a solução pensei em algo bem parecido
const number = array.find(i => { if (array.filter(j => j === i).length === 1) return i })
youtube premium ótimo vídeo
Esta solução é sua ou tem outra origem?
Como alguem chega em uma solucao como essa??
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.
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
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
@@GutoGalego com O(n) acho que dá pra fazer com um for e um while, vou tentar e jaja replico aqui.
conseguiu?@@seveng0th
@@seveng0th aqui jaz um dev, 4 meses depois e o rapaz ainda ta tentando.
3 não é 110
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.
#ajudei
meu parcerinho que programa/site é esse do fundo preto??
vscode
@@PintoDonald kkkkkkk obg mano, mas me referi a o programa q ele "desenha" a lista, as setas e afins
@@zec_s ops kkkkk
@@zec_s Não sei se você já chegou a descobrir, mas se caso não o website usado é o Excalidraw.
@@HIM-br9qy obrigado
`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)
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
@@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?
@@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
que difícil oq. é só fazer um map, com o elemento -> quantas vezes ele aparece e cabou. mete um if e já era😂
mas aí o espaço é O(N)
Cara, isso é de boa, as questões dificeis do leetcode tem constraints bem mais difícieis que essa
De boa... Beleza raspador de bits
Que site é esse aonde você pegou o desafio?
Leetcode
Qual o site dos desafios?
leetcode
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?
Bitwise Operators
Eu usaria um vetor de 31 bits
E contaria bit a bit
Sua solução é maneira
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
eu pensei num radix sort
Muito elegante!
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.
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".
@@augusto1997 radix sort é linear.
@@thiagovieira8569 yep. Embora ele não é O(1) em espaço. Ou seja ele precisa de memoria extra para auxiliar na ordenação.
@@augusto1997 mas essa memória extra cresce com mais dados de entrada? por que se não, não faz diferença alguma assintoticamente!
@@thomasthemazzerrunner3615 sim essa memória extra cresce com o o input, ou seja, nenhuma solução com sort resolve o problema
que vídeo insanoooooooooooooooooooooo
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
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.
Que interessante 😊😊😊