Los algoritmos son el conjunto de reglas a seguir en los cálculos u otras operaciones de resolución de problemas. Se considera uno de los temas más importantes considerados desde el aspecto de la programación. Además, uno de los temas más complejos pero interesantes. Desde el aspecto de la entrevista, si desea descifrar una entrevista de codificación, debe tener un fuerte dominio sobre Algoritmos y Estructuras de datos. En este artículo, leeremos sobre algunos de los algoritmos más importantes que lo ayudarán a descifrar entrevistas de codificación.
Hay muchos algoritmos importantes de los cuales algunos de ellos se mencionan a continuación:
- Algoritmos de clasificación
- Algoritmos de búsqueda
- Algoritmos de cadenas
- Divide y conquistaras
- retrocediendo
- Algoritmos codiciosos
- Programación dinámica
- Algo relacionado con árboles
- Algoritmos gráficos
- Otros algoritmos importantes
1. Algoritmos de clasificación
Los algoritmos de clasificación se utilizan para organizar los datos en un orden específico y utilizar los mismos datos para obtener la información requerida. Estos son algunos de los algoritmos de clasificación que son mejores con respecto al tiempo necesario para clasificar los datos.
A. Clasificación de burbujas
La clasificación de burbuja es el algoritmo de clasificación de intercambio más básico. Sigue intercambiando todos los pares adyacentes que no están en el orden correcto. El algoritmo de clasificación de burbujas, al comparar todos los pares adyacentes, toma O(N2) tiempo.
Ordenamiento de burbuja es un algoritmo de clasificación estable. También tiene espacio O(1) para ordenar. En todos los casos (Mejor, Promedio, Peor caso), Su la complejidad del tiempo es O(N2). Bubble type no es un algoritmo muy eficiente para grandes conjuntos de datos.
B. Clasificación por inserción
Como su nombre indica, es un algoritmo de inserción. Se elige un elemento y se inserta en su posición correcta en una matriz. Es tan easy como clasificar naipes. La ordenación por inserción es eficiente para conjuntos de datos pequeños. generalmente toma EN2) tiempo. Pero cuando se clasifican los elementos, se necesita A tiempo.
C. Clasificación de selección
En clasificación de selección, mantenemos dos partes de la matriz, una parte ordenada y otra parte sin ordenar. Seleccionamos el elemento más pequeño (si consideramos el orden ascendente) de la parte no ordenada y lo colocamos al comienzo de esta matriz no ordenada, y seguimos haciendo esto y así obtenemos la matriz ordenada. La complejidad temporal del ordenamiento por selección es EN2).
D. Clasificación por fusión
Merge type es un algoritmo de clasificación basado en divide y vencerás. Este algoritmo sigue dividiendo la matriz en dos mitades hasta que hacemos que todos los elementos sean independientes, y luego comienza a fusionar los elementos en orden ordenado. Todo este proceso lleva O (iniciar sesión) tiempo, O(registro2(n)) tiempo para dividir la matriz, y En) tiempo para fusionarse de nuevo.
Ordenar por fusión es un algoritmo de clasificación estable. También ocupa espacio O(n) para la clasificación. En todos los casos (Greatest, Common, Worst case), su complejidad temporal es O (iniciar sesión). La ordenación por combinación es un algoritmo muy eficiente para grandes conjuntos de datos, pero para conjuntos de datos más pequeños, es un poco más lento en comparación con la ordenación por inserción.
E. Clasificación rápida
Al igual que Merge Type, Fast type también se basa en el algoritmo divide y vencerás. En ordenación rápida, elegimos un elemento pivote y dividimos la matriz en dos partes tomando el elemento pivote como punto de división.
La complejidad temporal de Ordenación rápida es O(nlogn) excepto en el peor de los casos, que puede ser tan malo como O(n2). Para mejorar su complejidad temporal en el peor de los casos, utilizamos Algoritmo de clasificación rápida aleatoria. En el cual, elegimos el elemento pivote como un índice aleatorio.
2. Algoritmos de búsqueda
A. Búsqueda lineal
Búsqueda lineal es un método ingenuo de búsqueda. Comienza desde el principio y sigue buscando hasta que llega al closing. Toma O(n) tiempo. Este es un método muy importante para buscar algo en datos no ordenados.
B. Búsqueda binaria
La búsqueda binaria es uno de los algoritmos de búsqueda más eficientes. Funciona solo en datos ordenados. se ejecuta en O(registro2(n)) tiempo. Divide repetidamente los datos en dos mitades y busca en cualquier parte según las condiciones.
Búsqueda binaria se puede implementar utilizando tanto el método iterativo como el método recursivo.
Enfoque iterativo:
binarySearch(arr, x, low, excessive)
repeat until low = excessive
mid = (low + excessive)/2
if (x == arr(mid))
return mid
else if (x > arr(mid)) // x is on the appropriate aspect
low = mid + 1
else // x is on the left aspect
excessive = mid - 1
Enfoque recursivo:
binarySearch(arr, x, low, excessive)
if low > excessive
return False
else
mid = (low + excessive) / 2
if x == arr(mid)
return mid
else if x > arr(mid) // x is on the appropriate aspect
return binarySearch(arr, x, mid + 1, excessive) // recall with the appropriate half solely
else // x is on the left aspect
return binarySearch(arr, x, low, mid - 1) // recall with the left half solely
3. Algoritmo de cadena
A. Algoritmo de Rabin Karp
El Algoritmo de Rabin-Karp es uno de los algoritmos más solicitados en la codificación de entrevistas en cadenas. Este algoritmo nos ayuda de manera eficiente a encontrar las ocurrencias de alguna subcadena en una cadena. Supongamos que nos dan una cadena S y tenemos que averiguar el número de ocurrencias de una subcadena S1 en S, podemos hacer esto usando el Algoritmo de Rabin Karp. Complejidad temporal de Rabin Karp en la que la complejidad media es O(m+n) y la complejidad del peor de los casos es O(nm). Donde n es la longitud de la cadena S y m es la longitud de la cadena S1.
B. Algoritmo Z
El algoritmo Z es incluso mejor que el algoritmo Rabin Karp. Esto también ayuda a encontrar el número de ocurrencias de una subcadena en una cadena dada pero en tiempo lineal O(m+n) en todos los casos (mejor, promedio y peor). En este algoritmo, construimos una matriz Z que contiene un valor Z para cada carácter de la cadena. La complejidad temporal media de la algoritmo Z es O(n+m) y la complejidad espacial media también es O(n+m). Donde n es la longitud de la cadena S y m es la longitud de la cadena S1.
4. Divide y vencerás
Como su propio nombre sugiere, primero se divide en subproblemas más pequeños, luego estos subproblemas se resuelven y luego estos problemas se combinan para obtener la solución closing. Hay tantos algoritmos importantes que funcionan en el Divide y conquistaras estrategia.
Algunos ejemplos de algoritmos Divide and Conquer son los siguientes:
5. Retroceder
retrocediendo es una variación de la recursividad. Al retroceder, resolvemos el subproblema con algunos cambios uno a la vez y eliminamos ese cambio después de calcular la solución del problema a este subproblema. Se necesitan todas las combinaciones posibles de problemas para resolverlos.
Hay algunas preguntas estándar sobre el retroceso como se menciona a continuación:
6. Algoritmo codicioso
A algoritmo codicioso es un método para resolver problemas con la opción más óptima disponible. Se utiliza en situaciones en las que se requiere optimización, es decir, donde se requiere la maximización o la minimización.
Algunos de los problemas más comunes con los algoritmos codiciosos son los siguientes:
7. Programación dinámica
Programación dinámica es uno de los algoritmos más importantes que se solicita en la codificación de entrevistas. La programación dinámica funciona en recursividad. Es una optimización de la recursividad. La programación dinámica se puede aplicar a todos esos problemas, donde tenemos que resolver un problema usando sus subproblemas. Y la solución closing se deriva de las soluciones de subproblemas más pequeños. Básicamente almacena soluciones de subproblemas y simplemente usa el resultado almacenado donde sea necesario, a pesar de calcular lo mismo una y otra vez.
Algunas de las preguntas más importantes basadas en la programación dinámica son las siguientes:
8. Algoritmos de recorridos de árboles
Principalmente, hay tres tipos de el recorrido algoritmos:
A. Recorrido en orden
- Atraviesa el subárbol izquierdo, luego
- El nodo raíz transversal, entonces
- Subárbol derecho poligonal
B. Recorrido de pedidos anticipados
- El nodo raíz transversal, entonces
- Atraviesa el nodo izquierdo, luego
- Subárbol derecho poligonal
C. Recorrido posterior a la orden
- Atraviesa el subárbol izquierdo, luego
- Atraviesa el subárbol derecho, luego
- Nodo raíz transversal
9. Algoritmos basados en gráficos
A. Búsqueda primero en amplitud (BFS)
Búsqueda primero en amplitud (BFS) se utiliza para recorrer gráficos. Comienza desde un nodo (nodo raíz en árboles y cualquier nodo aleatorio en gráficos) y atraviesa niveles, es decir, en este recorrido atraviesa todos los nodos en el nivel precise y luego todos los nodos en el siguiente nivel. Esto también se llama recorrido de nivel sabio.
La implementación del enfoque se menciona a continuación:
- Creamos una cola y empujamos el nodo inicial del gráfico.
- A continuación, tomamos una matriz visitada, que realiza un seguimiento de todos los nodos visitados hasta el momento.
- Hasta que la cola no esté vacía, seguimos haciendo las siguientes tareas:
- Haga estallar el primer elemento de la cola, visítelo y empuje todos sus elementos adyacentes en la cola (que aún no se han visitado).
B. Primera búsqueda en profundidad (DFS)
Búsqueda en profundidad (DFS) es también un método para recorrer un gráfico. Partiendo de un vértice, atraviesa en profundidad. El algoritmo parte de algún nodo (nodo raíz en árboles y cualquier nodo aleatorio en gráficos) y explora lo más lejos posible a lo largo de cada rama antes de retroceder.
El enfoque es iterar recursivamente todos los nodos no visitados, hasta que se visiten todos los nodos. La implementación del enfoque se menciona a continuación:
- Hacemos una función recursiva, que se llama a sí misma con el vértice y el arreglo visitado.
- Visite el nodo precise e inclúyalo en la respuesta.
- Ahora, recorra todos sus nodos adyacentes no visitados y llame a la función para cada nodo que aún no se haya visitado.
C. Algoritmo de Dijkstra
Algoritmo de Dijkstra se utiliza para encontrar la ruta más corta de todos los vértices desde un nodo de origen en un gráfico que tiene todos los pesos de borde positivos. El enfoque del algoritmo se menciona a continuación:
- En primer lugar, mantenga una matriz no visitada del tamaño del número complete de nodos.
- Ahora, tome el nodo de origen y calcule las longitudes de ruta de todos los vértices.
- Si la longitud de la ruta es más pequeña que la longitud anterior, actualice esta longitud; de lo contrario, continúe.
- Repita el proceso hasta que se visiten todos los nodos.
Algoritmo de D. Floyd Warshall
Sala de Guerra Flyod El algoritmo se utiliza para calcular el camino más corto entre cada par de vértices en gráficos ponderados con bordes positivos solamente. El algoritmo utiliza una solución DP. Se van relajando los pares de vértices que se han calculado. La complejidad temporal del algoritmo es O(V3).
E. Algoritmo Bellman-Ford
Algoritmo de Bellman-Ford se utiliza para encontrar las rutas más cortas de todos los demás nodos desde un vértice de origen. Esto se puede hacer con avidez utilizando el algoritmo de Dijkstra, pero el algoritmo de Dijkstra no funciona para el gráfico con bordes negativos. Entonces, para gráficos con pesos negativos, se usa el algoritmo Ford de Bellman para encontrar la ruta más corta de todos los demás nodos desde un nodo de origen. La complejidad del tiempo es O(V*E).
10. Otros algoritmos importantes
A. Algoritmos bit a bit
Estos algoritmos realizan operaciones en bits de un número. Estos algoritmos son muy rápidos. Hay muchas operaciones bit a bit como And (&), OR ( | ), XOR ( ^ ), operador de desplazamiento a la izquierda ( << ), operador de desplazamiento a la derecha (>>), and so forth. Los operadores de desplazamiento a la izquierda se utilizan para multiplicar un número por 2 y los operadores de desplazamiento a la derecha ( >> ), se utilizan para dividir un número entre 2. Estos son algunos de los problemas estándar que se plantean con frecuencia en las entrevistas de codificación:
- Intercambio de bits en números
- Siguiente elemento mayor con el mismo número de bits establecidos
- Algoritmos de Karatsuba para la multiplicación
- Enmascaramiento de bits con programación dinámica
y muchos más…..
B. La tortuga y la liebre
El algoritmo de la liebre y la tortuga es uno de los algoritmos más utilizados de Linked Listing. También se conoce como algoritmo de Floyd. Este algoritmo se utiliza para:
- Encuentra el centro de la lista enlazada
- Detectar un ciclo en la lista vinculada
En este algoritmo, tomamos dos punteros en la lista enlazada y uno de ellos se mueve con el doble de velocidad (liebre) que el otro (tortuga). La thought es que si se cruzan en algún punto, esto prueba que hay un ciclo en la lista enlazada.
C. Algoritmo de Kadane
El algoritmo de Kadane se usa para encontrar la suma máxima de un subarreglo contiguo en el arreglo dado con números positivos y negativos.
Intuición:
- Siga actualizando una variable de suma agregando los elementos de la matriz.
- Siempre que la suma se vuelva negativa, hágala cero.
- Sigue maximizando la suma en una nueva variable llamada max_sum
- Al closing, el max_sum será la respuesta.
