Categoría: Trie

Encuentre la última URL única de una larga lista de URL en un solo recorrido

Posted on by Rudeus Greyrat

Dada una lista muy larga de URL, averigüe la última URL única. Solo se permite un recorrido de todas las URL. Ejemplos: Input: https://www.geeksforgeeks.org https://www.geeksforgeeks.org/quiz-corner-gq/ http://qa.geeksforgeeks.org https://practice.geeksforgeeks.org https://ide.geeksforgeeks.org https://write.geeksforgeeks.org https://www.geeksforgeeks.org/quiz-corner-gq/ https://practice.geeksforgeeks.org https://ide.geeksforgeeks.org https://www.geeksforgeeks.org/quiz-corner-gq/ http://qa.geeksforgeeks.org https://practice.geeksforgeeks.org Output: https://write.geeksforgeeks.org Podemos resolver este problema en un recorrido utilizando Triecon una Lista Doblemente Vinculada (Podemos insertar y borrar en … Continue reading «Encuentre la última URL única de una larga lista de URL en un solo recorrido»

Ordene una array de strings según la frecuencia de buenas palabras en ellas

Posted on by Rudeus Greyrat

Dado un conjunto de reseñas de productos ( R ) de diferentes clientes y una string S que contiene buenas palabras separadas por un _ , la tarea es ordenar las reseñas en orden decreciente de su valor de bondad. El valor de bondad se define por el número de buenas palabras presentes en esa … Continue reading «Ordene una array de strings según la frecuencia de buenas palabras en ellas»

Contar inversiones en una array | Conjunto 4 (Usando Trie)

Posted on by Rudeus Greyrat

El conteo de inversión para una array indica qué tan lejos (o cerca) está la array de ser ordenada. Si la array ya está ordenada, el recuento de inversión es 0. Si la array está ordenada en orden inverso, el recuento de inversión es el máximo.  Dos elementos a[i] y a[j] forman una inversión si … Continue reading «Contar inversiones en una array | Conjunto 4 (Usando Trie)»

Encuentra filas duplicadas en una array binaria

Posted on by Rudeus Greyrat

Dada una array binaria cuyos elementos son solo 0 y 1, necesitamos imprimir las filas que son duplicados de las filas que ya están presentes en la array. Ejemplos:  Input : {1, 1, 0, 1, 0, 1}, {0, 0, 1, 0, 0, 1}, {1, 0, 1, 1, 0, 0}, {1, 1, 0, 1, 0, 1}, … Continue reading «Encuentra filas duplicadas en una array binaria»

Experiencia de entrevista OLA | conjunto 12

Posted on by Rudeus Greyrat

Ronda 1:  Ronda de codificación en línea de Hackerearth.  Ronda 2: (1 h 15 min)  Vista izquierda de un árbol binario  Explicar la búsqueda binaria y su complejidad.  ¿Cómo funciona un mapa hash? ¿Cuál es la diferencia entre un mapa hash y una array?  Dado un gráfico acíclico y una función f(x) que devuelven el … Continue reading «Experiencia de entrevista OLA | conjunto 12»

Implementar un Directorio Telefónico

Posted on by Rudeus Greyrat

Dada una lista de contactos que existen en un directorio telefónico. La tarea es implementar la consulta de búsqueda para el directorio telefónico. La consulta de búsqueda en una string ‘ str ‘ muestra todos los contactos que tienen el prefijo ‘ str ‘. Una propiedad especial de la función de búsqueda es que, cuando … Continue reading «Implementar un Directorio Telefónico»

String más larga en una array que coincide con el prefijo de la string dada

Posted on by Rudeus Greyrat

Dada una array de strings arr[] y consultas Q donde cada consulta consta de una string str , la tarea es encontrar la string más larga en la array que coincida con el prefijo de la string dada str , es decir, la string debe ser el prefijo de str . Ejemplos: Entrada: arr[] = … Continue reading «String más larga en una array que coincide con el prefijo de la string dada»

Strings de una array que no son prefijos de ninguna otra string

Posted on by Rudeus Greyrat

Dada una array arr[] de strings, la tarea es imprimir las strings de la array que no son prefijos de ninguna otra string de la misma array. Ejemplos:   Entrada: arr[] = {“apple”, “app”, “there”, “the”, “like”}  Salida:  apple  like  there  Aquí “app” es un prefijo de “apple”  Por lo tanto, no se imprime y  “the” … Continue reading «Strings de una array que no son prefijos de ninguna otra string»

Intentos comprimidos

Posted on by Rudeus Greyrat

Un trie es una estructura de datos que almacena strings como una estructura de datos de árbol . El número máximo de hijos en un Node es igual al tamaño del alfabeto. Uno puede imprimir fácilmente letras en orden alfabético, lo que no es posible con hash . Propiedades de Trie : Es un árbol … Continue reading «Intentos comprimidos»

Búsqueda de patrones utilizando un Trie de todos los sufijos

Posted on by Rudeus Greyrat

Declaración del problema: dado un texto txt[0..n-1] y un patrón pat[0..m-1], escriba una función de búsqueda (char pat[], char txt[]) que imprima todas las apariciones de pat[ ] en texto[]. Puede suponer que n > m. Como se discutió en la publicación anterior , discutimos que hay dos formas de resolver de manera eficiente el … Continue reading «Búsqueda de patrones utilizando un Trie de todos los sufijos»