Coding Solution

MIME Type – CodinGame solution in C

Easyhash mapstring parsingcase-insensitive lookupUpdated
Short answer

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

  1. 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.
  2. 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.
  3. 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.
  4. 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

TimeO(N + total length of the file names)
SpaceO(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;
}

Common mistakes

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.

Similar puzzles

★ 5.0 · 16 reviews · 928 users Add to Chrome