zjaaal/experiments

Here I just mess around with code. I like to reverse engineer things, so expect re-implementations. Just for educational purposes.

Frontend Developer

I have been engaged in coding since 2020. I am a technology enthusiast and a lifelong learner.

• 🌍 I'm from Venezuela. Currently living in Buenos Aires, Argentina.
• ✉️ You can contact me at [email protected]
• 📌 Connect with me on LinkedIn

Stats

My CodeWars Stats

My GitHub Stats

experiments's Issues

DS&A Roadmap

Tome esto de coding-interview-university

Estructuras de datos

• Arreglos

  • Implemente un vector automáticamente redimensionable.
  • Descripción:
    • Arrays (video)
    • UCBerkley CS61B - Linear and Multi-Dim Arrays (video)
    • Dynamic Arrays (video)
    • Jagged Arrays (video)
  • Implemente un vector (Arreglo mutable con redimensionamiento automático):
    • Practique codificar usando arreglos y apuntadores, y un apuntador matemático para saltar a un índice en lugar de utilizar la indexación.
    • Nuevo arreglo de información primaria con memoria asignada.
      • Puede asignar un arreglo entero, simplemente no use sus características.
      • Empiece con 16, o si el número inicial es mayor, use potencias del 2 - 16, 32, 64, 128.
    • size() – Número de elementos.
    • capacity() – Número de elementos soportados.
    • is_empty()
    • at(index) – Regresa el elemento al índice dado. Falla si el índice esta fuera de sus limites.
    • push(item)
    • insert(index, item) – Inserta el elemento en el índice, intercambia el valor del índice y desplaza los elementos a la derecha.
    • prepend(item) – Puede usar para insertar encima del índice 0.
    • pop() – Elimina del final, regresa el valor.
    • delete(index) – Elimina el elemento en el índice, intercambia todos desplazándolos a la izquierda.
    • remove(item) – Busca el valor y elimina el índice que lo contiene, aunque este en varios lugares.
    • find(item) – Busca el valor y regresa el primer índice con ese valor, devuelve -1 si no lo encuentra.
    • resize(Nueva capacidad) // Función privada.
      • Cuando alcance el límite, redimensiona al doble el tamaño.
      • Cuando se haga “pop” a un elemento, si el tamaño es 1/4 de la capacidad, redimensiona a la mitad.
  • Tiempo:
    • O(1) Para añadir/eliminar al final (Amortizado para asignaciones por más espacio), índice o actualización.
    • O(n) Para insertar/eliminar donde sea.
  • Espacio:
    • Contiguo en la memoria, por lo que la proximidad ayuda al rendimiento.
    • Espacio necesario = (capacidad de matriz, que es> = n) * tamaño del elemento, pero incluso si 2n, todavía O (n))

• Listas Enlazadas

  • Descripción:
    • Singly Linked Lists (video)
    • CS 61B - Linked Lists (video)
  • C Code (video)
    - No todo el video, solo porciones acerca de la estructura de nodos y la asignación de memoria.
  • Listas enlazadas vs Arreglos:
    • Core Linked Lists Vs Arrays (video)
    • In The Real World Linked Lists Vs Arrays (video)
  • why you should avoid linked lists (video)
  • Gotcha: Necesita tener conocimiento del apuntador a apuntador:
    (Cuando se pasa un apuntador a una función este puede cambiar la dirección a la que el apuntador apunta)
    Esta página es sólo para tener una idea sobre un apuntador a un apuntador. No recomiendo esta lista de estilo transversal. La legibilidad y sostenibilidad sufren debido a la astucia.
    • Pointers to Pointers
  • Implemente (Lo hice con y sin un puntero de cola):
    • size() – Regresa el número de elementos en la lista.
    • empty() – Un bool que regresa verdadero si está vacío.
    • value_at(index) – Regresa el valor del el n-avo elemento (usando 0 como primero)
    • push_front(value) – Añade un elemento al frente de la lista.
    • pop_front() – Elimina el elemento frontal y regresa su valor.
    • push_back(value) – Añade un elemento al final.
    • pop_back() – Elimina el último elemento y devuelve su valor.
    • front() – Obtiene el valor del elemento frontal.
    • back() – Obtiene el valor del último elemento.
    • insert(index, value) – Inserta valor en el índice, por lo que el valor actual en ese índice es apuntado al nuevo elemento en el índice.
    • erase(index) – Borra el nodo del índice dado.
    • value_n_from_end(n) – Regresa el valor del nodo en la n-ava posición a partir del final de la lista.
    • reverse() – Pone al revés toda la lista.
    • remove_value(value) – Borra el primer elemento en la lista con ese valor.
  • Doble lista enlazada:
    • Description (video)
    • No es necesario.

• Pila:

  • Stacks (video)
  • No implementaré. Implementando con arreglos es trivial.

• Cola o fila

  • Queue (video)
  • Circular buffer/FIFO
  • Implementar usando listas enlazadas, con el puntero de la cola:
    • enqueue(value) – Añade el valor en la posición de la cola.
    • dequeue() – Regresa el valor y elimina el valor más recientemente añadido(frontal)
    • empty()
  • Implementar usando arreglos de tamaño fijo:
    • enqueue(value) – Añade elemento al final del almacenamiento disponible.
    • dequeue() – Regresa el valor y elimina el elemento más recientemente añadido.
    • empty()
    • full()
  • Costo:
    • Una mala implementación usando lista enlazada donde se enqueue en la cabeza y dequeue en la cola sería O (n), porque usted necesitaría el siguiente al último elemento, causando un recorrido completo cada dequeue.
    • enqueue: O(1) (amortizado, Lista enlazada y arreglo [sondaje])
    • dequeue: O(1) (Lista enlazada y arreglo)
    • empty: O(1) (Lista enlazada y arreglo)

• Matriz asociativa

  • Videos:

    • Hashing with Chaining (video)
    • Table Doubling, Karp-Rabin (video)
    • Open Addressing, Cryptographic Hashing (video)
    • PyCon 2010: The Mighty Dictionary (video)
    • (Advanced) Randomization: Universal & Perfect Hashing (video)
    • (Advanced) Perfect hashing (video)

  • Cursos en línea:

    • Core Hash Tables (video)
    • Data Structures (video)
    • Phone Book Problem (video)
    • Matriz asociativas distribuidas:
      • Instant Uploads And Storage Optimization In Dropbox (video)
      • Distributed Hash Tables (video)

  • Implementar con arreglo usando sondaje lineal

    • hash(k, m) - m es el tamaño de la matriz asociativa.
    • add(key, value) – Si la llave ya existe , actualiza el valor.
    • exists(key)
    • get(key)
    • remove(key)

Información adicional

• Búsqueda binaria

  • Binary Search (video)
  • Binary Search (video)
  • detail
  • Implementar:
    • Búsqueda binaria (en un arreglo ordenado de enteros)
    • Búsqueda binaria usando recursión.

• Operaciones bit a bit

  • Bits cheat sheet - Debería conocer varias de las potencias de 2 a partir de (2^1 to 2^16 and 2^32)
  • Obtenga un buen entendimiento de la manipulación de bits con: &, |, ^, ~, >>, <<
    • words
    • Buena introducción:
      Bit Manipulation (video)
    • C Programming Tutorial 2-10: Bitwise Operators (video)
    • Bit Manipulation
    • Bitwise Operation
    • Bithacks
    • The Bit Twiddler
    • The Bit Twiddler Interactive
  • Complemento a uno y dos:
    • Binary: Plusses & Minuses (Why We Use Two's Complement) (video)
    • 1s Complement
    • 2s Complement
  • Contar bits puestos:
    • 4 ways to count bits in a byte (video)
    • Count Bits
    • How To Count The Number Of Set Bits In a 32 Bit Integer
  • Redondeo a la próxima potencia de 2:
    • Round Up To Next Power Of Two
  • Valor de intercambio:
    • Swap
  • Valores absolutos:
    • Absolute Integer

Árboles

• Árboles - Notas & Antecedentes

  • Series: Trees (video)
  • Construcción básica de árboles
  • Recorrido
  • Algoritmos de manipulación
  • BFS (búsqueda en amplitud)
    • MIT (video)
    • Orden de nivel (BFS, usando colas):
      Tiempo de complejidad: O(n)
      Espacio de complejidad: Mejor: O(1), Peor: O(n/2)=O(n)
  • DFS (búsqueda en profundidad)
    • MIT (video)
    • Notas:
      Tiempo de complejidad: O(n)
      Espacio de complejidad:
      Mejor: O(log n) – Promedio de la altura del árbol.
      Peor: O(n)
    • inorder (DFS: left, self, right)
    • postorder (DFS: left, right, self)
    • preorder (DFS: self, left, right)

• Árboles de búsqueda binaria: BSTs

  • Binary Search Tree Review (video)
  • Series (video)
    • Comienza con la tabla de símbolos y pasa por las aplicaciones BST.
  • Introduction (video)
  • MIT (video)
  • C/C++:
    • Binary search tree - Implementation in C/C++ (video)
    • BST implementation - memory allocation in stack and heap (video)
    • Find min and max element in a binary search tree (video)
    • Find height of a binary tree (video)
    • Binary tree traversal - breadth-first and depth-first strategies (video)
    • Binary tree: Level Order Traversal (video)
    • Binary tree traversal: Preorder, Inorder, Postorder (video)
    • Check if a binary tree is binary search tree or not (video)
    • Delete a node from Binary Search Tree (video)
    • Inorder Successor in a binary search tree (video)
  • Implementar:
    • insert // Inserta valores en el árbol.
    • get_node_count // Obtener la cuenta de los valores almacenados.
    • print_values // Imprime los valores en el árbol, del min al max.
    • delete_tree
    • is_in_tree // Devuelve verdadero si el valor dado existe en el árbol.
    • get_height // Regresa la altura en los nodos (La altura de cada nodo es 1)
    • get_min // Regresa el valor mínimo almacenado en el árbol.
    • get_max // Regresa el valor máximo almacenado en el árbol.
    • is_binary_search_tree
    • delete_value
    • get_successor // Regresa el siguiente valor más alto en el árbol después del valor dado. Si no hay ninguno, devuelve -1.

• Montículo / Colas de Prioridad / Montículo binario

  • Visto como un árbol, pero usualmente es lineal en el almacenamiento (arreglo, lista enlazada)
  • Heap
  • Introduction (video)
  • Naive Implementations (video)
  • Binary Trees (video)
  • Tree Height Remark (video)
  • Basic Operations (video)
  • Complete Binary Trees (video)
  • Pseudocode (video)
  • Heap Sort - jumps to start (video)
  • Heap Sort (video)
  • Building a heap (video)
  • MIT: Heaps and Heap Sort (video)
  • CS 61B Lecture 24: Priority Queues (video)
  • Linear Time BuildHeap (max-heap)
  • Implementar una cola máxima:
    • insert
    • sift_up – Necesario para el insert.
    • get_max – Regresa el máximo elemento, sin eliminarlo.
    • get_size() – Regresa el número de elementos almacenados.
    • is_empty() – Devuelve verdadero si la cola está vacía.
    • extract_max – Regresa el máximo elemento, eliminándolo.
    • sift_down – Necesario para extract_max.
    • remove(i) – Elimina el elemento en el índice x.
    • heapify – Crea una cola de un arreglo de elementos, necesario para heap_sort.
    • heap_sort() – Toma un arreglo no ordenado y lo convierte en un arreglo ordenando en su lugar usando una cola máxima.
      • Nota: Usar una cola mínima reduciría operaciones, pero duplicaría el espacio necesario (No se puede hacer en lugar)

Ordenamientos

• Notas:

  • Implementar ordenamientos y conocer el mejor/peor de los casos y el promedio de complejidad de cada uno:
    • No ordenamiento de burbuja - Es terrible - O(n^2), excepto cuando n <= 16.
  • Estabilidad en algoritmos de ordenamiento("¿Es Quicksort estable?"):
    • Sorting Algorithm Stability
    • Stability In Sorting Algorithms
    • Stability In Sorting Algorithms
    • Sorting Algorithms - Stability
  • ¿Cuáles algoritmos pueden ser usados en listas enlazadas? ¿Cuáles en arreglos? ¿Cuál en ambos?
    • No recomendaría ordenar una lista enlazada, pero el ordenamiento por mezcla es realizable.
    • Merge Sort For Linked List

• Para ordenamientos por montículos, vea la estructura de datos de Colas o filas arriba. El ordenamiento por montículos es estupendo, pero inestable.

• Bubble Sort (video)

• Analyzing Bubble Sort (video)

• Insertion Sort, Merge Sort (video)

• Insertion Sort (video)

• Merge Sort (video)

• Quicksort (video)

• Selection Sort (video)

• Codificando Merge sort:

  • Using output array (C)
  • Using output array (Python)
  • In-place (C++)

• Codificando Quick sort:

  • Implementation (C)
  • Implementation (C)
  • Implementation (Python)

• Implemente:

  • Mergesort: O(n log n) Promedio y peor caso.
  • Quicksort O(n log n) Caso promedio.
  • El ordenamiento por selección y el de inserción ambos son O(n^2) Promedio y peor caso.
  • Para ordenamientos por montículos, vea la estructura de datos de Colas o filas arriba.

• No requeridos, pero los recomendaría:

  • Sedgewick - Radix Sorts (6 videos)
    • 1. Strings in Java
    • 2. Key Indexed Counting
    • 3. Least Significant Digit First String Radix Sort
    • 4. Most Significant Digit First String Radix Sort
    • 5. 3 Way Radix Quicksort
    • 6. Suffix Arrays
  • Radix Sort
  • Radix Sort (video)
  • Radix Sort, Counting Sort (linear time given constraints) (video)
  • Randomization: Matrix Multiply, Quicksort, Freivalds' algorithm (video)
  • Sorting in Linear Time (video)

Como resumen aquí esta una representación visual de 15 algoritmos de ordenamiento
Si necesita más detalle de este tema vea “Ordenamientos” en Detalles adicionales de ciertos temas

Gráficos

Los gráficos pueden ser usados para representar muchos problemas en las Ciencias de la Computación, así que es una sección larga, como lo son los árboles y ordenamientos.

• Notas:

  • Hay cuatro formas básicas de representar un grafo en memoria:
    • Objetos y apuntadores.
    • Matriz adyacente.
    • Lista adyacente.
    • Mapa adyacente.
  • Familiarícese con cada representación y sus pros y contras.
  • BFS and DFS – Conozca su complejidad computacional, sus compromisos y cómo implementarlos en código real.
  • Cuando se le haga una pregunta busqué una solución basada en grafos, si no encuentra continúe.

• Lecturas de Skiena – Gran introducción):

  • CSE373 2012 - Lecture 11 - Graph Data Structures (video)
  • CSE373 2012 - Lecture 12 - Breadth-First Search (video)
  • CSE373 2012 - Lecture 13 - Graph Algorithms (video)
  • CSE373 2012 - Lecture 14 - Graph Algorithms (con't) (video)
  • CSE373 2012 - Lecture 15 - Graph Algorithms (con't 2) (video)
  • CSE373 2012 - Lecture 16 - Graph Algorithms (con't 3) (video)

• Gráficos (revisión y más):

  • 6.006 Single-Source Shortest Paths Problem (video)
  • 6.006 Dijkstra (video)
  • 6.006 Bellman-Ford (video)
  • 6.006 Speeding Up Dijkstra (video)
  • Aduni: Graph Algorithms I - Topological Sorting, Minimum Spanning Trees, Prim's Algorithm - Lecture 6 (video)
  • Aduni: Graph Algorithms II - DFS, BFS, Kruskal's Algorithm, Union Find Data Structure - Lecture 7 (video)
  • Aduni: Graph Algorithms III: Shortest Path - Lecture 8 (video)
  • Aduni: Graph Alg. IV: Intro to geometric algorithms - Lecture 9 (video)
  • CS 61B 2014 (starting at 58:09) (video)
  • CS 61B 2014: Weighted graphs (video)
  • Greedy Algorithms: Minimum Spanning Tree (video)
  • Strongly Connected Components Kosaraju's Algorithm Graph Algorithm (video)

• Curso Completo de Coursera:

  • Algorithms on Graphs (video)

• Implementaré:

  • DFS con lista de adyacencia (recursión)
  • DFS con la lista de adyacencia (iterativa con la pila)
  • DFS con matriz de adyacencia (recursión)
  • DFS con matriz de adyacencia (iterativa con pila)
  • BFS con lista de adyacencia.
  • BFS con matriz de adyacencia.
  • Ruta de acceso de una sola fuente más corta (Dijkstra)
  • Árbol de expansión mínimo.
  • Algoritmos basados en DFS (ver videos de Aduni arriba):
    • Comprobar el ciclo (necesario para el tipo topológico, ya que vamos a comprobar el ciclo antes de comenzar)
    • Clasificación topológica.
    • Cuenta los componentes conectados en un grafo.
    • Lista de componentes fuertemente conectados.
    • Verificación de grafo bipartito.

||| Obtendrá más prácticas de gráficos en el libro de Skiena (vea Sección de libros debajo) y en los libros de entrevistas.

Más información adicional

• Recursión

  • Conferencias de Stanford sobre la recursividad y retroceso:
    • Lecture 8 | Programming Abstractions (video)
    • Lecture 9 | Programming Abstractions (video)
    • Lecture 10 | Programming Abstractions (video)
    • Lecture 11 | Programming Abstractions (video)
  • ¿Cuándo es apropiado usarlo?
  • ¿Qué es la recursión de cola? ¿Por qué es tan mala?
    • What Is Tail Recursion Why Is It So Bad?
    • Tail Recursion (video)

• Programación Dinámica

  • Este tema puede ser bastante difícil, ya que cada problema soluble PD debe definirse como una relación de recursión, y llegar a ella, puede ser complicado.
  • Sugiero que busque muchos ejemplos de problemas de PD hasta que tenga una comprensión sólida del patrón involucrado.
  • Videos:
    • Los videos de Skiena pueden ser duros de seguir ya que a veces usa el pizarrón, que es demasiado pequeño para verlo bien.
    • Skiena: CSE373 2012 - Lecture 19 - Introduction to Dynamic Programming (video)
    • Skiena: CSE373 2012 - Lecture 20 - Edit Distance (video)
    • Skiena: CSE373 2012 - Lecture 21 - Dynamic Programming Examples (video)
    • Skiena: CSE373 2012 - Lecture 22 - Applications of Dynamic Programming (video)
    • Simonson: Dynamic Programming 0 (starts at 59:18) (video)
    • Simonson: Dynamic Programming I - Lecture 11 (video)
    • Simonson: Dynamic programming II - Lecture 12 (video)
    • Lista de problemas individuales de PD (cada uno es corto):
      Dynamic Programming (video)
  • Notas de la clase de Yale:
    • Dynamic Programming
  • Coursera:
    • The RNA secondary structure problem (video)
    • A dynamic programming algorithm (video)
    • Illustrating the DP algorithm (video)
    • Running time of the DP algorithm (video)
    • DP vs. recursive implementation (video)
    • Global pairwise sequence alignment (video)
    • Local pairwise sequence alignment (video)

• Programación Orientada a Objetos

  • Optional: UML 2.0 Series (video)
  • Object-Oriented Software Engineering: Software Dev Using UML and Java (21 videos):
    • Puede omitir esto si tiene una gran comprensión de OO y OO prácticas de diseño.
    • OOSE: Software Dev Using UML and Java
  • Principios SOLID OOP:
    • Bob Martin SOLID Principles of Object Oriented and Agile Design (video)
    • SOLID Principles (video)
    • S - Single Responsibility Principle | Single responsibility to each Object
      • more flavor
    • O - Open/Closed Principal | On production level Objects are ready for extension but not for modification
      • more flavor
    • L - Liskov Substitution Principal | Base Class and Derived class follow ‘IS A’ principal
      • more flavor
    • I - Interface segregation principle | Los clientes no deberían ser forzados a implementar interfaces que no emplearán.
      • Interface Segregation Principle in 5 minutes (video)
      • more flavor
    • D -Dependency Inversion principle | Reducir la dependencia en la composición de los objetos.
      • Why Is The Dependency Inversion Principle And Why Is It Important
      • more flavor

• Patrones de diseño

  • Quick UML review (video)
  • Aprenda estos patrones:
    • strategy
    • singleton
    • adapter
    • prototype
    • decorator
    • visitor
    • factory, abstract factory
    • facade
    • observer
    • proxy
    • delegate
    • command
    • state
    • memento
    • iterator
    • composite
    • flyweight
  • Chapter 6 (Part 1) - Patterns (video)
  • Chapter 6 (Part 2) - Abstraction-Occurrence, General Hierarchy, Player-Role, Singleton, Observer, Delegation (video)
  • Chapter 6 (Part 3) - Adapter, Facade, Immutable, Read-Only Interface, Proxy (video)
  • Series of videos (27 videos)
  • Head First Design Patterns
    • Sé que el libro canónico es "Design Patterns: Elements of Reusable Object-Oriented Software", pero Head First es ideal para principiantes a OO.
  • Handy reference: 101 Design Patterns & Tips for Developers
  • Design patterns for humans

• Combinatorias (n elije k) & Probabilidad

  • Math Skills: How to find Factorial, Permutation and Combination (Choose) (video)
  • Make School: Probability (video)
  • Make School: More Probability and Markov Chains (video)
  • Khan Academy:
    • Diseño del curso:
      • Basic Theoretical Probability
    • Solo los videos - 41 (cada uno simple y corto):
      • Probability Explained (video)

• NP, NP-Completo y Algoritmos de aproximación

  • Conozca acerca de las clases más famosas de problemas de NP-completo, tales como el vendedor ambulante y el problema de la mochila, y sea capaz de reconocerlos cuando un entrevistador se los pide disfrazados.
  • Conozca que significa NP-completo.
  • Computational Complexity (video)
  • Simonson:
    • Greedy Algs. II & Intro to NP Completeness (video)
    • NP Completeness II & Reductions (video)
    • NP Completeness III (Video)
    • NP Completeness IV (video)
  • Skiena:
    • CSE373 2012 - Lecture 23 - Introduction to NP-Completeness (video)
    • CSE373 2012 - Lecture 24 - NP-Completeness Proofs (video)
    • CSE373 2012 - Lecture 25 - NP-Completeness Challenge (video)
  • Complexity: P, NP, NP-completeness, Reductions (video)
  • Complexity: Approximation Algorithms (video)
  • Complexity: Fixed-Parameter Algorithms (video)
  • Peter Norvig discute soluciones casi óptimas para el problema del vendedor ambulante:
    • Jupyter Notebook
  • Paginas 1048 - 1140 en CLRS si lo tiene.

• Memoria caché

  • LRU caché:
    • The Magic of LRU Cache (100 Days of Google Dev) (video)
    • Implementing LRU (video)
    • LeetCode - 146 LRU Cache (C++) (video)
  • CPU caché:
    • MIT 6.004 L15: The Memory Hierarchy (video)
    • MIT 6.004 L16: Cache Issues (video)

• Procesos e hilos

  • Computer Science 162 - Operating Systems (25 videos):
    • Para los procesos e hilos vea los videos 1-11.
    • Operating Systems and System Programming (video)
  • What Is The Difference Between A Process And A Thread?
  • Cubre:
    • Procesos, Hilos, Temas de Concurrencia.
      • Diferencia entre procesos e hilos.
      • Procesos.
      • Hilos.
      • Cerraduras.
      • Mutexes.
      • Semáforos.
      • Monitores.
      • Cómo trabajan ellos.
      • Bloqueo.
      • Livelock.
    • Actividad de CPU, interrupciones, conmutación de contexto.
    • Moderna concurrencia construida con procesadores multinúcleo.
    • Paging, segmentation and virtual memory (video)
    • Interrupts (video)
    • Scheduling (video)
    • Necesidades de recursos de proceso (memoria: código, almacenamiento estático, pila, monticulo y también descriptores de archivo, i /o)
    • Necesidades de recursos de hilos (partes anteriores (menos pila) con otros hilos en el mismo proceso, pero cada uno tiene su propio PC, contador de pila, registros y pila)
    • Bifurcación es realmente copia en escritura (sólo lectura) hasta que el nuevo proceso escribe en memoria, entonces hace una copia completa..
    • Cambio de contexto:
      • Cómo se inicia el cambio de contexto por el sistema operativo y el hardware subyacente.
  • threads in C++ (series - 10 videos)
  • concurrency in Python (videos):
    • Short series on threads
    • Python Threads
    • Understanding the Python GIL (2010)
      • reference
    • David Beazley - Python Concurrency From the Ground Up: LIVE! - PyCon 2015
    • Keynote David Beazley - Topics of Interest (Python Asyncio)
    • Mutex in Python