On Google plans for the Web

Now I’m talking publicly about progressive web apps and the future of Web development and the Internet, I’ve been asked a lot for my opinion about instant apps and, before instant apps, about why Google was trying to close the gap between the Web and native platforms, i.e. Android.

Actually, I don’t really know but despite the strategy would seem contradictory, after Google I/O it seems obvious to me: Google is running an experiment about switching its distribution platform. to bring more users to the search engine.

Why? Well, it makes sense that there should be a correlation between the time a user spends on Google search engine and the amount of money Google earns. So here is my assumption: given the marketplace is free from ads and most of the content is free, browsing the marketplace is not profitable or, at least, not as profitable as the Google search engine.

But we like applications, and to use applications implies some behaviour patterns, the result of all these years of mobile education. So, in order to make Web applications more appealing (and so, to increase the time a user spent in the search engine) why not to add native-application characteristics to Web applications?

In the other hand, it is Android. Another common question these days is: will we, Android developers, loose our jobs in the future? As if some of Android developers would feel threatened by progressive web apps in some way.

Well, honestly, I think no, at least in the near and mid time scenarios and Google has provided some extra warranties to make Android last for even more time. With Instant Apps, Google is closing the gap from the other end, it’s bringing to Apps what we like most from the Web: immediacy (no market, no download, no installation) and URLs so now we can search for Apps in Google engine. And that’s the point! No market, more time spent in Google search engine.

And why to bet for two approaches instead of one? Because it brings more users to the search engine and… they can (in terms of costs). If both initiatives succeed, both developer communities will be happy and users will spend their time into the most profitable distribution platform they can use: the Internet. Everybody win and the world is a wonderful place… for somebody. 😉

And that’s all folks! Notice that I could be totally wrong since all this is based on the premise that Google earns more money from the engine than from the market but there is some data to support my assumption out there (google it!) and, in the end, this is only speculation.

EDIT: I changed the nature of the experiment as it was not accurate enough. It is more clear now.

 

 

Mi segunda entrevista con Google

Bueno, antes de nada decir que no la he pasado, pero que no hay nada que lamentar. Estoy trabajando en Telefónica I+D desde hace tres semanas y me gusta mucho el puesto en el que estoy (sólo tengo que conseguir que me contraten ellos y no andar de subcontratado, jejeje).

Esta vez fueron otros 45 minutos; me puse muy nervioso y me trababa cada dos por tres. Es lo más negativo que observé de mi actuación: que me faltaban las palabras. De nuevo se dividió en dos partes: durante la primera tuve que describir mis experiencias trabajando y durante la segunda hacer algo de programación y analizar mis propios algoritmos. Salí muy convencido de que esta parte la había hecho bien pero, mira tú por dónde, hoy mismo me di cuenta de que hubo un par de problemas en mis respuestas.

En fin, espero que mis errores ayuden a otros. Vamos con el contenido de la entrevista.

Seguir leyendo “Mi segunda entrevista con Google”

Preguntas de entrevista de Google (con respuestas) II

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:

  1. Desbordamientos (y son un caso particular del segundo)
  2. 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:

  1. Reemplazar cada letra por el dígito correspondiente (A=1, B=2, C=3…)
  2. 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.

Preguntas de entrevista de Google (con respuestas)

Bueno, ayer me rechazaron en Gameloft. Pero vamos, estoy en tropocientos procesos de selección y no me precoupa demasiado. Al parecer uno de ellos parace que será con Google. Alguien de Google Careers se puso en contacto conmigo y me dijo que había pasado mi CV (del que tenéis una versión recién actualizada en el blog). Así que supongo que en me llamarán en breve. ¡Y voy a hacer trampas!

No, ahora en serio. Sencillamente se ha presentado una muy buena escusa para coger una lista de preguntas que Google acostumbra a preguntar y responderlas. Evidentemente no me las sé todas y la mayoría están buscadas por ahí pero espero que sirvan para el enriquecimiento personal y profesional de todo programador. Por supuesto, si alguien quiere proporcionar una respuesta mejor, que lo haga. Yo voy a intentar ser sencillo, abstracto e independiente de la implementación. A ver si hay suerte. Aquí van las 10 primeras:

Seguir leyendo “Preguntas de entrevista de Google (con respuestas)”