Liderar un problema de vida
Contenido eliminado Publicación traducida automáticamente Artículo escrito por rohanchopra96 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA
Categoría: Algorithms-Greedy Algorithms
Algoritmos | Algoritmos codiciosos | Pregunta 7
Supongamos que ejecutamos el algoritmo de ruta más corta de fuente única de Dijkstra en el siguiente gráfico dirigido ponderado por borde con el vértice P como fuente. ¿En qué orden se incluyen los Nodes en el conjunto de vértices para los cuales se finalizan las distancias de camino más cortas? (GATE CS 2004) (A) … Continue reading «Algoritmos | Algoritmos codiciosos | Pregunta 7»
Colocación de Sudo[1.3] | Jugando con pilas
Tiene 3 pilas, A (Pila de entrada), B (Pila auxiliar) y C (Pila de salida). Inicialmente, la pila A contiene números del 1 al N, debe transferir todos los números de la pila A a la pila C en orden ordenado, es decir, al final, la pila C debe tener el elemento más pequeño en … Continue reading «Colocación de Sudo[1.3] | Jugando con pilas»
Algoritmos | Algoritmos codiciosos | Pregunta 4
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»
Pasos mínimos en los que se puede obtener N sumando o restando en cada paso
Dado N, imprima la secuencia de un número mínimo de pasos en los que N se puede obtener a partir de 0 mediante la suma o resta del número de paso. Nota : en cada paso, podemos sumar o restar un número igual al número de paso de la posición actual. Por ejemplo, en el … Continue reading «Pasos mínimos en los que se puede obtener N sumando o restando en cada paso»
Algoritmos | Algoritmos codiciosos | Pregunta 5
¿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»
Compruebe si Array forma una secuencia creciente-decreciente o viceversa
Dada una array arr[] de N enteros, la tarea es encontrar si la array se puede dividir en 2 subarreglos, de modo que la primera subarreglo sea estrictamente creciente y la segunda sea estrictamente decreciente o viceversa. Si la array dada se puede dividir, imprima «Sí» , de lo contrario, imprima «No» . Ejemplos: Entrada: … Continue reading «Compruebe si Array forma una secuencia creciente-decreciente o viceversa»
Algoritmos | Algoritmos codiciosos | Pregunta 3
¿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»
Encuentre movimientos mínimos para traer todos los elementos en una celda de una array
Dada una array mat[][] , par de índices X e Y , la tarea es encontrar el número de movimientos para llevar todos los elementos distintos de cero de la array a la celda dada en (X, Y) . Un movimiento consiste en mover un elemento en cualquier celda a sus cuatro celdas direccionales adyacentes, … Continue reading «Encuentre movimientos mínimos para traer todos los elementos en una celda de una array»
Corte todas las varillas con cierta longitud de modo que la suma de la longitud de corte se maximice
Dadas N varillas de diferentes longitudes. La tarea es cortar todas las varillas con alguna altura entera máxima ‘h’ tal que la suma de las longitudes de corte de la varilla se maximice y debe ser mayor que M. Imprima -1 si no es posible tal corte. Nota: Una varilla no se puede cortar también. Ejemplos: Entrada: … Continue reading «Corte todas las varillas con cierta longitud de modo que la suma de la longitud de corte se maximice»