Difficulty: Easy · Skills: hash maps, string parsing, case-insensitive lookup, file extensions

What this puzzle tests in a coding interview

MIME Type is a dictionary lookup in disguise. It checks whether you reach for a hash map, extract the extension correctly from the last dot, and normalise case before the lookup.

How to solve it, step by step

1. Read the association table and store each extension in lowercase together with its MIME type.
2. For each file name, look for the last dot and take everything after it as the extension.
3. If there is no dot, the file is UNKNOWN.
4. Lowercase the extension and look it up in the table.
5. Print the MIME type when found, UNKNOWN otherwise.

Time and memory complexity

With a hash map each lookup is O(1) on average, so the total is O(N + Q) for N associations and Q files; the C version on the page scans the table linearly instead, which is O(N x Q) but still fast for these limits.

Traps to avoid

• Splitting on the first dot, so archive.tar.gz gets the wrong extension.
• Lowercasing the file name but not the stored extensions, or the reverse.
• Treating a file ending with a dot as having an empty extension that matches something.

Tip for a timed test

Use your language's built-in dictionary and rsplit or lastIndexOf; this is a five-minute puzzle if you avoid writing your own parser.

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

// Represents an association between an extension, and its mime type
struct pair { char *ext; char *mime; };

// A dictionnary can be implented very simply as a pair array
struct dict {
    int size;
    struct pair *elmts;
};

/* Returns the MIME type of label 'ext' in dictionnary 'dict'
   or "UNKNOWN" if there is no matching extension */
char *assoc (struct dict *d, char *ext) {
    for (int i = 0; i < d->size; i++)
        if (strcmp(d->elmts[i].ext, ext) == 0)
            return d->elmts[i].mime;
    return "UNKNOWN";
}

// Replaces all uppercase chars of 'str' by the corresponding lowercase chars
void toLower (char *str) {
    for (; *str != '\0'; str++)
        *str = tolower(*str);
}

// Returns a pointer on the first char of the extension of 'str' if it has one
// or NULL else
char *getExt (char *str) {
    for (char *ext = str+strlen(str); ext != str; ext--)
        if (*(ext-1) == '.')
            return ext;
    return NULL;
}

int main(int argc, char** argv)
{
    int dictSize, nbFiles;
    scanf("%d\n%d\n", &dictSize, &nbFiles);

    // Initializes the dictionary extension-MIME type
    struct dict d;
    struct pair *p;
    d.size = dictSize;
    d.elmts = malloc(d.size*sizeof(struct pair));
    for (int i = 0; i < dictSize; i++) {
        p = d.elmts+i;
        p->ext = malloc(11*sizeof(char));
        p->mime = malloc(51*sizeof(char));
        // here using scanf is quite safe because maximal lengths are known
        scanf("%s %s\n", p->ext, p->mime);
        toLower(p->ext);
    }

    // processes file 1 by 1, by isolating ext and matching it with a MIME type
    char file[257];
    char *ext;
    for (int i = 0; i < nbFiles; i++) {
        gets(file);
        toLower(file);
        ext = getExt(file);
        printf("%s\n", assoc(&d, ext?ext:""));
    }

    for (int i = 0; i < dictSize; i++) {
        p = d.elmts+i;
        free(p->ext);
        free(p->mime);
    }
    free(d.elmts);

    return EXIT_SUCCESS;
}
            

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")));
        }
    }
}
            

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")