EXPLICAÇÃO de um DESAFIO TÉCNICO da GOOGLE | First Missing Positive

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/phe...
--------------------------------------------
Não deixe de se inscrever e deixar o like!
Bem vindo ao canal phenpessoa :)
--------------------------------------------
Minhas redes sociais:
✅ github.com/phe...
✅ / phenpessoa
✅ x.com/phenpessoa
✅ / phenpessoa
✅ / phenpessoa
✅ / phenpessoa
✅ / phenpessoa
Contato profissional:
[e-mail]
--------------------------------------------
#programação #desafio #google

[@lohranrocha]

É 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!

[@thisiscleverson]

Esse canal era oq faltava no youtube!

[@alexalannunes]

Concordo

[@josecarlos-on4re]

Finalmente um canal de conteúdo com informações diretas, objetiva com tudo que precisamos saber

[@anderson.rgomes]

Que canal fantástico, sou desenvolvedor a 15 anos e gostei bastante.

[@rodrigolopes284]

Sou um completo noob da programação, fazedor de CRUD e eu fico admirado com a qualidade dos teus vídeos.

[@josehelvis674]

Fazedor de crud kkk, eu também

[@TheAbimaelST]

Mais um conteúdo premium! Parabéns mano!

[@Lmfenhir]

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.

[@vagnerlandio]

Teu canal é o que estava faltando nesse KZbin 🎉. O que mais tem no KZbin 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. 👏

[@lucasaraujo6.]

O cara é bonito, charmoso e ainda programa em go. Apaixonei!

[@Acqua_ff]

Humildemente, como um iniciante na programação eu não entendi foi merda nenhuma, mas eu achei muito da hora! Parabéns!

[@LuizAzevedown]

Parabéns pelo videio e pela didática! Espero que continue trazendo mais conteúdos desse gênero e em Go...

[@marquinhos0550]

Por favor, continue com os vídeos de desafios! Teu canal é incrível!

[@user-pv3yn8uf6i]

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.

[@mandrakememes319]

cara parabéns, a didática está bem legal, assim como os canais americanos o ritmo de fala está perfeito.

[@italo.magalhaes]

Absurda a qualidade do teu conteúdo, parabéns meu querido

[@leandrocesar4000]

Esse canal é incrível muito bom e quando usar termos mais simplificados vai ser de grande ajuda.

[@caiocutrim3596]

Cara que conteúdo maneiro, Deus abençoe. Ganhou mais um escrito

[@dulii4238]

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

[@samuca.prodev]

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.

[@eduardocerutti]

Teus videos estão me fazendo gostar de leet code novamente, bom trabalho mestre

[@laurolyra]

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

[@GabrielAlves-nj9or]

Caralho mano Tu é um gênio, nmrl O conteudo dos seus videos caiu em uma boa hora pra mim, valeu!

[@User_0x0000LDMR]

Segundo vídeo que vejo do canal e já me inscrevi, ótimo conteúdo

[@fabiomartinsbr]

Parabéns @phenpessoa! Muito legal o canal.

[@gustavoandreronconi7555]

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) }

[@eziovieira6664]

Vai crescer

[@gregjfarias]

caraca, que aula eu to migrando pro go agora e isso foi uma aula foda

[@JotaScript]

Cara, faz um vídeo sobre Big O notation. Mostrando o que é e exemplos de códigos!

[@phenpessoa]

Boa ideia!

[@cmhanft]

Cliquei em inscrever logo nos primeiros minutos, ótimo conteúdo. Se puder fazer algumas soluções em Python seria bom também Sucesso Pedro.

[@DevCearensePeloMundo]

Muito bom, consegui entender todas as soluçôes, bem bacana esse exercício

[@caiocesarmelolopes2156]

Muito bom! Parabéns pelo conteúdo!

[@luismerlini]

estou no quarto vídeo do canal, continue mano! ta ótimo!

[@phenpessoa]

Muito obrigado!

[@vanio.almeida]

Muito bom, ao usar o len() uma única vez melhoraia ainda mais o código, não precisaria verificar o tamanho varias vezes.

[@jimmyfernandes634]

Top demais!

[@Thijv]

Ótimo conteúdo, parabéns 👏👏👏

[@VitorOliveira-br5ts]

Aguardando por mais conteúdo

[@xFlayBR]

carai mlk, tu é brabo! parabéns!! usando go ainda, top!!!

[@medanielsantos]

Cheguei dando like, já sei que vai ser top, ansioso por um curso seu

[@skleon]

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.

[@marcos-fx4vu]

ai você está alocando mais memoria oque não pode pois a complexidade do espaço é de O(1)

[@igorbatista1735]

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...

[@user-hh4bk8gu6y]

cara nao para essa serie. muito foda, eu tenho que diminuir a velocidade de video sua capacidade de raciocinio eu nao acompanho kkk

[@brunocarvalheiro3882]

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.

[@ieieldoria]

Muito bom!

[@danilopereiradeluca9403]

Muito boa explicação!

[@MarcosVinicius-jf1mi]

Muito foda, até parece simples a solução

[@ewerton.valuecode]

Showw! Gastou quanto tempo para encontrar esta solução?

[@morph.developer]

Video de altissima qualidade, parabens pelo conteúdo.

[@lucasemanuelsilva657]

muito bom os seus videos, parabéns!!!

[@luizaugusto7763]

Vídeo muito interessante mano!

[@victorsoligo1119]

sabe muito

[@yago4614]

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

[@gabrielvasconcelos2166]

O homi é bom

[@matheusemanoel4108]

Que canal bom, sério

[@Lanbyteach]

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.

[@phenpessoa]

É uma boa ideia!

[@ispobra1240]

cheguei dando, já sei que vai ser top

[@gagunho]

Que delicia de video cara!☺

[@edwolt]

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

[@Bruno_Moraes2023]

conteúdo premium de graça, ai n tem como sou obrigado a me inscrever

[@gledsonrts5257]

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...

[@gabrielmendes5993]

lanca um curso , ensina JS e GO !

[@diegobaga]

Excelente!

[@HuberthSouza]

Conteúdo sensacional

[@juliorafael3762]

Qualidade demais

[@maclaurinrocha2881]

Como pode , só deu para ver agora 😢😢😢. Aula top TMJ

[@joaosantospereira8345]

Onde você achou esse problema?

[@programandoaos30]

Como esse tipo de canal tem somente 3k74 inscritos? Qualudade pura!!

[@elissonlima2430]

Se o input for ordenado é só retornar o último kk Returno array[len(array)-1]; kkk

[@auladeviolaogospel-cezarro8606]

❤

[@victorbiasibetti]

carai, mto bom mesmo!!!

[@caiqueribeiro2130]

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 😮

[@bebumescuro]

O nome disso eh experiencia… qualquer um q ja está acostumado com desafios, sabe o q fazer e nao fazer

[@ramonportela7048]

no caso de funções recursivas o space complexity é O(n) e não O(logn)

[@Adams456]

Entender o que está acontecendo é fácil, difícil é ter a ideia

[@Davisinhogameplay]

Pouco conhecimento grazadeus

[@user-hh4bk8gu6y]

se tu lancar um curso de logica eu compro

[@pedromartinsfalleiros7721]

Por que não usar conjunto?

[@tiagorafael9872]

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).

[@Dominic_Carioca]

Amigão, esse teste da google é para exercer qual profissão?

[@phenpessoa]

Engenheiro de software

[@BlinderSShortS-wk7tb]

Queria entender tudo isso, mas logo vou tá afiado

[@pedecabra3704]

👍 🔝

[@gutembergdossantoscarvalho1189]

Eu não entendo nada de programação. Mas teria como usar o case.

[@pazfelipe]

Assistir esse vídeo e declarar a minha burrice em nível astronômico 🤣🤣🤣🤣🤣

[@Lanbyteach]

Muito estranho usa o len(num). No rust temos que usar uma trait para implementar, Trait é meio que uma interface

[@phenpessoa]

Rust tem uma pezinho mais chegado em OOP, Go vai mais na direção funcional/imperativa. Nesse caso em específico.

[@fheonix5]

Eu ate entendi a bagaça mas eu nao faço um desse nivel

[@tommyscxtt3833]

Como acho esses desafios?

[@phenpessoa]

No site leetcode tem vários!

[@Dominic_Carioca]

​@@phenpessoaAmigão, esse teste é oara exercer qualquer profissão?

[@rafaelpimentelgomes8878]

n entendi nada

[@TheMonster1400original]

E eu achava que sabia programar

[@Songs_For_Hearts]

UMA CRITICA CONSTRUTIVA; NAO PRECISA FALAR TAO RAPIDO; O CONTEUDO EH BOM; ABRACOS;

[@mikesantos4707]

Sou sênior e programado desde 2021 e não entendi quase nada do vídeo.

[@David55293]

tenho que estudar mais