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


We Can Code Hackathon Ensenada 2016

We Can Code Hackathon 2016

Este fin de semana pasado, asistí por tercer año consecutivo al We Can Code Hackathon, organizado por la empresa Advancio en la ciudad de Ensenada, Baja California. A diferencia de los años pasados, en esta edición no había temas en específico, sólo programar algo cool.

Salimos de Mexicali a las 10:00, por lo que llegamos muy temprano a Ensenada (el registro comenzaba a las 17:00) y tuvimos tiempo de visitar a un amigo que estudia su maestría en el CICESE, y echarnos unas cheves en la playa

Cheves en la playa

con el objetivo de alcanzar el pico de Ballmer antes del hackathon, por supuesto.

A las 17:00 llegamos a la cede del evento, que era en el campus de CETYS Universidad, y como ya era tradición de años pasados, no teníamos ni idea de qué era lo que íbamos a hacer.

Varios integrantes del equipo habíamos leído sobre los WebTorrents en los últimos días y teníamos ganas de utilizarlos, así que de ahí partió la idea para desarrolla VideoWatch.Me (probablemente el link no sirva en el momento que lean este post).

VideoWatch.me

La idea de nuestro proyecto es un sitio web para compartir videos de forma distribuída.

YouTube, por mencionar un ejemplo, ha tenido últimamente problemas con sus usuarios, por sus EULAs restrictivos, la manera en que censuran videos que contienen propiedad intelectual de terceros (muchas veces bajo fair use), o sus políticas de no permitir a los creadores ganar dinero con sus videos si estos presentan ciertas temáticas. Sin embargo, la posición de esta plataforma es entendible: ellos hospedan los videos de sus usuarios, por lo que podrían llegar a tener problemas legales por el contenido de estos.

En VideoWatch.Me no existe tal problema, pues nosotros no hosteamos los videos, sino simplemento los magnet links. De hecho, nadie en particular tiene los videos en el sentido tradicional, pues estos se descargan de las computadoras de todos aquellos que lo estén viendo.

Otra ventaja del servicio es que no habría que esperar a que el video se "subiera" a la plataforma, sino que éste estaría listo para ser consumido desde el momento en que el creador lo decidiera.

Nos divertimos mucho creando este proyecto, aunque también tuvimos nuestros momentos de estrés. Al final se podría decir que "medio funcionó", porque nunca entendimos por qué dejaba de funcionar de repente.

El código está en GitHub (lo sentimos por el cochinero, es culpa de la desesperación).

A diferencia del año pasado, no ganamos ningún puesto ahora, pero por lo menos el tercer lugar se vino a Mexicali, con unos amigos de El Garage que hicieron un "bastón inteligente" para ciegos. Tendremos que pedirles la revancha el año que entra 😉.


¡Feliz día del programador!

Code Monkey

[javierrizzo@Kamino ~]$ node
> Math.round((new Date() - new Date(2016, 0, 0)) / (1000 * 60 * 60 * 24));
256  

El día de hoy es el ducentésimo quincuagésimo sexto (256) día del año, que es lo mismo que 28, o la cantidad de números que se pueden representar con un byte. Por eso es que hoy es el día del programador. Esta fecha normalmente se celebra el 13 de septiembre, pero como este año es biciesto, se recorre un día.

Como el 256 es el número FF en hexadecimal, el día se celebra usando una camisa azul (0000FF en RGB Web) o blanca (FF en muchos sistemas de 256 colores). Pero además de esto, hay muchas otras formas de celebrar, como

Muchos opinan que, en este día, los programadores debemos tomarnos un tiempo para reflexionar sobre lo que hemos aprendido o desarrollado referente a la programación en el año que ha pasado.

Por mi parte, empecé a trabajar como freelancer en Skyworks Inc. y como becario en el área de informática de CETYS Universidad. Los lenguajes que más he utilizado para proyectos personales son JavaScript y Haxe, mientras que para el trabajo es C#. Asistí a dos hackathones, y en menos de un mes asisitiré a otro más. También he tratado de difundir un poco mi gusto por la programación, con talleres de programación, electrónica y licencias libres en El Garage Project Hub.

Además de vestirme de azul, me uniré a la celebración programando en el trabajo, y usando una computadora vieja (necesaria para las prácticas de la clase de Diseño de Interfaces). ¿Tú cómo piensas celebrarlo?


Linux cumple 25 🎈🎉

Feliz cumpleaños Linux

El día de hoy, hace 25 años, Linus Torvalds anunció el desarrollo de su kernel con uno de los más famosos posts en la historia de la computación, en comp.os.minix de Usenet:

Hello everybody out there using minix -

I'm doing a (free) operating system (just a hobby, won't be big and professional like gnu) [...] it probably never will support anything other than AT-harddisks, as that's all I have :-(.  

Y boom. El sistema operativo que no iba a ser "grande ni profesional" se convirtió en el proyecto colaborativo más grande de la humanidad, y tan profesional que muchas de las más grandes compañías tecnológicas trabajan activamente para éste.

Linux Companies

Y es que es tan importante porque todos usamos Linux todos los días, aunque tal vez no lo uses en tu computadora personal: las páginas web, los smartphones Android, las SmartTVs (y otras Smart-cosas), varios automóviles, los PlayStation, las graficadoras de Texas Instruments, y muchos otros aparatos electrónicos de uso cotidiano funcionan gracias al kernel de Linux.

Así que este día les propongo:

Formas de celebrar el cumpleaños de Linux

  1. Hacer que tus amigos te compren una cerveza: Porque ya tienes un sistema operativo free (as in free speech) y ahora necesitas algo free (as in free beer).
  2. Colaborar en un proyecto de software libre: Para entrar al "tren del mame" del FOSS.
  3. Recompilar el Kernel: Porque eres valiente, paciente, y te gusta optimizar tu software al máximo. No olvides tus calcetines de la suerte.
  4. Instalar Linux: si no lo haz hecho antes, tiene que probarlo. Les dejo esta imagen que me gusta mucho:

Why use Linux

¡Feliz cumpleaños Linux!, vamos por 25 años más.


¡Feliz día de Debian #23!

Logo de Debian

Hoy 16 de agosto, como cada año, se celebra el día de Debian, porque hace exactamente 23 años se fundó este proyecto.

Debian "El sistema operativo universal" es uno de mis sistemas operativos (o distribuciones de GNU/Linux, como perefieras llamarle) favoritos. Lo uso en en este servidor web y lo usé durante mucho tiempo en mi PC, hasta que me cambié a Arch Linux hace poco más de un año. De hecho, mi primier distro fue Ubuntu, que es derivado de Debian.

Este día se celebra normalmente instalando Debian (¡duh!) o con eventos en varias ciudades del mundo (lástima que el que tengo más cercano es en la Ciudad de México, por lo que no es factible que asista a alguno). Pero también puedes celebrarlo viendo Toy Story, ya que las versiones de Debian llevan nombres de los personajes de ésta película, o informándote con la línea del tiempo oficial y con esta infografía:

Infografía de Debian

Y si tienes habilidades artísticas, deberías hacer un wallpaper para la próxima versión "Debian Stretch".

Muchas cosas importantes han salido de este proyecto, como el sistema de paquetes deb y muchas otras distribuciones de GNU/Linux. Quién sabe que le espera en los próximos años...


Verano Innovador SkyKids

Verano Innovador SkyKids

Esta semana (y la siguiente) se lleva a cabo el "Verano Innovador SkyKids", donde El Garage da cursos de varios temas de innovación y tecnología a niños hijos de empleados de Skyworks Inc.

Yo estoy encargado de dar uno de los cursos de electrónica con Arduino. Para este tipo de talleres (niños + Arduino) me gusta utilizar Scratch 4 Arduino, en vez del Arduino IDE, porque resulta más intuitivo para los niños y al mismo tiempo enseña la lógica de la programación.

El pasado miércoles el taller trató sobre las bases de la electricidad (resistencias, LEDs, protoboard, multímetro, voltaje, etc.), hoy viernes trató sobre las bases de la programación (Scratch) y la siguiente semana será juntar ambas para realizar proyectos con Arduino.

Los niños se divirtieron mucho en el taller de hoy, aprendiendo a programar al crear su propio videojuego, y me pidieron que pusiera sus juegos en mi sitio web.

Y como lo prometido es deuda, aquí están los juegos hechos por los "SkyKids".


Escribiendo un mismo documento de LaTeX en dos idiomas

CTAN Lion

Soy fanático de LaTeX. Creo que es la forma correcta de escribir documentos, pues muchas veces en procesadores de texto WYSIWYG (como MS Word), el documento puede verse bien, pero estar semánticamente incorrecto, y eso me molesta. LaTeX no te permite cometer esos errores.

Entonces tengo varios documentos escritos en LaTeX y, hasta ahora, tenía el problema de que algunos de ellos los necesitaba tanto en inglés como en español. Mi respuesta a este predicamento, como hubiera optado la mayoría, era escribir el documento en un idioma, crear una copia de este, y traducir la copia al segundio lenguaje. Sin embargo sentía que no era la manera correcta de hacer las cosas.

Sabía que tenía que haber una forma de escribir el código en ambos lenguajes y seleccionar uno de estos al momento de compilar.

Me puse a investigar y encontré una respuesta que me gustó en un foro de LaTeX:

Hacer un archivo .tex con comandos definidos como en el siguiente ejemplo:

\documentclass{article}

\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}

\usepackage[spanish,english]{babel}

\newcommand{\langes}[1]{%
  \ifes\selectlanguage{spanish}#1\fi}
\newcommand{\langen}[1]{%
  \ifen\selectlanguage{english}#1\fi}

\begin{document}

\section{%
\langes{Hola!}
\langen{Hello!}}

\langes{Éste texto está en Español.\\
las reglas tipográficas españolas  
\textit{deberían} aplicarse.}
\langen{This is text in English.\\
English typographic rules \textit{should} apply.}

Y compilarlo de la siguiente manera si lo queremos en español:

xelatex -jobname=document-es "\newif\ifes\newif\ifen\estrue \input{document}"  

o en en inglés:

xelatex -jobname=document-en "\newif\ifes\newif\ifen\entrue \input{document}"  

(Donde "document" es el nombre del archivo .tex y "document-es/document-en" es el nombre que tendrán los PDFs generados). Dando como resultado los siguientes documentos respectivamente:

Documento en español

Documento en inglés

Estoy muy satisfecho con esta técnica, ya empecé a aplicarla a mis documentos.


Dosis de Zeldas I

What if Zelda was a girl?


¡Este sitio web ya es seguro! (o cómo obtener HTTPS para tu sitio web)

HTTPS

HTTPS ha sido estándar desde el 2000, pero al día de hoy muchos sitios web siguen sin utilizarlo principalmente por tres razones:

  • Costo: Las empresas que emiten los certificados cobran por éstos al rededor de $250 USD anuales.
  • Carga en el servidor: Con HTTPS, la información transferida tiene que ser encriptada y desencriptada para poder ser leída, lo cual puee resultar en más trabajo para el servidor (aunque, seamos sinceros, es 2016... computar ya no es un problema).
  • Renovaciones: Renovar el certificado puede llegar a tomar mucho tiempo, debido a las verificaciones que se deben llevar a cabo.

Pero ya no más. Desde abril de 2016, Let's Encrypt ha estado ofreciendo certificados que son gratis, automatizados y abiertos.

El proceso es extremadamente sencillo, no me tomó más de 10 minutos generar el certificado y configurar la renovación automática. En el sitio web de Certbot, la herramienta que crearon con este propósito, puedes encontrar tutoriales para el sistema operativo y el webserver que estés utilizando.

Así que ya no hay excusa. Es 2016 y necesitamos proteger nuestra privacidad.


Seguridad esencial para servidores Linux

Seguridad

Me da mucho miedo el tema de la seguridad. Todo está roto y no importa que tanto te esfuerces, que tanto encriptes tus datos, siempre vas a cometer un descuido (especialmente si eres tan distraído como yo) y algún vivo se va a aprovechar de él.

Por eso no me atrevo a escribir una sola línea de código que tenga que manejar datos sensibles, y cada vez son menos los valientes: hoy en día, muchos sitios no te piden que crees una cuenta, sino que hagas login con tu cuenta de Facebook, Twitter o Gmail, porque ¿para qué guardar tus datos si Facebook ya lo hace y mejor de lo que yo podría llegar hacerlo?

Pero aunque mis necesidades de seguridad no son tan grandes, aún así mantengo un servidor (donde está alojado este blog), y es necesario implementarle, cuando menos, la seguridad más básica.

Por eso fue un alivio encontrar en HackerNews el siguiente artículo:

My First 10 Minutes On a Server - Primer for Securing Ubuntu,

que muestra como en 10 minutos puedes pasar de un servidor recién formateado, a un servidor seguro. Supongo que aquí también aplica el principio de Pareto: con el 20% del esfuerzo, puedes lograr el 80% de seguridad.

Los pasos ahí mostrados son para un servidor de Ubuntu, pero para cualquier otra distro es casi lo mismo.

Claro que esto no va a protejer, para nada, las aplicaciones hosteadas en este servidor, como dice el artículo, "ese es otro animal completamente", pero por lo menos nadie va a hacer login ni va a ejecutar programas si no se lo permites.