EXPLICAÇÃO de um DESAFIO TÉCNICO da GOOGLE | First Missing Positive
Вставка
- Опубліковано 22 лис 2023
- No vídeo de hoje, vamos resolver um desafio técnico de entrevistas da Google! :)
O desafio se chama First Missing Positive e é considerado difícil pelo LeetCode (nível Hard).
Além de explicar, (fazer um tutorial de como resolver), vou mostrar 3 soluções possíveis, e fazer uma análise assintótica de todas elas.
Link das soluções e benchmarks:
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
--------------------------------------------
#programação #desafio #google
É a primeira vez que eu consigo assistir um vídeo complexo e entender pelo menos a linha de raciocínio pra resolvê-lo. Consigo fazê-lo? não! mas só de acompanhar a estrutura de pensamento da até vontade de estudar mais pra chegar nesse nível. Parabéns, bro!
Esse canal era oq faltava no youtube!
Concordo
Por favor, continue com os vídeos de desafios! Teu canal é incrível!
Finalmente um canal de conteúdo com informações diretas, objetiva com tudo que precisamos saber
Irmao seu conteudo e muito top, realmente e muito bom, eu ia te pedir pra voce trazer conteudos de algoritimos involvendo logica sabe assim como esse, mas para as pessoas que sao iniciantes que estao comecando agora, vai ajudar muito cara, meus parabens pelo conteudo
Que canal fantástico, sou desenvolvedor a 15 anos e gostei bastante.
Parabéns pelo videio e pela didática! Espero que continue trazendo mais conteúdos desse gênero e em Go...
Esse canal é incrível muito bom e quando usar termos mais simplificados vai ser de grande ajuda.
Absurda a qualidade do teu conteúdo, parabéns meu querido
Parabéns @phenpessoa! Muito legal o canal.
Cara que conteúdo maneiro, Deus abençoe. Ganhou mais um escrito
Cheguei dando like, já sei que vai ser top, ansioso por um curso seu
Teus videos estão me fazendo gostar de leet code novamente, bom trabalho mestre
Segundo vídeo que vejo do canal e já me inscrevi, ótimo conteúdo
Cara era exatamente o tipo de conteúdo que estava procurando, e ainda com uma didática maior que a dos indianos hahaha, você ta de parabéns.
Mais um conteúdo premium! Parabéns mano!
Muito bom! Parabéns pelo conteúdo!
cara parabéns, a didática está bem legal, assim como os canais americanos o ritmo de fala está perfeito.
Cliquei em inscrever logo nos primeiros minutos, ótimo conteúdo.
Se puder fazer algumas soluções em Python seria bom também
Sucesso Pedro.
Caralho mano
Tu é um gênio, nmrl
O conteudo dos seus videos caiu em uma boa hora pra mim, valeu!
Ótimo conteúdo, parabéns 👏👏👏
O cara é bonito, charmoso e ainda programa em go. Apaixonei!
carai mlk, tu é brabo!
parabéns!! usando go ainda, top!!!
Muito bom, consegui entender todas as soluçôes, bem bacana esse exercício
Sou um completo noob da programação, fazedor de CRUD e eu fico admirado com a qualidade dos teus vídeos.
Fazedor de crud kkk, eu também
caraca, que aula
eu to migrando pro go agora e isso foi uma aula foda
Cara, conheci teu canal recentemente e estou impressionado com a qualidade dos vídeos, muito bem feito.
PS: Não conhecia essa técnica de Swap em Go, poderia mandar alguma referência pra estudo? A sintaxe é um pouco exótica...
Muito boa explicação!
Humildemente, como um iniciante na programação eu não entendi foi merda nenhuma, mas eu achei muito da hora! Parabéns!
Acho que foi o primeiro vídeo com altíssima qualidade (técnica e didática) sobre resolução de desafios em português q eu já vi! tá de parabéns, Pedro!
Em tempo: é o primeiro vídeo que eu tenho q assistir em velocidade 0,75 hahahahahahahhahaa
Muito bom, ao usar o len() uma única vez melhoraia ainda mais o código, não precisaria verificar o tamanho varias vezes.
Aguardando por mais conteúdo
muito bom os seus videos, parabéns!!!
Teu canal é o que estava faltando nesse UA-cam 🎉.
O que mais tem no UA-cam são canais com cursos de linguagens e framework, react de vídeos e desenvolvimento de soft skills.
Você não, você passa conhecimento que vai além de qualquer linguagem. 👏
Primeiro, muito bom o conteúdo, parabéns! Tem como construir uma solução sem o swap também, usando 2 variáveis de controle.
Vídeo muito interessante mano!
estou no quarto vídeo do canal, continue mano! ta ótimo!
Muito obrigado!
acho que dava para usar a fórmula do somatório tbm, soma todos os elementos relevantes no vetor e subtrai esse valor do somatório até n, a resposta será o número faltante
cara nao para essa serie. muito foda, eu tenho que diminuir a velocidade de video sua capacidade de raciocinio eu nao acompanho kkk
Cara, faz um vídeo sobre Big O notation. Mostrando o que é e exemplos de códigos!
Boa ideia!
Top demais!
Que canal bom, sério
Muito foda, até parece simples a solução
Muito bom!
Excelente!
Que delicia de video cara!☺
Video de altissima qualidade, parabens pelo conteúdo.
Ei, você dá curso?
HAHAHAHA/
Vou assistir mais umas vezes, seu raciocínio é muito rápido, faz sentido mas entender o que você está aplicando e falando ali com clareza vai ser da hora. E mano, parabéns. Continua que isso tá muito bom. E que bom que você se posicionou diferente da maioria, essa pegada de trazer esses desafios é bem interessantes.
Eu pensei numa solução bem ruim mas que seria O(1) em espaço auxiliar e O(n) em tempo, mas depende de um detalhe que eu não é dito no enunciado, que o inteiro tenha um limite máximo (ser um int de 32 bits, de 64, etc, mas não funcionaria para bigint).
O que daria para fazer é instanciar um array com uma posição para cada número possível, com todas as posições valendo false, assim que eu ler um numero eu troco o correspondente no vetor para true. Depois de percorrer todos os numeros, eu percorro o vetor e encontro a primeira posição com false.
Essa minha solução é ruim porque apesar de ser O(1) em espaço auxiliar (o tamanho do vetor depende do tipo do inteiro, e não da quantidade de números), já para int32 eu estaria consumindo 4 Gigas de RAM para essa operaçao simple, para int64 nem se fala. e apesar de ser O(n) em tempo, o tempo para percorrer esse vetor auxiliar também é muito grande, mesmo que seja constante.
Terminar de assistir o video para descobrir qual é a solução viável para o problema
Conteúdo sensacional
e ai Pedro, foi fazer o desafio e fiz de uma forma diferente.
package main
import "fmt"
// challenge
// given an unsorted integer array `nums`, return the smallest missing positive integer.
// you must implement an algorithm that runs in O(n) and uses O(1) auxiliary space.
func firstMissingPositive(nums []int) int {
// def the max and min
min := nums[0]
for i := 0; i < len(nums); i++ {
if i == len(nums)-1-i {
if nums[i] < min {
min = nums[i]
}
break
}
if nums[i] < nums[len(nums)-1-i] {
if nums[i] < min {
min = nums[i]
}
} else if nums[i] > nums[len(nums)-1-i] {
if nums[len(nums)-1-i] < min {
min = nums[len(nums)-1-i]
}
}
}
firstMissedNumber := min + 1
for i := 0; i < len(nums); i++ {
if nums[i] == firstMissedNumber {
firstMissedNumber += 1
i = -1
}
}
fmt.Println(firstMissedNumber)
return firstMissedNumber
}
func main() {
nums := []int{
0, 12,
}
firstMissingPositive(nums)
}
Showw! Gastou quanto tempo para encontrar esta solução?
cheguei dando, já sei que vai ser top
Qualidade demais
Estava pensando em algo interessante para um próximo vídeo, e acho que você pode curtir.
A proposta é construir um programa que busca por uma palavra específica em um texto, só que de uma forma um pouco diferente do convencional. Vamos dar uma olhada na representação hexadecimal e decimal da palavra desejada, convertendo-as em caracteres para fazer a busca.
É uma boa ideia!
Onde você achou esse problema?
Vai crescer
carai, mto bom mesmo!!!
Podendo usar o array inicial como armazenamento, uma solução mais simples é assim:
Pega todos os números negativos do array inicial e troca pro tamanho do array (ambos são irrelevantes, mas assim fica sem negativos). E agora que o array não tem mais números negativos, é só aplicar a segunda solução (com o array de booleanos), mas em vez de usar o array de booleanos, vc pode usar o sinal dos números no array fornecido pra contabilizar a presença de cada número.
ai você está alocando mais memoria oque não pode pois a complexidade do espaço é de O(1)
O homi é bom
Como pode , só deu para ver agora 😢😢😢.
Aula top TMJ
sabe muito
eu não sei se e so comigo mas quando ele explica sem o codigo fica mais difícil para mim entender o que ele esta falando, mas quando ele coloca o codigo faz sentido...
lanca um curso , ensina JS e GO !
Entender o que está acontecendo é fácil, difícil é ter a ideia
se tu lancar um curso de logica eu compro
no caso de funções recursivas o space complexity é O(n) e não O(logn)
Oi cara! Vê esta ideia... não sei se faz sentido !
Pega no array de entrada.
Marca a medida do array
Começa a iterar o array de entrada.
Se for o numero 1, elimina essa entrada do array, se não for, coloca um pointer e avança.
Verifica se o proximo numero é menor que o pointer, se for, avança o pointer, se não for, avança na iteração. Se for numero 2, elimina.
assim até à len do array. Quando uma posição é eliminada e essa posição tem um pointer, o pointer desce uma poisção até ao inicio do array.
Quando termina, se o array tiver mais que 1 elemento, e o elemento mais baixo for maior que o len do array, é esse o numero. Se só tiver 1 elemento, e esse elemento for o len do array, é o len do array +1.
Como esse tipo de canal tem somente 3k74 inscritos? Qualudade pura!!
Eu não entendo nada de programação. Mas teria como usar o case.
👍 🔝
❤
conteúdo premium de graça, ai n tem como sou obrigado a me inscrever
Eu sempre me pergunto como que alguém consegue ter uma solução igual a terceira. Até a segunda eu pensaria, mas essa última eu não ia imaginar nunca 😮
O nome disso eh experiencia… qualquer um q ja está acostumado com desafios, sabe o q fazer e nao fazer
Pouco conhecimento grazadeus
Amigão, esse teste da google é para exercer qual profissão?
Engenheiro de software
Queria entender tudo isso, mas logo vou tá afiado
Por que não usar conjunto?
Por que só a inserção dos elementos no conjunto já quebraria a regra do O(n). Normalmente a estrutura que implementa um conjunto é algo próximo de uma árvore binária, a inserção e a busca seria O(log n). Somente a inserção de todos os elementos positivos no conjunto já seria O(n log n).
Muito estranho usa o len(num). No rust temos que usar uma trait para implementar, Trait é meio que uma interface
Rust tem uma pezinho mais chegado em OOP, Go vai mais na direção funcional/imperativa. Nesse caso em específico.
Eu ate entendi a bagaça mas eu nao faço um desse nivel
Assistir esse vídeo e declarar a minha burrice em nível astronômico 🤣🤣🤣🤣🤣
Como acho esses desafios?
No site leetcode tem vários!
@@phenpessoaAmigão, esse teste é oara exercer qualquer profissão?
E eu achava que sabia programar
n entendi nada
Sou sênior e programado desde 2021 e não entendi quase nada do vídeo.
tenho que estudar mais
UMA CRITICA CONSTRUTIVA; NAO PRECISA FALAR TAO RAPIDO; O CONTEUDO EH BOM; ABRACOS;