Dado N número de escaleras. También dado el número de pasos que se pueden dar como máximo de un salto (K). La tarea es encontrar el número de formas posibles en que uno ( solo considere las combinaciones ) puede subir a la parte superior del edificio en K saltos o menos desde la planta … Continue reading «Número de formas de llegar al piso N tomando como máximo K saltos»
Dados tres números enteros N , A y B , la tarea es calcular la probabilidad de que la suma de los números obtenidos al lanzar los dados exactamente N veces se encuentre entre A y B . Ejemplos: Entrada: N = 1, A = 2, B = 3 Salida: 0.333333 Explicación: Formas de obtener … Continue reading «Probabilidad de que la suma de todos los números obtenidos al lanzar un dado N veces esté entre dos enteros dados»
Dado un tetraedro (los vértices son A, B, C, D), la tarea es encontrar el número de caminos cíclicos diferentes con longitud n desde un vértice. Nota: Considerando un solo vértice B, es decir, encontrar el número de caminos cíclicos diferentes de longitud N desde B hacia sí mismo. Ejemplos: Input: 2 Output: 3 The … Continue reading «Número de caminos cíclicos diferentes de longitud N en un tetraedro»
Dado un árbol con un valor de N Nodes de 1 a N y (N – 1) aristas y un número K , la tarea es eliminar la cantidad mínima de Nodes del árbol de modo que cada subárbol tenga como máximo K Nodes. Eliminar Nodes eliminará los bordes de esos Nodes a todos los … Continue reading «Número mínimo de Nodes que se eliminarán de modo que ningún subárbol tenga más de K Nodes»
Los números de tetranacci son una generalización de los números de Fibonacci definidos por la relación de recurrencia T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4) con T(0)=0, T(1)=1, T(2 )=1, T(3)=2, Para n>=4. Representan el caso n=4 de los números de n pasos de Fibonacci. Los primeros términos para n=0, 1,… son 0, … Continue reading «Números Tetranacci»
Dado un Grafo Acíclico Dirigido con n vértices y m aristas. La tarea es encontrar el número de caminos diferentes que existen desde un vértice de origen hasta el vértice de destino. Ejemplos: Entrada: origen = 0, destino = 4 Salida: 3 Explicación: 0 -> 2 -> 3 -> 4 0 -> 3 -> 4 … Continue reading «Número de rutas desde el origen hasta el destino en un gráfico acíclico dirigido»
El algoritmo de Kadane se usa para encontrar: (A) Subsecuencia de suma máxima en una array (B) Subsecuencia de suma máxima en una array (C) Subsecuencia de producto máxima en una array (D) Subsecuencia de producto máxima en una array Respuesta: (B) Explicación: El algoritmo de Kadane se utiliza para encontrar el subarreglo de suma … Continue reading «Algoritmos | Programación Dinámica | Pregunta 4»
Dada una array de N enteros positivos, escriba una función eficiente para encontrar la suma de todos esos enteros que se pueden expresar como la suma de al menos un subconjunto de la array dada, es decir, calcule la suma total de cada subconjunto cuya suma es distinta usando solo O( suma) espacio adicional. Ejemplos: … Continue reading «Encuentre todas las sumas distintas de subconjuntos (o subsecuencias) de una array | Conjunto-2»
Dada una array de tamaño N*N llena de 1 y 0 , la tarea es encontrar la distancia máxima desde una celda 0 hasta su celda 1 más cercana. Si la array se llena solo con 0 o solo con 1, devuelve -1. Nota: Solo se permiten movimientos horizontales y verticales en la array. Ejemplos: … Continue reading «Máximo de todas las distancias a la celda 1 más cercana desde cualquier celda 0 en una array binaria»
Usamos el enfoque de programación dinámica cuando (A) Necesitamos una solución óptima (B) La solución tiene una subestructura óptima (C) El problema dado se puede reducir al problema 3-SAT (D) Es más rápido que Greedy Respuesta: (B) Explicación : https://www.geeksforgeeks.org/dynamic-programming-set-2-optimal-substructure-property/ La opción (D) es incorrecta porque los algoritmos Greedy son generalmente más rápidos que la … Continue reading «Algoritmos | Programación Dinámica | Pregunta 2»