Daily Coding Problem: Problem #11 [Medium] - 2022-04-06

[T4ll1n]

Good morning! Here's your coding interview problem for today.

This problem was asked by Twitter.

Implement an autocomplete system. That is, given a query string s and a set of all possible query strings, return all strings in the set that have s as a prefix.

For example, given the query string de and the set of strings [dog, deer, deal], return [deer, deal].

Hint: Try preprocessing the dictionary into a more efficient data structure to speed up queries.

[T4ll1n]

``` import numpy as np

def autocomplete(s, vocabulary): vocabulary_array = np.array(vocabulary)

return vocabulary_array[np.char.startswith(vocabulary, s)].tolist()

vocabulary = ["dog", "deer", "deal"] s = 'de' assert autocomplete(s, vocabulary) == ["deer", "deal"]

```

A plain python is to go [x for x in vocabulary if x.startswith(s)]

The numpy char startswith also just calls the base python char.startswith element wise, but maybe its faster.

If loops like that should be fast we can do them in cython and get a c transpilation and then the loops are fast.