Dado un árbol de búsqueda binario, encuentre la mediana de él. Si no. de Nodes son pares: entonces mediana = ((n/2º Node + ((n)/2º+1) Node) /2 Si el número de Nodes es impar: entonces mediana = (n+1)/2º Node. Por ejemplo , la mediana de debajo de BST es 12. Más ejemplos: Given BST(with odd no. of … Continue reading «Encuentre la mediana de BST en tiempo O (n) y espacio O (1)»
Dada una array ordenada de tamaño n*n . Calcular la media y la mediana de la array. Ejemplos: Input : 1 2 3 4 5 6 7 8 9 Output :Mean: 5 Median: 5 Input : 1 1 1 2 2 2 4 4 4 Output :Mean: 2 Median: 2 Mean of matrix is = … Continue reading «Media y mediana de una array»
Dada una secuencia infinita de números enteros, encuentre el k-ésimo elemento más grande en cualquier punto del tiempo. Ejemplo: Input: stream[] = {10, 20, 11, 70, 50, 40, 100, 5, …} k = 3 Output: {_, _, 10, 11, 20, 40, 50, 50, …} El espacio extra permitido es O(k). Hemos discutido diferentes enfoques para … Continue reading «Programa Java para encontrar el elemento K’th más grande en una secuencia»
Dada una array de enteros. Escriba un programa para encontrar la K-ésima suma más grande de subarreglo contiguo dentro del arreglo de números que tiene números negativos y positivos. Ejemplos: Input: a[] = {20, -5, -1} k = 3 Output: 14 Explanation: All sum of contiguous subarrays are (20, 15, 14, -5, -6, -1) so … Continue reading «K-ésimo subarreglo contiguo de suma más grande»
Nos dan una array de tamaño n que contiene números enteros positivos. La diferencia absoluta entre los valores de los índices i y j es |a[i] – a[j]|. Hay n*(n-1)/2 de tales pares y se nos pide imprimir el k-ésimo (1 <= k <= n*(n-1)/2) como la diferencia absoluta más pequeña entre todos estos pares. … Continue reading «k-ésima diferencia absoluta más pequeña de dos elementos en una array»
Dado un árbol de búsqueda binaria, la tarea es encontrar el K-ésimo elemento más grande en el árbol de búsqueda binaria. Ejemplo: Input : k = 3 Root of following BST 10 / \ 4 20 / / \ 2 15 40 Output : 15 La idea es utilizar Reverse Morris Traversal , que se basa … Continue reading «K’th Elemento más grande en BST usando espacio adicional constante»
Dada una array de enteros con rango limitado (0 a 1000000). Necesitamos implementar un árbol de estadísticas de pedidos usando el árbol fenwick. Debe soportar cuatro operaciones: Insertar, Eliminar, Seleccionar y Clasificar. Aquí n denota el tamaño del árbol de Fenwick y q denota el número de consultas. Cada consulta debe ser una de las siguientes … Continue reading «Ordene el árbol estadístico usando el árbol fenwick (BIT)»
Dadas dos arrays de enteros arr1[] y arr2[] ordenadas en orden ascendente y un entero k. Encuentre k pares con las sumas más pequeñas tales que un elemento de un par pertenezca a arr1[] y otro elemento pertenezca a arr2[] Ejemplos: Input : arr1[] = {1, 7, 11} arr2[] = {2, 4, 6} k = … Continue reading «Programa C++ para encontrar k pares con sumas más pequeñas en dos arrays»
Recomendamos leer las siguientes publicaciones como requisito previo para esta publicación. K’th elemento más pequeño/más grande en array no ordenada | Establecer 1 k’ésimo elemento más pequeño/más grande en array sin clasificar | Conjunto 2 (Tiempo lineal esperado) Dada una array y un número k donde k es más pequeño que el tamaño de la … Continue reading «K’th elemento más pequeño/más grande en array no ordenada | Conjunto 3 (Tiempo lineal en el peor de los casos)»
Dada una array de enteros y un valor entero k, encuentre k sub-arrays no superpuestas que tengan k sumas máximas. Ejemplos: Input : arr1[] = {4, 1, 1, -1, -3, -5, 6, 2, -6, -2}, k = 3. Output : Maximum non-overlapping sub-array sum1: 8, starting index: 6, ending index: 7. Maximum non-overlapping sub-array sum2: … Continue reading «K sumas máximas de subarreglos contiguos que no se superponen»