Tuve una interesante experiencia de entrevista de trabajo hace un tiempo. La pregunta comenzó realmente fácil:

Q1: Tenemos una bolsa con números1, 2, 3, ...,100. Cada número aparece exactamente una vez, por lo que hay 100 números. Ahora se saca un número al azar de la bolsa. Encuentre el número perdido.

He escuchado esta pregunta de la entrevista antes, por supuesto, así que rápidamente respondí en la línea de:

A1: Bueno, la suma de los números1 + 2 + 3 + … + N es(N+1)(N/2) (verWikipedia: suma de series aritméticas) porN = 100, la suma es5050.

Por lo tanto, si todos los números están presentes en la bolsa, la suma será exactamente5050. Como falta un número, la suma será menor que esto, y la diferencia es ese número. Entonces podemos encontrar ese número faltante enO(N) tiempo yO(1) espacio.

En este punto, pensé que lo había hecho bien, pero de repente la pregunta tomó un giro inesperado:

Q2: Eso es correcto, pero ahora, ¿cómo harías esto siDOS faltan los números?

Nunca antes había visto / escuchado / considerado esta variación, así que entré en pánico y no pude responder la pregunta. El entrevistador insistió en conocer mi proceso de pensamiento, por lo que mencioné que quizás podamos obtener más información comparándolo con el producto esperado, o tal vez haciendo una segunda pasada después de haber reunido alguna información de la primera pasada, etc., pero realmente solo estaba disparando en la oscuridad en lugar de tener un camino claro hacia la solución.

El entrevistador intentó alentarme diciendo que tener una segunda ecuación es de hecho una forma de resolver el problema. En este punto, estaba un poco molesto (por no saber la respuesta de antemano), y le pregunté si esta es una técnica de programación general (léase: "útil"), o si es solo una respuesta truco / gotcha.

La respuesta del entrevistador me sorprendió: puedes generalizar la técnica para encontrar 3 números faltantes. De hecho, puedes generalizarlo para encontrark números perdidos.

Qk: Si exactamentek faltan números en la bolsa, ¿cómo lo encontrarían eficientemente?

Esto fue hace unos meses, y todavía no podía entender qué es esta técnica. Obviamente hay unΩ(N) límite inferior de tiempo ya que debemos escanear todos los números al menos una vez, pero el entrevistador insistió en que elHORA yESPACIO complejidad de la técnica de resolución (menos elO(N) exploración de entrada de tiempo) se define enk noN.

Entonces la pregunta aquí es simple:

¿Cómo resolveríasQ2?¿Cómo resolveríasQ3?¿Cómo resolveríasQk?AclaracionesGeneralmente hayN números del 1 ..N, no solo 1..100.No estoy buscando la solución obvia basada en conjuntos, p. usando unconjunto de bits, codificando la presencia / ausencia de cada número por el valor de un bit designado, por lo tanto, utilizandoO(N) bits en espacio adicional. No podemos permitirnos ningún espacio adicional proporcional aN.Tampoco estoy buscando el enfoque obvio de ordenar primero. Vale la pena mencionar este y el enfoque basado en conjuntos en una entrevista (son fáciles de implementar y dependen deN, puede ser muy práctico). Estoy buscando la solución del Santo Grial (que puede o no ser práctica de implementar, pero sin embargo tiene las características asintóticas deseadas).

Entonces, de nuevo, por supuesto, debe escanear la entrada enO(N), pero solo puede capturar una pequeña cantidad de información (definida en términos dek noN), y luego debe encontrar elk números perdidos de alguna manera.