More Interview Questions

All interviews are different, all candidates are different, all positions are different. The goal here is to provide some general questions to test engineering skills of candidates. These questions are common in recruiting process in technical companies like Google or Verisign.

How could you detect a loop in a linked list ? 

It's say linked list, to be more precise you only have a pointer to the head of the list, and you know how to move to the next element of the list.
Of course you are not allowed to modify the list at all. And obviously you should try to propose an algorithm that do it in the most efficient way, let say you should try to target O(n).

In more programmer oriented : write a function A that take as parameter the first element of a List and return a boolean with value true if the given List has a loop, false otherwise. You know how to pass to the next element of the List : just call element.next.

For those who want to try to answer by themself, stop reading here.

One good answer is to have 2 iterators that walk through the elements of the List, but at different speed. One iterator move from 1 element per iteration, the second one move from 2 elements per iteration, and check if it meet the first iterator during it's move. How fast goes the second iterator can be configurable.
If at one point the second iterator (fast moving) meet the first one, there is a loop in the List. If the second iterator reach the end of the List, there is obviously no loop.

In pseudo code, it would be :

function A (head element of List list) return boolean :
it1 is initialized to the head element of list
it2 is initialized to the head element of list
while it2 has not reach end list
    for number of element it2 will move
        it2 move to the next element.
        if the element of it2 is equal to the element of it1
            there is a loop ! return true
    it1 move to the next element
there is no loop. return false

As targeted, this algorithm will be on complexity of O(n), as the worst case is the last element looping to itself. When the last element loop to the first one, the algorithm will detect the loop in n / speed of the second iterator.
And finally, the memory footprint is very low.

What are the advantages of a LinkedList over an ArrayList ? 

This question is more often ask in a different way : what are the differences between a LinkedList and an ArrayList. But turning the question up side down like here is a bit more interesting. So what are the advantages ?

The basic advantage of the LinkedList is its O(1) insertion and deletion complexity for any given element, while ArrayList need to move back or forth the elements after the given element. Another advantage is the linearly increasing memory footprint of a LinkedList, when ArrayList memory (still linear but) increases by steps, and then perform sometimes costly memory copies. With such memory copies ArrayList have an amotized complexity in O(1), but this leads to non deterministic operations, which are unwanted when dealing with tight SLAs.
One more hidden advantage of the LindekList is still in the topic of memory usage : it does not require to allocate blocks of memory, elements stored in LinkedList do not require to be allocated in contiguous memory. Just notice that fragmentation of the memory is not always seen as good point.

Eventually Consistency demystified

In my crusade into the NoSQL world, Eventually Consistency is everywhere. I want to demystify this property a little bit here.

But let's begin with an example to have the same base for the discussion :

• Let "Node1", "Node2" and "Node3" be three nodes (servers) that are part of our distributed datastore.
• Let "User A", "User B", "User c" be three users wanting to read and write data in our fictive distributed datastore.

At time (1), "User A" write the value "A" to "Node1". "Node1" will replicate asynchronously this value to both "Node2" and "Node3" (specific to my example).
At time (2) the write call of "Node A" returns. But the replication of value "A" hasn't been completely propagate to "Node2" and "Node3".
At time (3), "User B" and "User C" will read value "A" from "Node1" and "Node2" respectively. "User B" got the latest value (because it reads the node which initiate the update), "User C" will read either the old or the new version of "A", but without any guarantee regarding what it will read.



In a future time (5), "User B" and "User C" re-read value "A" and then got the same value. At this point of time, the datastore is consistent.

Immediate Consistency

In a Immediate Consistency, opposing Eventually Consistency, the write call from "User A" should wait till the replication is done on other nodes before returning, and replica nodes ("Node2" and "Node3") should be synchronized to expose the new value at the same time.

Moreover, if "Node1" is unable to talk to "Node2", the write replication will probably fail then the write call from "User A" will fail.

As we can notice, Immediate Consistency is hard to scale (see two-phase commit or paxos algorithm), because it increases the latency of the writes and makes the system not redundant to failure.

Trade-off for scaling writes

Eventually Consistency is then a trade-off for scaling writes that seems reasonable in certain use-cases.

DNSSEC NSEC3 domain hash computation algorithm

DNSSEC is a DNS extension in order to authenticate and ensure integrity of DNS responses, in order to offers protection against DNS spoofing.

DNSSEC comes with two "denial of existence" mechanism : NSEC (RFCs 4033, 4034, 4035) and NSEC3 (RFC 5155).

Now how "denial of existence" works ?

When a query is performed on a non-existing domain, a specific answer is returned to the resolution client, given the closest domains that are alphabetically before and after the queried domain. But what is very sensible in this way of proving the non-existence of a domain is that we can easily enumerate the whole zone.

That's why NSEC3 was designed to prove the non-existence of a domain, but in the same time to avoid the zone walk through.
Instead of simply returning the closest domains, it returns a hash of the domains.

How to compute NSEC3 Hash ?

I will detail a little bit how this NSESC3 hash is computed :

I you have a look at a zone, you will find additional records, like NSEC3PARAM :

example.com. NSEC3PARAM 1 0 12 aabbccdd

The format of such record is composed of :

• an algorithm field. 1 means SHA1
• a flags field
• an iterations field
• a salt, represented as a sequence of case-insensitive hexadecimal digits.

Then the hashing algorithm is given by :

 IH(salt, x, 0) = H(x || salt), and
IH(salt, x, k) = H(IH(salt, x, k-1) || salt), if k > 0

With my example.com domain, the hash algorithm will be :

IH(fromHexStringToByte("aabbccdd"), toCanonicalWireFormat("example.com"), 12)

fromHexStringToByte is a base 16 decoder : fromHexStringToByte("aabbccdd") = [0xaa, 0xbb, 0xcc, 0xdd]. See RFC4648

toCanonicalWireFormat convert the domain in wire format using its canonical form : toCanonicalWireFormat("example.com") = [0x07, 0x65, 0x78, 0x61, 0x6d, 0x70, 0x6c, 0x65, 0x03, 0x63, 0x6f, 0x6d, 0x00]. See RFC4034 (canonical form), RFC3845 (wire format)

And that's it, you are now able to compute the NSEC3 hash of your favourite domain. You just need to wait for NSEC3PARAM to be published in the respective zone to got all the necessary parameters :)

Sequences scalability

Sequences are central part of most computer systems. They are used both in technical part (generate unique identifier for object) and in business part (count the remaining free tickets which can be sold).

When the load on the application goes higher, sequences become quickly central bottlenecks of systems. So the goal here is to first categorize different types of sequences and then gives some keys to see how sequences be distributed to increase their scalability, and hence the global scalability of the whole system.

Characteristics of sequences :

Order : the number generate should be used in a given order (ascendant or descendant), or the order do not matter. I will talk about ordered or unordered sequence.

Missing values : some values can be missing in the sequence. For example the sequence miss the value 4 should not alter the behavior of the application. I will talk about continued or discontinued sequence.

Finite sequence : all the values of the sequence are know and countable. Countable sequences are particular case of finite sequence where the sequence has a reasonable amount of values, and thus could be represented by one object per values. I will talk about finite or infinite sequence, and countable sequence.

Key to distribute sequences

Discontinued sequences are easy to scale : the application can pick numbers n by n in the sequence, reducing the amount of calls to the sequence by n. Good example for of discontinued sequences are objects identifier generators.

Unordered sequences are also easy to scale : a counter can be decomposed in n subcounter, picking at random one of the subcounter to increment or decrement will reduce the contention on one counter by n. A typical example is a quantity of object to sell. N subcounters are initialized with the sum is the total amount to sell. The object cannot be sold anymore when every subcounters are at 0.

Countable sequences can be scaled by representing every value of the sequence as a single object in the database. Updating an unused object is a easy task.

Finaly infinite, continued ordered sequence are very hard to scale because synchronization between all callers is required, so a single point of contention is mandatory.

Conclusion

Sequences are choke point in most systems, but as we saw above they can scale relatively simply with two simple tricks : read number n by n instead of 1 by 1, or decompose a counter in n subcounters.

Des nombres à usage unique (nonce)

Afin de répondre à une problématique de transmission d'informations sensibles sur un réseau pas sûr (Internet donc...), une solution est l'utilisation de nonce, diminutif de number used once, nombre à usage unique.

Ils sont utilisé pour mettre du sel dans des informations sensibles qui seront ensuite hashées et transmises en clair sur le réseau. Mais leur efficacité n'est effective seulement si on a la garantie qu'un même nonce ne va jamais être utilisé 2 fois !

Exemple type : vous développez un service d'authentification, mais celui-ce ne peut se faire sur du SSL. Vous souhaitez toutefois que si une personne intercepte les informations, elle ne puisse pas les réutiliser pour s'identifier à son tour.

Le seul hashage du mot de passe ne suffisant pas car la personne qui a interceptée le mot de passe hashé pourra rejouer la séquence pour simuler sa connexion, une solution est de hasher le mot de passe concaténé au nonce (du style sha256("#" + mot de passe + "#" + nonce + "#")), puis de transmettre le nom d'utilisateur, le nonce utilisé et le résultat du hashage. Le serveur disposera ainsi de toutes les informations pour vérifier si le mot de passe utilisé pour le hashage était effectivement correcte ou pas. Les prochaines requêtes faites avec ce nonce seront systématiquement refusées.

C'est pour faciliter l'accès à ces nombres que je mets à disposition un petit service de génération de nombre à unique, accessible publiquement à l'adresse

http://nonce.noisette.ch/next

Chaque appel à cette url retourne un chaine de 32 caractères composées des lettres a-z, A-Z et les chiffres 0-9. Notez que les chaines retournées sont donc senible à la casse.

Le nombre de nonce possible est donc (26+26+10)^32 = 2.27 * 10^57, soit à peu près 6-parasite, ou beaucoup plus que d'atomes dans l'univers.

A utiliser sans modération pour toute application nécessitant la transmission d'informations sensibles sur un réseau non sécurisé.

Edit (06.01.2011) : GAE ne supporte plus le proxying, vous pouvez essayer l'app directement sur http://noisette-nonce.appspot.com/.

De la concurrence des requêtes SQL

Sans cité Montaigne, voici un cas académique dans lequel la concurrence des requêtes SQL est souvent oubliée.

Nous avons une table hits qui contient 4 champs : une date (nommé date), une clé étrangère pointant vers un objet du système (nommée object_id) et un compteur implémenté sous ca forme la plus simple : un entier (nommé counter). Puisqu'on travail avec une framework qui implémente de l'active record on ajoute un champ id qui fera office de clé primaire.
A chaque utilisation de l'objet référencé par la clé étrangère on souhaite incrémenter le compteur et recommencer à 0 tous les minuits afin d'avoir un historique journalier de l'utilisation de l'objet. Alors comme on a quand même un peu réfléchi à la performance du système (un billet sur le sujet est en préparation), on définit un index composé des champs date et object_id. Puis on définit la fonction suivante, donnée ci-dessous en pseudo-code, qui incrémente notre compteur et insère un nouveau tuple si aucun n'existe pour le jour courant :

void function hit ( int $object_id ) {
  SELECT FROM hits WHERE object_id = $object_id AND date = NOW()
  if (row_exists)
      UPDATE hits SET counter = counter + 1 WHERE  object_id = $object_id AND date = NOW()
  else
      INSERT INTO hits (object_id, date, counter) VALUES ($object_id, NOW(), 1)
}

Tout se passe bien jusqu'au jour où on se rend compte qu'il y a plusieurs lignes par objet et par jour dans la base de données.

Ce problème vient du fait qu'il peut se passer un temps indéterminé entre la requête SELECT et l'INSERT. Si à 00h01 2 requêtes sont faites en même temps sur le même objet, il est fort probable que 2 requêtes SELECT soient faites avant un INSERT, et donc les 2 tests if (row_exists) vont retourner faux et 2 INSERT seront fait.

Les solutions pour résoudre ce problème sont multiples, elles passent de la redéfinition de la clé primaire en date, object_id plutôt que notre champ id, ce qui aurait comme comportement de faire échouer le 2ème INSERT, erreur qui pourrait être capturée et traitée spécifiquement. Une autre solution serait de mettre un verrou sur la fonction, chose très aisée en Java avec le mot-clé synchronized. La fonction deviendrait void synchronized function hit(int object_id), évitant ainsi ce type de problème de concurrence.

Dans tous les cas les applications web sont aussi (voir même plus) soumises aux problèmes de concurrence, et l'expérience nous montre que la technique de l'autruche de même que les phrases du style "Il ne PEUT PAS y avoir 2 requêtes en même temps" sont à bannir absolument.

Getting Things Done® (GTD® aussi) : le sydrome du "Ca c'est fait !"

Un mot très en vogue en ce moment (cf Google trend sur getting things done), GTD® est une méthodologie d'organisation des tâches quotidiennes à accomplir. Dévoilée dans un livre écrit par David Allen publié en 2001, Getting Things Done®, the art of stress-free productivity, elle reprend un certain nombre de choses connues en matière de gestion du temps mais les systématise dans un processus structuré, gage d'efficacité.

Cette systématique est intéressante car elle peut nous faire prendre conscience de la méthodologie que peut-être certain utilisaient déjà et ainsi nous amener à y réfléchir en vue de l'optimiser à nos besoins.

L'objectif de GTD® est de porter toute la créativité et l'énergie sur la seule action qu'on a délibérément choisi de faire et d'approcher au mieux un état de productivité sans stress annoncé.

Les 2 concepts mis en exergue par cette théorie sont les suivants :

• Les tâches sont interdépendantes
• Les priorités des tâches dépendent d'un contexte

Fort de ce constat, GTD® nous donne une systématique pour

• recenser les tâches et les reporter sur des listes par sujet,
• identifier celle qui peuvent être exécutées immédiatement et les reporter sur une TODO list
  
• les réaliser dans un ordre de priorité dépendant du contexte (temps à disposition, état de fatigue, endroit, ...).
  

Une fois la tâche accomplie, GTD® propose une phase de revue durant laquelle la tâche est notée comme faite (le fameux syndrome du "Ca c'est fait !", qui n'est en réalité rien qu'un petit vu sur la TODO list mais qui procure une satisfaction bien au-delà du consentement, mais là je m'égare...) et le cycle organisationnel peut recommencer.

GTD® ne propose pas de support spécifique pour la liste des tâches à accomplir (TODO list), mais précise que le moyen utilisé doit être fiable.

Une petite corollaire de GTD® que je trouve intéressantes est que les tâches prenant moins de 2 minutes sont faites immédiatement. Car "moins de 2 minutes" est à peu près le temps pris pour la gestion organisationnelle de la tâche.

Pour ceux qui comme moi pensent que la curiosité n'est pas toujours un vilain défaut :

• http://www.davidco.com/what_is_gtd.php
• http://fr.wikipedia.org/wiki/Getting_Things_Done
• http://wiki.43folders.com/index.php/Productivity_pr0n

Getting Things Done® et GTD® sont des marques déposées depuis 2005.

60 millions de hashes md5 !

Sur mon petit projet de revserse md5 lookup database, je viens de dépasser les 60'000'000 de hashes md5 dans la base de données interne, qui fait maintenant 4.2 GB.

En gros j'ai introduit dans la base tous les hashes de 4 lettres composés des caractères a-z, A-Z, 0-9, ., -, _, !, $, *, %, &, /, (, ), =, ?, #, @, +, ", [, ], {, }, et tous les hashes de 5 lettres composés de caractères a-z.

On remarque que sur l'échantillon généré les hashes sont bien uniformément répartis, mais on a une préférence non significative pour les hashes commençant pas 0x46.

La prochaine étape est les hashes de 5 à 7 lettres composés des caractéres a-z et 0-9, ce qui nous fait ~80'000'000'000 de hashes supplémentaires...
Ensuite je prendrais les dictionnaires Openoffice afin de générer les hashes de mots existants.

Happy md5 cracking sur md5.noisette.ch.

Reverse MD5

La fonction MD5 est une fonction dit à sens unique, c'est-à-dire que ne connaissant que la sortie, il est difficile de trouver l'entrée qui a produit cette sortie.

C'est pourquoi des reverse md5 databases sont apparues sur Internet. Leur principe est tout simple : c'est une grande base de données contenant la pair (texte, hash). Ainsi on peut la questionner du hash recherché et elle nous retourne le texte correspondant si il est connu.

La base de données doit donc être remplie avant de pouvoir produire des réponses, mais une fois qu'elle contient suffisamment de données, les recherches peuvent commencer à être intéressantes. Les techniques des remplissages sont simples, elles vont du parcours de pages web ou de dictionnaires pour rechercher des mots quelconques à l'ajout manuel par des utilisateurs.

J'ai rapidement fait une petite application qui questionne plusieurs des ces reverse md5 databases, qui elle est disponible à l'addresse http://md5.noisette.ch/form.php

Elle se base sur la toute petite API suivante : http://md5.noisette.ch/?hash=<le_hash_en_hex> qui retourne du XML

<md5lookup>
  <hash><!--[CDATA[2a0231531bc1a7fc29e2fa8d64352ae9]]--></hash>
  <string><!--[CDATA[noisette]]--></string>
</md5lookup>

L'approche est très alléchante car une fois le hash dans la base de données, les réponses sont fournies en O(1). Les mots de passe stockés en md5 peuvent donc être retrouvés extrèmenent rapidement.
La contre-partie de cette approche est qu'elle nécessite beaucoup de hash précalculé avant d'être utilisable, et donc produira une énorme base de données :
Le md5 étant sur 128 bits, on pourrait avoir une table de 2^^128 entrées, pour peu qu'on ne prenne pas en compte les doublons. Donc rien que pour les hash, il nous faudrait ~5*10^^39 bytes de stockage = ~5000 téra de téra de téra bytes. Enfin juste pas possible quoi. Si on fait le raisonnement inversion on se dit que notre serveur a 200Gb d'espace disque, on peut donc stocker 12.5 milliards de hash, donc 12.5 milliards de possibilités de mots de passe = un peu plus de 2^^33 possibilités. On est loin des 2^^128...

En résumé, c'est une approchoe time / memory tradoff 100% mémory :)

Les algorithmes de recherche binaire et par fusion sont bogués

C'est la constatation alarmante qu'a fait Joshua Bloch, Software développeur chez Google, dans son article Nearly All Binary Searches and Mergesorts are Broken (Presque tous les algorithme de recherche binaire et par fusion sont bogués) et il en explique précisément la cause.

Il cite en exemple la méthode binarySearch de la librairie java.util.Arrays, qu'il a lui même écrit avant de quitter Sun.

La ligne contenant ce bug est la suivante :

int mid = (low + high) / 2;

Le bug en question est un "bête" integer overflow qui peut apparaître si on manipule un tableau de l'ordre de plus de 2^30 éléments.

Le plus dérangeant dans cette histoire banale est que ce genre de bug, pourtant trouvé dans une routine de peu de lignes, est passé inaperçu pendant près de 60 ans.

Cet exemple démontre très précisément qu'il est impossible d'écrire du code sans bugs, et que donc les prochaines améliorations seront plus d'en limiter les conséquences que de les éradiquer.