TheWhiteCode

Te pediré que resuelvas algunos problemas de programación usando Python y que me des el código, que debe ser lo suficientemente comprensible y el algoritmo debe ser eficiente y considerar todos los posibles casos especiales y manejar entradas grandes de manera eficiente.  Cuentas con 10 minutos como tiempo maximo para realizar cada tarea ¿Está bien?

El proceder: Lápiz y papel

Por lo general es una mala idea comenzar a programar en seguida, en vez de ello se debe escuchar atentamente a la otra persona y a continuación hacer preguntas que te permitan idealizar mejor una solución.

Es imprescindible el hacer notas a medida que el locutor describe los requisitos de la tarea y paralelamente anotar preguntas sobre cada punto, al finalizar el locutor deberías revisar tus notas, complementarlas con ideas y preguntas, las cuales debes formular al locutor, claramente algunas preguntas se tienen que hacer posteriormente al entender mejor el tema y algunas tampoco sean necesarias.

Ejercicio #1: Palindromos

En ese orden de ideas, ¿puedes generar un código para verificar si una palabra dada es un palíndromo, darme ejemplos y describir tu código?

Que carajos es un palindromo estaras pensando.. Bueno esto hace parte de entender el problema, debes preguntar cada detalle, asi que el locutor normalmente te explicara que es un palindromo y seria genial si puedes tu generar un par de ejemplos para poder comenzar.

- Un palíndromo, también llamado palíndroma o palindroma, es una palabra o frase que se lee igual en un sentido que en otro. -

Unos ejemplos serian:

1. madam


2. abba
   


3. Bob


4. Anna

Ahora tienes que tratar de analizar como solucionarias tu el problema en primer lugar, prestando atencion a los detalles y generando un algoritmo de paso:

Dada la definición de un palindromo, lo primero que hacemos es comparar las palabras a cada extremo y ver si son iguales, para ello debemos de alguna manera iterar sobre la cadena de caracteres y podrias pensar inmediatamente en un loop.

Al tener claro ya el problema, podriamos plantear la primera solución a continuación:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def is_palindrome(word):
    """
    Returns True if the given word is a palindrome, False otherwise.
    """
    i = 0
    j = len(word) - 1
    
    while i < j:
        if word[i] != word[j]:
            return False
        i += 1
        j -= 1
        
    return True

Esta función toma una cadena como entrada y devuelve True si la cadena es un palíndromo, y False de lo contrario. El enfoque que utilizamos aquí es comenzar desde ambos extremos de la cadena y comparar los caracteres en esas posiciones. Si son iguales, nos movemos hacia el centro de la cadena y seguimos haciendo esto hasta que llegamos al medio. Si encontramos cualquier par de caracteres que no sean iguales, sabemos que la cadena no es un palíndromo y devolvemos False. Si llegamos al medio de la cadena y no hemos encontrado ningún carácter desigual, sabemos que la cadena es un palíndromo y devolvemos True.

En este código, hemos utilizado un loop while para iterar sobre los caracteres en la cadena. Tenemos dos variables i y j que se inicializan al primer y último índice de la cadena, respectivamente. Seguimos comparando los caracteres en estos índices, e incrementamos i y decrementamos j hasta que lleguemos al centro de la cadena. Si en algún momento encontramos dos caracteres que no son iguales, devolvemos False. Si llegamos al centro de la cadena y no hemos encontrado ningún carácter que no sea igual, devolvemos True.

Este código maneja todos los posibles casos extremos, incluyendo cadenas vacías y cadenas de longitud par o impar. También funciona eficientemente para tamaños de entrada grandes, ya que sólo necesita iterar sobre la mitad de los caracteres de la cadena.

Para testear el codigo usaremos los ejemplos encontrados anteriormente:

1
2
3
4
5
6
7

 True
print(is_palindrome("hello"))    # False
print(is_palindrome("madam"))    # True
print(is_palindrome("abba"))     # True
print(is_palindrome("python"))   # False
print(is_palindrome("bob"))     # True
print(is_palindrome("Anna"))     # True

Nuestro codigo funciona bien, sin embargo el que funcione bien no significa que sea bien calificado, puesto que en las entrevistas tambien se quiere ver tanto el nivel de familiaridad con el lenguage como los fundamentos de todo programador como lo es el clean code y una parte de este es el refractoring que basicamente es el mejorar el codigo, asi que rapidamente podemos formular una segunda solución al problema.

Por lo general un loop trae un costo de O(n), asi que este seria el costo minimo de nuestro algoritmo, a menos que exista un algoritmo o estructura de datos en la biblioteca estandard (en este caso de python) que nos pueda ayudar a hacelerar las cosas, y tambien es bien visto el hacer uso de ellas para dar a entender que tienes un conocimiento amplio del lenguage de programación que usas. 

Asi que al visualizar el problema y su primera solucion, vemos que tenemos que comparar la primera y la ultima letra de la palabra dada, recorriendo la palabra hacia la mitad (lo cual ahora nos dice que nuestro algoritmo solo necesite O(n/2), siendo n el largo de la palabra) y recordando un poco de estructuras de datos, nos acordamos del funcionamiento de una queue, mejor de una dequeue.

Asi que podemos usar una estructura de datos para hacer que la verificación del palíndromo sea más eficiente. Una forma de hacer esto es usar una estructura de datos deque (cola de dos extremos) o dequeue para almacenar los caracteres en la palabra. Luego podemos usar los métodos popleft() y pop() de la dequeue para comparar los caracteres al principio y al final de la palabra, respectivamente. Este enfoque tiene una complejidad temporal de O(n/2), lo cual seria mas rapido que el algoritmo anterior en primera instancia:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from collections import deque

def is_palindrome(word):
    """
    Returns True if the given word is a palindrome, False otherwise.
    """
    # Create a deque from the word
    d = deque(word)
    
    # Compare the characters at the beginning and end of the deque
    while len(d) > 1:
        if d.popleft() != d.pop():
            return False
    
    return True

Este código usa un deque para almacenar los caracteres en la palabra y solo necesita comparar los caracteres al principio y al final del deque, lo que lo hace más eficiente que el enfoque lineal usado en el código anterior.

En el enfoque lineal anterior, iteramos más de la mitad de los caracteres de la palabra, comparando cada carácter con su carácter correspondiente en el otro lado de la palabra. Esto lleva O(n/2) tiempo, ya que solo estamos visitando la mitad de los caracteres de la palabra.

En el enfoque usando la dequeue, también visitamos solo la mitad de los caracteres de la palabra. Sin embargo, en lugar de iterar sobre los caracteres de la palabra, estamos utilizando los métodos popleft() y pop() de dequeue para acceder al primer y último carácter de la deque, respectivamente. Dado que estos métodos tardan un tiempo constante en ejecutarse, la complejidad temporal general de este enfoque también es O(n/2).

En términos de velocidad, este enfoque es generalmente más rápido que el enfoque lineal anterior, ya que utiliza un algoritmo más eficiente y evita la sobrecarga de las variables de índice i y j y las comparaciones necesarias para acceder a los caracteres de la palabra. Además, la estructura de datos dequeue se ha optimizado para una rápida inserción y eliminación en ambos extremos, lo que mejora aún más su rendimiento para esta tarea.

El Manual de los algoritmos y las estructuras de datos.

  ¿Quieres estar preparado para cualquier entrevista de trabajo en programación? El Manual es la guía esencial que todo programador debe tener. Con explicaciones detalladas y ejemplos prácticos, aprenderás los algoritmos más usados y complejos que necesitas conocer para destacar en cualquier entrevista. ¡No pierdas la oportunidad de obtener esta herramienta invaluable para tu carrera!  

Descarga el manual directamente desde este enlace

https://leanpub.com/elmanualdelosalgoritmosylasestructurasdedatosfondoblanco

No te pierdas la segunda parte con otro ejemplo de ejercicio en una oferta de trabajo!

¿Te ha gustado?, quisieras acceder a más contenido?

Dejame saber tu opinion en los comentarios!