Experiencia de la entrevista de Microsoft Office India | Juego 170 (exp. 2 años)

Ronda 1:
validar una string de expresión aritmética infija (las llaves y los corchetes son similares a los paréntesis): (1+2)*{[90*3]-[67+8-9]}

Respuesta propuesta: Patio de maniobras de Djikstra

Respuesta del entrevistador: árbol analizador

La ronda 2:

Dado un estante de libros, clasifique esos libros de acuerdo con cualquier propiedad particular de un libro, por ejemplo, alfabéticamente aumentando el nombre del autor, la categoría, la fecha de publicación, etc. El valor de la propiedad del libro debe obtenerse de un servicio externo y la llamada es caro.

Restricciones: espacio O(1), las llamadas para obtener la prioridad de un libro deben minimizarse lo más posible.

Respuesta propuesta: clasificación rápida con un mapa de prioridad asociado con la propiedad del libro, un esquema de partición modificado donde la prioridad de cada elemento se obtiene una vez, total de llamadas nlogn.

Variación de la restricción: Swaps mínimos.

Respuesta propuesta:

1. Clasificación por selección con tiempo O(n^2) y espacio O(1). – n intercambios

2. Clasificación de cubos con O(n) espacio y tiempo. – 0 intercambios

Ronda 3:

Dada una string muy larga y un mapa de transformación, reemplace todas las ocurrencias de cualquier string de agujas con sus transformaciones resultantes, por ejemplo

input_string = “abcd;lt;qwer;gt;asd;”
map = {";lt;" : "<", ";gt;" : ">"}
transform(input_string, map) // should equal “abcd<qwer>asd;”

Respuesta propuesta: solución ingenua procesando carácter por carácter y reemplazando el sufijo si coincide con alguna de las agujas.