Javascript Problem Solving
1 function composition
Given an array of functions [f1, f2, f3, ..., fn], return a new function fn that is the function composition of the array of functions.
The function composition of [f(x), g(x), h(x)] is fn(x) = f(g(h(x))).
The function composition of an empty list of functions is the identity function f(x) = x.
You may assume each function in the array accepts one integer as input and returns one integer as output.
Example 1:
Input: functions = [x => x + 1, x => x * x, x => 2 * x], x = 4 Output: 65 Explanation: Evaluating from right to left ... Starting with x = 4. 2 * (4) = 8 (8) * (8) = 64 (64) + 1 = 65
var compose = function(functions) {
return function(x) {
if(functions.length ===0){
return x;
}
let result = x;
for(let i =functions.length-1; i>=0;i--){
let func = functions[i];
result = func(result)
}
return result;
}
};
const fn = compose([x => x + 1, x => 2 * x])
console.log(fn(4))
2 Arguments Length
Write a function argumentsLength that returns the count of arguments passed to it.
Example 1:
Input: args = [5] Output: 1 Explanation: argumentsLength(5); // 1
var argumentsLength = function(...args) {
console.log(args.length)
};
argumentsLength(1, 2, 3); // 3
3 called at most once
Given a function fn, return a new function that is identical to the original function except that it ensures fn is called at most once.
The first time the returned function is called, it should return the same result as fn. Every subsequent time it is called, it should return undefined.
Example 1:
Input: fn = (a,b,c) => (a + b + c), calls = [[1,2,3],[2,3,6]]
Output: [{"calls":1,"value":6}]
Explanation:
const onceFn = once(fn);
onceFn(1, 2, 3); // 6
onceFn(2, 3, 6); // undefined, fn was not called
var once = function(fn) {
let hasExecuted = false;
return function(...args){
if (!hasExecuted) {
hasExecuted = true;
return fn(...args);
}else{
return undefined;
}
}
};
/**
* let fn = (a,b,c) => (a + b + c)
* let onceFn = once(fn)
*
* onceFn(1,2,3); // 6
* onceFn(2,3,6); // returns undefined without calling fn
*/
4 Resolve Both Promises
Given two promises promise1 and promise2, return a new promise. promise1 and promise2 will both resolve with a number. The returned promise should resolve with the sum of the two numbers.
Example 1:
Input: promise1 = new Promise(resolve => setTimeout(() => resolve(2), 20)), promise2 = new Promise(resolve => setTimeout(() => resolve(5), 60)) Output: 7 Explanation: The two input promises resolve with the values of 2 and 5 respectively. The returned promise should resolve with a value of 2 + 5 = 7. The time the returned promise resolves is not judged for this problem.
var addTwoPromises = async function(promise1, promise2) {
const value1 = await promise1; //resolove the first promise
const value2 = await promise2; //resolve the second
return value1 + value2; // add the result and return
};
addTwoPromises(Promise.resolve(2), Promise.resolve(2))
.then(data => {
console.log('resolved value', data);
});
const promiseA = new Promise((resolve) => setTimeout(() => resolve(5), 1000));
const promiseB = new Promise((resolve) => setTimeout(() => resolve(10), 2000));
addTwoPromises(promiseA, promiseB)
.then(data => {
console.log('resolved value', data);
});
5 sleep
Given a positive integer millis, write an asynchronous function that sleeps for millis milliseconds. It can resolve any value.
Example 1:
Input: millis = 100
Output: 100
Explanation: It should return a promise that resolves after 100ms.
let t = Date.now();
sleep(100).then(() => {
console.log(Date.now() - t); // 100
});
async function sleep(millis) {
await new Promise((resolve) => setTimeout(() => resolve(), millis))
}
let t = Date.now()
sleep(100).then(() => console.log(Date.now() - t)) // 100
6 Timeout Cancellation
Given a function fn, an array of arguments args, and a timeout t in milliseconds, return a cancel function cancelFn.
After a delay of cancelTimeMs, the returned cancel function cancelFn will be invoked.
setTimeout(cancelFn, cancelTimeMs) Initially, the execution of the function fn should be delayed by t milliseconds.
If, before the delay of t milliseconds, the function cancelFn is invoked, it should cancel the delayed execution of fn. Otherwise, if cancelFn is not invoked within the specified delay t, fn should be executed with the provided args as arguments.
Example 1:
Input: fn = (x) => x * 5, args = [2], t = 20
Output: [{"time": 20, "returned": 10}]
Explanation:
const cancelTimeMs = 50;
const cancelFn = cancellable((x) => x * 5, [2], 20);
setTimeout(cancelFn, cancelTimeMs);
The cancellation was scheduled to occur after a delay of cancelTimeMs (50ms), which happened after the execution of fn(2) at 20ms.
var cancellable = function(fn, args, t) {
let shouldCancel = false;
setTimeout(() => {
if(!shouldCancel){
fn(...args)
}
}, t);
return ()=> shouldCancel=true;
};
const result = [];
const fn = (x) => x * 5;
const args = [2], t = 20, cancelTimeMs = 50;
const start = performance.now();
const log = (...argsArr) => {
const diff = Math.floor(performance.now() - start);
result.push({"time": diff, "returned": fn(...argsArr)});
}
const cancel = cancellable(log, args, t);
const maxT = Math.max(t, cancelTimeMs);
setTimeout(cancel, cancelTimeMs);
setTimeout(() => {
console.log(result); // [{"time":20,"returned":10}]
}, maxT + 15)
7 Interval Cancellation
Given a function fn, an array of arguments args, and an interval time t, return a cancel function cancelFn.
After a delay of cancelTimeMs, the returned cancel function cancelFn will be invoked.
setTimeout(cancelFn, cancelTimeMs) The function fn should be called with args immediately and then called again every t milliseconds until cancelFn is called at cancelTimeMs ms.
Example 1:
Input: fn = (x) => x * 2, args = [4], t = 35
Output:
[
{"time": 0, "returned": 8},
{"time": 35, "returned": 8},
{"time": 70, "returned": 8},
{"time": 105, "returned": 8},
{"time": 140, "returned": 8},
{"time": 175, "returned": 8}
]
var cancellable = function(fn, args, t) {
fn(...args);
const intervalId = setInterval(()=>{
fn(...args)
},t)
return ()=>clearInterval(intervalId);
};
const result = [];
const fn = (x) => x * 2;
const args = [4], t = 35, cancelTimeMs = 190;
const start = performance.now();
const log = (...argsArr) => {
const diff = Math.floor(performance.now() - start);
result.push({"time": diff, "returned": fn(...argsArr)});
}
const cancel = cancellable(log, args, t);
setTimeout(cancel, cancelTimeMs);
setTimeout(() => {
console.log(result); // [
// {"time":0,"returned":8},
// {"time":35,"returned":8},
// {"time":70,"returned":8},
// {"time":105,"returned":8},
// {"time":140,"returned":8},
// {"time":175,"returned":8}
// ]
}, cancelTimeMs + t + 15)
8 Memoize
function memoize(fn) {
const memory = new Map();
return function(...args) {
const key = JSON.stringify(args);
if(memory.has(key)){
return memory.get(key);
}
const result = fn.apply(this,args);
memory.set(key,result)
return result;
}
}
9 Promise Time Limit
Given an asynchronous function fn and a time t in milliseconds, return a new time limited version of the input function. fn takes arguments provided to the time limited function.
The time limited function should follow these rules:
If the fn completes within the time limit of t milliseconds, the time limited function should resolve with the result. If the execution of the fn exceeds the time limit, the time limited function should reject with the string "Time Limit Exceeded".
Example 1:
Input:
fn = async (n) => {
await new Promise(res => setTimeout(res, 100));
return n * n;
}
inputs = [5]
t = 50
Output: {"rejected":"Time Limit Exceeded","time":50}
Explanation:
const limited = timeLimit(fn, t)
const start = performance.now()
let result;
try {
const res = await limited(...inputs)
result = {"resolved": res, "time": Math.floor(performance.now() - start)};
} catch (err) {
result = {"rejected": err, "time": Math.floor(performance.now() - start)};
}
console.log(result) // Output
The provided function is set to resolve after 100ms. However, the time limit is set to 50ms. It rejects at t=50ms because the time limit was reached.
var timeLimit = function (fn, t) {
return async function (...args) {
return new Promise((resolve, reject) => {
const timeoutId = setTimeout(() => {
reject("Time Limit Exceeded");
}, t);
fn(...args)
.then((result) => {
clearTimeout(timeoutId);
resolve(result);
})
.catch((e) => {
clearTimeout(timeoutId);
reject(e);
});
});
};
};
10 Valid Parentheses
Given a string s containing just the characters '(', ')', ', ', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()" Output: true
var isValid = function(s) {
let stack = [];
let pairs=["{}","[]","()"]
for(let char of s){
if (char === '(' || char === '{' || char === '[') {
stack.push(char)
}else {
const top = stack.pop()
let currentPair = top+char;
if(!pairs.includes(currentPair) ){
return false;
}
}
}
return stack.length == 0;
};
11 Check if obj is Empty
Given an object or an array, return if it is empty.
An empty object contains no key-value pairs. An empty array contains no elements. You may assume the object or array is the output of JSON.parse.
Example 1:
Input: obj = {"x": 5, "y": 42}
Output: false
Explanation: The object has 2 key-value pairs so it is not empty.
var isEmpty = function(obj) {
return Object.keys(obj).length === 0;
};
12 Remove Element
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.
Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:
Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums. Return k.
Custom Judge:
The judge will test your solution with the following code:
int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
// It is sorted with no values equaling val.
int k = removeElement(nums, val); // Calls your implementation
assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.
Example 1:
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).
var removeElement = function(nums, val) {
let k=0;
for(let num of nums){
if(num !=val){
nums[k]=num
k++;
}
}
return k;
};
13 Chunk Array
var chunk = function(arr, size) {
let start=0;
let end= size;
let chenkArr = [];
for(let i =0;i<arr.length;i=i+size){
const newArr= arr.slice(i,i+size);
chenkArr.push(newArr)
console.log(chenkArr)
}
};
14 Increment the large integer
You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.
Increment the large integer by one and return the resulting array of digits.
Example 1:
Input: digits = [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123. Incrementing by one gives 123 + 1 = 124. Thus, the result should be [1,2,4].
function plusOne(digits) {
const n = digits.length;
for (let i = n - 1; i >= 0; i--) {
digits[i] += 1;
if (digits[i] < 10) {
return digits;
}
digits[i] = 0;
}
digits.unshift(1);
return digits;
}
15 Roman to Decimal
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II. Example 1:
Input: s = "III" Output: 3 Explanation: III = 3. Example 2:
Input: s = "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3.
var romanToInt = function(s) {
let symbolMap = {
I:1,
V:5,
X:10,
L:50,
C:100,
D:500,
M:1000
}
let number=0;
for(let i=0; i<s.length;i++){
let currentValue = symbolMap[s[i]];
let nextValue = symbolMap[s[i+1]];
console.log(currentValue,nextValue)
if(nextValue && nextValue > currentValue){
number += nextValue - currentValue
i++;
}else{
number = number + currentValue;
}
}
console.log(number)
return number;
};
16 Search Insert
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [1,3,5,6], target = 5 Output: 2 Example 2:
Input: nums = [1,3,5,6], target = 2 Output: 1
var searchInsert = function(nums, target) {
for (let i = 0; i < nums.length; i++) {
if (nums[i] >= target) {
return i;
}
}
return nums.length;
};
17 One plus
You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.
Increment the large integer by one and return the resulting array of digits.
Example 1:
Input: digits = [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123. Incrementing by one gives 123 + 1 = 124. Thus, the result should be [1,2,4].
var plusOne = function(digits) {
for(let i=digits.length-1; i>=0; i--){
const sum = digits[i] +1;
digits[i]=sum;
if(sum<10){
return digits;
}
digits[i] = 0;
}
digits.unshift(1);
console.log(digits)
return digits
};
18 Add Binary
Given two binary strings a and b, return their sum as a binary string.
Example 1:
Input: a = "11", b = "1" Output: "100" Example 2:
Input: a = "1010", b = "1011" Output: "10101"
var addBinary = function(a, b) {
let i = a.length - 1;
let j = b.length - 1;
let sum = '';
let carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
const digitA = i >= 0 ? parseInt(a[i]) : 0;
const digitB = j >= 0 ? parseInt(b[j]) : 0;
const currentSum = digitA + digitB + carry;
const currentDigit = currentSum % 2;
carry = Math.floor(currentSum / 2);
sum = currentDigit.toString() + sum;
i--;
j--;
}
return sum;
};
19 Sqrt(x) , leet-code 69
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator.
For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.
Example 1:
Input: x = 4 Output: 2 Explanation: The square root of 4 is 2, so we return 2. Example 2:
Input: x = 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.
- using linear search whichis very slow
if(x==0)return 0;
if(x==1)return 1;
if(x==2)return 1;
for(let i=0; i<x; i++){
if(i*i==x){
return i;
}else if(i*i>x){
return i-1;
}
}
- using binary search which is faster
var mySqrt = function(x) {
if(x===0)return 0;
let left =1;
let right =x
while(left<=right){
let mid = Math.floor((left +right)/2);
if(mid*mid <x){
left = mid +1
}else if(mid*mid >x){
right = mid-1
}else return mid;
}
return right
};
20 Climbing Stairs, 70
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top.
- 1 step + 1 step
- 2 steps Example 2:
Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top.
- 1 step + 1 step + 1 step
- 1 step + 2 steps
- 2 steps + 1 step
var climbStairs = function(n) {
if(n==1)return 1;
if(n==2)return 2;
let steps=[1,2];
for(let i=2; i<n;i++){
steps.push(steps[i-1]+ steps[i-2])
}
console.log(steps)
return steps[n-1];
};
21 Remove Duplicates from Sorted List 83
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
var deleteDuplicates = function(head) {
let currentNode = head;
while(currentNode != null && currentNode.next != null){
console.log(currentNode.val)
if(currentNode.val== currentNode.next.val){
currentNode.next = currentNode.next.next;
}else{
currentNode = currentNode.next;
}
}
return head;
};
22 Merge Sorted Array 88
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Explanation: The arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
var merge = function(nums1, m, nums2, n) {
let i = m-1;
let j= n-1;
let k = m +n -1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
console.log(nums1)
return nums1;
};
23 Binary Egents
Return an English translated sentence of the passed binary string.
The binary string will be space separated. Example: binaryAgent("01000001 01110010 01100101 01101110 00100111 01110100 00100000 01100010 01101111 01101110 01100110 01101001 01110010 01100101 01110011 00100000 01100110 01110101 01101110 00100001 00111111") should return the string Aren't bonfires fun!?
function binaryToEnglish(binaryString) {
const binaryArray = binaryString.split(' '); // Split the binary string into an array of binary numbers
let englishSentence = '';
for (let binaryNum of binaryArray) {
const decimalNum = parseInt(binaryNum, 2); // Convert binary number to decimal
const char = String.fromCharCode(decimalNum); // Convert decimal to ASCII character
englishSentence += char;
}
return englishSentence;
}
24 Number to roman Numerals
function romanize(num) {
var lookup = {
M:1000,
CM:900,
D:500,
CD:400,
C:100,
XC:90,
L:50,
XL:40,
X:10,
IX:9,
V:5,
IV:4,
I:1
};
let roman = '';
for (let i in lookup ) {
while ( num >= lookup[i] ) {
roman += i;
num -= lookup[i];
}
}
return roman;
}
24 Caesars Cipher
One of the simplest and most widely known ciphers is a Caesar cipher, also known as a shift cipher. In a shift cipher the meanings of the letters are shifted by some set amount.
A common modern use is the ROT13 cipher, where the values of the letters are shifted by 13 places. Thus A ↔ N, B ↔ O and so on.
Write a function which takes a ROT13 encoded string as input and returns a decoded string.
All letters will be uppercase. Do not transform any non-alphabetic character (i.e. spaces, punctuation), but do pass them on.
function rot13(str) {
let words = str.split(" ")
let newStr=[];
for(let word of words){
let newWord="";
for(let char of word){
const isUppercase = /^[A-Z]$/.test(char);
if(isUppercase){
const asciiCode = char.charCodeAt(0);
let newAski = asciiCode+13;
if(newAski>90){
newAski = 64+ (newAski-90);
}
const character = String.fromCharCode(newAski);
newWord += character;
}else{
newWord += char;
}
}
console.log(newWord)
newStr.push(newWord)
}
console.log(newStr.join(" "))
return newStr.join(" ");
}
rot13("SERR PBQR PNZC");
25 Symmetric Tree 101
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
function isSymmetric(root) {
if (!root) {
return true; // An empty tree is considered symmetric
}
return isMirror(root.left, root.right);
}
function isMirror(node1, node2) {
if (!node1 && !node2) {
return true; // Both nodes are null, considered symmetric
}
if (!node1 || !node2) {
return false; // One node is null, considered not symmetric
}
if (node1.val !== node2.val) {
return false; // Values of the nodes are different, considered not symmetric
}
// Recursively check if the left subtree of node1 is a mirror of the right subtree of node2
// and if the right subtree of node1 is a mirror of the left subtree of node2
return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);
}
const root = {
val: 1,
left: {
val: 2,
left: {
val: 3,
left: null,
right: null,
},
right: {
val: 4,
left: null,
right: null,
},
},
right: {
val: 2,
left: {
val: 4,
left: null,
right: null,
},
right: {
val: 3,
left: null,
right: null,
},
},
};
// Execute the isSymmetric function
const result = isSymmetric(root);
// Print the result
console.log(result);
26 Maximum Depth of Binary Tree 104
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
var maxDepth = function(root) {
if(!root){
return 0;
}
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth)+1;
};
27 Same Tree 100
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
var isSameTree = function(p, q) {
if (!p && !q) {
return true;
}
if (!p || !q) {
return false;
}
if (p.val !== q.val) {
return false;
}
const leftSubtreeSame = isSameTree(p.left, q.left);
const rightSubtreeSame = isSameTree(p.right, q.right);
return leftSubtreeSame && rightSubtreeSame;
};
28 Binary Tree Inorder Traversal
Given the root of a binary tree, return the inorder traversal of its nodes' values.
var inorderTraversal = function(root) {
const result = [];
inorderHelper(root, result);
return result;
};
function inorderHelper(node, result) {
if (node === null) {
return;
}
inorderHelper(node.left, result);
result.push(node.val);
inorderHelper(node.right, result);
}