JS | Auto-complete feature using Trie | Search Suggestions System | Coding Round Interview Question

Input: 
products = ["mobile","mouse","moneypot","monitor","mousepad"],
searchWord = "mouse"
Output: [
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]After typing mou, mous and mouse the system suggests ["mouse","mousepad"]

The idea,

  • Sorting Simple Traversal
  • Trie + DFS

Sort | Simple Traversal

  1. Sort the products
  2. Keep filtering products that match our input
var suggestedProductsSort = function(products, searchWord) {
products.sort();
let res = [];
for (let i=0; i< searchWord.length; i++) {
products = products.filter( (p) => p[i] == searchWord[i]);
res.push(products.slice(0, 3));
}
return res;
}

Trie + DFS

  1. Create a Trie from the given products input.
  2. Iterate each character of the searchWord adding it to the prefix to search for.
  3. After adding the current character to the prefix traverse the trie pointer to the node representing prefix.
  4. Now traverse the tree from curr pointer in a preorder fashion and record whenever we encounter a complete word.
  5. Limit the result to 3 and return dfs once reached this limit.
  6. Add the words to the final result.

Adding a word “mouse”, “money” to TRIE,

Adding word “mouse”, “money” to TRIE,
/**
* @param {string[]} products
* @param {string} searchWord
* @return {string[][]}
*/
var suggestedProducts = function (products, searchWord) {

products.sort();

function Trie() {
this.children = {};
}

Trie.prototype.addWord = function (word) {
let current = this;

for (let i = 0; i < word.length; i++) {
const char = word.charAt(i);

if (!current.children[char]) {
current.children[char] = new Trie();
}
current = current.children[char];
}

current.word = word;
}

let trie = new Trie();

for (const product of products) {
trie.addWord(product);
}

const output = [];
for (let i = 0; i < searchWord.length; i++) {
const char = searchWord.charAt(i);
trie = !!trie ? trie.children[char] : null;
output.push(!!trie ? dfs(trie) : []);
}

return output;

function dfs(node, output = []) {
if (!!node.word) {
output.push(node.word);
}

for (const child in node.children) {
dfs(node.children[child], output)
}

return output.length >= 3 ? output.slice(0, 3) : output;
}

};

--

--

--

Working in Walmart as UI Developer | Mentor | React | JavaScript | HTML | CSS

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Turning E2E Tests Into Web Scraping

Statistics of Dow Jones

Dead in The Water: Async Behavior

Redux and RxJs

11 Weird Facts You Didn’t Know About JavaScript Adventures

first look at algorithms and recursion

How I use React’s useEffect

JavaScript Algorithm: Distance Between Points

Custom TSLint rules with TSQuery 😍

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
iAmSonika | www.startlearncoding.com

iAmSonika | www.startlearncoding.com

Working in Walmart as UI Developer | Mentor | React | JavaScript | HTML | CSS

More from Medium

An Introduction to Props in React

Version controlling And JavaScript

Difference Between Class Based And Function Based Components (REACT.JS) [Which is Better?]

Swap Nodes in Pairs💰