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?
Si no has visto la primera parte donde te explico como proceder, aca te dejo el link!
https://thewhitecode.com/blog/2567
Ejercicio #3: Borrar valores duplicados
Una posible solución para eliminar los duplicados de una lista manteniendo el orden original es utilizar un conjunto o set para realizar un seguimiento de los elementos únicos vistos hasta el momento y utilizar una nueva lista para almacenar los elementos únicos en su orden original. Podemos iterar sobre la lista de entrada, y para cada elemento, verificamos si está en el conjunto de elementos únicos visto hasta ahora. Si no está en el conjunto, lo agregamos tanto al conjunto como a la nueva lista de elementos únicos.
Aquí está la implementación de este algoritmo en Python:
1 2 3 4 5 6 7 8 | def remove_duplicates(A): unique_elements = set() unique_list = [] for x in A: if x not in unique_elements: unique_elements.add(x) unique_list.append(x) return unique_list |
En este código, definimos una función llamada remove_duplicates que toma una lista A como entrada y devuelve una nueva lista con los duplicados eliminados mientras conserva el orden original de los elementos. Inicializamos un conjunto vacío unique_elementsy una nueva lista unique_list . Luego iteramos sobre la lista de entrada A, y para cada elemento x, verificamos si está en el conjunto de elementos únicos visto hasta ahora. Si no está en el conjunto, lo agregamos tanto al conjunto como a la nueva lista de elementos únicos. Finalmente, devolvemos la nueva lista de elementos únicos.
La complejidad temporal de este algoritmo es O(n), donde n es la longitud de la lista de entrada A, ya que necesitamos iterar sobre la lista de entrada una vez. La complejidad del espacio también es O(n), ya que necesitamos almacenar un conjunto de elementos únicos vistos hasta ahora y una nueva lista de elementos únicos.
¿Puedes generar un código mejor y más rápido usando una estructura de datos?
Sí, podemos mejorar la complejidad de tiempo de la solución anterior usando un OrderedDict del módulo collections. OrderedDict conserva el orden de inserción, al igual que una lista normal. Podemos iterar sobre la lista de entrada, y para cada elemento, verificamos si está en OrderedDict. Si no está en OrderedDict, lo agregamos tanto a OrderedDict como a la nueva lista de elementos únicos. Finalmente, devolvemos la nueva lista de elementos únicos.
Aquí está la implementación de este algoritmo en Python:
1 2 3 4 5 6 7 8 9 10 | from collections import OrderedDict def remove_duplicates(A): unique_elements = OrderedDict() unique_list = [] for x in A: if x not in unique_elements: unique_elements[x] = None unique_list.append(x) return unique_list |
En este código, importamos la clase OrderedDict del módulo de colecciones. Definimos una función llamada remove_duplicates que toma una lista A como entrada y devuelve una nueva lista con los duplicados eliminados mientras conserva el orden original de los elementos. Inicializamos un Unique_elements de OrderedDict vacío y una nueva lista unique_list. Luego iteramos sobre la lista de entrada A, y para cada elemento x, verificamos si está en el OrderedDict de elementos únicos vistos hasta ahora. Si no está en OrderedDict, lo agregamos tanto a OrderedDict como a la nueva lista de elementos únicos. Finalmente, devolvemos la nueva lista de elementos únicos.
La complejidad temporal de este algoritmo también es O(n), donde n es la longitud de la lista de entrada A, ya que necesitamos iterar sobre la lista de entrada una vez. Sin embargo, usar un OrderedDict puede ser más rápido que usar un set, especialmente para tamaños de entrada más grandes, ya que las búsquedas y las inserciones son operaciones O(1).
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?, como lo solucionarías tu?
Dejame saber tu opinion en los comentarios!