import "./styles.css";
const Directory = (props) => {
const { content } = props;
return content.children.map((item) => {
const isDirectory = "children" in item;
return (
<div class="container" key={item.name}>
<span> {isDirectory ? "Dir - " : "File - "}</span>
<span>{item.name}</span>
{isDirectory && <Directory content={item} />}
</div>
);
});
};
export default function App() {
return (
<Directory
content={{
name: "Root",
children: [
{
name: "John"
},
{
name: "Private",
children: [
{
name: "Private1"
},
{
name: "Private2"
}
]
}
]
}}
/>
);
}
/* Output
File - John
Dir - Private
File - Private1
File - Private2
*/
Categories
Shallow copy vs Deep copy
// Shallow Copy.
const obj = {
a: 1,
b: 2,
c: 3,
d: {
f: 4,
},
};
const testObj = {
...obj // Similar to Object.assign()
};
testObj.d.f = 5; // This modified the original object.
console.log(obj.d);
// {
// f: 4,
// }
const newTestObj = {
...obj,
d: {
...obj.d
},
};
// Deep Copy.
const deepCopy = (inpObj) => {
const obj = {};
for (const [key, val] of Object.entries(inpObj)) {
obj[key] = typeof val === 'object' ? deepCopy(val) : val;
}
return obj;
};
console.log(deepCopy(obj));
// {
// a: 1,
// b: 2,
// c: 3,
// d: {
// f: 5
// }
// }
Categories
Singleton pattern – Javascript
Often times we would want to limit number of instances of a class to 1. We can achieve this using the following pattern. You can use Object.freeze() to prevent further modifications of an object.
// Using ES6 Classes.
class Singleton {
static getInstance() {
if (!this.instance) {
this.instance = new Object('Test');
}
return this.instance;
}
}
console.log(Singleton.getInstance() === Singleton.getInstance());
// true
// Using functions.
function SingletonWrapper() {
let instance;
return {
getInstance: function() {
if (!instance) {
instance = new Object('Test');
}
return instance;
}
}
}
const singletonWrapper = SingletonWrapper();
console.log(singletonWrapper.getInstance() === singletonWrapper.getInstance());
// true
Categories
Minimum Window Substring
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
if (s.length < t.length) {
return '';
}
const sMap = Array(256).fill(0);
const tMap = Array(256).fill(0);
for (const c of t) {
tMap[c.charCodeAt(0)]++;
}
let count = 0;
let start = 0;
let minStart = -1;
let min = s.length;
for (let j = 0; j < s.length; j++) {
const c = s[j].charCodeAt(0);
sMap[c]++;
if (sMap[c] <= tMap[c]) {
count++;
}
if (count === t.length) {
// Minimize the window by moving the start pointer.
while (sMap[s[start].charCodeAt(0)] > tMap[s[start].charCodeAt(0)]) {
sMap[s[start].charCodeAt(0)]--;
start++;
}
const currLen = j - start + 1;
if (currLen < min) {
min = currLen;
minStart = start;
}
}
}
if (minStart === -1 && count !== t.length) {
return '';
}
return minStart !== -1 ? s.substring(minStart, minStart + min) : s;
};
console.log(minWindow('ABCDFEDFI', 'DF'));
// DF
Categories
Maximum Subarray of size K
// Uses sliding window technique. Runtime Complexity 0(n).
const maxSubarraySizeK = (arr, k) => {
if (arr.length < k) {
return [];
}
let sum = 0;
let s = 0;
let maxSum = Number.MIN_VALUE;
for (let i = 0; i < arr.length; i++) {
if (i < k) {
sum += arr[i];
maxSum = sum;
} else {
sum += arr[i] - arr[i - k];
if (sum > maxSum) {
maxSum = sum;
s = i - k + 1;
}
}
}
return arr.slice(s, s + k);
};
console.log(maxSubarraySizeK([1, 4, 2, 10, 2, 3, 1, 0, 20], 4));
// [3, 1, 0, 20] - 24
Categories
Largest Subarray Length K
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var largestSubarray = function(arr, k) {
let max = arr[0];
let maxIndex = 0;
for (let i = 0; i <= arr.length - k; i++) {
if (arr[i] > max) {
max = arr[i];
maxIndex = i;
}
}
return arr.slice(maxIndex, maxIndex + k);
};
console.log(largestSubarray([1, 4, 5, 2, 3], 4));
// [4, 5, 2, 3]
Max Heap (Javascript)
class MaxHeap { constructor(capacity) { this.capacity = capacity; this.size = 0; this.arr = []; } add(val) { if (this.size < this.capacity) { this.arr[this.size++] = val; this.trickleUp(this.size - 1); } } trickleUp(i) { const parent = Math.floor((i - 1) / 2); if (parent >= 0 && this.arr[i] > this.arr[parent]) { this.swap(i, parent); this.trickleUp(parent); } } delete() { if (this.size) { const ret = this.arr[0]; this.arr[0] = this.arr[this.size-- - 1]; this.trickleDown(0); return ret; } } trickleDown(i) { const left = 2 * i + 1; const right = 2 * i + 2; let largest = i; if (left < this.size && this.arr[left] > this.arr[largest]) { largest = left; } if (right < this.size && this.arr[right] > this.arr[largest]) { largest = right; } if (largest !== i) { this.swap(i, largest); this.trickleDown(largest); } } swap(a, b) { const temp = this.arr[a]; this.arr[a] = this.arr[b]; this.arr[b] = temp; } hasNext() { return this.size > 0; } } /** Test **/ const maxHeap = new MaxHeap(1000); maxHeap.add(1); maxHeap.add(90); maxHeap.add(11); maxHeap.add(5); while (maxHeap.hasNext()) { console.log(maxHeap.delete()); } /* Output: 90 11 5 1 */ // Time complexity for each operation: O(log(n)).
The following code uses “Trie” data structure. The character ‘.’ in a word could represent any letter when searching.
class TrieNode { constructor(val) { this.val = val; this.children = {}; this.isWord = false; } } var WordDictionary = function() { this.root = new TrieNode(null); }; /** * @param {string} word * @return {void} */ WordDictionary.prototype.addWord = function(word) { let current = this.root; const charArray = word.split(''); for (const s of charArray) { if (!(s in current.children)) { current.children[s] = new TrieNode(s); } current = current.children[s]; } current.isWord = true; }; /** * @param {string} word * @return {boolean} */ WordDictionary.prototype.search = function(word) { return this.searchString(word, this.root); }; WordDictionary.prototype.searchString = function(str, node) { let current = node; const charArray = str.split(''); for (const [index, char] of Object.entries(charArray)) { if (!(char in current.children)) { if (char === '.') { for (const [key, childNode] of Object.entries(current.children)) { if (this.searchString(str.substring(parseInt(index) + 1), childNode)) { return true; } } } return false; } else { current = current.children[char]; } } return current.isWord; }; var obj = new WordDictionary(); obj.addWord('bad'); obj.addWord('bat'); obj.addWord('cat'); console.log(obj.search('b..')); // true console.log(obj.search('cat')); // true console.log(obj.search('dog')); // false
Categories
Coin Change
/** * @param {number[]} coins * @param {number} amount * @return {number} */ const coinChange = (coins, amount) => { if (!coins) { return -1; } return getCoinChangeMin(coins, amount, {}); }; const getCoinChangeMin = (coins, amount, dp) => { if (amount < 0) { return -1; } if (amount === 0) { return 0; } if (amount in dp) { return dp[amount]; } let min = Number.MAX_VALUE; for (const coin of coins) { let currMin = getCoinChangeMin(coins, amount - coin, dp); if (currMin >= 0 && currMin < min) { min = currMin; } } return dp[amount] = min === Number.MAX_VALUE ? -1 : min + 1; };
Categories
N-Queens Js
const solveNQueens = (n) => { if (n < 1) { return []; } const ret = []; getAll(n, 0, ret, []); return ret; }; const getAll = (n, row, ret, rowCol) => { if (row === n) { ret.push(buildSolution(rowCol, n)); return; } for (let col = 0; col < n; col++) { if (isValid(row, col, rowCol)) { rowCol[row] = col; getAll(n, row + 1, ret, rowCol); } } }; const isValid = (row, col, rowCol) => { for (let r = 0; r < row; r++) { if (rowCol[r] === col) { return false; } const c = rowCol[r]; if ((row - r) === Math.abs(c - col)) { return false; } } return true; }; const buildSolution = (rowCol, n) => { const ans = []; for (let i = 0; i < n; i++) { let str = ''; for (let j = 0; j < n; j++) { str += rowCol[i] === j ? 'Q' : '.'; } ans.push(str); } return ans; };