MIME Type – CodinGame solution in C
Load the extension-to-MIME table into a hash map keyed by the lowercased extension, then for each file name take the substring after the last dot, lowercase it and look it up. If the name has no dot, or the extension is not in the table, print UNKNOWN. Everything is O(1) per lookup, so the whole puzzle runs in linear time in the size of the input.
The problem
You are given a table of N associations between a file extension (like html or png) and its MIME type (like text/html), followed by Q file names. For every file name you must print the MIME type that corresponds to its extension, or UNKNOWN if it cannot be determined.
The extension is whatever follows the last dot of the name. Extensions are compared without caring about upper or lower case, but the MIME type must be printed exactly as given. N and Q are both below 10,000, extensions are at most 10 alphanumeric characters and file names at most 256 characters, so a quadratic scan is borderline in slow languages.
Approach, step by step
- Build a dictionaryRead the N pairs and store them in a hash map (HashMap in Java, dict in Python). Lowercase the extension before inserting it, and keep the MIME type untouched, since it is printed verbatim.
- Find the last dotFor each file name, locate the last occurrence of '.' with lastIndexOf, rsplit or strrchr. Only the part after that final dot counts: archive.tar.gz has the extension gz, not tar.gz.
- Handle names without an extensionIf there is no dot at all, the answer is UNKNOWN immediately. If the name ends with a dot, the extension is the empty string, which never matches a table entry, so it also yields UNKNOWN.
- Normalise and look upLowercase the extracted extension and query the map. Print the stored MIME type on a hit and UNKNOWN on a miss, one line per file.
Complexity
O(N + total length of the file names)O(N)Each association is inserted once and each file costs one scan of its name plus an average O(1) hash lookup. The C version uses a linear scan of the table instead, which is O(N x Q) comparisons but still fast enough at these sizes.
Solution code
Bug fixed in this version: The C version compiles only with warnings: it calls tolower without including <ctype.h> and reads lines with gets(), which was removed from the C11 standard. Recent compilers (GCC 14 and later) turn these implicit declarations into hard errors, so a cleaner replacement using fgets and strrchr is provided. The Java and Python versions are correct.
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
Uses a HashMap with getOrDefault and lastIndexOf('.'); the whole file name is lowercased, which is harmless because only the extension is used.
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
Splits the lowercased name on '.' and keeps the last piece; a list of length 1 means there was no dot, so the name is treated as having no extension.
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")
Common mistakes
- Using the first dot instead of the lastSplitting on the first '.' turns my.photo.png into the extension photo.png and returns UNKNOWN. Always take the text after the final dot.
- Lowercasing the MIME type tooOnly the extension comparison is case-insensitive. If you lowercase the whole input line when reading the table, an output like image/vnd.Microsoft.Icon will no longer match the expected answer.
- Crashing on names without a dotIn Java, substring(lastIndexOf('.') + 1) on a name with no dot returns the whole name, which may accidentally match an extension such as 'txt'. Test explicitly for 'no dot' and answer UNKNOWN.
- Trailing dot and empty extensionA file called report. has an empty extension. Code that indexes the character after the dot without checking the length can read past the end of the string in C or raise an exception in other languages.
- Timeouts on the large testComparing each file against every association with string equality is 100 million comparisons in the worst case. That is fine in C but can time out in Python or JavaScript; a hash map makes the last test trivial.
Going further
The puzzle is really a lesson in normalising a key before hashing it. Rather than doing a case-insensitive comparison at query time, you convert both sides to one canonical form (lowercase) once, and then a plain hash map does the work. The same idea shows up in real code when you build lookups on e-mail addresses, URLs or user names. A subtle case most write-ups ignore: a file name can consist of only a dot plus an extension, such as .htaccess. By the puzzle's rule (text after the last dot) its extension is htaccess, so it must be looked up like any other name, not treated as a hidden file with no extension.
FAQ
Is the extension comparison case-sensitive in the MIME Type puzzle?
No. PNG, png and Png must all match the same association, so lowercase extensions both when storing and when looking them up. The MIME type itself must be printed with its original case.
What should I print for a file like archive.tar.gz?
Only the part after the last dot counts, so the extension is gz. Print the MIME type associated with gz, or UNKNOWN if gz is not in the table.
Do I need a hash map, or is a list enough?
A list scanned linearly passes in C, but with up to 10,000 associations and 10,000 files it is risky in slower languages. A hash map gives constant-time lookups and is the idiomatic solution.