let suggestedProducts = function(products, searchWord) {
const MAX_RESULT_COUNT = 3;
let root = {
children: {}
};
function addToNode(word, index, node) {
if (index >= word.length) {
node.end = true;
return;
}
//
const child = node.children[word[index]];
if (child) {
addToNode(word, index + 1, child);
}
else {
let child = {val: word[index], parent: node, children: {}};
node.children[word[index]] = child;
addToNode(word, index + 1, child);
}
}
function getWord(leaf) {
let node = leaf;
let str = '';
while (node) {
if (node.val) str = node.val + str; //?
node = node.parent; //?
}
return str; //?
}
function searchProducts(searchString) {
let words = [];
let nodes = [...Object.entries(root.children)], len = searchString.length;
while (nodes.length) {
let currentNodeLength = nodes.length;
while (currentNodeLength > 0) {
currentNodeLength--;
const node = nodes.pop();
const [key, val] = node;
if (len > 0 && key === searchString[searchString.length - len]) {
nodes.unshift(...Object.entries(val.children));
if (len === 1 && val.end) {
words.push(getWord(val));
}
} else if (len <= 0) {
if (val.end) words.push(getWord(val));
nodes.unshift(...Object.entries(val.children));
}
}
len--;
}
return words.sort().slice(0, Math.min(MAX_RESULT_COUNT, words.length));
}
for(let product of products) {
addToNode(product, 0, root);
}
let result = [];
for (let i = 0; i < searchWord.length; i++) {
result.push(searchProducts(searchWord.substring(0, i + 1))); //?
}
return result; //?
};
Category: Recursion
Categories
Search Matrix
let searchMatrix = function(matrix, target) {
if(!matrix.length) return false;
function search(startRow, endRow, startCol, endCol) {
console.log(startRow, endRow, startCol, endCol);
let midRow = Math.floor((startRow + endRow) / 2); //?
let midCol = Math.floor((startCol + endCol) / 2); //?
if (startRow < endRow && startCol < endCol) {
const midValue = matrix[midRow][midCol]; //?
if(midValue === target) {
return true;
}
if (midValue < target) {
return search(midRow + 1, endRow, startCol, endCol)
|| search(startRow, endRow, midCol + 1, endCol);
}
else {
return search(startRow, midRow, startCol, endCol)
|| search(startRow, endRow, startCol, midCol);
}
}
return false;
}
return search(0, matrix.length, 0, matrix[0].length);
};
Categories
Oranges Rotting
let orangesRotting = function(grid) {
const FRESH = 1,
ROTTEN = 2,
VISITED = -1;
let rotten = [],
totalFresh = 0,
totalEmpty = 0,
total = 0;
function getAdjacents(row, col) {
let result = [];
// check top
if (row > 0 && grid[row -1][col] === FRESH) {
grid[row -1][col] = VISITED;
result.push([row - 1, col]);
}
// check bottom
if (row < grid.length - 1 && grid[row + 1][col] === FRESH) {
grid[row +1][col] = VISITED;
result.push([row + 1, col]);
}
// check left;
if (col > 0 && grid[row][col - 1] === FRESH) {
grid[row][col - 1] = VISITED;
result.push([row, col - 1]);
}
// check right
if (col < grid[row].length - 1 && grid[row][col + 1] === FRESH) {
grid[row][col + 1] = VISITED;
result.push([row, col + 1]);
}
return result;
}
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[i].length; j++) {
const data = grid[i][j];
if (data === ROTTEN) {
rotten.push(...getAdjacents(i, j));
}
else if (data === FRESH || data === VISITED) {
totalFresh++;
}
else {
totalEmpty++;
}
total++;
}
}
totalFresh -= rotten.length;
let minute = 0;
while (rotten.length) {
let len = rotten.length;
while (len --> 0) {
let point = rotten.pop();
let [row, col] = point;
grid[row][col] = ROTTEN;
rotten.unshift(...getAdjacents(row, col));
}
totalFresh -= rotten.length;
minute++;
}
if (total === totalEmpty) return 0;
let hasFreshOranges = totalFresh > 0;
if (hasFreshOranges) return -1;
return minute;
};
Categories
Decode String
let decodeString = function(str) {
if (str.indexOf("[") < 0) {
return str;
}
let openingIndex = [];
let newStr = "";
for (let i = 0; i < str.length; i++) {
if (str[i] === "[") {
openingIndex.push(i);
newStr += str[i];
}
else if (str[i] === "]") {
let opening = openingIndex.pop();
let allMultipliers = str.substring(0, opening).match(/\d+/g);
let multiplier = allMultipliers[allMultipliers.length - 1];
let data = str.substring(opening + 1, i);
if (data.indexOf("[") < 0) {
newStr = newStr.substring(0, newStr.lastIndexOf("[") - multiplier.length) + data.repeat(multiplier);
console.log({opening, multiplier, data, newStr});
}
else {
newStr += str[i];
}
}
else {
newStr += str[i];
}
}
return decodeString(newStr);
};
let reverseLinkedList = function(root, reverse = new ListNode(0)) {
if (root) {
let toAdd = root;
let next = root.next;
let reversedNext = reverse.next;
toAdd.next = reversedNext;
reverse.next = toAdd;
reverseLinkedList(next, reverse);
}
return reverse.next;
}
function fib(x) {
let cache = {}
function fibInternal(n) {
if(n == 0) return 0;
if(n <= 2) return 1;
if (cache[n]) return cache[n];
const result = fibInternal(n - 1) + fibInternal(n - 2);
cache[n] = result;
return result;
}
return fibInternal(x)
}
let lookAndSay = function(nth, number = "1") {
if (nth === 1) return number;
let index = 0,
counter = 1,
currentNumber = "";
let result = "";
while (index < number.length) {
if (index === 0) {
currentNumber = number[index];
}
else if (currentNumber === number[index]) {
counter++;
}
else if (currentNumber !== number[index]) {
result = `${result}${counter}${currentNumber}`;//?
counter = 1;
currentNumber = number[index];
}
index++;
}
result = `${result}${counter}${currentNumber}`;//?
return lookAndSay(--nth, result);
}
let mergeSort = function(numbers) {
function mergeSort(arr) {
if (arr.length === 1) return arr;
let center = Math.floor(arr.length / 2);
let left = arr.slice(0, center);
let right = arr.slice(center);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let results = [];
while (left.length && right.length) {
if (left[0] < right[0]) {
results.push(left.shift());
}
else {
results.push(right.shift());
}
}
return [...results, ...left, ...right];
}
return mergeSort(numbers);
}
Categories
Number of Islands
let numIslands = function(matrix) {
if (!matrix.length) return 0;
let land = 1, visited = 'X',
counter = 0,
maxRow = matrix.length - 1,
maxCol = matrix[0].length - 1;
function exploreAndMark(row, col) {
if (row < 0 || col < 0 || row > maxRow || col > maxCol) {
return;
}
if (matrix[row][col] === land) {
matrix[row][col] = visited;
// explore up
exploreAndMark(row - 1, col);
// explore down
exploreAndMark(row + 1, col);
// explore left
exploreAndMark(row, col - 1);
// explore right
exploreAndMark(row, col + 1);
}
}
for (let row = 0; row <= maxRow; row++) {
for (let col = 0; col <= maxCol; col++) {
if (matrix[row][col] === land) {
counter++;
exploreAndMark(row, col);
}
}
}
return counter;
}
let secondHighest = function(arr1, arr2) {
if (arr1.length === 1 && arr2.length === 1) {
return Math.min(arr1[0], arr2[0]);
}
else if (arr1.length === 0 && arr2.length === 2) {
return Math.min(arr2[0], arr2[1]);
}
else if (arr2.length === 0 && arr1.length === 2) {
return Math.min(arr1[0], arr1[1]);
}
let mid1 = Math.ceil((arr1.length / 2) - 1)
let mid2 = Math.ceil((arr2.length / 2) - 1);
if (arr1[mid1] <= arr2[mid2]) {
arr1 = arr1.slice(mid1 + 1);
arr2 = arr2.slice(mid2);
}
else {
arr1 = arr1.slice(mid1);
arr2 = arr2.slice(mid2 + 1);
}
return secondHighest(arr1, arr2);
}