Advanced Data Structure – Página 26

Diseñe eficientemente consultas de inserción, eliminación y mediana en un conjunto

julio 5, 2022 Rudeus Greyrat

Dado inicialmente un conjunto vacío y una serie de consultas sobre él, cada una posiblemente de los siguientes tipos: Insertar : inserta un nuevo elemento ‘x’. Eliminar : elimina un elemento existente ‘x’. Mediana : imprime el elemento mediano de los números actualmente en el conjunto Ejemplo: Input : Insert 1 Insert 4 Insert 7 … Continue reading «Diseñe eficientemente consultas de inserción, eliminación y mediana en un conjunto»

ACV para árbol n-ario | Consulta constante O(1)

julio 5, 2022 Rudeus Greyrat

Hemos visto varios métodos con diferentes complejidades de tiempo para calcular LCA en un árbol n-ario: Método 1: método ingenuo (mediante el cálculo de la ruta de la raíz al Node) | O(n) por consulta Método 2: uso de la descomposición Sqrt | O(sqrt H) Método 3: Uso del enfoque de DP de array dispersa … Continue reading «ACV para árbol n-ario | Consulta constante O(1)»

Imprima todas las palabras que coincidan con un patrón en CamelCase Notation Dictionary

julio 5, 2022 Rudeus Greyrat

Dado un diccionario de palabras donde cada palabra sigue la notación CamelCase, imprima todas las palabras en el diccionario que coincidan con un patrón dado que consiste solo en caracteres en mayúsculas. CamelCase es la práctica de escribir palabras compuestas o frases de modo que cada palabra o abreviatura comience con una letra mayúscula. Los … Continue reading «Imprima todas las palabras que coincidan con un patrón en CamelCase Notation Dictionary»

Eliminar operación en B-Tree

julio 5, 2022 Rudeus Greyrat

Se recomienda hacer referencia a las siguientes publicaciones como requisito previo para esta publicación. Árbol B | Juego 1 (Introducción) B-Tree | Conjunto 2 (Insertar) B-Tree es un tipo de árbol de búsqueda multidireccional. Por lo tanto, si no está familiarizado con los árboles de búsqueda multidireccional en general, es mejor que eche un vistazo … Continue reading «Eliminar operación en B-Tree»

Propagación diferida en el árbol de segmentos | conjunto 2

julio 5, 2022 Rudeus Greyrat

Dada una array arr[] de tamaño N . Hay dos tipos de operaciones: Actualizar (l, r, x): Incremente el a[i] (l <= i <= r) con el valor x. Query(l, r) : encuentre el valor máximo en la array en un rango de l a r (ambos están incluidos). Ejemplos: Entrada: arr[] = {1, 2, … Continue reading «Propagación diferida en el árbol de segmentos | conjunto 2»

Lista de autoorganización: método de mover al frente

julio 5, 2022 Rudeus Greyrat

La lista autoorganizada es una lista que se reorganiza o se reorganiza para un mejor rendimiento. En una lista simple, un elemento a buscar se busca de manera secuencial, lo que da la complejidad temporal de O(n). Pero en un escenario real, no todos los elementos se buscan con frecuencia y, la mayoría de las … Continue reading «Lista de autoorganización: método de mover al frente»

Consultas para encontrar el límite inferior de K de Prefix Sum Array con actualizaciones usando Fenwick Tree

julio 5, 2022 Rudeus Greyrat

Dada una array A[ ] que consta de enteros no negativos y una array Q[ ][ ] que consta de consultas de los siguientes dos tipos: (1, l, val): actualice A[l] a A[l] + val . (2, K): encuentre el límite inferior de K en la array de suma de prefijos de A[ ] . … Continue reading «Consultas para encontrar el límite inferior de K de Prefix Sum Array con actualizaciones usando Fenwick Tree»

Diseñe una estructura de datos de cola para obtener el mínimo o el máximo en tiempo O (1)

julio 5, 2022 Rudeus Greyrat

Problema: diseñe una estructura de datos, una SpecialQueue que admita las siguientes operaciones enque, deque, getMin() o getMax() donde la operación getMin() toma O(1) tiempo. Ejemplo: Let the data to be inserted in queue be – 4, 2, 1, 6 Operation Queue Output push(4) 4 – push(2) 4, 2 – push(1) 4, 2, 1 – … Continue reading «Diseñe una estructura de datos de cola para obtener el mínimo o el máximo en tiempo O (1)»

Compruebe si el Trie dado contiene palabras que comienzan con todos los alfabetos

julio 5, 2022 Rudeus Greyrat

Dado un Trie , la tarea es verificar si contiene palabras que comiencen con todos los alfabetos de [a – z] . Ejemplos: Entrada: teclas[] = {“elemento”, “niebla”, “genial”, “hola”, “ok”, “ios”, “loro”, “prueba”, “kim”, “mango”, “naturaleza” , “manzana”, “pelota”, “gato”, “perro”, “lima”, “ruby”, “brillo”, “tinkter”, “ultra”, “ volly”, “wow”, “xerox”, “ yak”, “zenon”, “broma”} … Continue reading «Compruebe si el Trie dado contiene palabras que comienzan con todos los alfabetos»

Imprimir strings en orden de diccionario inverso usando Trie

julio 5, 2022 Rudeus Greyrat

Trie es una estructura de datos de recuperación de información eficiente . Con Trie, las complejidades de búsqueda se pueden llevar a un límite óptimo. Dada una serie de strings . La tarea es imprimir todas las strings en el orden inverso del diccionario usando Trie . Si hay duplicados en la array de entrada, debemos … Continue reading «Imprimir strings en orden de diccionario inverso usando Trie»