🎓 A1Learner
🔍
0 of 42 lessons completed

Design Autocomplete: The Ask

Search suggestions are the completions a search box shows while a user types, before the search itself runs. This lesson clarifies the ask: the box shows the top 5 suggestions for the typed prefix, and the whole answer comes back in about 100 milliseconds.

Each keystroke sends a request

Typing the word photo sends one request per letter, 5 requests in all. The printout shows the text growing letter by letter.

typed = "photo"
prefix = ""
for letter in typed:
    prefix = prefix + letter
    print("typed so far:", prefix)
print("requests sent:", len(typed))

The daily count as a rate

A daily count becomes a per-second rate by dividing by the seconds in a day. The printout shows both numbers for this service.

searches_per_day = 5000000000
seconds_per_day = 86400
per_second = round(searches_per_day / seconds_per_day)
print("searches per day:", searches_per_day)
print("searches per second:", per_second)

What the box shows

Terms carry a count of past searches, and the box ranks the matches for the typed text. Only the first few matches are shown, even when more terms match.

terms = [
    ("photo", 900),
    ("photos", 800),
    ("photo editor", 700),
    ("photography", 500),
    ("photo print", 300),
    ("photo book", 200),
    ("pizza", 950),
]
prefix = "pho"
matches = [pair for pair in terms if pair[0].startswith(prefix)]
matches.sort(key=lambda pair: -pair[1])
for term, count in matches[:5]:
    print(term, count)
print("suggestions shown:", len(matches[:5]))

Example

terms = [
    ("photo", 900),
    ("photos", 800),
    ("photo editor", 700),
    ("photography", 500),
    ("photo print", 300),
    ("photo book", 200),
    ("pizza", 950),
]

def suggest(prefix):
    matches = [pair for pair in terms if pair[0].startswith(prefix)]
    matches.sort(key=lambda pair: -pair[1])
    return [term for term, count in matches[:5]]

total_requests = 0
for word in ["photo", "pizza"]:
    prefix = ""
    for letter in word:
        prefix = prefix + letter
        total_requests = total_requests + 1
    print(word, "->", suggest(word))
print("total requests:", total_requests)

Key points

  • Search suggestions: the completions the box offers for the text typed so far.
  • Top suggestions: the highest-ranked completions, ranked by how often each term is searched.
  • One request per keystroke: each new letter asks the service for a fresh answer.
  • Scale: the service handles 5,000,000,000 searches a day, which is 57,870 searches per second.
  • Speed budget: the whole answer must come back in about 100 milliseconds.

In this example, two typed words send one request per letter, and each finished word is answered from the stored counts. The two searches take 10 requests in all, and each answer holds the top suggestions for its word.

Note

the ask fixes what the box shows and how fast it shows it; how the service builds the list comes next.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

What must the autocomplete answer contain?