Keyword Search Algorithm, can't find bug in my solution

Question

I was trying to solve an interview question, and I didn't get most of the test cases correct -- however, I'm unable to spot my bug after looking at it for an hour. The parameters of the question are:

• You are given a list of keywords/search results in an array

• The user would type in a word (or string)

• Start searching for keywords that match the string above once 2+ characters are typed. Once a character is typed, the list continues

• Only display 3 keywords. If there are more than 3, return the first 3 in alphabetical order

• Case insensitive, but word must START with the same letter(s)

• return the lists of keywords as a 2D Array

  function searchSuggestions(repository, customerQuery) {
  
        if(customerQuery.length < 2) return [];
        repository.sort();
        console.log("REPO:", repository);
        console.log("QUERY:", customerQuery);
  
  
        let result = [];
  
        for(let i = 0; i < customerQuery.length; i++) {
            if(i === 0) continue;
            let currentWord = customerQuery.substring(0, i + 1);     
            console.log("Current Word:", currentWord);
            let match = [];
            // Loop through Repo words
            for (let j = 0; j < repository.length; j++) {
                if (match.length === 3) break;
                console.log("REPO[J]:",repository[j].toLowerCase().substring(0, currentWord.length));
                // Compare our current word to the repo word's substring since it has to start with it
                if(repository[j].toLowerCase().substring(0, currentWord.length) === currentWord.toLowerCase()) {
                    match.push(repository[j].toLowerCase());
                    console.log("ITEM IS A MATCH");
                }
            }
            // push to results
            result.push(match)
        }
  
        console.log("RESULT", result);
        return result;
    }
  

Here is the list of keywords for 1 test case:

REPO: [
  'Abs',  'abbS',
  'abc',  'bcs',
  'bdsa', 'cdde',
  'rgb',  'xxmm',
  'yjmm', 'zeee'
]

Here is what the user is searching:

QUERY: abbs

So we will search on 'ab', 'abb', and 'abbs' for keyword matches

Current Word: ab
REPO[J]: ab
ITEM IS A MATCH
REPO[J]: ab
ITEM IS A MATCH
REPO[J]: ab
ITEM IS A MATCH

Current Word: abb
REPO[J]: abs
REPO[J]: abb
ITEM IS A MATCH
REPO[J]: abc
REPO[J]: bcs
REPO[J]: bds
REPO[J]: cdd
REPO[J]: rgb
REPO[J]: xxm
REPO[J]: yjm
REPO[J]: zee

Current Word: abbs
REPO[J]: abs
REPO[J]: abbs
ITEM IS A MATCH
REPO[J]: abc
REPO[J]: bcs
REPO[J]: bdsa
REPO[J]: cdde
REPO[J]: rgb
REPO[J]: xxmm
REPO[J]: yjmm
REPO[J]: zeee

Here is my final result:

RESULT [ [ 'abs', 'abbs', 'abc' ], [ 'abbs' ], [ 'abbs' ] ]

Apparently this was incorrect, but even if I did it by hand, I'm not seeing the issue..? Can someone spot my error? Obviously this isn't the best solution (2 for loops, O(n^2)), but I was trying to get a brute force solution first which I apparently didn't even accomplish. I'm unaware of what the actual answer is. Doing it by hand, I get the same thing I get above.

Answer 1

Only display 3 keywords. If there are more than 3, return the first 3 in alphabetical order

[ 'abs', 'abbs', 'abc' ] is not alphabetical.

The default array.sort() is case-sensitive, so "Abs" is placed before "abc". One way to overcome this is to use localeCompare on the lowercase strings:

repository.sort((a, b) => a.localeCompare(b, 'en', {'sensitivity': 'base'}))

Or you could convert them to lowercase up front and then sort:

const repo = repository.map(s => s.toLowerCase()).sort()'

Answer 2

You could sort repo in advance and take an early exit on greater words or found items.

function getSuggestion(word) {
    const
        repo = ['Abs', 'abbS', 'abc', 'bcs', 'bdsa', 'cdde', 'rgb', 'xxmm', 'yjmm', 'zeee']
            .sort((a, b) => a.toLowerCase().localeCompare(b.toLowerCase())),
        result = [];

    if (word.length < 2) return [];
    word = word.toLowerCase();
    for (const r of repo) {
        const l = r.toLowerCase();
        if (l.startsWith(word)) result.push(r);
        if (l.slice(0, word.length) > word || result.length === 3) break;
    }
    return result;
}

console.log(getSuggestion('a'));
console.log(getSuggestion('ab'));
console.log(getSuggestion('abb'));
console.log(getSuggestion('abbs'));