Question: This is an interview question: Design a data structure to perform the following operation efficiently: `boolean isPrefix(String s1, String s2)`.

I guess we can create a `multimap`, which maps prefixes to their strings. For instance,

```
strings: "aa", "ab", "abc", "ba", "ca"
multimap: "a"   -> ["aa", "ab", "abc"]
          "aa"  -> ["aa"]
          "ab"  -> ["ab", "abc"]
          "abc" -> ["abc"]
          "ba"  -> ["ba"]
          "ca"  -> ["ca"]

```

Which data structure would you propose ?

Answer: 
The trie data structure would seem like an obvious answer, but the problem as stated doesn't require an advanced data structure. A simple string comparison will suffice and would be very fast. Ultimately, if you want to validate that one string is a prefix of another, you will have to compare every character at corresponding positions. No data structure eliminates the need for the character-by-character comparison.

That being said, if you're *searching* for the prefix in a large body of text, there are other techniques such as [Rabin-Karp probablistic string matching](http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm).
The most effective storage for prefix information is probably the [trie](http://en.wikipedia.org/wiki/Trie).

In this, the strings correspond to nodes in a tree where one string has another as a prefix exactly when its node is below the other in the tree.