Microsoft IV - A comer!

La tercera entrevista fue una 'lunch interview' en el edificio 26 con Aaron Holmes. Cómo siempre, hablé con la recepcionista y a los 5 minutos mi entrevistador bajó a recogerme, pero esta vez no me llevó a su oficina sino al restaurante.

El restaurante era tipo buffet, y tenía como distintas secciones: ensaladas, hamburguesas, postres, etc. Yo me decidí por una ensalada (tenían de todo para echarle), y Aaron, como buen americano, se pidió una hamburguesa con patatas fritas =) Después de coger la comida, nos sentamos y empezamos a hablar.

Basicamente me estuvo contando lo que hacían en su grupo. Estaban trabajando en el sistema de actualizaciones de Windows Vista y Windows Seven, y también en el instalador de programas (los archivos .cab y esas historias). Luego me preguntó un poco por mis experiencias trabajando en grupo y por mi último proyecto hasta que acabamos de comer y nos fuimos a la oficina.

Tocaban más 'coding questions'. La primera fue la siguiente:

Escribir una función que dada una lista de nombres (por ejemplo "Peter, Charles, David") y un entero positivo N genere otra lista con el siguiente formato "A gives to B, C gives to D, ...", donde A, B, C y D son personas de la lista inicial. La lista resultante debe cumplir las siguientes reglas:
- Todos dan N veces
- Todas reciben N veces
- Nadie da más de una vez a la misma persona
- Nadie se da a si mismo
- El resultado debe ser aleatorio, es decir, la misma entrada debe producir distintas salidas

La pregunta me resultó un poco rara al principio, pero luego me di cuenta de que no era difícil. Empecé dando una solución que no era aleatoria, y luego empecé a dar ideas para aleatorizarla, hasta que di con la que el entrevistador estaba esperando. Quedó bastante impresionado y me dijo que me quería hacer otra pregunta.

Dada un secuencia de enteros positivos y negativos, encontrar la subsecuencia de suma máxima. Por ejemplo, en [4, 7, -3, 100, -9, 5] la subsecuencia de suma máxima sería [4, 7, -3, 100].

Este problema es todo un clásico. Ya había leido de otra gente a la que se lo habían preguntado y creía saber la solución, así que me puse contento. Sin embargo, resulta que la que creía que era la solución no lo era realmente jaja, así que allí estaba solo ante el peligro. Empecé a buscar posibles soluciones y el entrevistador me fue dando consejos hasta que llegué a la solución correcta, que tiene complejidad O(n) y sólo implica recorrer la lista una vez. Aaron quedó muy satisfecho porque había resuleto el problema muy rápido.

El tiempo de la entrevista se había agotado, así que el entrevistador me acompañó a la entrada. Mi siguiente entrevistador era su jefe, un indio cuyo nombre nunca llegué a entender. Me dijo que esperase allí, que vendría a recogerme en unos minutos. Así que nada, me senté en un sofá a esperar mi cuarta entrevista.