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;
};