Me estoy preparando para la entrevista para Google. ¿Tengo que conocer el algoritmo de Karatsuba para la multiplicación rápida de dos enteros?

Absolutamente no tienes que saber eso. Básicamente, hay cero posibilidades de que se le haga esa pregunta (a menos que haya dejado alguna evidencia de quién es usted, en cuyo caso un entrevistador podría encontrar esta pregunta y formularla por completo debido a su actividad en línea).

Dicho esto, sería útil si usted es el tipo de persona que es naturalmente curiosa y aprende estas cosas por su propio bien, en lugar de simplemente tratar de pasar alguna entrevista.

Tienes que saber – No. Nadie le pedirá que implemente el algoritmo Karastuba o cualquier otro si no es básico.
Sin embargo, debe saberlo, ya que una pregunta que hacen podría implicar la multiplicación de dos enteros, y si el entrevistador pregunta “¿puede hacer que funcione más rápido?”, Podría romper este algoritmo. (Aunque el entrevistador podría estar pensando en otra cosa que podría mejorar). Tener un arsenal de algoritmos listos en tu cabeza nunca es una mala idea.
Sin embargo, tenga en cuenta que nadie quedará impresionado con su conocimiento de algoritmos complicados si no puede resolver un problema limpiamente en el momento dado.

Realmente lo dudo.

¿Tienes que saber? NO.

Se le puede pedir que implemente la multiplicación de dos enteros. Podría hacerlo de la manera tradicional, y luego mencionar al entrevistador hacia el final que hay un algoritmo para hacerlo en O (n ^ 1.6). A lo sumo, el entrevistador le pedirá que proporcione una descripción rápida del algoritmo más rápido o simplemente indique la técnica que se sigue.

Recuerde, escribir un algoritmo es una cosa, e implementarlo mientras maneja todos los casos límite es otra. En una entrevista, se espera que maneje todos los casos límite en su implementación. Si es posible que recuerde la implementación de este algoritmo sin ningún problema, continúe, pero no creo que los entrevistadores de Google esperen que recuerde esto. Están entrenados para no ser idiotas.

Tal vez algún entrevistador aficionado de alguna startup que piense que es una buena manera de encontrar buenos ingenieros esperaría que usted lo recuerde.