Hace poco, mientras conversaba con un amigo autodidacta que está inmerso en el aprendizaje de programación a través de cursos, se encontró con una situación intrigante: le hicieron preguntas sobre algoritmos de ordenamiento, un concepto que desconocía por completo. Este escenario no es inusual, especialmente para aquellos que no han cursado una carrera universitaria en informática, donde estos algoritmos, generalmente en Java, son comunes.
Aunque no es necesario recordar todos los algoritmos, e incluso es posible que no los utilices en tu día a día, es crucial comprenderlos por dos razones fundamentales. En primer lugar, muchos de estos algoritmos son empleados en bases de datos para optimizar búsquedas y obtener resultados más eficientes. En segundo lugar, y aún más importante, estas son preguntas frecuentes en entrevistas laborales.
Con la intención de brindar apoyo a mi amigo y a todos aquellos que se encuentran en una situación similar, decidí redactar este artículo, detallando algunos de los algoritmos de búsqueda que podrían surgir en una entrevista de trabajo.
Programación dinámica
En esencia, se busca minimizar las funciones recursivas eliminando las llamadas recursivas mediante diversas estrategias. Para profundizar, la recursividad se suprime almacenando los resultados de las subfunciones anteriores, evitando así múltiples llamadas innecesarias. Según el manual, esta práctica reduce la complejidad temporal de ejecución de forma exponencial a polinómica. A continuación, se presentan algunos ejemplos de estas estrategias:
Ugly Numbers
class SampleUglyNumbers{
/*This function divides a by
greatest divisible power of b*/
static int maxDivide(int a, int b)
{
while (a % b == 0)
a = a / b;
return a;
}
/* Function to check if a number
is ugly or not */
static int isUgly(int no)
{
no = maxDivide(no, 2);
no = maxDivide(no, 3);
no = maxDivide(no, 5);
return (no == 1) ? 1 : 0;
}
/* Function to get the nth ugly
number*/
static int getNthUglyNo(int n)
{
int i = 1;
// ugly number count
int count = 1;
// Check for all integers
// until count becomes n
while (n > count) {
i++;
if (isUgly(i) == 1)
count++;
}
return i;
}
// Driver code
public static void Main()
{
int no = getNthUglyNo(150);
// Function call
Console.WriteLine("150th ugly"
+ " no. is " + no);
}
}
Fibonacci Numbers
using System;
class SampleFibonacciNumbers
{
static void fib(int n)
{
int a = 0, b = 1, c;
if (n >= 0)
Console.Write( a + " ");
if (n >= 1)
Console.Write( b + " ");
for (int i = 2; i <= n; i++)
{
c = a + b;
Console.Write( c + " ");
a = b;
b = c;
}
}
public static void Main ()
{
fib(9);
}
}
Binomial Coefficient
public static long BinomCoefficient(long n, long k)
{
if (k > n) { return 0; }
if (n == k) { return 1; }
if (k > n - k) { k = n - k; }
long c = 1;
for (long i = 1; i <= k; i++)
{
c *= n--;
c /= i;
}
return c;
}
Permutation Coefficient
using System;
class SamplePermutatioCoefficient
{
// Returns value of Permutation
// Coefficient P(n, k)
static int permutationCoeff(int n,
int k)
{
int [,]P = new int[n + 2,k + 2];
// Caculate value of Permutation
// Coefficient in bottom up manner
for (int i = 0; i <= n; i++)
{
for (int j = 0;
j <= Math.Min(i, k);
j++)
{
// Base Cases
if (j == 0)
P[i,j] = 1;
// Calculate value using previosly
// stored values
else
P[i,j] = P[i - 1,j] +
(j * P[i - 1,j - 1]);
// This step is important
// as P(i,j)=0 for j>i
P[i,j + 1] = 0;
}
}
return P[n,k];
}
// Driver Code
public static void Main()
{
int n = 10, k = 2;
Console.WriteLine("Value of P( " + n +
","+ k +")" + " is " +
permutationCoeff(n, k) );
}
}Binary Search
La búsqueda binaria funciona cuando tenemos una matriz ordenada de elementos y una clave de búsqueda. Funciona seleccionando el elemento del medio y comparándolo con la clave de búsqueda. Si el valor que buscamos es igual al elemento del medio, este será retornado. Si el elemento es menor o mayo del elemento del medio, la búsqueda seguirá de una mitad u otra mitad dejando una de las 2 miradas fuera de la siguiente búsqueda. Una vez separada se vuelve a comenzar por el valor medio.
public static object BinarySearchDisplay(int[] arr, int key) {
int minNum = 0;
int maxNum = arr.Length - 1;
while (minNum <=maxNum) {
int mid = (minNum + maxNum) / 2;
if (key == arr[mid]) {
return ++mid;
} else if (key < arr[mid]) {
max = mid - 1;
}else {
min = mid + 1;
}
}
return "None";
}
Depth First Search
Este algoritmo de búsqueda inicia el proceso de búsqueda desde el nodo y llega hasta la última hoja de la rama izquierda. Luego de llegar hasta la hoja más a la izquierda, comienza a retroceder y atraviesa el árbol hacia la derecha. Este tipo de búsqueda tiene un problema, si tenemos más de un ciclo, es posible que estemos obligados a visitar más de un nodo una vez. El tiempo de respuesta dependerá del número de vértices y aristas que tengamos en un grafo.
public static bool DepthFirstSearch<T>(this IEnumerable<T> vertices, T rootVertex, T targetVertex, Func<T, IEnumerable<T>> getConnectedVertices, Func<T, T, bool> matchFunction = null)
{
if (getConnectedVertices == null)
{
throw new ArgumentNullException("getConnectedVertices");
}
if (matchFunction == null)
{
matchFunction = (t, u) => object.Equals(t, u);
}
var directlyConnectedVertices = getConnectedVertices(rootVertex);
foreach (var vertex in directlyConnectedVertices)
{
if (matchFunction(vertex, targetVertex))
{
return true;
}
else if (vertices.DepthFirstSearch(vertex, targetVertex, getConnectedVertices, matchFunction))
{
return true;
}
}
return false;
}
Merge Sort
Este pertenece a los algoritmos de ordenamiento. Funciona según los principios de divide y vencerás. Esto quiere decir que dividiremos el problema en partes más pequeñas y las resolveremos una a una para fusionarlas finalmente. Merge Sort divide la matriz por la mitad e invoca a una función de ordenación en ambas mitades. Esas mitades se ordenan y luego se combinan mediante la función merge.
using System;
namespace SampleMergeSort
{
class Program
{
static public void MergeMethod(int[] numbers, int left, int mid, int right)
{
int[] temp = new int[25];
int i, left_end, num_elements, tmp_pos;
left_end = (mid - 1);
tmp_pos = left;
num_elements = (right - left + 1);
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
temp[tmp_pos++] = numbers[left++];
else
temp[tmp_pos++] = numbers[mid++];
}
while (left <= left_end)
temp[tmp_pos++] = numbers[left++];
while (mid <= right)
temp[tmp_pos++] = numbers[mid++];
for (i = 0; i < num_elements; i++)
{
numbers[right] = temp[right];
right--;
}
}
static public void SortMethod(int[] numbers, int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
SortMethod(numbers, left, mid);
SortMethod(numbers, (mid + 1), right);
MergeMethod(numbers, left, (mid + 1), right);
}
}
static void Main(string[] args)
{
int[] numbers = { 38, 27, 43, 3, 9, 82, 10 };
int len = numbers.Length;
Console.WriteLine("Before Merge Sort:");
foreach(int item in numbers)
{
Console.Write(item + " ");
}
Console.WriteLine();
Console.WriteLine("After Merge Sort");
SortMethod(numbers, 0, len - 1);
foreach (int item in numbers)
{
Console.Write(item + " ");
}
Console.Read();
}
}
}
Quick Sort
Al igual que el anterior, se basa en la premisa divide y triunfarás. La diferencia con el anterior es en su funcionalidad de ordenamiento. En este algoritmo seleccionaremos el último elemento como el número pivot y lo colocaremos en medio. Quedarán a la izquierda los números más pequeños y a la derecha los números más grandes. Ambos lados se llamarán nuevamente con la función de ordenamiento que dará como resultado la matriz ordenada.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Quick_Sort
{
class Program
{
private static void Quick_Sort(int[] arr, int left, int right)
{
if (left < right)
{
int pivot = Partition(arr, left, right);
if (pivot > 1) {
Quick_Sort(arr, left, pivot - 1);
}
if (pivot + 1 < right) {
Quick_Sort(arr, pivot + 1, right);
}
}
}
private static int Partition(int[] arr, int left, int right)
{
int pivot = arr[left];
while (true)
{
while (arr[left] < pivot)
{
left++;
}
while (arr[right] > pivot)
{
right--;
}
if (left < right)
{
if (arr[left] == arr[right]) return right;
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
else
{
return right;
}
}
}
static void Main(string[] args)
{
int[] arr = new int[] { 2, 5, -4, 11, 0, 18, 22, 67, 51, 6 };
Console.WriteLine("Original array : ");
foreach (var item in arr)
{
Console.Write(" " + item);
}
Console.WriteLine();
Quick_Sort(arr, 0, arr.Length-1);
Console.WriteLine();
Console.WriteLine("Sorted array : ");
foreach (var item in arr)
{
Console.Write(" " + item);
}
Console.WriteLine();
}
}
}
Conclusiones
Estos son algunos de los algoritmos más frecuentemente solicitados en entrevistas técnicas. Cabe destacar que el vasto mundo de los algoritmos de búsqueda y ordenamiento abarca una amplia variedad de técnicas y enfoques. Si estás interesado en explorar un tutorial más completo que abarque una gama más amplia de algoritmos, no dudes en expresarlo en los comentarios. Estoy aquí para ayudar y proporcionar el contenido que sea más beneficioso para ti.
