RESOLVENDO um DESAFIO TÉCNICO da NETFLIX
No vídeo de hoje, vamos resolver um desafio técnico da netflix! :)
Link dos benchmarks e das soluções: github.com/phenpessoa/lc/tree...
--------------------------------------------
Não deixe de se inscrever e deixar o like!
Bem vindo ao canal phenpessoa :)
--------------------------------------------
Minhas redes sociais:
✅ github.com/phenpessoa
✅ / phenpessoa
✅ x.com/phenpessoa
✅ / phenpessoa
✅ / phenpessoa
✅ / phenpessoa
✅ / phenpessoa
Contato profissional:
phenpessoayt@gmail.com
--------------------------------------------
Referências:
Vídeo da entrevista da netflix: • How I Failed My Netfli...
--------------------------------------------
#programação #phenpessoa #netflix
Пікірлер: 132
Pessoal, algumas observações: Nos benchmarks eu usei a string que seria o pior exemplo possível para a primeira solução O(n^2), mas, ainda assim, ela era pequena. Outra coisa que eu poderia ter feito era ter pré-alocado o mapa pra caber todos os caracteres, fazendo m := make(map[rune]int, 26). Nesse caso, as alocações da solução 2 cairiam de 5 para 1. E para strings grandes, a solução 2 seria mais rápida do que a 1. E é justamente esse o objetivo de big O, entender o comportamento para inputs grandes. Porém, a solução 3 continua sendo a mais rápida e a que usa menos memória, mesmo para inputs muito grandes. Coloquei os códigos e os benchmarks aqui: github.com/phenpessoa/lc/tree/main/lc-go/387
@aprendacomprazer
8 ай бұрын
Nem precisava fazer com 2 loops, a otimização não ta muito legal.
@phenpessoa
8 ай бұрын
Qual seria a solução com 1 loop só? @aprendacomprazer
@tlscaranto
8 ай бұрын
@@phenpessoa com 1 loop fiz assim let non_repeating = []; for (let i = 0; i let element = word[i]; const matches = word.match(new RegExp(element, 'g')); if (matches && matches.length === 1) { non_repeating.push(element); } } return non_repeating[0] ?? '_';
@williandandrade
8 ай бұрын
@@tlscaranto tem que ver a implementação mas essa solução pode ser quadrática se o match da expressão regular realiza loops internos (bem provável)
@diogomedeirosdealmeida3317
5 ай бұрын
o que vc usou pra fazer os benchmarks ?
muito boa a solução! Eu já tinha pensado logo de cara que o map seria o mais eficiente, mas aprendi uma nova forma hoje!!
Não entendi absolutamente nada, mas é incrível acompanhar tua linha de raciocínio. Estudando bastante pra conseguir chegar nesse nível! Parabéns, brother!
@fheonix5
2 ай бұрын
eu me sinto um pedaço de troço de côcô kkkkkkkkkkkk tendi nadaa
cara na moral, que vídeo INCRÍVEL! por favor, continua fazendo seus vídeos, são muito tops!
Eu estou impressionado no nível absurdo de conhecimento e habilidades que você tem! Parabéns, irmão. Este é a primeira vez que vejo um vídeo seu, mas já vou devorar o que mais tiver kkkk principalmente de GO, que é o que comecei a aprender recentemente.
Pedrão, seus vídeos estão um absurdo de bom!!! Estou acompanhando o canal desde que tinha 500 pessoas, e eu pensei... Nossa, esse canal é tão bom que em breve vai viralisar! E cá estamos próximos aos 3mil e em breve aos 300mil e logo mais 3milhões. Adorei esse vídeo, trás outros nesse formato!!!
@phenpessoa
8 ай бұрын
Cara, muito bom ouvir isso! Obrigado pelo comentário!!
Um dos poucos canais de tecnologia que aborda conteúdos sobre estrutura de dados de forma didática. Sério, alguém vê algum canal relevante falar sobre Big O Notation, análise assintótica e etc? Parabéns, Pedro!
@Andrewscarlosreis
8 ай бұрын
tbm estou procurando kkk
@lucas.acelino
8 ай бұрын
Eu indico a vocês o canal programação dinâmica, lá eles têm uma Playlist que aborda os conceitos de estrutura de dados. Fica a dica. Canal: @pgdinamica
Muito bom. Fiquei com algumas dúvidas sobre code point, runa e heap allocation. Seria legal um vídeo sobre esses temas.
Parabéns pelo conteúdo Pedro, a sua filosofia de aprender da forma mais difícil faz todo o sentido, aquilo que seu professor disse na faculdade sobre memoria também faz, cada vez da pra ver muito jogo saindo ,com gráficos não muito relevante para a geração anterior mas consumindo o dobro de Hardware, a falta do capricho na hora de desenvolver projetos é muito perceptível, talvez uma hora essa bolha vai estourar.
Nossa senhora, esse conteúdo foi absurdo de bom. Parabéns pelo vídeo.
esse canal devia ser gigantesco pqp, só conteúdo bom!! sucesso aí
Aí eu te pergunto: Pra que fazer faculdade se a gente tem conteúdos desse calibre no youtube? kkkkkkk Brincadeiras a parte. O que eu quis dizer foi: "Olha a importância de fazer uma faculdade e aplicar os conceitos teóricos na prática.". Fodaaaa Pedrão! Me surpreendendo a cada conteúdo.
@shadergz
8 ай бұрын
Professor de facu falam que memória hj em dia não tem importância (Tô nem zuando)! Muito idiotas
@MrAbrazildo
8 ай бұрын
@@shadergzTem q lutar muito por 64 KB de L1 cache. Às vezes só tem metade disso.
@carloseduardodeoliveira6902
5 ай бұрын
Então, se vc quiser ir pra fora do BR vai ter q enfrentar uma burocracia maior do q já é, c a facu só a burocracia tradicional. Ah! E tem empresas aqui no BR q contratam só e somente se tu tiver facu. Logo a facu serve pra "facilitar" a entrada no mercado.
Zica de mais!! Muito bom os vídeos
Sempre que assisto seus vídeos tenho uma nova perspectiva, eles têm agregado muito conhecimento a mim.
20 anos e continuo aprendendo algo novo. Amo nossa área.
Top de mais. Parabéns pelo video.
fantastico. eu já havia resolvido esse caso porém não havia me atentado a esta alocação na heap.
Já implementei um algoritmo parecido com esse em C. Parabéns pelo video otima didática
Que achado! Um tibiano explicando algoritmo como um verdadeiro David Malan, ótimo conteúdo!!
Por favor , por mais vídeos assim ❤❤❤❤
Ótimo vídeo, parabéns.
Foi sensacional, eu pensei em usar um hash map logo de cara, achei que era a melhor solução possivel, até ver a última solução. GENIAL!
Exelente vídeo!
muito bom… entendi Go em 10 minutos contigo!!!
Parabéns muito bom os videos
ABSUUUUUUUURDOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO PENA SER CURTO! BOM DEMAIS! FICO 1H VENDO FÁCIL
@gssj-o8p
8 ай бұрын
Não é curto é que ele fala em 2x haha
@eltrem_th
8 ай бұрын
@@gssj-o8p kaksksksksks siiim
SHOW!!
parabens pelo conteudo
Muito bom 👍
Muito massa cara
Seria possível adicionar algum paralelismo computacional para diminuir o tempo, por exemplo threads ou OpenMP. Imagino que ao utilizar diversas threads iterando por partes diferentes de um loop simultaneamente, o tempo poderia ser reduzido para (log n), porém é fato que o custo de memória de alocação de um vetor de quantidades por thread escalaria junto da quantidade de threads. Como apenas o primeiro caracter sem repetição deverá ser printado, acredito que essa porção do código deverá ser sequencial, então no final das contas o código acabaria continuando como O(n). Finalmente, paralelizar a contagem de caracteres seria uma abordagem válida para o problema? Ou eu deveria apenas me preocupar com a melhor maneira de otimizar o código sequencialmente?
Já tinha feito essa questão, é muito legal. Tem uma parecida nas 21 gratuitas do hackeranking também. Fiz uma prova da IBM nedda plataforma e fiquei rncucado por que tinham 2 questões... Uma no nível mais ou menos dessa que demorei a metade do tempo e a outra que simplesmente nao consegui entender. Não entendi nem o objetivo. Era um tipo de jogo enrolado que nem consegui pensar sobre como redolver. Enfim, estudando pra caramba , um dia passo pra uma empresa gigante dessa.
Qual as ferramentas para encontrar gargalos de otimização que você utiliza em C, Go ou outras linguagens, até mesmo Python? Como fazer o Benchmark? Seria interessante fazer um vídeo demonstrando isso, é uma dúvida de muitos que conheço.
Fala meu rei, seria legal também ver o benchmark acontecendo no vídeo, que aliás, muito bom! 🚀
@phenpessoa
8 ай бұрын
Boa ideia! No próximo eu coloco, obrigado! :)
Um adendo, a estrutura de dados map não é exatamente constante, se for implementado como uma arvore, acessos são no pior caso, O(log(n)). E no hash map, é O(n). É só que na média, o hash map tem complexidade O(1). E também pelo fato do n=26 ser constante fazendo a complexidade dessa do map não interferir na complexidade do algoritmo como um todo.
Estou na faculdade pagando a cadeira de algoritmos agora e gostei muito desse vídeo, me ajudou a entender mais ainda o que estudo!
Que bacana de conteúdo
Excelente!
Video muito bom
Cara vc usou alguma extensão para ver o timeout ?
Muito bom o conteúdo. Minha vida era uma mentira,com o big O e funções lineares.
Esse contador em vetor é particularmente útil quando se está otimizando um radix sort! Ahahahahaha
adoro assistir ver metflix!
tenho uma dificuldade enorme em categorizar um algoritimo, exemplo se ele é n2 logN e etc
muito bom
Top =D
TOP 1 amigo, não vejo cara melhor
Eu pensei em uma solução (como iniciante): pegar cada char da string e por em um nova string, com a condição de que se o char já estiver dentro da nova string, ele ignore. No final teremos 2 strings, ai basta comparar se uma é exatamente igual a outra, se for, nenhum item se repete e teremos retorno 1, e se as strings forem diferentes, teremos retorno -1.
@junior.santana
4 ай бұрын
Algumas observações dessa solução: 1. Pra checar se um char já existe na sua segunda string vc teria que loopar nela (emsmo que a linguagem forneça alguma helper function pra isso , internamente é feita um busca linear na string). Com isso conforme a segunda string vai crescendo essa busca tbm se torna mais lenta. Por isso, armazenar em um hashtable, map, etc usando o char como a key. 2. O problema pedia que fosse retornado o index do primeiro non-repeating character, essa solução apenas retorna se existe algum repetido ou não. (Pra esse caso ao encontrar um item repetido o loop já poderia ser interrompido sem necessidade de compara as duas strings no final)
sabe muito
Você é um gênio tá
Vc tem algum material de conteúdos avançados em go? Trabalho com esta linguagem e sempre busco melhorias, abs!
@phenpessoa
8 ай бұрын
Putz, pior que de cabeça não… mas entra no discord de Go. Com certeza o pessoal vai ter indicações lá.
Pedro quais ferramentas usa para esse benchmark? E consegue compartilhar quais caminhos tomou para aprender estes pontos? Gostaria de mapear o que pulei e o que nao fiz,para nao ter este conhecimento hoje, passado tanto tempo como programador
@phenpessoa
8 ай бұрын
O benchmark eu usei a própria ferramenta de benchmark de Go. Já vem junto com a linguagem. Acredito que estudar dynamic programming seja muito importante, não sei se já fez isso.
@mnsnows
8 ай бұрын
@@phenpessoa até o momento não, mas posso começar
Cara, mal sei montar uma aplicação completa. Mas resolvi esse desafio graças ao livro Introdução a programação com Python. Que loucura, estou muito orgulhoso de mim.
@phenpessoa
8 ай бұрын
Top!! Parabéns 👏🏻👏🏻
Percebi que preciso estudar mais! Pelo amor de Deus hahaha
Animaaaal!!! 🎉🎉🎉
Imaginei uma array multidimensional onde ela vai recebendo itens que não existem e se já existe conta dentro . Ex [ ['a', 1], .... ] Depois é só ler a primeira ocorrência com 1
@gabrieldonascimentogomes9619
7 ай бұрын
Isso é praticamente um dicionário em formato de lista
Rapaz, queria ter 1% dessa desenvoltura pra explicar as coisas kkkkkk Quando me perguntam algo que eu sei eu simplesmente travo kkkkk
Eu programo a muitos anos, mas eu nunca me considerei um programador de verdade, principalmente por não ter tido oportunidade de trabalhar na área. Quando eu parei pra resolver esse desafio, eu pensei: "pô, eu não vou usar mapas ou qualquer biblioteca interna pra eu tentar criar o código mais otimizado possível" e eu fui direto pra essa lógica de pegar o código da letra e subtrair por 97 trabalhando com uma array, principalmente por eu estar usando uma linguagem compilada. Quando eu fui ver a solução, já me senti um animal por não ter usado os mapas... até chegar no final do vídeo! Kakakakaka Eu tenho que dar mais crédito a mim mesmo as vezes, acho que eu sou um bom programador no final das contas!😅
Caceta meu conterrâneo, quero aprender a programar contigo
Só um detalhe, no segundo for da segunda solução poderia usar o m ao invés do s, visto que sempre s > m.
@phenpessoa
8 ай бұрын
Não pode pq pode ter mais de 1 caracter que não se repete, e nesse caso teria que retornar o que aparece primeiro. E mapas não são ordenados.
po vi a ultima solucao, bem legal
Fala Pedro, bora pra mais vídeos de algorítimo
To iniciando no mundo da programação, nessa entrevista o desafio teria que ser desenvolvido em uma linguagem especifica? Porque parece ser muito tranquilo de resolver com python string = "leetcode" for index, caractere in enumerate(string): if string.count(caractere) == 1: print(index) break else: print("_")
@phenpessoa
8 ай бұрын
Poderia ser resolvido em qualquer linguagem. Esse desafio é bem tranquilo mesmo. Mas eles pedem pra você fazer uma análise de Big O da sua solução e depois pedem pra você melhorar o algoritmo. Nesse caso aí a sua solução é O(n^2).
@ghxvitinho
8 ай бұрын
@@phenpessoa Entendi, eu fiquei meio perdido no vídeo porque não tô no nível técnico suficiente ainda haha, mas percebi que a função count vai fazer outro loop a cada caractere da string, por isso o O(n^2). Enfim, vou continuar estudando e daqui um tempo volto aqui com mais conhecimento pra entender 100%, obrigado pela atenção, ganhou um inscrito!
voce recomenda algum curso online de algoritmos e estruturas de dados ?
@phenpessoa
8 ай бұрын
Se souber inglês, recomendo o do primeagen na front end masters… É gratuito.
Essa aqui me pegou desprevenido. Sem nem titubear eu pensei em solução utilizando um objeto (sou do JS), mas nunca imaginei que em Go fizesse tanta diferença. Vou testar em JS
@phenpessoa
8 ай бұрын
Mostra o resultado pra gente depois por favor :)
Resolução em java : classe de resolução: public class Resolution { public void resolution(String s) { var counter = 0; char[] letters = s.toCharArray(); for(int i = 0; i for (int j = 0; j if(letters[i] == letters[j] && letter[i] != ' ') { counter++; } } if(counter == 1) { System.out.println(letters[i]); break; } counter = 0; } if(counter == 0) { System.out.println("-1"); } } } classe de execução: public class Main { public static void main(String[] args) { var resolution = new Resolution(); var s = "opa"; resolution.resolution(s); } } se encontrarem algum bug me avisem 😁
Entendi nada. Muito bom! Brincadeiras à parte... Tenho um ano de estudo e prática em casos reais mas sou muito ruim de lógica, parece impossível pra mim, ou eu pelo menos levo muito mais tempo que outros pra entender. Alguem que passa por essa dificuldade também tem algumas dicas? (Além do obvio: prática, constância...) Btw, ótimo vídeo, conheci o canal à pouco e já me inscrevi. Bom trabalho! Aguardo mais conteúdo.
@phenpessoa
8 ай бұрын
Fico feliz que gostou! Seja bem vindo. Acho que é só com prática mesmo. Procure vídeos sobre dynamic programming também, pode ajudar bastante.
@Iuan1
8 ай бұрын
@@phenpessoa Obrigado!
s = "abaabac" def count_elem(string_compare): a = {} for elem in string_compare: if not elem in a: a[elem] = 0 else: a[elem] += 1 b = a.values() c = 0 d = list(a.keys()) for bitem in b: if bitem == 0: return d[c] else: c += 1 return "_" print(count_elem(s)) eu: "escrevendo a solução rapidamente." o recrutador observando o código: "que porra é essa meu amigo."
minha pergunta e, como? kkkk como q fica tao bom assim ?
Ótimo vídeo! No entanto apenas a primeira solução atende ao problema! O problema pede para retornar o PRIMEIRO caractere que não se repete! A segunda solução assume que as chaves dos maps em go preservam a ordem de inserção. Isto não é verdade, dessa forma, o seu algoritmo vai retornar um caractere que não se repete, mas não necessariamente o primeiro caractere como exigido! No que se refere à terceira solução, o mesmo problema ocorre! Você está salvando os valores na ordem em que aparecem no alfabeto sem se preocupar com a ordem em que aparecem na string! Desta forma, considerando um mesmo conjunto de carácteres, independente da permutação, o resultado sempre será o mesmo, o que está errado em cenários em que existem 2 ou mais carácteres que não se repetem!
@phenpessoa
8 ай бұрын
Não é verdade. As soluções estão corretas. O segundo loop itera sobre a string. Não sobre o mapa ou o array. Preservando a ordem. Inclusive um dos testes do leetcode usa strings em que mais de 1 caracter não se repete, e o teste passa, nas duas soluções.
@viniciusps01
8 ай бұрын
@@phenpessoa De fato, você está correto! Eu não me atentei que você estava iternado sobre a string! Solução mais simples que a minha! Parabéns
Obrigado pelo vídeo, ele me lembrou pq não devo seguir pela programação kkkkkkkkkkkk
@phenpessoa
8 ай бұрын
🤣🤣🤣🤣🤣🤣 Aí não
a complexidade da propria leitura e escrita do hashmap nao é n, e por consequencia uma busca dentro de um for, n * n, e portanto On^2?
@tsmurer
8 ай бұрын
nvm, joguei no chatgpt e ele me explicou kkkk
Cara, fiz em Python no LC e fazendo por conta cheguei na solução utilizando hashmap, daí depois de ver a solução utilizando unicode, quando mandei a solução pro LC o runtime foi apenas 2ms mais rápido do que utilizando hashmap e usou 0.1mb a mais, o LC tá louco? Vi algumas submissões em Python iguais as minhas e estavam mais rápidas. Runtime hashmap: 137ms Runtime unicode: 135ms
@phenpessoa
8 ай бұрын
O leetcode é muito instável nesse sentido. Já mandei a mesma solução pra vários problemas algumas vezes, e aí as vezes fica 60% acima da média, as vezes 95% acima da média. Não tem como usar como parâmetro. Tem que usar uma ferramenta própria de benchmark. Agora, por python ser interpretado eu não sei se ele oferece arrays, javascript por exemplo não tem array, apesar de serem chamados assim. Aí você já não ganha o beneficio de uma estrutura ser stack allocated vs heap allocated, vai ser sempre heap allocated.
@erickrds
8 ай бұрын
@@phenpessoa Sim, em Python não tem array de fato, é igual JS. Pedi pro ChatGepetéco rodar uns benchmarks em python e com hashmap mesmo nos piores cenários fica igual ao unicode ou até melhor. Acho que já parte pro gargalo da linguagem mesmo. Valeu pelo vídeo. Edit: o Python até tem um módulo array, que em teoria fica mais próxima de uma linguagem baixo nível, mas na prática rodando aqui foi até pior kkkk
qual a linguagem de programação usada?
@phenpessoa
8 ай бұрын
Go
@diegoemmanuel1014
8 ай бұрын
grato@@phenpessoa
Solução com apenas um FOR: package org.example; public class Netflix { public static int exercise(String s) { int[] letters = new int[26]; int index = 0; for (int i = 0; i char l = s.charAt(i); letters[l - 'a']++; char l2 = s.charAt(index); if (letters[l2 - 'a'] != 1 && letters[l - 'a'] == 1) index = i; } char l = s.charAt(index); return letters[l - 'a'] == 1 ? index : -1; } }
Não seria mais fácil resolver usando a função split?
@newton892
8 ай бұрын
Typescript function firstUniqChar(s: string): number { for (const index in s.split('')) { if (s.split(s[index]).length === 2) return Number(index) } return -1 };
@phenpessoa
8 ай бұрын
É outra solução. Mas também é O(n^2). Além disso, pra cada split você tá alocando uma nova lista em memória, tornando essa solução bem cara.
@newton892
8 ай бұрын
@@phenpessoa Entendi... Vlw😅
Achei muito complexo. Acho que preciso estudar algoritmo e estrutura de dados urgentíssimo rsrsrs
fiz com python esse primeiro ele tem como saber se um obj já existe em um dicionario ai fica assim: string = 'teste' objAnalise = {} for i in string: if i in objAnalise: objAnalise[i] += 1 else: objAnalise[i] = 0 for i in string: if objAnalise[i] > 0: print(i) break edit : agora que eu vi que ele fez essa opção também kkkkk.... mas fica ai em python
Não passaria kk
ok, tenho muito a estudar.
sinceramente não sei o motivo de uma empresa passar um teste desse. fui numa entrevista e o gerente disse que a cliente quer fazer um projeto parecido com esse. sabe fazer então está contratado, não sabe fazer, tchau. o cara faz esse teste técnico e depois passam um projeto de sênior com prazo e o cara nem sabe por onde começar e nem quando vai terminar
E ai Pedro 🙋🏻 Será que assim não funciona (em c#)? To criando umas possibilidades aqui 🤔 var str = "abacabad"; foreach (var letter in str) { if(str.Count(l => l == letter) == 1) { return letter; } } return '_';
@phenpessoa
8 ай бұрын
Perfeito, essa solução funciona. Mas ela é O(n^2) pq o método Count vai iterar sobre toda a string cada vez que for chamado.
@legitimoth
8 ай бұрын
@@phenpessoa Sim. Pra fazer algo performático o algoritmo não fica tão clean. Da pra fazer usando Dictionary acrescentando o int pra duplicidade e depois pegamos o primeiro que só tiver 1. Mas acho pouco clean o código. Lá pra fora os caras priorizam performance ao invés de simplicidade? (to pensando em aplicar pra lá, mas ainda não apliquei).
Foi fácil resolver em PY usando list.methods e tal (sou iniciante). Mas pra fazer dessa última maneira eu não faço ideia de como seria LOL. Conteúdo insando!
òtimo vídeo. Entendi nada👌👌
@phenpessoa
8 ай бұрын
🤣🤣🤣🤣 Aí me quebra
Consegui resolver em C#: static List RepetKeys(string text) { Dictionary keyValues = new Dictionary(); foreach (char c in text) { keyValues[c] = (keyValues.ContainsKey(c) ? keyValues[c] + 1 : 1); } List list = new List(); list = keyValues .Where(x => x.Value == 1) .Select(x => x.Key.ToString()) .ToList(); return (list.Count == 0 ? new List() { "_" } : list); }
Não
Minha solução antes de ver o vídeo: package main func main() { desafio := []string{"c", "a", "b", "d", "d", "c", "b", "a"} var uniqueValue string repeatTimes := 0 for i := 0; i for j := 0; j if desafio[i] != desafio[j] && uniqueValue != desafio[j] { uniqueValue = desafio[i] } else if desafio[i] == desafio[j] && repeatTimes == 0 { repeatTimes++ } else { uniqueValue = "" repeatTimes = 0 break } } if uniqueValue != "" { break } } if uniqueValue != "" { println("solutions(s) =", uniqueValue) } else { println("solutions(s) = _") } }