The following solution uses “Bottom up dynamic programming” approach.
/**
* @param {number} amount
* @param {number[]} coins
* @return {number}
*/
const change = (amount, coins) => {
const dp = Array(amount + 1).fill(0);
dp[0] = 1;
for (const coin of coins) {
for (let i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
};
// Analysis n - length of coins
// m - amount
// Time Complexity O(n*m)
// Space Complexity O(m) /**
* @param {string} S
* @return {string}
*/
const reorganizeString = (S) => {
let counts = [];
for (let i = 0; i < 26; i++) {
counts[i] = 0;
}
for (let i = 0; i < S.length; i++) {
counts[S.charAt(i).charCodeAt(0) - 'a'.charCodeAt(0)] += 100;
}
for (let i = 0; i < 26; i++) {
counts[i] += i;
}
//Encoded counts[i] = 100*(actual count) + (i)
counts.sort((a, b) => a - b);
let t = 1;
let ret = [];
for (let i = 0; i < 26; i++) {
const ch = String.fromCharCode('a'.charCodeAt(0) + (counts[i] % 100));
let count = Math.floor(counts[i] / 100);
if (count > Math.floor((S.length + 1) / 2))
return '';
while (count > 0) {
if (t >= S.length)
t = 0;
ret[t] = ch;
t += 2;
count--;
}
}
return ret.join('');
};
console.log(reorganizeString('aab'));
// 'aba'Given an encoded string 3[abc]2[bc] the decoded output should be of the form “abcabcabcbcbc”. Assume that all the brackets are well formed and that all strings are encoded correctly.
/**
* @param {string} s
* @return {string}
*/
const decodeString = (str) => {
const stack = [];
for (const ch of str.split('')) {
if (ch === ']') {
let currStr = '';
while (stack[stack.length - 1] !== '[') {
currStr = stack.pop() + currStr;
}
stack.pop();
let k = 0;
let base = 1;
while (stack.length && parseInt(stack[stack.length - 1]) >= 0) {
k += parseInt(stack.pop()) * base;
base *= 10;
}
if (k !== 0) {
stack.push(currStr.repeat(k));
}
} else {
stack.push(ch);
}
}
return stack.join('');
};Given a list of meetings, that may or may not overlap, calculate the total number of rooms that are required to conduct all the meetings according to the schedule.
Java
class Solution {
public int minMeetingRooms(int[][] intervals) {
int[] start = new int[intervals.length];
int[] end = new int[intervals.length];
for (int i = 0; i < intervals.length; i++) {
start[i] = intervals[i][0];
end[i] = intervals[i][1];
}
Arrays.sort(start);
Arrays.sort(end);
int endPtr = 0, rooms = 0;
for (int i = 0; i < intervals.length; i++) {
if (start[i] < end[endPtr]) {
rooms++;
} else {
endPtr++;
}
}
return rooms;
}
}Runtime Complexity: O(nlog(n))
Space Complexity: O(n)
Javascript (ES6)
/**
* @param {number[][]} intervals
* @return {number}
*/
const minMeetingRooms = (intervals) => {
let startList = [];
let endList = [];
let endPos = 0;
let rooms = 0;
for (const [start, end] of intervals) {
startList.push(start);
endList.push(end);
}
startList.sort((a, b) => a - b);
endList.sort((a, b) => a - b);
for (let i = 0; i < intervals.length; i++) {
if (startList[i] < endList[endPos]) {
rooms++;
} else {
endPos++;
}
}
return rooms;
};
// console.log(minMeetingRooms([[7, 10],[2, 4]]));
// 1Given a non-empty string “word” can it be broken into a list of non-empty words contained in a dictionary ? The words can be repeated.
Java
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
return word_Break(s, new HashSet(wordDict), 0, new Boolean[s.length()]);
}
public boolean word_Break(String s, Set<String> wordDict, int start, Boolean[] memo) {
if (start == s.length()) {
return true;
}
if (memo[start] != null) {
return memo[start];
}
for (int end = start + 1; end <= s.length(); end++) {
if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end, memo)) {
return memo[start] = true;
}
}
return memo[start] = false;
}
}JavaScript (ES6)
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
const wordBreak = (s, wordDict) => canWordBreak(s, 0, wordDict);
const dp = {};
const canWordBreak = (word, index, wordDict) => {
if (index === word.length) {
return dp[index] = true;
}
if (dp[index] !== undefined) {
return dp[index];
}
for (let breakIndex = index + 1; breakIndex <= word.length; breakIndex++) {
if (wordDict.indexOf(word.substring(index, breakIndex)) > -1 && canWordBreak(word, breakIndex, wordDict)) {
return dp[index] = true;
}
}
return dp[index] = false;
}
// console.log(wordBreak("catsandog",
// ["cats","dog","sand","and","cat"]));
// falseThe following ES6 Javascript code, helps to throttle function calls without discarding them. It uses a queue to keep track of all the function calls. We can use the reset method to reset the queue and the setTimeout() method.
const throttle = (fn, delay) => {
let timeout;
let noDelay = true;
let queue = [];
const start = () => {
if (queue.length) {
const {context, args} = queue.shift();
fn.apply(context, arguments);
timeout = setTimeout(start, delay);
} else {
noDelay = true;
}
};
const ret = (...args) => {
queue.push({
context: this,
args,
});
if (noDelay) {
noDelay = false;
start();
}
};
ret.reset = () => {
clearTimeout(timeout);
queue = [];
};
return ret;
};
/* Usage */
const print = (number) => {
console.log(`Hello World! ${number}`);
}
const test = throttle(print, 3000);
test(1);
test(2);
test(3);
// test.reset(); This will clear the queue and hence the above test case will only output the first line.
// Output:
// Hello World! 1
// Hello World! 2
// Hello World! 3
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
if (!s || s.length === 0)
return '';
let start = 0,
end = 0;
for (let i = 0; i < s.length; i++) {
// There can be 2n - 1 centers for the palindromes. We can
// include each character and the space in between the
// characters.
let l1 = expandAroundCenters(s, i, i);
let l2 = expandAroundCenters(s, i, i + 1);
let l = Math.max(l1, l2);
if (l > end - start) {
start = i - Math.floor((l - 1) / 2);
end = i + Math.floor(l / 2);
}
}
return s.substring(start, end + 1);
};
var expandAroundCenters = function(s, left, right) {
while (left >= 0 &&
right < s.length &&
s.charAt(left) === s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
// Time Complexity O(n ^ 2)
// Space Complexity O(1)
The following is a method to perform smooth animation of an element from left to right given the duration and distance. In this example, the element is being animated from left to right at 60 fps for a duration of 5 seconds and a distance of 100px. The animation is cancelled midway at 3 seconds using cancelAnimationFrame().
const animate = (element, duration/*seconds*/, distance) => {
if (!element) {
return;
}
element.style.position = 'relative';
let start;
let requestID;
const durationMs = duration * 1000; // Milliseconds.
const step = (timestamp) => {
if (start === undefined)
start = timestamp;
const elapsed = timestamp - start;
const fraction = Math.min(elapsed / durationMs, 1);
element.style.transform = `translateX(${fraction * distance}px)`;
if (elapsed < durationMs) { // Stop the animation after duration.
requestID = requestAnimationFrame(step);
}
}
requestID = requestAnimationFrame(step);
return () => {
element.style.transform = 'translateX(0px)';
cancelAnimationFrame(requestID);
};
}
const cancel = animate(document.getElementById('child'), 5, 100);
setTimeout(() => {
cancel();
}, 3000);<div id="parent">
<div id="child">
</div>
</div>
#parent {
height: 200px;
width: 200px;
background-color: lightblue;
}
#child {
height: 100px;
width: 100px;
background-color: lightgreen;
}
This can be further optimized using the FLIP technique
Given an input array that consists of numbers that may consist of duplicates, return the position of the number that is picked. This position has to be a “Random Pick Index” if the picked number has duplicates.
Example: Input: [1, 2, 4, 4, 4], Pick -> 4 then you can return 2, 3, or 4 randomly with equal probability. If 1 is the pick then 0 needs to be returned as there is only one occurrence at 0.
/**
* @param {number[]} nums
*/
var Solution = function(nums) {
this.obj = {};
for (let i = 0; i < nums.length; i++) {
if (this.obj[nums[i]] === undefined)
this.obj[nums[i]] = [];
this.obj[nums[i]].push(i);
}
};
/**
* @param {number} target
* @return {number}
*/
Solution.prototype.pick = function(target) {
var dupes = this.obj[target].length;
return dupes === 1 ?
this.obj[target][0] :
this.obj[target][Math.floor(dupes * Math.random())];
};
/**
* Your Solution object will be instantiated and called as such:
* var obj = new Solution(nums)
* var param_1 = obj.pick(target)
*/