I have been thinking about this problem for a while and not sure how to solve it as in best data structure and time complexity for it. This is not homework or anything like that, just casual problem solving, I tried solving it earlier this year, but then I forgot about it.
Imagine you have a website that will make searches best on a keyword you type. You have a data structure that is formed of objects with 2 properties
"word": < string value, name of the word >
"popularity": < numerical value, how often the word has been searched >
You can pick any data structure you want, and it can be sorted by the highest value first or alphabetically based on "word" values.
for example, consider data values below
data = [{
"word": "ipad"
"popularity": 100
},
{
"word": "iphone"
"popularity": 1321
},
{
"word": "ipod"
"popularity": 22
}
]
if I searched for "ipa", i should get "ipad"
if I searched for "ip", I should get "iphone"
if I searched for "ipod", I should get "ipod"
The algorithm needs to check if there is an exact match for the keyword typed, if found then you return the word; if there isn't an exact match you will select the word with the highest popularity value and you return it.
The way I wanted to resolve this was by using an array of objects to find the best match, but that was O(n) which was not good enough.
I am curious to find out any other ideas, article recommendations to read.