Hora de un ⚡️ #thread! Hoy vamos a tocar un ejercicio de algoritmia bastante famoso en la entrevista de algoritmos y estructuras de datos!
Es un ejercicio para preparación en entrevistas #FAANG.
Este es nivel fácill, así que manos a la obra! #Javascript
leetcode.com/problems/valid…
Es un ejercicio para preparación en entrevistas #FAANG.
Este es nivel fácill, así que manos a la obra! #Javascript
leetcode.com/problems/valid…
Para este ejercicio, vamos a usar una estructura de datos que me gusta bastante, llamada Stack.
Si necesitas refrescar tu memoria, este video de 6 segundos nos dice lo básico de stacks!
Si necesitas refrescar tu memoria, este video de 6 segundos nos dice lo básico de stacks!
https://twitter.com/charliesbot/status/1366989054433062912?s=20
El problema nos dice esto
- Nos van a enviar un string que contiene los caracteres '(', ')', '{', '}', '[' y ']'
- Una cadena es válida si para un símbolo que abre, existe su contraparte en el orden correcto
- De otra forma, es inválida
- Nos van a enviar un string que contiene los caracteres '(', ')', '{', '}', '[' y ']'
- Una cadena es válida si para un símbolo que abre, existe su contraparte en el orden correcto
- De otra forma, es inválida
Antes de codear, primero tenemos que escribir nuestro algoritmo. Es una excelente práctica para enfrentar estos ejercicios.
Qué solución se te ocurre para poder resolver este problema?
Qué solución se te ocurre para poder resolver este problema?
Ok, se me ocurre esto...
1) Recorremos el string
2) Checamos cada símbolo
3) Si es uno que abre, guardamos su versión que cierra
en un stack
4) Si es uno que cierra, sacamos el último valor del stack
5) Comparamos el valor que sacamos con el caracter actual
1) Recorremos el string
2) Checamos cada símbolo
3) Si es uno que abre, guardamos su versión que cierra
en un stack
4) Si es uno que cierra, sacamos el último valor del stack
5) Comparamos el valor que sacamos con el caracter actual
Definitivamente con solo una imagen no va a quedar tan claro! Pero para eso tenemos este #thread: es momento de checar paso a paso que hace el algoritmo.
Recuerda: no podemos codear sin tener claro que vamos a resolver y como.
Recuerda: no podemos codear sin tener claro que vamos a resolver y como.
Primera iteración: leemos (
( es un símbolo que abre. Como queremos tener rastro de que hemos leído para saber si esta balanceado, vamos a usar el stack para tener esa información.
Guardamos la versión que cierra de "(", que es ")" en el stack.
Seguimos!
( es un símbolo que abre. Como queremos tener rastro de que hemos leído para saber si esta balanceado, vamos a usar el stack para tener esa información.
Guardamos la versión que cierra de "(", que es ")" en el stack.
Seguimos!
Segunda iteración: leemos [
Nuevamente, un símbolo que abre. Como queremos saber en el futuro que símbolo necesitamos para el balanceo, guardamos su versión que cierra, que es "]"
Nuevamente, un símbolo que abre. Como queremos saber en el futuro que símbolo necesitamos para el balanceo, guardamos su versión que cierra, que es "]"
Te das cuenta para que estamos usando el stack? Estamos guardando los valores que queremos encontrar en el futuro para saber si el balanceo es correcto.
El stack nos está ayudando a saber que símbolos vamos a buscar, y en que orden!
El stack nos está ayudando a saber que símbolos vamos a buscar, y en que orden!
Tercera iteración: leemos {
Igual que antes, { es un símbolo que abre, por lo que vamos a guardar en el stack el símbolo que cierra, que es "}"
El siguiente paso es interesante, porque es hora de usar el stack en su esplendor.
Igual que antes, { es un símbolo que abre, por lo que vamos a guardar en el stack el símbolo que cierra, que es "}"
El siguiente paso es interesante, porque es hora de usar el stack en su esplendor.
Un caso diferente! Ahora nos topamos con un valor que cierra -> }
Cómo podemos saber si visitamos antes a su versión opuesta? Para eso tenemos el stack.
Hacemos pop en el stack, que es el valor que estabamos esperando antes.
Cómo podemos saber si visitamos antes a su versión opuesta? Para eso tenemos el stack.
Hacemos pop en el stack, que es el valor que estabamos esperando antes.
Si el valor que obtuvimos al hacer pop es igual al valor que estamos leyendo en este momento, significa que hasta ahora, esta balanceado, y podemos seguir.
Si no fuera así, inmediatamente es inválido!
Si no fuera así, inmediatamente es inválido!
Ahora nos encontramos con "]", que también cierra! Hora de checar el stack.
pop -> ]
El valor que obtuvimos al hacer pop es igual al valor actual? Sí!
Podemos seguir 🤓
pop -> ]
El valor que obtuvimos al hacer pop es igual al valor actual? Sí!
Podemos seguir 🤓
Y llegamos al último símbolo! ")"
Nuevamente checamos el último valor del stack, lo comparamos al que tenemos actualmente, y resulta que...
) === )
Espera! Nos falta checar un caso más.
Nuevamente checamos el último valor del stack, lo comparamos al que tenemos actualmente, y resulta que...
) === )
Espera! Nos falta checar un caso más.
Terminar el string no es señal de que está balanceado aún!
Si el stack se queda con valores aún después de terminar de recorrer el string, significa que no está balanceado.
El último check es -> el stack está vacío?
En este caso sí lo está: este string está balanceado!
Si el stack se queda con valores aún después de terminar de recorrer el string, significa que no está balanceado.
El último check es -> el stack está vacío?
En este caso sí lo está: este string está balanceado!
Ahora sí, hora de codear con #Javascript!
Primero, vamos a codear lo que estamos seguro que necesitamos.
- Necesitamos un for para recorrer el string
- Un stack (que representamos con un array y los métodos push/pop)
- Necesitamos un for para recorrer el string
- Un stack (que representamos con un array y los métodos push/pop)
Ahora necesitamos verificar si el símbolo es uno que abre o cierra.
Podemos poner muchooos ifs/else para esto. Pero, que tal si usamos otra estructura para esto?
Un hashmap nos va a ayudar a crear la relación entre símbolos!
Podemos poner muchooos ifs/else para esto. Pero, que tal si usamos otra estructura para esto?
Un hashmap nos va a ayudar a crear la relación entre símbolos!
Sigue codear el caso en el que el símbolo es uno que abre.
Podemos tomar ventaja de los valores "truthy" de #Javascript.
Si valor actual del string lo usamos como key para acceder al hashmap, puede que nos regrese un valor.
Si regresa el valor, es un símbolo que abre.
Podemos tomar ventaja de los valores "truthy" de #Javascript.
Si valor actual del string lo usamos como key para acceder al hashmap, puede que nos regrese un valor.
Si regresa el valor, es un símbolo que abre.
Como teníamos en el algoritmo, si es un símbolo que abre, tenemos que guardar su versión que cierra en el stack.
El hashmap ya nos dió ese valor al acceder a el! Solamente nos queda agregarlo.
Y seguimos leyendo el string.
El hashmap ya nos dió ese valor al acceder a el! Solamente nos queda agregarlo.
Y seguimos leyendo el string.
Pero, y si el hashmap no nos dio un valor? Es porque el símbolo es uno que cierra.
Sacamos el último valor del stack con un "pop", y comparamos con el valor actual!
Son los mismos? Todo bien, seguimos.
Son diferentes? Inmediatamente rompemos el ciclo. Es inválido!
Sacamos el último valor del stack con un "pop", y comparamos con el valor actual!
Son los mismos? Todo bien, seguimos.
Son diferentes? Inmediatamente rompemos el ciclo. Es inválido!
Y el último check! Verificamos que el stack está vacío.
Si es así, está balanceado! 🥳
Si es así, está balanceado! 🥳
Lo logramos! Puedes probarlo con más casos, incluso escenarios inválidos para confimar que esto funciona como esperamos 🌟
Y esto es todo! Nos vemos pronto en otro ⚡️#thread de "Resolviendo ejercicios de entrevistas de algoritmos/estructuras de datos en #FAANG con #Javascript!
🤓
🤓
• • •
Missing some Tweet in this thread? You can try to
force a refresh
