Acabo de terminar una ronda de entrevistas con Google. Así que mi memoria de lo que realmente hicieron está todavía fresca;)
Sin decir nada que viole el NDA, puedo decirte esto: debes prepararte en varios temas, aunque no podrán preguntarte en todos ellos. Debes conocer los algoritmos básicos: ordenación por selección, ordenación por intercambio, quicksort, heapsort o mergesort, uso de listas, pilas, colas (de prioridad), árboles y tries; pero los gráficos son aún más importantes: depth first traversal, breadth first, Kruskal, Prim. Ciertamente, deberías saber cómo hacer todo esto utilizando las bibliotecas estándar de tu lenguaje, pero cuanto más puedas hacer sin bibliotecas, mejor.
Puede que no te pregunten explícitamente por ninguno de ellos, pero seguro que te pedirán un análisis de Big O que te resultará fácil si lo has seguido en todos los algoritmos anteriores. Espere tener que hacerlo en cualquier código que escriba en la pizarra como solución a un desafío de codificación.
Hay libros en el mercado abierto que mencionan todo esto, así como otras cosas que debe saber. «Cracking the Coding Interview» es un libro especialmente bueno, escrito por alguien que solía hacer estas entrevistas en Google y que todavía sigue casi el mismo estilo en CareerCup. Aunque no seguí todas sus recomendaciones, me sentí mucho mejor preparado para los retos que me plantearon porque había dedicado al menos una cantidad de tiempo considerable a seguir algunas de sus recomendaciones.
Ahora bien, dado que has dicho que lo que buscas es un puesto de firmware/embebido, supongo que los gráficos no son tan importantes como para muchos otros puestos en Google, muchos de los cuales implican problemas de software dominados por algún tipo de recorrido de gráficos. Pero los algoritmos básicos seguirán siendo importantes para el firmware, y el análisis Big-O particularmente importante.
Sin embargo, yo esperaría un cambio de enfoque entre los algoritmos: para el código de firmware/embebido, los desafíos de bit-twiddling son más relevantes, así que espera que el Fascículo 0 y 1 del Vol 4 de «El Arte de la Programación de Computadoras» de Knuth cubra los tipos de algoritmos sobre los que es más probable que te pregunten.
Hay un montón de buenos posts de Stack Overflow sobre la preparación para una entrevista de Google también. Incluso en reddit: How to Crack the Toughest Coding Interviews, por Gayle McDowell, ex ingeniero de Google y miembro del comité de contratación.
Por último, aquí hay una fuente sorprendentemente buena sobre todos los algoritmos: Dictionary of Algorithms and Data Structures (Diccionario de Algoritmos y Estructuras de Datos) mantenido por el NIST, antes conocido como NBS.