10 Problem Solution
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627
/*function validAnagram(s1, s2) {
if(typeof s1 !== "string" || typeof s2 !== "string") {
return false;
}
const len1 = s1.length;
const len2 = s2.length;
if(len1 !== len2) {
return false;
}
const s1Map = {};
for(let val of s1) {
if(s1Map[val]) {
s1Map[val] += 1;
}else {
s1Map[val] = 1;
}
}
for(let val of s2) {
if(s1Map[val] === undefined || s1Map[val] <= 0) {
return false;
}
s1Map[val] -= 1;
}
return true;
}
console.log("validAnagram output - ", validAnagram("danger", "gardenn"));*/
function firstAndLastIndex(arr, target) {
const len = arr.length;
if(len === 0 || arr[0] > target || arr[len-1] < target) {
return [-1, -1];
}
const firstIndex = getStartIndex(arr, target);
if(firstIndex === -1) {
return [-1, -1];
}
let lastIndex = getLastIndex(arr, target, firstIndex);
return [firstIndex, lastIndex];
}
function getStartIndex(arr, target) {
if(arr[0] === target) {
return 0;
}
let start = 0, end = arr.length-1;
while(start <= end) {
const mid = Math.floor((start+end)/2);
if(arr[mid] === target && arr[mid-1] < target) {
return mid;
}else if(arr[mid] < target) {
start = mid+1;
}else {
end = mid-1;
}
}
return -1;
}
function getLastIndex(arr, target, start) {
let end = arr.length-1;
if(arr[end] === target) {
return end;
}
while(start <= end) {
const mid = Math.floor((start+end)/2);
if(arr[mid] === target && arr[mid+1] > target) {
return mid;
}else if(arr[mid] > target) {
end = mid-1;
}else {
start = mid+1;
}
}
return -1;
}
console.log("firstAndLastIndex output - ", firstAndLastIndex([1,2,2,2,3,4], 2));
class MinHeap {
constructor(arr=[]) {
this.data = arr;
if(this.data.length > 1) {
for(let i=this.data.length-1;i >= 0;i--) {
this.siftdown(i);
}
}
}
siftup(index) {
if(index >= this.data.length || index <= 0) {
return null;
}
let parent = Math.floor((index-1)/2);
while(index > 0 && this.data[index] < this.data[parent]) {
const temp = this.data[index];
this.data[index] = this.data[parent];
this.data[parent] = temp;
index = parent;
parent = Math.floor((index-1)/2);
}
}
siftdown(index) {
if(index >= this.data.length/2 || index < 0) {
return null;
}
let left = 2*index+1;
let right = 2*index+2;
while(left < this.data.length && (this.data[index] > this.data[left] || (right < this.data.length && this.data[index] > this.data[right]))) {
const min = right >= this.data.length || this.data[left] <= this.data[right] ? left : right;
const temp = this.data[index];
this.data[index] = this.data[min];
this.data[min] = temp;
index = min;
left = 2*index+1;
right = 2*index+2;
}
}
insert(item) {
this.data.push(item);
this.siftup(this.data.length-1);
}
get_min() {
return this.data[0];
}
extract_min() {
if(this.data.length === 0) {
return null;
}
const return_val = this.data[0];
this.data[0] = this.data.pop();
this.siftdown(0);
return return_val;
}
update_by_index(val, index) {
if(index < 0 || index >= this.data.length) {
return null;
}
const current_val = this.data[index];
this.data[index] = val;
if(val > current_val) {
this.siftdown(index);
}else if(val < current_val) {
this.siftup(index);
}
return true;
}
update(oldVal, newVal) {
for(let i=0;i<this.data.length;i++) {
if(this.data[i] === oldVal) {
this.update_by_index(newVal, i);
return true;
}
}
return false;
}
}
class MaxHeap {
constructor(arr=[]) {
this.data = arr;
if(this.data.length > 1) {
for(let i=this.data.length-1;i>=0;i--) {
this.siftdown(i);
}
}
}
siftup(index) {
if(index <= 0 || index >= this.data.length) {
return null;
}
let parent = Math.floor((index-1)/2);
while(index > 0 && this.data[parent] < this.data[index]) {
const temp = this.data[index];
this.data[index] = this.data[parent];
this.data[parent] = temp;
index = parent;
parent = Math.floor((index-1)/2);
}
}
siftdown(index) {
if(index < 0 || index >= this.data.length-1) {
return null;
}
let left = 2*index+1;
let right = 2*index+2;
while(left < this.data.length && (this.data[index] < this.data[left] || (right < this.data.length && this.data[index] < this.data[right]))) {
const maxValIndex = right >= this.data.length || this.data[left] > this.data[right] ? left : right;
const temp = this.data[index];
this.data[index] = this.data[maxValIndex];
this.data[maxValIndex] = temp;
index = maxValIndex;
left = 2*index+1;
right = 2*index+2;
}
}
insert(item) {
this.data.push(item);
this.siftup(this.data.length-1);
}
get_max() {
return this.data[0];
}
extract_max() {
if(this.data.length === 0) {
return null;
}
const return_val = this.data[0];
this.data[0] = this.data.pop();
this.siftdown(0);
return return_val;
}
update_by_index(val, index) {
if(index < 0 || index >= this.data.length) {
return null;
}
const current_val = this.data[index];
this.data[index] = val;
if(val > current_val) {
this.siftup(index);
}else if(val < current_val) {
this.siftdown(index);
}
return true;
}
update(oldVal, newVal) {
for(let i=0;i<this.data.length;i++) {
if(this.data[i] === oldVal) {
this.update_by_index(newVal, i);
return true;
}
}
return false;
}
}
const inputArr = [4,2,9,7,5,6,7,1,3];
const k = 4;
function getKthLargestElement(arr, k) {
const len = arr.length;
if(len < k) {
return null;
}
const getMaxHeap = new MaxHeap(arr);
for(let i=1;i<k;i++) {
getMaxHeap.extract_max();
}
return getMaxHeap.get_max();
}
// Symetrical tree
function isSymetricalTree(root=null) {
if(root === null || (root.left === null && root.right === null)) {
return true;
}
function symetricalStatus(leftTree, rightTree) {
if(leftTree === null && rightTree === null) {
return true;
}else if(leftTree === null || rightTree === null) {
return false;
}else {
if(leftTree.val !== rightTree.val) {
return false;
}
return symetricalStatus(leftTree.left, rightTree.right) && symetricalStatus(leftTree.right, rightTree.left);
}
}
return symetricalStatus(root.left, root.right);
}
// Generate Valid Parenthesis of payer n
function Generate(n) {
function Parenthesis(num, diff, comb, combs) {
if(diff < 0 || diff > n) {
return null;
}else if(num === 0) {
if(diff === 0) {
combs.push(comb.join(""));
}
}else {
comb.push("(");
Parenthesis(num-1, diff+1, comb, combs);
comb.pop();
comb.push(")");
Parenthesis(num-1, diff-1, comb, combs);
comb.pop();
}
}
const combs = [];
Parenthesis(n*2, 0, [], combs);
return combs;
}
// console.log(Generate(3));
// Petrol pump station
function getIndex(gasArr, costArr) {
const len = gasArr.length;
let currentGas = 0;
let startIndex = 0, currentIndex = 0, isStarted = false;
while(startIndex < len) {
while(currentGas >= 0 && (currentIndex !== startIndex || !isStarted)) {
isStarted = true;
currentGas += gasArr[currentIndex]-costArr[currentIndex];
currentIndex = (currentIndex+1)%len;
}
if(currentGas >= 0 && currentIndex === startIndex) {
return startIndex;
}else if(currentIndex <= startIndex) {
return -1;
}
currentGas = 0;
isStarted = false;
startIndex = currentIndex;
}
return -1;
}
function getStationIndex(gasArr, costArr) {
const len = gasArr.length;
let totalGas = 0, prevGas = 0;
let startIndex = 0;
for(let i=0;i<len;i++) {
prevGas += gasArr[i]-costArr[i];
if(prevGas < 0) {
startIndex = i+1;
totalGas += prevGas;
prevGas = 0;
}
}
if(startIndex >= len || prevGas+totalGas < 0) {
return -1;
}else {
return startIndex;
}
}
console.log(getIndex([1,5,3,3,5,3,1,3,4,5],[5,2,2,8,2,4,2,5,1,2]));
console.log(getIndex([2,2,2,2,2,2,2,2,2,2],[1,1,1,1,1,1,1,1,1,50]));
console.log(getStationIndex([1,5,3,3,5,3,1,3,4,5],[5,2,2,8,2,4,2,5,1,2]));
console.log(getStationIndex([2,2,2,2,2,2,2,2,2,2],[1,1,1,1,1,1,1,1,1,50]));
// All Schedule Problem
function isAllSchedule(n, preRequisiteArr=[]) {
const len = preRequisiteArr.length;
if(len < 2) {
return true;
}
const doneCourses = new Set();
let ongoingCourse = new Set();
const courseDependencyMap = new Map();
for(let [mainCourse, dependentCourse] of preRequisiteArr) {
if(courseDependencyMap.has(mainCourse)) {
courseDependencyMap.set(mainCourse, [...courseDependencyMap.get(mainCourse), dependentCourse]);
}else {
courseDependencyMap.set(mainCourse, [dependentCourse]);
}
}
function traverseMap(mainCourse, dependentCourseArr) {
if(!dependentCourseArr || dependentCourseArr.length === 0 || doneCourses.has(mainCourse)) {
doneCourses.add(mainCourse);
return true;
}else if(ongoingCourse.has(mainCourse)) {
return false;
}else {
ongoingCourse.add(mainCourse);
for(let course of dependentCourseArr) {
if(!traverseMap(course, courseDependencyMap.get(course))) {
return false;
}
}
ongoingCourse.delete(mainCourse);
doneCourses.add(mainCourse);
return true;
}
}
for(let [course,dependentCourseArr] of courseDependencyMap) {
if(doneCourses.has(course)) {
continue;
}else {
if(!traverseMap(course, dependentCourseArr)) {
return false;
}
ongoingCourse = new Set();
}
}
return true;
}
console.log(isAllSchedule(6, [[0,1],[1,3],[2,1],[4,1],[4,2],[5,3],[5,4]]));
// create permutation with number n starting with 1
function swap(str, index1, index2) {
if(index1 === index2) {
return str;
}
const str1 = str[index1];
const str2 = str[index2];
return str.substring(0,index1)+str2+str.substring(index1+1,index2)+str1+str.substring(index2+1);
}
function printPermutation(str, start, end) {
if(start === end) {
console.log(str);
return;
}
for(let i=start;i<=end;i++) {
let tempStr = swap(str,start,i);
printPermutation(tempStr, start+1, end);
}
return;
}
function createAllPermutation(n) {
let str = "";
for(let i=1;i<=n;i++) {
str += i;
}
if(n < 2) {
console.log(str);
return;
}
printPermutation(str, 0, n-1);
return;
}
createAllPermutation(3);
// give kth permutation
function factorial(n) {
let result = 1, resultMap = {};
for(let i=1;i<=n;i++) {
result *= i;
resultMap[i] = result;
}
return resultMap;
}
function getKthPermutation(n, k) {
const totalPermMap = factorial(n);
if(k < 1 || k > totalPermMap[n]) {
return null;
}
const permArr = [];
for(let i=1;i<=n;i++) {
permArr.push(i);
}
if(k === 1) {
return permArr.join("");
}
const resultArr = [];
k -= 1;
while(n > 0) {
const totalPerm = totalPermMap[n];
const partLength = totalPerm/n;
const section = Math.floor(k/partLength);
const currentNum = permArr[section];
resultArr.push(currentNum);
permArr.splice(section, 1);
n--;
k = k%partLength;
}
return resultArr.join("");
}
console.log(getKthPermutation(4,16));
// window substring problem
function mapLetters(s1) {
const map1 = {};
for(let str of s1) {
if(typeof map1[str] === "number") {
map1[str] += 1;
}else {
map1[str] = 1;
}
}
return map1;
}
function getMinimumSubstring(s1, s2) {
const len1 = s1.length, len2 = s2.length;
if(len2 > len1) {
return null;
}
const map1 = mapLetters(s1), map2 = mapLetters(s2);
let totalConditions = 0;
for(let key of Object.keys(map2)){
if(!map1[key] || map1[key] < map2[key]) {
return null;
}
totalConditions++;
};
const prevMap = mapLetters(s1.substr(0, len2-1));
let prevCondition = 0;
Object.keys(prevMap).forEach(key => {
if(key in map2 && prevMap[key] >= map2[key]) {
prevCondition++;
}
});
for(let length=len2;length<=len1;length++) {
if(s1[length-1] in prevMap) {
prevMap[s1[length-1]] += 1;
}else {
prevMap[s1[length-1]] = 1;
}
if(s1[length-1] in map2 && prevMap[s1[length-1]] === map2[s1[length-1]]) {
prevCondition++;
}
const currMap = Object.assign({},prevMap);
let currCondition = prevCondition;
for(let index=0;index<=len1-length;index++) {
if(index > 0) {
const newChar = s1[index+length-1];
const oldChar = s1[index-1];
if(newChar in currMap) {
currMap[newChar] += 1;
}else {
currMap[newChar] = 1;
}
if(newChar in map2 && currMap[newChar] === map2[newChar]) {
currCondition++;
}
if(oldChar in map2 && currMap[oldChar] === map2[oldChar]) {
currCondition--;
}
currMap[oldChar] -= 1;
}
if(currCondition === totalConditions) {
return s1.substr(index, length);
}
}
}
return null;
}
function getMinSubString(src, tgt) {
const srcLen = src.length, tgtLen = tgt.length;
if(tgtLen > srcLen) {
return null;
}
const srcMap = mapLetters(src), tgtMap = mapLetters(tgt);
let totalConditions = 0;
for(let key of Object.keys(tgtMap)){
if(!srcMap[key] || srcMap[key] < tgtMap[key]) {
return null;
}
totalConditions++;
};
let start = 0, end = srcLen-1, left = 0, satisfied = 0;
const currMap = {};
for(let right=0;right<srcLen;right++) {
currMap[src[right]] = typeof currMap[src[right]] === "number" ? currMap[src[right]]+1 : 1;
if(src[right] in tgtMap && currMap[src[right]] === tgtMap[src[right]]) {
satisfied++;
}
if(satisfied === totalConditions) {
while(!(src[left] in tgtMap) || currMap[src[left]] > tgtMap[src[left]]) {
currMap[src[left]] -= 1;
left++;
}
if(end-start > right-left) {
start = left;
end = right;
}
}
}
return src.substring(start, end+1);
}
console.log(getMinimumSubstring("ADCFEBECEABEBADFCDFCBFCBEAD", "ABCA"));
console.log(getMinimumSubstring("ADCFEBECEABEBADFCDFCBFCBEAD", "ABCZ"));
console.log(getMinSubString("ADCFEBECEABEBADFCDFCBFCBEAD", "ABCA"));
console.log(getMinSubString("ADCFEBECEABEBADFCDFCBFCBEAD", "ABCZ"));
console.log(getMinSubString("ADCFEBECEABEBADFCDFCBFCBEAD", "ADCFEBECEABEBADFCDFCBFCBEAD"));
//Largest Rectangle in histogram
function getSmallestFromLeft(arr) {
const stack = [], result = [-1];
stack.push({value: arr[0], index: 0});
for(let i=1;i<arr.length;i++) {
while(stack.length > 0 && stack[stack.length-1].value > arr[i]) {
stack.pop();
}
if(stack.length === 0) {
result.push(-1);
}else {
result.push(stack[stack.length-1].index);
}
stack.push({value: arr[i], index: i});
}
return result;
}
function getSmallestFromRight(arr) {
const len = arr.length;
const stack = [], result = new Array(len);
result[len-1] = len;
stack.push({value: arr[len-1], index: len-1});
for(let i=len-2;i>=0;i--) {
while(stack.length > 0 && stack[stack.length-1].value > arr[i]) {
stack.pop();
}
if(stack.length === 0) {
result[i] = len;
}else {
result[i] = stack[stack.length-1].index;
}
stack.push({value: arr[i], index: i});
}
return result;
}
function getLargestRectangle(heights) {
const len = heights.length;
if(len === 0) {
return 0;
}else if(len === 1) {
return heights[0];
}
const fromLeft = getSmallestFromLeft(heights);
const fromRight = getSmallestFromRight(heights);
let result = -Infinity;
for(let i=0;i<len;i++) {
result = Math.max(result, heights[i]*(fromRight[i]-fromLeft[i]-1));
}
return result;
}
console.log(getLargestRectangle([3,2,4,5,7,6,1,3,8,9,11,10,7,5,2,6]));
JavaScript
INFO