Problemas de la entrevista con Microsoft

Microsoft

A finales del noviembre pasado fui a la Ciudad de México a realizar cuatro entrevistas en las oficinas de Microsoft, con el fin de participar en un internship que se llevará a cabo el próximo verano. Varios conocidos me han preguntado sobre los problemas que me pusieron en las entrevistas, por lo que he decidido escribir este post.

Los problemas podían resolverse en cualquier lenguaje, pero sin utilizar nada que no estuviera en la librería estándar de C, por lo que decidí resolverlos en éste.

Intentaré que el código que ponga aquí se parezca lo más posible a lo que contesté durante las entrevistas, pero como programé en papel, probablemente se me pasaron unos cuantos errores de sintaxis, o algún error tonto de lógica.


Problema 1: Árboles binarios de búsqueda

El primer entrevistador era de nacionalidad hindú y trabajaba en el equipo de actualizaciones, tanto de Windows como de Xbox.

Comenzó preguntándome un poco de teoría de estructuras de datos: ¿qué es un árbol binario?, ¿cuál es la diferencia entre un árbol binario y un árbol binario de búsqueda?, y otras preguntas similares. Ya que contesté las preguntas, me puso el siguiente problema:

Implementa una función que convierta un arreglo en un árbol binario de búsqueda.

struct node {
  int value;
  struct node *left;
  struct node *right;
};

void insert_value(struct node *root, int value) {
  struct node *current = root;
  int found = 0;
  while(!found) {
    if(value <= current->value) {
      if(current->left == NULL) {
        found = 1;
        current->left = malloc(sizeof(struct node));
      }
      current = current->left;
    } else {
      if(current->right == NULL) {
        found = 1;
        current->right = malloc(sizeof(struct node));
      }
      current = current->right;
    }
  }
  current->value = value;
}

struct node *array_to_tree(int *array, int len) {
  struct node *root;
  if(len >  0) {
    root = malloc(sizeof(struct node));
    root->value = array[0];
    for(int i = 1; i < len; i++) {
      insert_value(root, array[i]);
    }
  }
  return root;
}

Una vez terminada mi tarea, añadió un poco más de dificultad a ésta:

Implementa una función que permita eliminar un valor del árbol.

void insert_tree(struct node *root, struct node *to_insert) {
  if(to_insert != NULL) {
    insert_value(root, to_insert->value);
    insert_tree(root, to_insert->left);
    insert_tree(root, to_insert->right);
    free(to_insert->left);
    free(to_insert->right);
  }
}

struct node *delete_value(struct node *root, int value) {
  struct node *current = root;
  struct node *parent = NULL;
  while(current->value != value) {
    if(value < current->value && current != NULL) {
      parent = current;
      current = current->left;
    } else {
      parent = current;
      current = current->right;
    }
    if(current == NULL) return root;
  }
  if(parent != NULL) {
    if(parent->left == current) {
      parent->left = NULL;
    } else {
      parent->right = NULL;
    }
    insert_tree(parent, current->left);
    insert_tree(parent, current->right);
  } else {
    if(current->left != NULL) {
      root = current->left;
      parent = current->right;
      current->right = NULL;
      insert_tree(root, parent);
    } else if(current->right != NULL) {
      root = current->right;
      parent = current->left;
      current->left = NULL;
      insert_tree(root, parent);
    }
  }
  return root;
}

Los problemas de este entrevistador fueron bastante sencillos, muy teóricos, supongo que sólo estaba probando mi conocimiento sobre estructuras de datos.

Problema 2: Invertir palabras

Implementa una función que, dada la cadena "I love Mexico City, and I love to code", la convierta en "I evol ocixeM ytiC, code to love I and".

La segunda entrevistadora también era de origen hindú y trabajaba en el equipo de Bing.

Éste creo que fue el problema más truculento, porque la entrevistadora quería cierto nivel de eficiencia, o sea, que no recorriera la cadena varias veces. Me tomó bastante rato darme cuenta de que si volteaba cada palabra de la oración como lo pide antes de la coma

I evol ocieM ytiC, dna I evol ot edoc

y luego volteaba toda la oración a partir de la coma, quedaría la cadena buscada

I evol ocieM ytiC, code to love I and

Una vez notado ésto, fue sencillo programar la función:

void reverse(char string[], int len) {
  int comma_i = 0;
  int last_space = -1;
  char b;
  for(int i = 0; i <= len; i++) {
    if(string[i] == ' ' || string[i] == ',' || i == len) {
      for(int j = i - 1; j > (last_space + i) / 2; j--) {
        b = string[j];
        string[j] = string[last_space + i  - j];
        string[last_space + i - j] = b;
      }
      last_space = i;
      if(string[i] == ',') comma_i = i;
    }
  }

  for(int i = len - 1; i >= comma_i + 2 + (len - comma_i - 1) / 2; i--) {
    b = string[i];
    string[i] = string[comma_i + len + 1 - i];
    string[comma_i + 1 + len - i] = b;
  }
}

Problema 3: Bolsa de valores

Implementa una función que, dado un arreglo de 24 números que representan el valor de una acción a lo largo de las 24 horas del día, retorne las horas de compra y venta óptimas para obtener la mayor ganancia.

La tercera entrevistadora era originaria de Ucrania y trabajaba en varios productos relacionados con cloud computing, entre ellos Azure.

Este problema también requirió que pensara un rato para idear la manera eficiente de recorrer el arreglo.

int *shares(double values[]) {
  static int result[2] = {0,1};
  int local_l = -1;
  for(int i = 2; i < 24; i++) {
    if(values[i] < values[result[0]]) local_l = i;
    if(values[i] > values[result[1]]) {
      result[1] = i;
      if(local_l > result[0]) result[0] = local_l;
    }
  }
  if(values[result[0]] >= values[result[1]]) return NULL;
  return result;
}

Problema 4: Fechas

Implementa una función que, dado el string "12/10/2016", retorne "December 10, 2016".

El último entrevistador era de Turquía y trabajaba en Windows Defender.

Este problema me pareció super sencillo cuando me lo explicaron y comencé a "resolverlo" de inmediato, hasta que se me ocurrió preguntar si debía validar el string ingresado y me dijeron que sí, lo que aumentó un poco de dificultad, pero nada del otro mundo.

char *months[] = {"January", "February", "March", "April", "May", "June",
  "July", "August", "September", "October", "November", "December"};

struct date {
  int day;
  int month;
  int year;
};

int is_leap_year(int y) {
  if(y % 4 != 0) return 0;
  else if(y % 100 != 0) return 1;
  else if(y % 400 != 0) return 0;
  else return 1;
}

int is_valid_month(int m) {
  if(m >= 1 && m <= 12) return 1;
  return 0;
}

int has_valid_format(char date[]) {
  if(strlen(date) == 10) {
    if(
        isdigit(date[0]) && isdigit(date[1])
        && date[2] == '/'
        && isdigit(date[3]) && isdigit(date[4])
        && date[5] == '/'
        && isdigit(date[6]) && isdigit(date[7]) && isdigit(date[8]) 
        && isdigit(date[9])
      ) return 1;
  }
  return 0;
}

int c_to_i(char c) {
  return c - 48;
}

struct date *string_to_date(char datestr[]) {
  struct date *d = malloc(sizeof(struct date));
  d->month = c_to_i(datestr[0]) * 10 + c_to_i(datestr[1]);
  d->day = c_to_i(datestr[3]) * 10 + c_to_i(datestr[4]);
  d->year = c_to_i(datestr[6]) * 1000 + c_to_i(datestr[7]) * 100
    + c_to_i(datestr[8]) * 10 + c_to_i(datestr[9]);
  return d;
}

int is_valid_day(struct date *d) {
  if(d->day < 1) return 0;
  switch(d->month) {
    case 1: case 3: case 5: case 7: case 8: case 10: case 12:
      if(d->day <= 31) return 1;
      break;
    case 4: case 6: case 9: case 11:
      if(d->day <= 30) return 1;
      break;
    case 2:
      if(d->day <= 28) return 1;
      if(is_leap_year(d->year) && d->day == 29) return 1;
      break;
  }
  return 0;
}

int is_valid_date(struct date *d) {
  if(is_valid_month(d->month) && is_valid_day(d)) return 1;
  return 0;
}

char *convert_date(char date[]) {
  static char new_date[18] = {0};
  if(has_valid_format(date)) {
    struct date *d = string_to_date(date);
    if(is_valid_date(d)) {
      sprintf(new_date, "%s %d, %d", months[d->month - 1], d->day, d->year);
      free(d);
      return new_date;
    }
    free(d);
  }
  return NULL;
}

Una semana más tarde, me enviaron un correo electrónico avisándome que había pasado las entrevistas y me ofrecían un empleo de verano en Seattle, Washington, específicamente en el equipo de Bing.

MS Interview Results