Design an ecommerce search auto complete suggestion. (Type ahead).

Requirements
1. All the ecommerce products should be included in the catalogue
2. Response type should be in milliseconds
3. Fuzzy search should be allowed

Example
when user type c,
Response - ["christmas decorations","christmas tree","christmas lights","gift cards","iphone 13 pro max case","advent calendar 2021"]

when user type ca,
["carhartt beanie","candles","cat toys","candy","carhartt hoodie","advent calendar 2021"]

when user type can
["candles","candy","christmas candy","candy canes","can opener","noise cancelling headphones","yankee candles","candle making kit","christmas candles","canvases for painting"]

when user type cano
["canon camera","canopy","canon","canon m50","canopy tent","canopy bed","canon ivy mini photo printer","canon printer","canopy bed curtains","canon lens"]

https://completion.amazon.com/search/complete?search-alias=aps&client=amazon-search-ui&mkt=1&q=canon

I came up with a design with Elastic search DB and cache the results in redis. But Interviewer is not satisfied. Thought of new cache structure built using trie, which is also not encouraged.

This question is asked for me in oracle cloud infrastructure interview. I could not come up with an optimal solution even days after the interview. Please point me in the right direction. Thanks in Advance