RESUELVO el PROBLEMA que hice en MI PRIMERA ENTREVISTA como INGENIERO DE SOFTWARE
Vložit
- čas přidán 5. 07. 2024
- Consigue mi curso en MasterMind! 🚀 bit.ly/3kr4bTc
Seguimos viendo más problemas de entrevistas de trabajo para posiciones de desarrollador o ingeniero de software. Esta vez, con Árboles!
👾 Redes sociales 👾
► Twitter: / bettatech
► Instagram: / betta_tech
► Canal Secundario: / @forkdebettatech
► Slack: bit.ly/33gaDDM
👨🏼🏫 MIS CURSOS 👨🏼🏫
👽 Curso de iniciación a la programación con JavaScript:
► bit.ly/3kr4bTc
👕 MERCHANDISING DEL CANAL:
► Tienda CZcams: / bettatech
► Tienda Teespring: teespring.com/stores/bettatec...
⭐️ AFILIADOS ⭐️
🎁 7% Descuento en HOSTINGER (Código BETTATECH)
► www.hostg.xyz/aff_c?offer_id=...
🧠 Autocompletado con IA (Kite)
► www.kite.com/get-kite/?...
🐾 MacPaw (CleanMyMacX):
► macpaw.audw.net/c/2523912/941...
🎵 TODA la música es de EpidemicSound:
► www.epidemicsound.com/referra...
✉️ CONTACTO PROFESIONAL:
► Respuesta no garantizada:
bettatechyt@gmail.com
📚 LIBROS 📚
Design Patterns
► amzn.to/39XuQlq
Head First Design Patterns
► amzn.to/2uq6XUq
Refactoring
► amzn.to/2SQnf2c
Clean Architecture
► amzn.to/3bZVonJ
Clean Code
► amzn.to/32WVKq3
Introduction to Algorithms
► amzn.to/34SyVFP
Cracking the Coding Interview
► amzn.to/2QkdwC6
⏱ ÍNDICE:
• 0:00 - Introducción
• 1:34 - Árboles
• 2:54 - El Problema
• 3:31 - Implementando la solución
• 4:07 - Dibujitos
• 6:30 - Implementando la solución 2
• 14:53 - Análisis de coste
• 17:27 - Conclusión
#roadTo100k - Věda a technologie
Si queréis ver el otro problema REAL que resolvimos en BettaTech, os lo dejo por aquí!
👉🏻 czcams.com/video/HoT3y-L2t20/video.html
Como bien ha notado @Javier Gavilán Mérida, ancestor debe inicializarse a NULL para tratar el caso en el que nos pasen nodos no existentes. Gracias!
Hey wey. Por qué Betta Tech y no Alfa Tech?
O igual mejor validar antes del for que route1 y route2 no sean null, de lo contrario retornas null sin llegar al for.
Me encanta ver como va mejorando la calidad de tus videos!
Los amo a los dos, les besaría sus calvas hasta que tenga mi título
Oh my god!! el dross de la programacion aqui!!!! saludos.
Ya van subiendo la barra bien cabron, tengo que ponerme Las pilas
Esas barbas les dan poderes de desarrollo jajaja
Se rompió la cuarta pared... fffuuuuaaaa!!!!
No podemos volverlo dinámica? Es decir al final del video dejas como un "ejercicio" y en el siguiente video lo explicas o das la solución. Ganas tu y ganamos nosotros
Me gusta esa dinámica, asi para practicar y se puede hacer seguido!
Sigue a liratron, hace streams los miércoles realizando ejercicios de leetcode, es ingeniero en Amazon, igual a veces lleva a invitados interesantes
Cuando estoy resolviendo algoritmos siemper me enfoco en el problema pero casi no visualizo los posibles acontecimientos , tengo que reforzar esa parte.
Brutal, lo vere uno y otra vez para entenderlo mejor. Saludos.
Me encanta este tipo de video, no dejes de hacerlos. Excelente contenido.
Una sección sin duda muy interesante, me parecen geniales estés tipo de videos. Saludos!
Me gustan mucho este tipo de videos, sería genial una sección dedicada!
Muchas gracias por este tipo de vídeos. :)
Hace poco encontré tu canal y es increíble, muchas gracias por estos videos.
Te lo juro tio, te explicas mejor que muchos profesores. Muchas gracias por tus vídeos y ojala llegues al millon de subs.
Muchas gracias por este tipo de videos, son muy útiles para practicar c:
Gracias por el video! Sería interesante más videos sobre esta serie, creo que ayudan mejor a aterrizar teoría e ideas que tenemos. Los de videos de explicación de algoritmos serían muy buenos también :) saludos!
Estos vídeos me parecen muy interesantes y más que estoy viendo este tema en la universidad.
Es la primera vez que veo los videos de tu canal y me encantaron, muchas felicidades !!!!
Muchísimas gracias!!!!
Por favor, continúa subiendo este tipo de videos. Saludos desde República Dominicana.
Llevo mirando tus videos desde hace poco, pero en menos que una semana empiezo mis estudios de informatica en la Universidad Tecnica de Berlin y estoy mas que agradecido a tu canal por compartir todo este conocimiento.
Gracias ☺️! Ahora ya podré tener más posibilidades para trabajar!!🌹😍
Me perdí un poco pero lo veré varias hasta entender, muy buena explicación gracias BettaTech por este contenido espero se siga difundiendo.
Excelente video gracias,,me han aportado mucho en mi carrera q estoy haciendo actualmente,, gracias
Justo el tipo de videos que he estado viendo para prepararme para mi entrevista técnica de programación.
Genial. Un saludo y gracias por tus magníficas explicaciones.
Gracias a ti!
Cursos de estructuras de datos y algoritmos! Por favor
La rompes con estos videos, sos un crack, saludos desde Honduras!
Gracias! Saludos!
Me encantan tus videos!! Espero que sigas así, se nota cada vez una mejora en ellos!
Una duda, qué monitor usas?
Un saludo desde Madrid 😊
muy buen material, desde hoy te sigo, también al holamundo, son los dos canales me parecen muestran verdadero contenido de provecho, mis felicitaciones.
Gracias por las explicaciones!
¡Excelente video Betta Tech! Aprendí bastante, Muchas gracias 😄
Por fin pude entender la estructura de datos de los árboles, y me gustó conocer esa propiedad de que solo existe un camino entre cualquier par de nodos. Y que no es cíclico 😮
También aprendí un poco más de como se hacen los análisis algorítmicos 😄
Aún tengo que repasar otras cosas ¡Saludos!
Nos encanta que resuelvas problemas por eso los likes, por que no haces el problema del laberinto con el camino más corto
Super like! Muy bueno este tipo de videos.
Hola! primero muchas gracias por subir este tipo de videos, es muy interesante, que opinas de resolver este tipo de ejercicios tipo arboles, usando recursividad?. Saludos desde Argentina
Muy buen video! Esta vez te pasaste! :)
Buenas, me ha encantado el vid.
Ya lo han comentado antes, pero en mi opinión sería más adecuado tener en cada empleado una referencia a su jefe en lugar de la lista de empleados del jefe. Obtener la solución no sólo sería lineal, sino que sería lineal respecto a las profundidades de ambos nodos que suele tender a ser logarítmica en función al número de nodos.
Un saludo.
Me encanto tu video, ¿podrías hacer un vídeo recomendando libros o recursos en linea para aprender estructuras de datos?
Excelente como siempre...
Siempre e pensado en hacer cursos de algún tema informático, aunque actualmente no me siento tan preparado porque no tengo conocimientos tan profundos que digamos, pero mi objetivo al querer hacer esos vídeos es dar cursos de programación o de temas informáticos pero con buena calidad y gratis ya que yo e pasado por muchas dificultades por las cuales no puedo costearme cursos que a lo mejor me harían avanzar más rápido en mi formación aparte de lo que me da la universidad
Pero solo quiero decirte que a ti te veo con la capacidad de hacer un muy buen curso y ojalá fuera gratuito para ayudar a la comunidad a crecer y sin importar las limitantes económicas, espero leas este comentario y te animes a hacer cursos, de preferencia comienza con uno de estructuras de datos xd
Hola... estoy encantado de haberme suscripto... es muy enriquecedor escucharte... solo preguntarte en que lenguaje hiciste el ejercicio... felicitaciones, me estoy iniciando en programación a mis 53 años y acá en Argentina hay que reinventarse... saludos
Como todos los nodos de un arbol solo tienen un único "padre", en la implementación de la estructura de datos hubiera incorporado un atributo "parent: TreeNode" (que en el caso del nodo raiz seria vacio) y un método recursivo que sea "getRouteToRoot( node: TreeNode)" donde dado un nodo nos devuelve el camino hacia la raiz. Así nos ahorramos un BFS y simplemente es ver cual es el último ancestro común entre los dos nodos!
Totalmente de acuerdo, una relación desde el empleado a su jefe, en lugar de un jefe con una lista de empleados, mejorará el rendimiento del algoritmo!
Y para llegar a los nodos dados, necesitas una búsqueda igual o no?
Buena pregunta @@johncerpa3782,
Suponiendo que no te den directamente el nodo, sino el contenido (por ejemplo el nombre o el id del empleado), como en cualquier base de datos, necesitaríamos un índice que vincule el dato (contenido) con su nodo. La búsqueda en éstos índices podría hacerse en tiempo constante (p.e. con una tabla hash).
@@DuniC0 Podría ser. Habría que tener en cuenta la complejidad en espacio de esa solución porque ocuparías mucho más, creo yo.
@@johncerpa3782 de hecho no, si hace precomputo de n nodos el hash table o el array de esos indices también tendría el mismo espacio en memoria que es n, es decir lineal.
Estuvo buenisimo la explicacion y el paso a paso, me ha aclarado varias dudas. Hablando de dudas, que paleta de colores usas? Y estará disponible para vscode?
deberías colocarlo como un reto, es decir propones el ejercicio das unos días para responderlo escoges 3 de esas soluciones, las analizas y propones tu propia solución así se hace mas dinámico. Pero me encantan este tipo de videos, espero ver mas.
Al principio lo había pensado comparando cada ancestro de un array con el primero del otro, después el siguiente y asi, llendo de abajo hacia arriba y cuando encuentre uno igual cortamos el bucle, es casi lo mismo que se plantea en el vídeo, solo que el metió código para que sea más ligero de procesar, pero son fors y whiles, asique sigue siendo O2x o O3x, si usas Python podrías implementar Numpy y sería aún más rápido, ya que Numpy usa una especie de funciones especializadas en recorrer arrays
ancestor debe ser por defecto null, si te pasan como parámetro value1 el valor 34, no existe en el arbol y por lo tanto no existe ancestro común :)
Totalmente cierto! Error mío!
Muy bueno, no entendi, todavia tengo que reforzar tendre que volver a ver el video hasta entenderlo a la perfeccion gracias.
Muy buen video, saludos!
Muy buen vídeo, saludos desde México!!
Gracias! 😊
ese algoritimo se puede mejorar muchisimo si añades un atributo de profundidad y enves de partir desde el nodo raiz, partes desde cada nodo evaluando el padre y comparandolo con el otro siempre y cuando sean de la misma profundidad, en caso de que no sean de la misma profundidad priorizas en avanzar en el que tiene mayor profundidad hasta que sean iguales y asi ir comparando y asi te evitas recorrer todo desde nodo raiz y solo recorrer desde abajo hacia arriba.
El problema de la solución no es el coste computacional si no el coste de memoria. Si el árbol es muy grande almacenamos demasiados datos. Una solución más óptima sería sacar la profundidad de ambos e igualarlos en profundidad escalando a través de sus padres en el más profundo. Con ello no hay nada que almacenar y es ir comparando elementos de la misma profundidad hasta que coincidan
Que esquema de color usas en vim?
Super video! Saludos! 🤗
Muchas gracias!!!!
Hola me gustan tus videos, tengo una duda existencial, siento que no soy nada malo programando, no soy un súper crack, pero tengo esa lógica que se necesita para ello. Estoy en tercer año de Ing. de Sistemas (Bachiller), y me pongo a pensar si será mejor dejar la Uni en el olvido para comenzar a practicar y practicar programación. soy de Costa Rica y tengo 35 años, por eso siento a veces que debería de dejar la Uni y comenzar a picar código, ¿Qué recomiendas?
Buen video oye cómo se llama la extensión de colores que tienes?
Me gusta mucho esta serie 👏
Hola Martin, esta genial el video, pero me queda una duda, en general estas estructuras se tienen los nodos hijos como Left y Right.. o estoy equivocado.. Saludos desde Chile.
Hombre no nos agradezcas a nosotros, gracias a ti que nos despejas las inseguridades de como son las entrevistas de trabajo, sigue asi, saludos.
Me parece interesante quiero más videos de este tipo
Empecé a estudiar programación y no entiendo nada, pero me gusta. Podría estar viendo videos como éste. Espero que en algún momento entienda algo ^_^
Que bien explica este man, nada que ver con mis catedraticos de universidad.
ve la lista de problemas de codeforces o del ICPC :3
esos están bien hardcoreee!!!!
Saludos :P
Excelente canal, soy nuevo suscriptor
Este problema pide recursividad a gritos, desde mi punto de vista hace la solución mucho más elegante.
Además, aplicando la recursividad puedes hacer la construcción de la ruta a la vez por lo que te ahorras esa otra búsqueda ya que en el retorno puedes construir el array con el camino de forma bastante simple.
De todos es una buena aproximación para la gente que es novata.
muy buen aporte
Buenas, tengo una duda. En caso de que en el ejemplo se cojan 10 y 5, el primer ancestro común que dará la función que creaste no sería 5 ?. De ser así estaría correcto? no tendría que dar 2 como primer ancestro común ya que el 5 sobre el 5 no sería un ancestro sino el mismo ?. Un saludo y mil gracias :)
Excelente broo
Videos así hacen que me encante pasármela todo el día en Hackerrank (≧▽≦)
Excelente contenido. 👌
Gracias!!
me alegra mucho que leas los comentarios y los aceptes positivamente! yo fui uno de los que comentó lo que dices al principio, pero con la explicación si que me parece más logico... buen video!
Gracias! Poco a poco mejoramos :D
Recorrería desde los nodos de entrada hasta la raíz, interceptaría los dos conjuntos de nodos resultantes y el primer elemento de la intercepción es el primer nodo en común.
Estaría bien que dejaras un GIT con el código por si alguien le quiere echar un vistazo. Buen video saludos.
Gracias por este hermoso video esto me resume un corte de este semestre en mi ing. lo chistoso es que el profe solo lee y no dan ganas de ver este tema.
interesa más y practique.
creo que amo tu canal 🥺
me encanto el video. Yo lo que hubiese hecho es guardar la referencia del padre en la estructura del arbol, luego cuando me dan dos nodos lo que hago es recorrer el árbol hasta encontrarlos. Una vez que tengo la referencia de cada nodo, lo que hago es preguntar por el valor de su padre y voy haciendo los siguientes pasos:
a) Agarro el valor del nodo padre de A y comparo el valor con el nodo padre de B
b) el que es más grande (en valor) significa que esta más abajo en la jerarquia, por ende, tengo que agarrar el padre de ese nodo (sería el abuelo para el nodo en cuestión) y preguntar su valor y vuelvo a repetir la pregunta de quien es más grande
C) el punto de quiebre sería cuando encuentro el mismo valor en los nodos padres (la solución al problema) o encuentro directamente la raíz del árbol (solución del problema)
un saludo y me encantan tus videos, siempre los miro y aprendo y/o recuerdo algunos temas :)
pd: para hacer la solución que dije es obvio que tengo que tener el árbol ordenado sino no podría aplicarla. Muchas veces eso en las entrevistas no te aclaran eso,yo lo que hago siempre es suponerlo y aclararlo cuando doy la solución
Que tema usas de vim se ve genial ! 😍
Tengo una duda, cual es el lenguaje que estas utilizando en el video?
siempre que veo arboles pienso en funciones recursivas creo que se podia hacer recursivamente y es mas optimo no tienes que recorer tantos nodos pero la forma de resolverlo aqui es mas sencilla de entender
Pregunta, el for de minuto 9:00 , no deberia estar hecho de mayor a menor? No podriamos dar con un jefe que no es el mas chico en comun entre las dos rutas?
Hola buen dia justo el problema que mencionas lo pusieron en HackerRank, lo Resolvi con MS SQL.
Hola , cual es tu AirlineTheme?
Buen vídeo!
Muy buen material. Estaría muy bien una serie sobre cómo enfrentarse a una entrevista de trabajo real, con todas sus etapas.
Gracias por el vídeo!
Sería bueno no llamar a normalize 3 veces, quizás guardarlo en una variable? Eso lo haría mucho mas rápido.
Que gran video enserio necesitaba más de este tipo eres una increíble persona sigue así!!
Excelente video
Es coste lineal en el caso de que se requiera saber el LCA una única vez, en caso contrario se debería implementar un algoritmo mas optimizado que pre-calcule el LCA para cada par de nodos. Una solución seria emplear el algoritmo de RMQ sobre un recorrido DFS
Si tuvieramos datos repetidos en el node.val no funcionaria, yo recomendaria cambiar el algoritmo a hacer comparaciones de clases en vez de valor al igual que en el hashmap no guardar el children.val, si no la instancia de la clase, no estoy 100% de como usa el hasheo de objetos en js pero en python es posible hacerlo
en que lenguaje lo programa?
Sería interesante que hagas un video explicando la solución logarítmica al mismo problema
Estableciendo que fuera posible y que lograramos encontrar una solución con ese coste
El for let child que está dentro del comité route no lo contaste, eso no haría que ese método aumente su complejidad?
Llego tarde pero para quién le interese (al principio tuve la misma duda) :
*Ese mismo for* es lo que le da complejidad lineal al while, ya que en el peor de los casos el nodo actual tiene al resto de los nodos del árbol como hijos. En dicho caso, no se vuelve a ejecutar más el for ya que no quedarían niveles más bajos y simplemente el while itera sobre esos nodos hasta pegarle o no encontrar nada.
En caso de que el nodo tenga pocos hijos simplemente se sigue avanzando hacia abajo por cada uno de ellos hasta pegar con el objetivo y descartando esos hijos de los siguientes for, por lo que nunca deberías repetir ningún camino y en el peor de los casos recorrés todo el árbol una sóla vez. La relación de recurrencia quedaría algo como T(N) = N-h + O(h), siendo h el numero de hijos del nodo actual y el O(h) correspondería a encolar esos hijos en la cola, valga la redundancia.
Interesante vídeo, me encantan estos ejercicios que pese a no ser complicados requieren de pensar un par de minutos (si no se tiene mucha experiencia como yo). Por otro la do me gustaría hacerte una pregunta, ¿Qué opinas del uso de break? He visto que lo usaste en el else (minuto 9 aprox), y siempre he leído que los break rompen la ejecución de manera abrupta y que se desaconseja su uso, de hecho creo que en Python ni siquiera existe, me gustaría saber tu opinión como profesional, yo como Junior leo mucho pero al final no se muy bien lo que creer.
Un saludo y enhorabuena por tu trabajo con el canal, es muy divertido y educativo.
Desde mi punto de vista no es aconsejable usarlo si lo puedes evitar. Normalmente si encuentras un break ocurre uno de 2 casos posibles:
Caso #1: El break está señalando una condición sencilla de salida de un bucle, y por tanto la condición del "if" que lleva al break debería estar situada en la condición del while o for
Caso #2: El break está señalando una condición compleja de salida de un bucle, lo cual implica que al menos parte del bucle es complejo, y por tanto todo el bucle debería salir a una función a parte y usarse return en lugar de break (esto te permite identificar rápidamente la salida con resultado, que es el return dentro del bucle, de la salida sin resultado, que será el return fuera del bucle, normalmente ambos return cerca entre si y al final de la función).
Sin embargo, no es que estos 2 casos que yo comento sean definitivos, aún hoy día hay debate sobre esto. Te adjunto un enlance a un comentario de stackoverflow que señala por qué no está de acuerdo con el uso de break SI SE PUEDE EVITAR (nada es definitivo):
es.stackoverflow.com/a/132112
Al final la cuestión está en como conseguir que el flujo sea fácil de seguir, o lo que es lo mismo, el código sea fácil de leer y entender. Un return sale directamente de la función, por lo tanto no hay realmente problemas para seguir el flujo, sin embargo un break solo termina el bucle, por lo tanto vas a tener que saltar de una línea dentro del bucle a la línea final del bucle (que es más difícil de identificar) para poder continuar.
Yo antes que el uso de break veo mejor el uso de continue, ya que el inicio de un bucle es más fácil de identificar y bien usado continue puede reducir el nivel de indentación necesario:
Pasaríamos de esto:
for( int i = 0 ; i
@@javiergavilanmerida2133 Muchas gracias por la explicación, seguro que a más de uno le viene genial, yo en ese sentido la "teoría" me la sé y mi opinión es que si usas un break; es que no has pensado lo suficiente en la lógica del algoritmo en cuestión ya que para mi un break; es el último recurso ya que se puede crear un código sin su uso de forma mucho más limpia (como comentas con la extracción a método y el uso de return o el uso de condiciones en otros casos). Simplemente me hubiera gustado saber el por que pone ese break; ahí BettaTech y su opinión, ya que como comentas, no hay nada establecido y puede que haya gente que quiera usarlo, yo como Junior no me echaré las manos a la cabeza aún que a mi personalmente no me guste.
Ojalá hubiera más gente como tu en internet con ganas de dar explicaciones tan detalladas, y gracias por el enlace a la discusión de stackoverflow, no conocía ese debate.
Un saludo y nuevamente, gracias.
Joder que bueno está Vsauce ahora que empezó a hablar español
No he visto la solución.
Pero según yo, la solución es almacenar el camino en una pila y luego revisar ambas pilas y ver en jerarquía cuál es el primer elemento común que hay dentro de ellas. Podríamos hacerlo con recursividad y un if
cual es tu tema de viim?
Puede hablar de nodos? Para junior :D
Hola BettaTech... disculpa salirme un poco del tema pero yo estoy suscrito a tu canal y ya no recibo notificaciones de nuevos vídeos.
Por lo que pude averiguar es Google quien el 13/ago/2020 quien ya no envía e-mail de aviso sobre nuevos videos.
La pregunta del millón es cómo solucionar este problema, no sólo para tu canal sino que para todos los que uno puede estar suscrito?
Creo que el bfs no haria falta. Si se le añade el puntero de un hijo al padre. Asi poder hacer directamente el backtrace. Lo que significa coste logaritmico (por niveles de arbol)
Dentro del while de computeRoute, donde hay un for que itera cada hijo del nodo que se está revisando actualmente, no generaría algún tipo de complejidad n^2 ? Considerando que por cada nodo de los N nodos se revisan todos sus hijos, lo cual es una cantidad variable de iteraciones.
Ojalá veas esto y respondas n.n gracias por tu contenido!
Un hijo solo puede tener un padre, por lo que si miras el global de todas las iteraciones que se hacen, solo visitas cada nodo una vez. Si N es el numero de nodos, como maximo puedes hacer n iteraciones. El N^2 aparece cuando haces bucles donde repites visitas normalmente
No se si a lo mejor es una barbaridad, pero en principio me parece ( creo...) mas sencillo ir desde el nodo1 y desde el nodo2 hacia atras (conociendo por supuesto el length para salir al llegar al root) y el primer nodo[i-1] (para el primero) que coincida con el nodo [j-1] (para el segundo) en valor; seria la solución.
Pensé en esta solución, la veo más eficiente ya que no haría falta recorrer el árbol desde la raíz hasta cada uno de los nodos
creo que hubiera sido mejor implementar una busqueda por profundidad, de esta forma obtienes inmediatamente el camino desde la raiz al hijo, y no tienes que guardar los padres ni nada de eso
Esto se puede hacer en O(log n) en el mejor caso
En python ayudaría a la resolución del problema los conjuntos.
Yo lo que tenía pensado hacer es ir bajando los niveles del árbol hasta llegar a un nodo que entre sus hijos no estuviera los dos nodos citados aunque ahora que lo pienso quizás no sea muy eficiente. Buen vídeo para recordar los recorridos de árboles.
No te mentire, es lo que hice cuando en su momento estuve en la entrevista esta 😂 Lo que hice fue hacer un bfs, y por cada nodo que visitaba hacia otro bfs buscando ambos nodos. Cuando encontraba el primer nivel donde ya no encontrabana los dos, bingo. Pero claro eso a la practica podia ser cuadratico
@@BettaTech Gracias, es un gran consuelo, que yo no soy de computación.