Seguimos con otras diez preguntas de entrevista de Google tras la primera entrega de esta serie. Insisto en que si conoceis mejores respuestas o soluciones las pongais en los comentarios.
#11 ¿Cómo se pasan las cookies en el protocolo HTTP?
Bueno, esta me parece bastante fácil. Las cookies, que no son más que pares clave=valor se pasan como texto plano en las cabeceras de cualquier petición o respuesta HTTP. Cuando el explorador realiza una petición, pasa las cookies tal cual se las mandó el servidor simulando así una suerte de «estado persistente».
Puede encontrarse información sobre el protocolo HTTP y las cookies en particular en Wikipedia.
#12 Escribe una expresión regular que acepte direcciones de correo
Divide y vencerás: la estructura de un correo electrónico es [usuario]@[host] así que ya podemos hacer una versión inicial de la expresión regular:
()@()
Tenemos que rellenar esos corchetes. Vamos con el host que tiene una forma como [subdominio].[dominio]. Ese punto final es optativo (se supone que todos los FQDN lo llevan en su normalización) así que la expresión regular para el host será algo como:
([a-zA-Z0-9][a-zA-Z0-9-]*\.)+[a-zA-Z]+(\.)?
Es más o menos correcto. El primer grupo entre corchetes obliga a que el nombre del dominio empiece por un carácter alfanumérico. El segundo acepta el resto de caracteres (alfanuméricos y el guión) y hace terminar la cadena en punto. Todo esto podemos repetirlo indefinidamente (en realidad un nombre de dominio sólo puede tener hasta 253 caracteres). Debemos terminar con una extensión que representa un dominio de primer nivel formado por caracteres alfabéticos (al menos, uno) y el punto optativo final. Los puntos están precedidos de la barra para que no sean considerados caracteres especiales.
Ahora, el nombre de usuario depende. Pongamos algunas reglas. Supongamos que solo permitimos caracteres alfanuméricos, guiones bajos, puntos y símbolos de sumar y restar y que debe comenzar por un carácter alfanumérico o guión bajo . Su longitud mínima será de 1 caracter. Tenemos pues:
[_a-zA-Z0-9][_a-zA-Z0-9-+.]*
Ahora, combinando las tres, tenemos:
([_a-zA-Z0-9][_a-zA-Z0-9-+.]*)@(([a-zA-Z0-9][a-zA-Z0-9-]*\.)+[a-zA-Z]+(\.)?)
Y listo, ese churro valida direcciones email.
Os invito a probarlo en RegexPal.
#13 Escribe una función f(a, b) que toma dos cadenas de caracteres y devuelve otra sólo con los caracteres comunes en el orden en el que aparecen en a. Escribe una versión que ejecute en orden N cuadrado y otra en orden N.
Vamos a suponer caracteres alfabeticos y en minúscula:
La primera solución que se nos puede ocurrir es algo como esto (en Python).
def f(a,b):
r = ''
for c in a:
if c in b and c not in r:
r += c
return r
Esta solución es N cuadrado pues el hecho de comprobar si el caracter c está o no en b supone un recorrido por los caracteres de b. Así que tenemos un bucle de longitud(b) dentro de otro de longitud(a) luego longitud(a)*longitud(b) pertenece a O(N^2). Esto es notación O que supongo que a cualquier ingeniero le sonará de algo.
La solución N es también muy fácil. Para ello necesitamos una función auxiliar que haga a=0, b=1, c=2…
def alpha_to_index(c):
return ord(c)-ord('a')
def f(a,b):
l = [0]*26
for c in b:
i = alpha_to_index(c)
if not l[i]:
l[i] = 1 # Indica aparición en b
r = ""
for c in a:
i = alpha_to_index(c)
if l[i] == 1:
r += c
l[i] = 2 # Indica ya añadida al resultado
return r
Este algoritmo se ejecuta en longitud(a)+longitud(b) que pertenece a O(n) Para quitar las restricciones de minúscula y caracteres alfabéticos, en vez de un array se usa un hashmap (un diccionario en Python) para albergar el estado de los caracteres.
En breve dedicaré un post a la notación O y a cómo calcular el coste de un algoritmo.
#14 Te dan un código fuente que se rompe en cada ejecución. Tras ejecutarlo 10 veces en un depurador te das cuenta de que nunca se rompe dos veces por el mismo sitio. El código fuente sólo usa un hilo y la biblioteca estándar de C. ¿Qué errores de programación podrían estar causando los problemas? ¿Cómo podrías probar cada uno?
A mi se me ocurre que las causas pueden ser principalmente dos:
- Desbordamientos (y son un caso particular del segundo)
- Comportamientos indefinidos
Para probarlos cogería un lista de comportamientos indefinidos y probaría que no se están ralizando asunciones erroneas. Para los desbordamientos comprobaría los casos típicos (desbordamiento de array, de paso de parámetro, copia de arrays…).
#15 Explica cómo funciona el control de congestión en el protocolo TCP
La verdad es que este no es mi fuerte así que si alguien se sabe otra forma más sencilla de explicarlo, estaré encantdo de rectificar la respuesta. Entre lo que recuerdo de redes y lo que he sacado de la Wikipedia, la explicación se parece a esto:
El típico (porque hay varios) consiste en variar el tamaño de la llamada ventana de congestión mediante un algoritmo llamado Slow-Start. La necesidad del protocolo surge porque los extremos de una conexión TCP no tienen manera de saber a priori la calidad la red. En principio, no pueden saber el tamaño máximo del datgrama (los datos enviados en TCP) que causaría la mayor tasa de transferencia sin desbordar la capacidad de la ruta seleccionada.
Encontrar este óptimo es tarea del algoritmo de control de congestión. Para ello, el emisor cuenta con una ventana de congestion que especifica cuántos datagramas enviará de golpe. La ventana comienza al tamaño máximo de un datagrama y cada vez que se acusa un recibo se dobla. Eventualmente se superará un umbral llamado sstresh que hará que la ventana aumente linealmente. En el momento en que la cantidad de datagramas satura la red se comienzan a perder paquetes y se produce una de las siguientes situaciones:
- Si se detecta un timeout, la ventana se reestablece al tamaño máximo de un datagrama.
- Si en vez de un timeout, se detectan tres acuses iguales, la ventana se reduce a la mitad del mínimo entre la ventana de congestión y la ventana de recepción (el tamaño máximo del datagrama que el nodo está dispuesto a aceptar por vez).
#16 En Java, ¿cuál es la diferencia entre final, finally y finalize?
Yo me sabía dos (final y finally):
- final es un modificador de tipo. En variables indica que, una vez inicializada en el constructos, no puede volver a ser modificada. En clases indica que no se puede heredar de ella.
- finally es una clusula del bloque try / catch que indica qué se debe hacer finalmente, antes de continuar la ejecución
- finalize es el método al que invoca el recolector de basura al ir a destruir un objeto
Fuente: http://www.janeg.ca/scjp/gc/finalize.html
#17 ¿Qué es la programación multihilo? ¿Qué es un deadlock?
La programación multihilo hace referencia a distintas líneas de ejecución dentro de un programa. Cada línea de ejecución es un subprograma que mantiene su propio estado y es independiente de los demás. La comunicación se realiza mediante el traspaso de mensajes o a través de recursos compartidos. El acceso a estos recursos compartidos promueve toda una nueva serie de problemas relaccionados con el acceso simultáneo a los mísmos.
Un deadlock o interbloqueo es un problema de sincronización que se da cuando el hilo A se encuentra esperando un recurso del hilo B y viceversa. He encontrado un ejemplo muy claro de interbloqueo en el blog de JASoft.org
En él se nos invita a pensar en un proceso que transfiere dinero entre dos cuentas. Obviamente el proceso trata de obtener un acceso exclusivo a cada cuenta al comienzo de su ejecución por si ya hay otro proceso manipulando dicha cuenta. Si una cuenta está en uso, el hilo que la requiere esperará (haciendo nada) hasta que sea liberada.
Ahora supongamos que se producen dos transferencias en sentidos contrarios. Ambos procedimientos comenzarán por bloquear sus cuentas origen pero al tratar de bloquear las cuentas destino se encontraran con que tal cuenta ya se encuentra bloqueada. Y lo que es peor, de esta situación no saldrán nunca.
Fuente: http://geeks.ms/blogs/jalarcon/archive/2011/04/29/191-qu-233-es-un-deadlock-o-interbloqueo.aspx
#18 Escribe una función toExcel(v) que coja el valor de una columna excel (A, B, C, …, AA, AB, …, AAA) y devuelva su valor entero (A=1, B=2, C=3, …, AA=27…)
Este ejercicio es muy interesante pero aun lo es más el contrario. Para abordarlo, vamosa reducir al conjunto de letras a A, B y C. Ahora tenemos que A=1, B=2 y C=3 y la secuencia es A, B, C, AA, AB, AC, BA, BB, BC, CA, CB, CC…
Si recordais el post con el que (casi) abrimos el blog, relacionado con las bases de numeración y con el hecho de que la suma de 1 y 1 sea 10 en binario, vereis que esto se acerca mucho a contar en base 3. El problema es que los dígitos en base 3 son 0, 1 y 2; y no 1, 2 y 3 (o A, B y C) como ocurre en este caso. Resulta que en este problema no contamos con ningún dígito que represente el 0 pero sí con uno que representa la base.
Bien, vayamos primero con el problema contrario. Transformemos, por ejmplo, 12 en CC.
El número 12, escrito en base tres tiene la siguiente pinta: 110 dado que puede expresarse como 1*3^2 + 1*3^1 + 0*3^0 Ahora bien, como no contamos con ningún símbolo para representar el 0 pero sí par representar el 3, vamos a ajustar 110 tratando de quitar los 0s. Podemos quitar una «decena» y añadir 3 unidades lo que resulta en 103 cuya descomposición sería 1*3^2 + 0*3^1 + 3*3^0 que sigue siendo 12. Ahora tenemos un 0 más así que quitamos 1 «centena» y ponermos 3 «decenas» quedando 033. Como los 0s a la izquierda no importan pues ya hemos terminado y su descomposición es 0*3^2 + 3*3^1 + 3*3^0 que sigue siendo 12. Ahora reemplazamos cada dígito por su letra quedando CC.
De aquí puede inferirse fácilmente el algoritmo de transformación que nos piden y puede resumirse en dos sencillos pasos:
- Reemplazar cada letra por el dígito correspondiente (A=1, B=2, C=3…)
- Interpretar en base 3 (o, generalmente, en base la longitud del conjunto de símbolos)
def char_to_index(c):
return ord(c) - ord('A') + 1
def toExcel(v):
l = len(v)
r = 0
for i in range(l):
c = v[i]
r += char_to_index(c) * (26**(l-i))
return r
El caso contrario requiere el estudio de un caso más. Pongamos que queremos transformar 9 en BC. 9 en base tres es 100. Empezamos quitando 0 de más a la derecha: quitamos 1 «decena» y añadimos 3 unidades resultando en 1-13 cuya descomposición sería 1*3^2 – 1*3^1 + 3*3^0 que sigue siendo 9. Como tampoco tenemos símbolos para números negativos quitamos 1 «centena» y añadimos 3 «decenas» quedando 023 cuya descomposición es 0*3^2 + 2*3^1 + 3*3^0 que sigue siendo 9. Ahora reemplazamos cada dígito por su letra lo que nos lleva a BC.
El algoritmo supone modificar ligeramente el clásico de las divisiones y restos utilizado para transformar a una base dada (comprobado que funciona):
def char_to_index(c):
return ord(c) - ord('A') + 1
def index_to_char(i):
if not i:
return ''
return chr(ord('A') + i - 1)
def fromExcel(n):
res = []
d = n
fixmode = False # Indica que estamos en modo ajuste (restar 1 al siguiente resto y añadir 26 al actual)
while d >= 26:
r = d%26
# Si estamos ajustando los restos, asumimos que ya hemos añadido 3 al anterior y le quitamos uno a este
if fixmode:
r -= 1
# Si es (o queda) negativo, le sumamos veintiseis y pasamos (o conservamos) el modo de ajuste
if r<=0:
r += 26
fixmode = True
# Si no lo es, dejamos el modo de ajuste
else:
fixmode = False
res.insert(0, r)
d = int(d/26)
res.insert(0, d)
return ''.join(map(index_to_char, res))
#19 Si tienes 1 millon de enteros. ¿Cómo los ordenarías eficientemente? Modifica un algoritmo conocido para hacerlo.
Dedicaremos en breve otro post a los algoritmos de ordenación. Baste decir que para tal cantidad de datos se prefieren estrategias «divide y vencerás». Primeramente el milllón de datos puede separarse en tramos (digamos de 10000 ó 100000) enteros y ordenarse separadamente mediante qsort. Luego pueden mezclarse con merge sort.
También se podría haber aplicado merge sort directamente.
Ojo, si nos dan límites de memoria entonces tendremos que ir poco a poco. Leer unos cuantos, aplicar una técnica anterior, escribir el resultados; leer otros pocos, volver a aplicar una técnica y volver a escribir el resultado… Al final, habrá que mezclar los archivos ordenados.
Fuente: teneis aquí una solución por Guido van Rossum con código en Python 3.0
#20 Tienes un flujo continuo e infinito de consultas (las consultas de Google que la gente introduce). Describe como podrías tomar una buena estimación de 1000 muestras de este conjunto inagotable de datos.
Esta pregunta no la entiendo y, sencillamente, preguntaría por más información. ¿Qué característica tienen que cumplir estas mil muestras? Supongo que se referirá a las 1000 consultas más solicitadas. Para ello se puede usar una estructura de datos (que acabo de descubrir) llamada splay-tree o árbol biselado que no es otra cosa que un árbol binario con la propiedad de que los elementos más recientemente accedidos pueden recuperarse más rápidamente.
Esta solución del árbol biselado requiere alguna normalización que convierta las consultas en números. Se podría utilizar alguna función hash.
Si esta no es la característica que deben cumplir las muestras, entonces la solución cambia. Por ejemplo si tiene que ser aleatoria se puede dividir el conjunto de consultas en 1000 segmentos y seleccionar un elemento al azar de cada uno.
EDIT: Según un comentario (con el que estoy de acuerdo) de Jisakiel en Facebook, la muestra debería cumplir normalidad. Ahora bien, estamos en las mismas, normalidad sí pero ¿respecto de qué? Si nos asaltan con esta pregunta, es nuestra obligación fusilar al entrevistador con aclaraciones hast que sepamos exactamente las propiedades de la muestra.
Uno + uno = diez 