Intersección de dos listas de cuerdas

Tuve una pregunta de entrevista en este sentido:

Dadas dos listas de clientes desordenados, devuelva una lista de la intersección de las dos listas. Es decir, devolver una lista de los clientes que aparecen en ambas listas.

Algunas cosas que establecí:

  • Supongamos que cada cliente tiene un nombre único
  • Si el nombre es el mismo en ambas listas, es el mismo cliente
  • Los nombres son de la forma nombre apellido apellido
  • No hay trucos de II, Jr, personajes extraños, etc.

Creo que el punto era encontrar un algoritmo / uso eficiente de las estructuras de datos para hacerlo de la manera más eficiente posible.

Mi progreso fue así:

  • Lea una lista en la memoria, luego lea la otra lista un elemento a la vez para ver si hay una coincidencia
  • Alfabetice ambas listas, luego comience en la parte superior de una lista y vea si cada elemento aparece en la otra lista.
  • Coloque ambas listas en listas ordenadas, luego use la lista más corta para verificar elemento por elemento (de esa manera, una lista tiene 2 elementos, solo marque esos 2 elementos)
  • Coloque una lista en un hash y compruebe la existencia de claves de la otra lista

El entrevistador siguió preguntando: “¿Qué sigue?”, Así que asumo que me estoy perdiendo algo más.

¿Algún otro truco para hacer esto eficientemente?

Nota al margen, esta pregunta estaba en Python, y acabo de leer sobre sets , que parecen hacerlo de la manera más eficiente posible. ¿Alguna idea de cuál es la estructura de datos / algoritmo de sets ?

  1. Coloque una lista en un filtro de floración y úselo para filtrar la segunda lista.
  2. Coloque la segunda lista filtrada en un filtro de floración y úselo para filtrar la primera lista.
  3. Ordena las dos listas y encuentra la intersección por uno de los métodos anteriores.

El beneficio de este enfoque (además de permitirle usar una estructura de datos casi oscura en una entrevista) es que no requiere ningún almacenamiento de O (n) hasta después de que (con alta probabilidad) reduzca el tamaño del problema.


El entrevistador siguió preguntando: “¿Qué sigue?”, Así que asumo que me estoy perdiendo algo más.

Tal vez solo seguirían preguntando eso hasta que te quedes sin respuestas.


http://code.google.com/p/python-bloom-filter/ es una implementación de python de filtros bloom.

Realmente no importa cómo se implementó … pero creo que se implementa en C, por lo que es más rápido y está mejor set([1,2,3,4,5,6]).intersection([1,2,5,9]) es probable lo que querían

En python la legibilidad cuenta para mucho! y las operaciones de configuración en python se usan ampliamente y se examinan bien …

Dicho esto, otra forma pythonica de hacerlo sería

 list_new = [itm for itm in listA if itm in listB] 

o

 list_new = filter(lambda itm:itm in listB,listA) 

Básicamente, creo que estaban probando si estabas familiarizado con Python, no si pudieras implementar el algoritmo. ya que hicieron una pregunta que se adapta tan bien a Python