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:
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:
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!
laura_mart
Me preparé parte de mi última entrevista con esta serie y el ejercicio de la ventana deslizante me lo preguntaron casi tal cual. ¡Muchas gracias!
maria_dev
¿Tienen planeada una parte 4? Me encantaría ver un repaso de diseño de sistemas y preguntas de APIs junto a los de algoritmos.
anna.data
En el mundo de los pipelines este problema es el DISTINCT de SQL con orden: SELECT DISTINCT arranca a perder el orden original, así que uno recurre a row_number() over (partition by valor) o al patrón de hash join que preserva el orden de la tabla izquierda. El set + lista del post es exactamente un hash join con preserve-order. Dato para el post: en PostgreSQL el array + DISTINCT también pierde orden, vale la pena mencionarlo si viene una parte de SQL.
marcus.thompson
En Go esto se escribe con un map[int]bool para los que ya viste y una slice para el resultado: misma idea del set + lista, dos contenedores, O(n) con constante pequeña. Lo que me parece valioso de la serie es que muestra PRIMERO la solución ingenua y luego la mejora — en las entrevistas reales te esperan que propongas la ingenua, la ejecutes, y después la optimices, no que salgas directo con la perfecta.
omarhaddad
Como reviewer, la pregunta que le haría al candidato en este ejercicio es '¿por qué necesitas DOS estructuras (el set y la lista) y no una sola?'. Si responde que el set no mantiene orden (pre-3.7) o propone OrderedDict o un dict vacío como set, va bien. Es el tipo de pregunta que separa a quien memorizó el patrón de quien lo entendió. La serie la enmarca bien.
danielweber
Aclaración importante: desde Python 3.7 (PEP 468) los dict normales YA preservan el orden de inserción, así que la 'mejora' con OrderedDict es redundante — set + lista es la solución idiomática y suficiente. La explicación del post es correcta en la lógica, pero en una entrevista moderna me preguntaría al candidato si conoce esa diferencia entre OrderedDict y dict, que es una pregunta de entrevista muy común en sí misma.