MIME Type – solution CodinGame en C
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
- 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.
- 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.
- 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.
- Normaliser puis chercherPassez l'extension extraite en minuscules et interrogez le dictionnaire. Affichez le type trouvé ou UNKNOWN, une ligne par fichier.
Complexité
O(N + longueur totale des noms)O(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;
}
MIME Type – Java
HashMap avec getOrDefault et lastIndexOf('.') ; tout le nom est mis en minuscules, ce qui ne pose pas de problème puisque seule l'extension sert.
import java.util.*;
class Solution {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int nbAssociations = in.nextInt();
int nbFiles = in.nextInt();
in.nextLine();
// assoc associates to each file extension the corresponding MIME type
Map assoc = new HashMap();
for (int i = 0; i < nbAssociations; i++) {
assoc.put(in.next().toLowerCase(), in.next());
in.nextLine();
}
for (int i = 0; i < nbFiles; i++) {
// isolates the extension, which is the part after the last .
String fileName = in.nextLine().toLowerCase();
int pos = fileName.lastIndexOf('.');
String extension = (pos == -1) ? "" : fileName.substring(pos+1, fileName.length());
// prints the corresponding MIME type, or UNKNOWN
System.out.println((String)(assoc.getOrDefault(extension, "UNKNOWN")));
}
}
}
MIME Type – Python 3
Le nom en minuscules est découpé sur '.', et on garde le dernier morceau ; une liste d'un seul élément signifie qu'il n'y avait pas de point.
import sys
nbAssociations, nbFiles = int(input()), int(input())
# assoc associates to each file extension the corresponding MIME type
assoc = {}
for i in range(nbAssociations):
ext, mime = input().split()
assoc[ext.lower()] = mime
for i in range(nbFiles):
name = input().lower().split('.')
ext = name[-1] if len(name) != 1 else None
print(assoc[ext] if ext in assoc else "UNKNOWN")
Erreurs fréquentes
- Prendre le premier point au lieu du dernierDécouper au premier '.' transforme ma.photo.png en extension photo.png et renvoie UNKNOWN. Il faut toujours prendre le texte après le dernier point.
- Mettre aussi le type MIME en minusculesSeule la comparaison des extensions ignore la casse. Si vous passez toute la ligne en minuscules à la lecture de la table, une sortie comme image/vnd.Microsoft.Icon ne correspondra plus à la réponse attendue.
- Oublier le cas sans pointEn Java, substring(lastIndexOf('.') + 1) sur un nom sans point renvoie le nom entier, qui peut tomber par hasard sur une extension comme txt. Testez explicitement l'absence de point.
- Point final et extension videUn fichier nommé rapport. a une extension vide. Lire le caractère après le point sans vérifier la longueur provoque un dépassement en C ou une exception ailleurs.
- Timeout sur le gros testComparer chaque fichier à toutes les associations, c'est jusqu'à 100 millions de comparaisons. Ça passe en C, beaucoup moins en Python ou JavaScript : la table de hachage règle le problème.
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.