En el ámbito de las pruebas de software automatizadas, las habilidades de programación son esenciales. Las entrevistas técnicas a menudo incluyen ejercicios de codificación que evalúan la lógica, el conocimiento de estructuras de datos fundamentales como listas enlazadas, árboles binarios, y algoritmos como ordenamiento y búsqueda, junto con su complejidad temporal. Además, se enfatizan tres paradigmas clave: hashing, recursión y división y conquista.

Conceptos de Hashing

El hashing se refiere al uso de estructuras de mapeo en Python, como diccionarios y conjuntos, que ofrecen búsqueda eficiente con complejidad O(1), a diferencia de las secuencias como listas que tienen O(n). Esto es útil para deduplicación y optimización de consultas en problemas de listas.

Deduplicación de Listas

Para eliminar duplicados sin mantener el orden, se puede convertir la lista a un conjunto. Si se requiere preservar el orden, se puede emplear un diccionario o un conjunto auxiliar con una lista de resultados.

Ejemplo sin orden específico:

datos = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
unicos = list(set(datos))
print(unicos)

Salida: [1, 2, 3, 4, 5, 6, 9] (el orden puede variar).

Para mantener el orden de inserción:

datos_originales = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
vistos = set()
resultado = []
for elemento in datos_originales:
    if elemento not in vistos:
        vistos.add(elemento)
        resultado.append(elemento)
print(resultado)

En versiones de Python 3.6 y superiores, los diccionarios preservan el orden de inserción, lo que permite una deduplicación ordenada.

Agrupación y Conteo

Para agrupar elementos y contar ocurrencias, se pueden usar comprensiones de lista o módulos como itertools.

mezcla = [1, 'a', 2, 'b', 1, 'a', 3, 'c', 'b']
conjunto = set(mezcla)
conteos = [(item, mezcla.count(item)) for item in conjunto]
conteos.sort(key=lambda x: x[1], reverse=True)
print(conteos)

Top K en Datos Masivos

Para encontrar los K elementos más grandes en grandes volúmenes de datos, se puede usar ordenamiento con deduplicación o bibliotecas como heapq para eficiencia en memoria.

import heapq
import random

def generador_numeros(cantidad):
    for _ in range(cantidad):
        yield random.randint(0, cantidad * 10)

datos_grandes = generador_numeros(10000000)
k = 1000
mayores_k = heapq.nlargest(k, datos_grandes)
print(mayores_k[:5])

Problema de la Suma de Dos

Dada una lista y un objetivo, encontrar índices de dos eelmentos que sumen el objetivo. Usar hashing para reducir la complejidad de O(n^2) a O(n).

lista_num = [1, 5, 3, 7, 8, 2]
objetivo = 10
mapeo = {}
pares = []
for idx, valor in enumerate(lista_num):
    complemento = objetivo - valor
    if complemento in mapeo:
        pares.append((mapeo[complemento], idx))
    mapeo[valor] = idx
print(pares)

Problemas de Recursión

La recursión es una técnica donde una función se llama a sí misma para descomponer problemas en subproblemas más simples. Es común en problemas como factorial, secuencias de Fibonacci y recorridos de árboles.

Factorial

Calcular el factorial de un número entero positivo.

def calcular_factorial(numero):
    if numero <= 1:
        return 1
    return numero * calcular_factorial(numero - 1)

print(calcular_factorial(5))

Secuencia de Fibonacci

Generar números de la serie Fibonacci, donde cada número es la suma de los dos anteriores. Se puede usar memoización para optimizar.

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 2:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))

Problemas de Salto

Modelar escenarios como un saltador que puede avanzar en pasos fijos. La recursión define la relación entre niveles.

Ejemplo para saltos de 1 o 2 pasos:

def formas_saltar(pasos):
    if pasos <= 2:
        return pasos
    return formas_saltar(pasos - 1) + formas_saltar(pasos - 2)

print(formas_saltar(6))

Ordenamiento Rápido

Implementar quicksort recursivamente, dividiendo la lista alrededor de un pivote.

def ordenamiento_rapido(secuencia):
    if len(secuencia) < 2:
        return secuencia
    pivote = secuencia[0]
    menores, iguales, mayores = [], [pivote], []
    for elem in secuencia[1:]:
        if elem < pivote:
            menores.append(elem)
        elif elem == pivote:
            iguales.append(elem)
        else:
            mayores.append(elem)
    return ordenamiento_rapido(menores) + iguales + ordenamiento_rapido(mayores)

datos_ordenar = [3, 6, 8, 10, 1, 2, 1]
print(ordenamiento_rapido(datos_ordenar))

Búsqueda Binaria

Buscar un valor en una lista ordenada dividiendo repetidamente el intervalo de búsqueda.

def busqueda_binaria(lista, objetivo, inicio=0, fin=None):
    if fin is None:
        fin = len(lista) - 1
    if inicio > fin:
        return -1
    medio = (inicio + fin) // 2
    if lista[medio] == objetivo:
        return medio
    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, objetivo, medio + 1, fin)
    else:
        return busqueda_binaria(lista, objetivo, inicio, medio - 1)

lista_ordenada = [1, 3, 5, 7, 9, 11]
print(busqueda_binaria(lista_ordenada, 7))

Recorridos de Árboles Binarios

Los árboles binarios se representan con nodos que contienen datos y referencias a hijos izquierdo y derecho. Los recorridos en profundidad (preorden, inorden, postorden) usan recursión.

class Nodo:
    def __init__(self, valor, izquierdo=None, derecho=None):
        self.valor = valor
        self.izquierdo = izquierdo
        self.derecho = derecho

def recorrido_preorden(raiz):
    if raiz is None:
        return
    print(raiz.valor)
    recorrido_preorden(raiz.izquierdo)
    recorrido_preorden(raiz.derecho)

# Ejemplo de uso (omitiendo construcción del árbol por brevedad)

Profundidad Máxima de un Árbol

Calcular la altura máxima de un árbol binario usando recursión.

def profundidad_maxima(nodo):
    if nodo is None:
        return 0
    izquierda = profundidad_maxima(nodo.izquierdo)
    derecha = profundidad_maxima(nodo.derecho)
    return max(izquierda, derecha) + 1

Verificación de Árboles Idénticos

Determinar si dos árboles binarios son estructuralmente idénticos y tienen los mismos valores.

def son_iguales(arbol1, arbol2):
    if arbol1 is None and arbol2 is None:
        return True
    if arbol1 is None or arbol2 is None:
        return False
    return (arbol1.valor == arbol2.valor and 
            son_iguales(arbol1.izquierdo, arbol2.izquierdo) and 
            son_iguales(arbol1.derecho, arbol2.derecho))

Verificación de Árbol Balanceado

Un árbol está balanceado si la diferencia de altura entre sus subárboles izquierdo y derecho no excede 1 para todo nodo.

def es_balanceado(nodo):
    if nodo is None:
        return True
    altura_izq = profundidad_maxima(nodo.izquierdo)
    altura_der = profundidad_maxima(nodo.derecho)
    return abs(altura_izq - altura_der) <= 1 and es_balanceado(nodo.izquierdo) and es_balanceado(nodo.derecho)

Otros Temas Comunes

Estadísticas de Cadenas

Contar la frecuencia de caracteres en una cadena.

cadena = "ejemplo de texto"
frecuencias = {}
for caracter in cadena:
    frecuencias[caracter] = frecuencias.get(caracter, 0) + 1
print(frecuencias)

Inversión de Cadenas

Invertir una cadena, posiblemente solo caracteres alfabéticos.

cadena_original = "abc123def"
lista_invertida = []
for i in range(len(cadena_original) - 1, -1, -1):
    if cadena_original[i].isalpha():
        lista_invertida.append(cadena_original[i])
    else:
        lista_invertida.append(cadena_original[i])
cadena_invertida = ''.join(lista_invertida)
print(cadena_invertida)

Validación de Paréntesis

Verificar si los paréntesis en una cadena están correctamente cerrados usando una pila.

def validar_parentesis(expresion):
    pila = []
    pares = {')': '(', ']': '[', '}': '{'}
    for caracter in expresion:
        if caracter in pares.values():
            pila.append(caracter)
        elif caracter in pares:
            if not pila or pila.pop() != pares[caracter]:
                return False
    return len(pila) == 0

prueba = "{[()]}()(]"
print(validar_parentesis(prueba))

Fusión de Listas Ordenadas

Combinar dos listas ordenadas en una sola lista ordenada.

lista1 = [1, 3, 5, 7]
lista2 = [2, 4, 6, 8, 10]
resultado = []
i = j = 0
while i < len(lista1) and j < len(lista2):
    if lista1[i] < lista2[j]:
        resultado.append(lista1[i])
        i += 1
    else:
        resultado.append(lista2[j])
        j += 1
resultado.extend(lista1[i:])
resultado.extend(lista2[j:])
print(resultado)

Implementación de Pila con Colas

Simular el comportamiento LIFO de una pila usando dos colas.

from collections import deque

class PilaConColas:
    def __init__(self):
        self.cola_principal = deque()
        self.cola_auxiliar = deque()
    
    def apilar(self, valor):
        self.cola_principal.append(valor)
    
    def desapilar(self):
        while len(self.cola_principal) > 1:
            self.cola_auxiliar.append(self.cola_principal.popleft())
        elemento = self.cola_principal.popleft()
        self.cola_principal, self.cola_auxiliar = self.cola_auxiliar, self.cola_principal
        return elemento

pila = PilaConColas()
for num in [10, 20, 30]:
    pila.apilar(num)
print(pila.desapilar())