Antecedentes
Fue una entrevista telefónica para el ingeniero de software en el puesto de prueba aplicado en Google, Kirkland, Washington Office.
{Antecedentes del candidato: más de 8 años de experiencia en el área de desarrollo de software / herramientas de prueba}
- Mañana tengo una entrevista para un puesto de ingeniero integrado (ver descripción). ¿Qué preguntas puedo esperar en general y en el aspecto técnico?
- ¿Cómo son las entrevistas de ingeniería de software de Google Hyderabad?
- Se le proporciona una matriz A de k valores que contienen valores int en orden ordenado (asec). Encuentre los valores de k superiores (asec) que pueden ser el número de la matriz A, o la suma de dos números de A o la suma de tres números de A.?
- ¿Cuáles son algunas de las últimas preguntas de la entrevista de programación de Google?
- ¿Cómo se convirtieron las preguntas sobre estructuras de datos y algoritmos en la norma para las entrevistas tecnológicas?
Pregunta
Dada una cadena, encuentre la posición de inicio del bloque más grande de caracteres repetidos.
Proceso de pensamiento para diseñar la solución
Se puede implementar un algoritmo simple en O (N), porque solo necesitamos considerar bloques de caracteres consecutivos (subcadenas) en la cadena dada. El algoritmo que implementé tomó los siguientes pasos:
· Supongamos que nuestra cadena (llámela s) es “aacdefaaaabbccc”;
· Comenzamos desde la primera posición y nos movemos hacia la derecha siempre que el personaje permanezca igual, deteniéndose cuando nos encontramos con otro personaje; por ejemplo, el primer paso consideraría los dos primeros ‘aa’ y se detendría en ‘c’;
· Cada vez que dejamos de contar, si la longitud del bloque actual es mayor que cualquier bloque que hayamos encontrado hasta ahora. Por ejemplo, cuando nos detenemos en la ‘b’ después de ‘aaaa’, estableceríamos el máximo global en 4.
· Finalmente, simplemente devolvemos la posición correspondiente al inicio de la subcadena más larga que contiene los mismos caracteres.
Piezas resistentes
No pensé en varios otros casos, por ejemplo
– ¿Qué sucederá si los caracteres repetidos tendrán el mismo recuento, por ejemplo, aabb, aquí 2 a’s y 2 b’s?
– ¿Qué hay de los espacios entre la cadena, por ejemplo, Sumit tt? Entonces se detendrá aquí o contará tres t repetitivos
– ¿Qué hay de los caracteres de un solo byte y de varios bytes?