Este es el tercer artículo en la serie sobre entrevistas para ingenieros de Frontend. Si te perdiste los primeros artículos, puedes accederlos aquí:
Pre-requisitos
- Conocimiento intermedio de JavaScript (ciclos, objetos, arreglos)
- Conocimiento básico de Big O y Recursión (Intro a Rendimiento de Algoritmos y Algoritmos de Búsqueda)
- Conocimiento de ES6 (arrow functions)
- Conocimiento de clases y métodos en JavaScript
Cómo correr los ejemplos
Durante este artículo estaré utilizando repl.it para demostrar los ejemplos. Cada ejemplo tendrá un enlace donde podrás correr el código. Además podrás hacerle fork para que experimentes con el algoritmo o añadas notas.
Al entrar a los enlaces de repl.it podrás darle play o Run al algoritmo para ver el resultado. Para ver el código, presiona Show files. Puedes copiarlo a tu cuenta presionando Fork repl.
👉 Recomiendo que intentes construir el algoritmo antes de proceder a mi solución. Puedes hacerlo en repl.it, localmente en tu computadora, o cualquier otro método que te permita correr funciones de JavaScript.
Introducción
Las estructuras de datos son uno de los temas favoritos en las entrevistas para desarrolladores. Son la manera en que organizamos la información en nuestras aplicaciones. Aunque generalmente se asocian con el backend, como desarrolladores frontend es importante saber cómo y cuándo usar cada tipo ya que interactuamos con información todo el tiempo. Encontrarás que algunas estructuras ya las usas a menudo en tu código y que otras, tal vez, son más especializadas. No existe una estructura mejor que las demás. La mejor estructura dependerá de la aplicación.
En esta serie de artículos hablaré sobre algunas de las estructuras más comunes, sus métodos, y ejemplos. Empezaré repasando el tema de clases en Javascript ya que serán la herramienta que utilizaremos para modelar las estructuras.
Stacks y queues son estructuras lineales bien parecidas. La diferencia entre estas es cómo se añaden nuevos elementos a la lista. Cubriremos ambos en este artículo.
Clases
Algunos lenguajes incluyen estas estructuras de datos, pero JavaScript no. Por esto, utilizaremos clases para crear estructuras que podrán ser reutilizadas. Esta no es la única manera de crear estas estructuras, pero como las clases nos permiten crear plantillas de objetos con propiedades y métodos predeterminados he decidido utilizarlas para este artículo.
Aquí les daré una breve introducción a conceptos básicos de clases. La palabra class crea una constante por lo que la clase no podrá ser definida nuevamente. El método para crear nuevos objetos es el constructor .
Ejemplo
En este ejemplo creamos una clase para artículos.
Basados en esta clase, podremos crear artículos que contengan título y autor. Para esto, se utiliza la palabra clave new.
También podemos añadirle funcionalidad a través de métodos. Se le llama método a una función que afecta instancias individuales de una clase. Los métodos de dataStructuresArticles no afectarán a sortingAlgorithmsArticle.
Los métodos en las clases se añaden fuera del constructor y utilizan la misma sintaxis de una declaración de función, pero sin la palabra clave function. Accede a las variables utilizando this.
Añadirle un page view a dataStructuresArticle, no afecta los page views de sortingAlgorithmsArticle.
Stacks
Un stack es una estructura de datos para almacenar listas o colecciones. Lo que lo diferencia de otras es que sólo puedes tomar dos acciones:
- añadir elementos al final de la lista
- sacar elementos del final de la lista
Esto es conocido como LIFO, por sus siglas en inglés. Last In, First Out quiere decir que el último en entrar, es el primero en salir.
Algunos ejemplos de la vida real pueden ser los siguientes:
- Montaña de pancakes - montas pancake sobre pancake y empiezas a comer por el último que montaste
- Montaña de sillas - acomodas las sillas una encima de la otra, pero para poder sacar una tienes que sacar la última que pusiste y así sucesivamente
Además, tiene muchas aplicaciones en programación. Un ejemplo discutido en el primer artículo de esta serie es el call stack.
En JavaScript, esta estructura no existe, por lo que comúnmente se utiliza un arreglo en su lugar. Podemos utilizar los métodos de Array.prototype.push() y Array.prototype.pop() para imitar los métodos de un stack. El problema con esto es que los arreglos tienen muchos otros métodos que los stacks no tienen. Sin querer, podemos utilizar esos otros métodos rompiendo las reglas de lo que hace un stack. Vamos a implementar una clase que solo nos permita acceder los métodos que tiene un stack.
La clase Stack mantiene récord de los elementos en la primera y en la última posición y del tamaño del stack para garantizarnos un rendimiento de O(1) en cada una de estas acciones. Esta clase modela nuestra lista o colección. Esto es suficiente para crear una instancia de stack, pero no hemos creado los elementos que lo compondrán. Utilizaremos una clase para modelar los elementos a los cuales llamaremos nodes (nodo).
Un nodo solo se preocupa por su propio valor y por qué elemento estaba antes de él.
Pseudocode push(val)
- Crea un nodo con el valor aceptado por la función
- Si es el primer nodo, asígnalo como primero
- Si no es el primer nodo, asigna el último nodo como el anterior de este nuevo nodo
- Asigna el nuevo nodo como el último
Aumenta el tamaño del stack por 1
Vamos a crear nuestro primer stack y añadirle algunos nodos.
Pseudocode pop()
- Verifica si hay nodos en el stack, si no hay devuelve null
- Si hay, guarda el último nodo en una constante
- Si el stack solo tiene un nodo, re-asigna el primero y el último a null
- Si tiene más de un nodo, re-asigna el último al anterior al penúlitmo
- Reduce el tamaño del stack por 1
- Devuelve el nodo que guardaste en el segundo paso
Ahora podemos remover nodos del Stack.
La complejidad de un stack es:
Como sólo tenemos información sobre los nodos al principio y al final, para buscar un nodo con un valor particular debemos ir nodo por nodo. Hay diferentes maneras de modelar un stack en Javascript. No importa la que escojas, asegúrate que escribirlo para que la complejidad constante para añadir y remover elementos ya que esto es una de las partes más importantes de un stack.
✨ Replit Stacks ✨
Queues
Al igual que en el stack en el queue solo puedes añadir y remover. La diferencia es que en el queue añades al final y remueves del principio. Esto es conocido como FIFO (First In, First Out). El primer elemento en entrar a la lista, es el primero en salir.
Un ejemplo de la vida real es una fila (o cola) en el que el primero en llegar es el primero en ser atendido. En JavaScript, el ejemplo puede ser el event loop que procesa mensajes en orden de llegada.
Para modelar esta estructura en JavaScript utilizaremos los métodos de enqueue(val) y dequeue(). Estos son parecidos a los métodos de arreglos push(val) y unshift(), respectivamente.
La clase de Queue es muy parecida a la de Stack. Lo que cambia son los métodos.
La clase de Node para Queue se preocupa por su propio valor y por el nodo que le sigue. El stack se preocupaba por el anterior.
Pseudocode enqueue(val)
- Crea un nuevo nodo con el valor aceptado por la función
- Si el queue está vacío, asigna el nodo al primero y al último
- Si el queue tiene nodos, asigna el nodo al próximo valor del último nodo
- Asigna el nodo al último elemento en la lista
- Aumenta el tamaño del queue por 1
- Devuelve el queue
Pseudocode dequeue()
- Si el queue está vacío, devuelve null
- Si tiene nodos, guarda el primero en una constante
- Si solo tiene un elemento, re-asigna el primero y el último a null
- Si tiene más de un nodo, re-asigna el primero al segundo elemento
- Reduce el tamaño del queue por 1
- Devuelve el nodo que guardaste en el segundo paso
Ahora podemos crear queues y añadirle y removerle elementos.
La complejidad de un queue es:
Como el queue sabe qué nodo está al principio y qué nodo está al final, inserción y remoción son constantes. Sólo hay que cambiar los punteros correspondientes y añadir el nuevo nodo. De igual manera, al tener sólo esta información, para recorrer o encontrar un valor particular, tenemos que visitar cada nodo hasta dar con el que buscamos.
✨ Replit Queue ✨
Conclusión
A la hora de escoger una estructura de datos es importante considerar los requerimientos para escoger la mejor opción. Las estructuras discutidas en este artículo son excelentes cuando necesitas mantener un orden particular, pero solo necesitas acceso en algún extremo. En JavaScript, podrías imitarlas usando un arreglo y sus métodos push(val), pop(), unshift(val), shift(), pero en las últimas dos perderías el beneficio del rendimiento constante que caracteriza a estas estructuras.
En el próximo artículo discutiré otra estructura lineal parecida a estas, linked-lists. También podrías crear stacks y queues utilizando linked-lists, pero JavaScript no tiene ninguna de estas así que es conveniente crear una clase para la que vayas a utilizar.