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

What’s The Difference Between Angular JS And Angular?

Dependency Injection in Node.js

Setup shadow-cljs react project

Logical Operators in JavaScript

CS373 Spring 2022: Ali Al-Adhami, Week 5

Asynchronous JavaScript — Callbacks & Promises

Things you may not know about Chrome DevTools

How To Add Charts in Laravel 5 using ChartJS

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

JS |Minimum swaps to get together 1’s

What are Synchronous and Asynchronous in JavaScript

Array Flattening

Journey of DLithe Bootcamp Java Full Stack Developer |(06–04–2022)