Preguntas frecuentes de entrevistas sobre algoritmos | Serie 1

¿Qué es un algoritmo?  
Informalmente, un algoritmo es cualquier procedimiento computacional bien definido que toma algún valor, o conjunto de valores, como entrada y produce algún valor, o conjunto de valores, como salida. Un algoritmo es, por lo tanto, una secuencia de pasos computacionales que transforman la entrada en la salida. (Fuente: Introducción a los Algoritmos 3ra Edición por CLRS ) 

¿Cuál es la complejidad temporal de la búsqueda binaria?  
La complejidad temporal de la búsqueda binaria es O (Log). Consulte Búsqueda binaria para obtener más detalles. 

¿Se puede utilizar la búsqueda binaria para listas enlazadas?  
Dado que el acceso aleatorio no está permitido en una lista enlazada, no podemos alcanzar el elemento central en el tiempo O(1). Por lo tanto, la búsqueda binaria no es posible para listas enlazadas. Sin embargo, hay otras formas, consulte Saltar lista, por ejemplo. 

¿Cómo encontrar si dos rectángulos dados se superponen?  
Dos rectángulos no se superponen si se cumple una de las siguientes condiciones. 
1) Un rectángulo está por encima del borde superior de otro rectángulo. 
2) Un rectángulo está en el lado izquierdo del borde izquierdo de otro rectángulo. 
Consulte Buscar si dos rectángulos se superponen para obtener más detalles. 

¿Cómo encontrar el ángulo entre las manecillas de horas y minutos en un momento dado?  
La idea es tomar un punto de referencia como 12. Encuentra el ángulo que mueven las manecillas de horas y minutos, resta los dos ángulos para encontrar el ángulo entre ellos. Consulte el ángulo entre la manecilla de la hora y la manecilla de los minutos para obtener más detalles. 

¿Cuándo ocurre el peor caso de QuickSort?  
En QuickSort , seleccionamos un elemento pivote, luego dividimos la array dada alrededor del elemento pivote colocando el elemento pivote en su posición correcta en una array ordenada. 
El peor caso de clasificación rápida ocurre cuando una parte después de la partición contiene todos los elementos y la otra parte está vacía. Por ejemplo, si se ordena la array de entrada y se elige el último o el primer elemento como pivote, ocurre lo peor. Consulte https://www.geeksforgeeks.org/quick-sort/ para obtener más detalles. 

Una array ordenada se rota en algún punto desconocido, cómo buscar eficientemente un elemento en ella. 
Un enfoque simple es usar la búsqueda lineal, pero podemos buscar en el tiempo O (Logn) usando la búsqueda binaria . Consulte Buscar un elemento en una array ordenada y dinámica para obtener más detalles. 
Otras variaciones de este problema, como encontrar el elemento mínimo o el elemento máximo en una array ordenada y rotada . 

Dada una gran string de caracteres, ¿cómo encontrar de manera eficiente el primer carácter único en ella?  
La solución eficiente es usar el carácter como índice en una array de conteo. Recorre la string dada y almacena el índice de la primera ocurrencia de cada carácter, también almacena el recuento de ocurrencias. Luego recorra la array de conteo y encuentre el índice más pequeño con conteo como 1. Vea encontrar el primer carácter único para obtener más detalles. 

¿Cómo contar las inversiones en una array ordenada?  
Dos elementos arr[i] y arr[j] en un arreglo arr[] forman una inversión si a[i] > a[j] e i < j. Cómo contar todas las inversiones en una array no ordenada. Consulte Contar inversiones en una array para conocer todos los enfoques. 

Dada una array grande, ¿cómo encontrar de manera eficiente el k-ésimo elemento más grande en ella?  
Puede haber muchas soluciones para esto. La mejor solución es usar el montón mínimo. Construimos un Min Heap MH de los primeros k elementos. Para cada elemento, después del k-ésimo elemento (arr[k] a arr[n-1]), compárelo con la raíz de MH, si el elemento es mayor que la raíz, entonces conviértalo en raíz y llame a heapify para MH, de lo contrario, ignore eso. Finalmente, MH tiene k elementos más grandes y la raíz de MH es el k-ésimo elemento más grande. Consulte k elementos más grandes (o más pequeños) para obtener más detalles. 

Dada una array de tamaño n con un rango de números de 1 a n+1. La array no contiene ningún duplicado, falta un número, busque el número que falta.  
Puede haber muchas formas de solucionarlo. El mejor entre es usar XOR. Consulte Buscar el número que falta para obtener más información. Hay muchas variaciones de este problema, como encontrar los dos números que se repiten , encontrar un número que falta y uno que se repite , etc. 

¿ Cómo escribir un método eficiente para calcular x elevado a la potencia n?  
La idea es usar divide y vencerás aquí para hacerlo en tiempo O (Iniciar sesión). Consulte Escribir un programa en C para calcular pow(x,n) para obtener más detalles. 

Dada una string de entrada y un diccionario de palabras, averigüe si la string de entrada se puede segmentar en una secuencia de palabras del diccionario separadas por espacios.  
La idea es usar Programación Dinámica. Consulte Problema de división de palabras para obtener más detalles. 

Dada una fila de n monedas de valores v1. . . vn, donde n es par. Jugamos un juego contra un oponente alternando turnos. En cada turno, un jugador selecciona la primera o la última moneda de la fila, la retira de la fila de forma permanente y recibe el valor de la moneda. Determine la máxima cantidad posible de dinero que definitivamente podemos ganar si nos movemos primero.  
Esta también es una pregunta de programación dinámica. Consulte Estrategia óptima para un juego para obtener más detalles. 

Se le proporciona una array de palabras ordenadas en un idioma arbitrario, debe encontrar el orden (o la precedencia de los caracteres) en el idioma. Por ejemplo, si las arrays dadas son {“baa”, “abcd”, “abca”, “cab”, “cad”}, entonces el orden de los caracteres es ‘b’, ‘d’, ‘a’, ‘c’. Tenga en cuenta que las palabras están ordenadas y en el idioma dado «baa» viene antes de «abcd», por lo tanto, ‘b’ está antes de ‘a’ en la salida. Del mismo modo, podemos encontrar otros pedidos. 
Esto se puede resolver usando dos pasos: primero cree un gráfico procesando un conjunto dado de palabras, luego haga una clasificación topológica del gráfico creado. Consulte esto para obtener más detalles. 

También te puede interesar 
 

• Preguntas de entrevista de estructura de datos más frecuentes | Serie 1 
   
• Cuestionarios de práctica sobre varios temas de algoritmos
• Notas de última hora – Algo

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.