Coding Solution

MIME Type – solution CodinGame en C

Facilehash mapstring parsingcase-insensitive lookupMis à jour le
Réponse courte

Stockez la table extension -> type MIME dans un dictionnaire dont la clé est l'extension en minuscules. Pour chaque fichier, récupérez ce qui suit le dernier point, passez-le en minuscules et cherchez-le dans le dictionnaire. Sans point ou sans correspondance, affichez UNKNOWN : chaque recherche est en O(1) et le tout tourne en temps linéaire.

L'énoncé

On vous donne N associations entre une extension de fichier (html, png...) et un type MIME (text/html, image/png...), puis Q noms de fichiers. Pour chacun, il faut afficher le type MIME correspondant à son extension, ou UNKNOWN s'il est impossible de le déterminer.

L'extension est la partie située après le dernier point du nom. La comparaison des extensions ignore la casse, mais le type MIME doit être recopié tel quel. N et Q restent sous 10 000, les extensions font au plus 10 caractères et les noms de fichiers au plus 256 : une double boucle passe en C mais devient limite dans les langages lents.

La démarche, étape par étape

  1. Construire un dictionnaireLisez les N couples et rangez-les dans une table de hachage (HashMap en Java, dict en Python). Mettez l'extension en minuscules avant de l'insérer, et ne touchez pas au type MIME, qui sera affiché à l'identique.
  2. Trouver le dernier pointPour chaque nom, cherchez la dernière occurrence de '.' avec lastIndexOf, rsplit ou strrchr. Seul ce qui suit ce point compte : archive.tar.gz a pour extension gz, pas tar.gz.
  3. Gérer les noms sans extensionS'il n'y a aucun point, la réponse est directement UNKNOWN. Si le nom se termine par un point, l'extension est vide : elle ne correspond à aucune entrée et donne aussi UNKNOWN.
  4. Normaliser puis chercherPassez l'extension extraite en minuscules et interrogez le dictionnaire. Affichez le type trouvé ou UNKNOWN, une ligne par fichier.

Complexité

TempsO(N + longueur totale des noms)
MémoireO(N)

Chaque association est insérée une fois, et chaque fichier coûte un parcours de son nom plus une recherche en O(1) en moyenne. La version C parcourt la table linéairement (O(N x Q) comparaisons), ce qui reste assez rapide à cette échelle.

Code de la solution

MIME Type – C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef struct { char ext[16]; char mime[64]; } Pair;

static void lower(char *s) {
    for (; *s; s++) *s = (char)tolower((unsigned char)*s);
}

int main(void) {
    int n, q;
    if (scanf("%d %d", &n, &q) != 2) return 0;
    Pair *table = malloc(sizeof(Pair) * (n > 0 ? n : 1));
    for (int i = 0; i < n; i++) {
        scanf("%15s %63s", table[i].ext, table[i].mime);
        lower(table[i].ext);
    }
    fgetc(stdin); /* consume the newline left after the last association */

    char line[512];
    for (int i = 0; i < q; i++) {
        if (!fgets(line, sizeof line, stdin)) break;
        line[strcspn(line, "\r\n")] = '\0';
        lower(line);
        char *dot = strrchr(line, '.');
        const char *answer = "UNKNOWN";
        if (dot != NULL) {
            for (int j = 0; j < n; j++) {
                if (strcmp(table[j].ext, dot + 1) == 0) { answer = table[j].mime; break; }
            }
        }
        puts(answer);
    }
    free(table);
    return 0;
}

Erreurs fréquentes

Pour aller plus loin

Ce puzzle apprend surtout à normaliser une clé avant de la hacher. Plutôt que de faire une comparaison insensible à la casse à chaque requête, on ramène une fois pour toutes les deux côtés à une forme canonique (les minuscules), puis un dictionnaire classique fait le travail. C'est exactement ce qu'on fait en production pour indexer des e-mails ou des URL. Un cas rarement évoqué : un nom composé uniquement d'un point et d'une extension, comme .htaccess. Selon la règle du puzzle (ce qui suit le dernier point), son extension est htaccess et il doit être cherché normalement, pas traité comme un fichier caché sans extension.

Questions fréquentes

La comparaison des extensions est-elle sensible à la casse ?

Non. PNG, png et Png doivent correspondre à la même association : mettez les extensions en minuscules à l'insertion comme à la recherche. Le type MIME, lui, s'affiche avec sa casse d'origine.

Que faut-il afficher pour archive.tar.gz ?

Seule la partie après le dernier point compte, donc l'extension est gz. Affichez le type associé à gz, ou UNKNOWN s'il n'existe pas.

Faut-il vraiment une table de hachage ?

Une liste parcourue linéairement passe en C, mais avec 10 000 associations et 10 000 fichiers c'est risqué dans les langages plus lents. Le dictionnaire donne des recherches en temps constant et reste la solution idiomatique.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome