Categoría: Greedy Algorithms

Encuentre los cambios mínimos requeridos en una array para que contenga k elementos distintos

Posted on by Rudeus Greyrat

Dada una array arr de tamaño N y un número K . La tarea es encontrar los elementos mínimos que se reemplazarán en la array con cualquier número tal que la array se componga de K elementos distintos. Nota: la array puede consistir en elementos repetidos. Ejemplos:   Entrada: arr[]={1, 2, 2, 8}, k = 1  Salida: … Continue reading «Encuentre los cambios mínimos requeridos en una array para que contenga k elementos distintos»

Algoritmos | Algoritmos codiciosos | Pregunta 4

Posted on by Rudeus Greyrat

En la pregunta #2, ¿cuál de las siguientes representa la palabra “muerto” ? (A) 1011111100101 (B) 0100000011010 (C) Tanto A como B (D) Ninguno de estos Respuesta: (C) Explicación: El árbol de Huffman generado es: character code-word f 0 c 100 d 101 a 1100 b 1101 e 111 La palabra muerto se puede representar … Continue reading «Algoritmos | Algoritmos codiciosos | Pregunta 4»

Suma de la diferencia mínima entre elementos consecutivos de una array

Posted on by Rudeus Greyrat

Dada una array de pares donde cada par representa un rango, la tarea es encontrar la suma de la diferencia mínima entre los elementos consecutivos de una array donde la array se llena de la siguiente manera:  Cada elemento de una array se encuentra en el rango dado en su índice correspondiente en la array … Continue reading «Suma de la diferencia mínima entre elementos consecutivos de una array»

Ruta de costo mínimo desde el Node de origen hasta el Node de destino a través de un Node intermedio

Posted on by Rudeus Greyrat

Dado un gráfico ponderado no dirigido. La tarea es encontrar el costo mínimo de la ruta desde el Node de origen hasta el Node de destino a través de un Node intermedio. Nota: Si un borde se recorre dos veces, solo una vez se calcula el peso como costo.   Ejemplos:   Entrada: origen = 0, destino = … Continue reading «Ruta de costo mínimo desde el Node de origen hasta el Node de destino a través de un Node intermedio»

String lexicográficamente más pequeña formada al agregar un carácter de los primeros K caracteres de una string dada

Posted on by Rudeus Greyrat

Dada una string S que consta de alfabetos en minúsculas. La tarea es encontrar la string X lexicográficamente más pequeña de la misma longitud que se pueda formar utilizando la operación que se indica a continuación: En una sola operación, seleccione cualquier carácter entre los primeros K caracteres de la string S como máximo, elimínelo … Continue reading «String lexicográficamente más pequeña formada al agregar un carácter de los primeros K caracteres de una string dada»

Algoritmos | Algoritmos codiciosos | Pregunta 5

Posted on by Rudeus Greyrat

¿Cuál de los siguientes es cierto acerca de los algoritmos Kruskal y Prim MST? Suponga que Prim se implementa para la representación de listas de adyacencia mediante Binary Heap y Kruskal se implementa mediante unión por rango. (A) En el peor de los casos, la complejidad temporal de ambos algoritmos es la misma. (B) En … Continue reading «Algoritmos | Algoritmos codiciosos | Pregunta 5»

Número máximo de unos en una array N*N con restricciones dadas

Posted on by Rudeus Greyrat

Dados dos enteros  y  , donde  . Encuentre el número máximo de unos en una  array binaria que puede tener tal que cada subarray de tamaño  tenga al menos una celda como cero. Ejemplos:  Input:5 3 Output: Maximum number of ones = 24 The matrix will be: 1 1 1 1 1 1 1 1 … Continue reading «Número máximo de unos en una array N*N con restricciones dadas»

Factor de inversión mínimo en una array

Posted on by Rudeus Greyrat

Dada una array de n enteros positivos, la tarea es encontrar el factor inversor mínimo en la array dada. El factor de inversión se define como la diferencia absoluta entre el reverso de dos números arr i y arr j donde i != j. Nota : los ceros finales deben ignorarse al invertir los dígitos, es decir, … Continue reading «Factor de inversión mínimo en una array»

Minimizar los pasos necesarios para alcanzar el valor N

Posted on by Rudeus Greyrat

Dada una recta numérica infinita del rango [-INFINITY, +INFINITY] y un número entero N , la tarea es encontrar el recuento mínimo de movimientos necesarios para llegar a N , comenzando desde 0 , ya sea moviendo i pasos hacia adelante o 1 pasos hacia atrás en cada i -ésimo movimiento. Ejemplos: Entrada: N = … Continue reading «Minimizar los pasos necesarios para alcanzar el valor N»

Algoritmos | Algoritmos codiciosos | Pregunta 3

Posted on by Rudeus Greyrat

¿Cuál es la complejidad temporal de la codificación Huffman? (A) O(N) (B) O(NlogN) (C) O(N(logN)^2) (D) O(N^2) Respuesta: (B) Explicación: O(nlogn) donde n es el número de caracteres únicos. Si hay n Nodes, extractMin() se llama 2*(n – 1) veces. extractMin() toma el tiempo O(logn) ya que llama minHeapify(). Entonces, la complejidad general es O … Continue reading «Algoritmos | Algoritmos codiciosos | Pregunta 3»