Un montón mínimo es un árbol binario completo en el que los Nodes secundarios tienen un valor más alto (menor prioridad) que los Nodes principales, es decir, cualquier ruta desde la raíz hasta los Nodes hoja tiene un orden ascendente de elementos. En el caso de un árbol binario, se considera que la raíz está … Continue reading «Análisis de complejidad de varias operaciones de Binary Min Heap»
Prerrequisito: Análisis de Algoritmos 1. ¿Cuál es la complejidad de tiempo y espacio del siguiente código: CPP int a = 0, b = 0; for (i = 0; i < N; i++) { a = a + rand(); } for (j = 0; j < M; j++) { b = b + rand(); } Python … Continue reading «Preguntas de práctica sobre el análisis de la complejidad del tiempo»
Dado un arreglo arr[] de N enteros, la tarea es encontrar el subarreglo de longitud máxima que contiene elementos similares. Ejemplos: Entrada: arr[] = {1, 2, 3, 4, 5, 5, 5, 5, 5, 2, 2, 1, 1} Salida: 5 Explicación: El subarreglo {5, 5, 5, 5, 5 } tiene una longitud máxima de 5 con … Continue reading «Longitud máxima del subarreglo tal que todos los elementos sean iguales en el subarreglo»
Dada una array arr que contiene enteros positivos, la tarea es verificar si la array arr dada es una concatenación de dos permutaciones o no. Una secuencia de M enteros se llama permutación si contiene todos los enteros del 1 al M exactamente una vez. Ejemplos: Entrada: arr[] = {1, 2, 5, 3, 4, 1, 1} … Continue reading «Comprobar si una Secuencia es una concatenación de dos permutaciones»
Considere a continuación dos funciones del lenguaje C para calcular la suma de elementos en una array 2D. Ignorando las optimizaciones del compilador, ¿cuál de las dos es una mejor implementación de sum? // Function 1 int fun1(int arr[R][C]) { int sum = 0; for (int i=0; i<R; i++) for (int j=0; j<C; j++) sum … Continue reading «Rendimiento de bucles (una pregunta de almacenamiento en caché)»
Dadas dos monedas que tienen probabilidad de obtener cara p% y q% respectivamente, la tarea es determinar la probabilidad de obtener dos caras consecutivas después de elegir monedas al azar entre las monedas dadas. Ejemplos: Entrada: p = 33, q = 66 Salida: 0,550000000000000 Entrada: p = 33, q = 66 Salida: 0,5500000000000000 Enfoque: dado … Continue reading «Probabilidad de obtener dos caras consecutivas al elegir una moneda al azar entre dos tipos de monedas diferentes»
Dada una array arr[] de N elementos, debe realizar la siguiente operación en la array dada hasta que la array se reduzca a un solo elemento, Elige dos índices i y j tales que i != j . Reemplace arr[i] con arr[i] – arr[j] y elimine arr[j] de la array. La tarea es maximizar e … Continue reading «Encuentre el valor máximo del último elemento después de reducir la array con operaciones dadas»
Dados n, m, A y B. La tarea es contar el número de pares de enteros (x, y) tales que 1 x n y 1 y m y (x+y) mod A y (x+y) mod B ambos son iguales a 0. Ejemplos: Input: n = 60, m = 90, A = 5, B = 10 Output: … Continue reading «Cuente los pares (i,j) tales que (i+j) sea divisible por A y B ambos»
Dado un número entero N , la tarea es contar todas las secuencias posibles de longitud N de modo que todos los elementos de la secuencia sean del rango [1, N] y la suma de los elementos de la secuencia sea par. Como la respuesta podría ser muy grande, imprima la respuesta módulo 10 9 … Continue reading «Cuente el número total de secuencias de sumas pares»
1. Complejidad computacional: Complejidad computacional, una medida de la cantidad de recursos informáticos (tiempo y espacio) que consume un algoritmo en particular cuando se ejecuta. La complejidad temporal de una máquina de Turing viene dada por la función T(n), donde T(n) = Número máximo de movimientos realizados por la TM para procesar una … Continue reading «Complejidad Computacional v/s Jerarquía de Chomsky»