Spotify, tráfico de influencias

propuesto por josejuan

Spotify presenta tres retos para quien quiera trabajar allí como programador. Uno de ellos es obtener una lista de beneficiarios sujeta a ciertas restricciones.

Enunciado
Fuente: http://www.spotify.com/es/jobs/tech/bilateral-projects/

El resumen podría ser:

Una empresa tiene dos oficinas, una en Estocolmo y otra en Londres.

Sus empleados trabajan por parejas, de tal modo que un miembro de la pareja está en Estocolmo y la otra en Londres.

Los empleados de Estocolmo tienen nº de identificación del 1000 al 1999 y los de londres del 2000 al 2999.

Una vez al año, la empresa reúne a todos los miembros de los equipos a una playa paradisíaca para comentar los pormenores del trabajo que cada equipo realiza, pero este año, por motivos de la crisis, deciden que será suficiente con que un miembro del equipo (parejas) vaya a la playa.

Además, para abaratar costes, como algunos empleados están en varios equipos (parejas), irán aquellos empleados con más equipos (para que vayan los menos empleados y salga lo más barato posible).

Así, dado un archivo con los ID's de las parejas, nos piden que generemos el listado de las empleados que irán a la playa.

Así, da igual quienes vayan al final a la playa mientras se cumpla que:

1. todos los equipos (parejas) están representados.
2. van a la playa el menor número de empleados posible.

Sin embargo, tú tienes un amigo que trabaja en Estocolmo (con ID 1009) e intentarás que tu amigo esté en la lista de quienes se irán a la playa (si es posible).

Por ejemplo:

Dada la entrada:
   1009 2011
   1017 2011

La salida será:
   2011

porque son un sólo empleado quedan representados todos los equipos (parejas), desafortunadamente, no puede ir tu amigo.


Dada la entrada:
   1009 2000
   1009 2001
   1002 2002
   1003 2002

La salida será:
   2002
   1009 

Ver todo el enunciado

Preguntas sobre el desafío

¿Tienes dudas sobre el desafío? plantéala aquí

Plantea tu pregunta

5 Soluciones

Dar mi solución

0votos
Spotify, tráfico de influencias en Haskell
por

josejuan

hace 4 años

Hace dos años comenté que el problema es NP-completo, estaba equivocado, pues en el caso de grafos bipartitos (como ocurre aquí) usando el teorema de König existe un algoritmo polinomial fácil de implementar (siguiendo la demostración de http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29 )

0votos
Spotify, tráfico de influencias en PHP
por

niglesiasg

hace 5 años

En primer momento se carga la información del fichero en una matriz con 3 columnas; las dos primeras para controlar los id de los empleados, y la tercera para indicar si la pareja esta o no representada en la lista final de elegidos. Mediante un bucle vamos buscando el mejor candidato, dando preferencia al amigo (id=1009). Lo añadimos a la lista final y marcamos sus parejas. Por último optimizamos la lista final buscado empleados que se puedan eliminar.

0votos
Spotify, tráfico de influencias en C#
por

Javier Pérez

hace 6 años

Tomando como entrada un archivo de texto, se obtienen los datos de manera mas amigable y luego se obtiene de cada pareja cual tiene mas repeticiones en total, para enchufar a tu amigo simplemente seria, en el caso que las repeticiones sean iguales en los dos extremos dar preferencia al ID de tu amigo

Dar mi solución