JavaScript Practice Coding Examples

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function twoSum(nums, target) {
 const map = new Map();

 for (let i = 0; i < nums.length; i++) {
 const complement = target - nums[i];

 if (map.has(complement)) {
 return [map.get(complement), i];
 }

 map.set(nums[i], i);
 }

 return [];
}

// Test cases
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSum([3, 2, 4], 6)); // [1, 2]
console.log(twoSum([3, 3], 6)); // [0, 1]

// Time Complexity: O(n)
// Space Complexity: O(n)

/**
 * @param {string} s
 * @return {string}
 */
function reverseString(s) {
 return s.split('').reverse().join('');
}

// Alternative: Using two pointers
function reverseStringTwoPointers(s) {
 const arr = s.split('');
 let left = 0;
 let right = arr.length - 1;

 while (left < right) {
 [arr[left], arr[right]] = [arr[right], arr[left]];
 left++;
 right--;
 }

 return arr.join('');
}

// Test cases
console.log(reverseString("hello")); // "olleh"
console.log(reverseStringTwoPointers("world")); // "dlrow"

// Time Complexity: O(n)
// Space Complexity: O(n)

/**
 * @param {string} s
 * @return {boolean}
 */
function isPalindrome(s) {
 const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '');
 return cleaned === cleaned.split('').reverse().join('');
}

// Alternative: Two pointers
function isPalindromeTwoPointers(s) {
 const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '');
 let left = 0;
 let right = cleaned.length - 1;

 while (left < right) {
 if (cleaned[left] !== cleaned[right]) {
 return false;
 }
 left++;
 right--;
 }

 return true;
}

// Test cases
console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("race a car")); // false
console.log(isPalindromeTwoPointers("Was it a car or a cat I saw?")); // true

// Time Complexity: O(n)
// Space Complexity: O(n)

/**
 * @param {number} n
 * @return {string[]}
 */
function fizzBuzz(n) {
 const result = [];

 for (let i = 1; i <= n; i++) {
 if (i % 15 === 0) {
 result.push("FizzBuzz");
 } else if (i % 3 === 0) {
 result.push("Fizz");
 } else if (i % 5 === 0) {
 result.push("Buzz");
 } else {
 result.push(i.toString());
 }
 }

 return result;
}

// Test cases
console.log(fizzBuzz(15)); 
// ["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

// Time Complexity: O(n)
// Space Complexity: O(n)

/**
 * @param {number[]} nums
 * @return {number}
 */
function maxSubArray(nums) {
 let maxSum = nums[0];
 let currentSum = nums[0];

 for (let i = 1; i < nums.length; i++) {
 currentSum = Math.max(nums[i], currentSum + nums[i]);
 maxSum = Math.max(maxSum, currentSum);
 }

 return maxSum;
}

// Test cases
console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4])); // 6
console.log(maxSubArray([1])); // 1
console.log(maxSubArray([5,4,-1,7,8])); // 23

// Time Complexity: O(n)
// Space Complexity: O(1)

/**
 * @param {string} s
 * @return {number}
 */
function lengthOfLongestSubstring(s) {
 let maxLength = 0;
 let left = 0;
 const charSet = new Set();

 for (let right = 0; right < s.length; right++) {
 while (charSet.has(s[right])) {
 charSet.delete(s[left]);
 left++;
 }
 charSet.add(s[right]);
 maxLength = Math.max(maxLength, right - left + 1);
 }

 return maxLength;
}

// Test cases
console.log(lengthOfLongestSubstring("abcabcbb")); // 3
console.log(lengthOfLongestSubstring("bbbbb")); // 1
console.log(lengthOfLongestSubstring("pwwkew")); // 3

// Time Complexity: O(n)
// Space Complexity: O(min(m,n)) where m is charset size

/**
 * @param {string} s
 * @return {boolean}
 */
function isValid(s) {
 const stack = [];
 const pairs = {
 ')': '(',
 '}': '{',
 ']': '['
 };

 for (const char of s) {
 if (char in pairs) {
 if (stack.length === 0 || stack.pop() !== pairs[char]) {
 return false;
 }
 } else {
 stack.push(char);
 }
 }

 return stack.length === 0;
}

// Test cases
console.log(isValid("()")); // true
console.log(isValid("()[]{}")); // true
console.log(isValid("(]")); // false
console.log(isValid("([)]")); // false
console.log(isValid("{[]}")); // true

// Time Complexity: O(n)
// Space Complexity: O(n)

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
function mergeSortedArrays(nums1, nums2) {
 const result = [];
 let i = 0;
 let j = 0;

 while (i < nums1.length && j < nums2.length) {
 if (nums1[i] <= nums2[j]) {
 result.push(nums1[i]);
 i++;
 } else {
 result.push(nums2[j]);
 j++;
 }
 }

 // Add remaining elements
 while (i < nums1.length) {
 result.push(nums1[i]);
 i++;
 }

 while (j < nums2.length) {
 result.push(nums2[j]);
 j++;
 }

 return result;
}

// Test cases
console.log(mergeSortedArrays([1,3,5], [2,4,6])); // [1,2,3,4,5,6]
console.log(mergeSortedArrays([1,2,3], [])); // [1,2,3]
console.log(mergeSortedArrays([], [4,5,6])); // [4,5,6]

// Time Complexity: O(n + m)
// Space Complexity: O(n + m)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function binarySearch(nums, target) {
 let left = 0;
 let right = nums.length - 1;

 while (left <= right) {
 const mid = Math.floor((left + right) / 2);

 if (nums[mid] === target) {
 return mid;
 } else if (nums[mid] < target) {
 left = mid + 1;
 } else {
 right = mid - 1;
 }
 }

 return -1;
}

// Test cases
console.log(binarySearch([-1,0,3,5,9,12], 9)); // 4
console.log(binarySearch([-1,0,3,5,9,12], 2)); // -1

// Time Complexity: O(log n)
// Space Complexity: O(1)

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
function groupAnagrams(strs) {
 const map = new Map();

 for (const str of strs) {
 const sorted = str.split('').sort().join('');

 if (!map.has(sorted)) {
 map.set(sorted, []);
 }

 map.get(sorted).push(str);
 }

 return Array.from(map.values());
}

// Test cases
console.log(groupAnagrams(["eat","tea","tan","ate","nat","bat"]));
// [["eat","tea","ate"],["tan","nat"],["bat"]]

// Time Complexity: O(n * k log k) where k is max string length
// Space Complexity: O(n * k)

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
function findMedianSortedArrays(nums1, nums2) {
 // Ensure nums1 is the smaller array
 if (nums1.length > nums2.length) {
 [nums1, nums2] = [nums2, nums1];
 }

 const m = nums1.length;
 const n = nums2.length;
 let left = 0;
 let right = m;

 while (left <= right) {
 const partition1 = Math.floor((left + right) / 2);
 const partition2 = Math.floor((m + n + 1) / 2) - partition1;

 const maxLeft1 = partition1 === 0 ? -Infinity : nums1[partition1 - 1];
 const minRight1 = partition1 === m ? Infinity : nums1[partition1];
 const maxLeft2 = partition2 === 0 ? -Infinity : nums2[partition2 - 1];
 const minRight2 = partition2 === n ? Infinity : nums2[partition2];

 if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
 if ((m + n) % 2 === 0) {
 return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
 } else {
 return Math.max(maxLeft1, maxLeft2);
 }
 } else if (maxLeft1 > minRight2) {
 right = partition1 - 1;
 } else {
 left = partition1 + 1;
 }
 }

 throw new Error("Input arrays are not sorted");
}

// Test cases
console.log(findMedianSortedArrays([1,3], [2])); // 2
console.log(findMedianSortedArrays([1,2], [3,4])); // 2.5

// Time Complexity: O(log(min(m,n)))
// Space Complexity: O(1)

/**
 * @param {string} s
 * @return {string}
 */
function longestPalindrome(s) {
 if (s.length < 2) return s;

 let start = 0;
 let maxLength = 1;

 function expandAroundCenter(left, right) {
 while (left >= 0 && right < s.length && s[left] === s[right]) {
 const currentLength = right - left + 1;
 if (currentLength > maxLength) {
 start = left;
 maxLength = currentLength;
 }
 left--;
 right++;
 }
 }

 for (let i = 0; i < s.length; i++) {
 expandAroundCenter(i, i); // Odd length
 expandAroundCenter(i, i + 1); // Even length
 }

 return s.substring(start, start + maxLength);
}

// Test cases
console.log(longestPalindrome("babad")); // "bab" or "aba"
console.log(longestPalindrome("cbbd")); // "bb"

// Time Complexity: O(n^2)
// Space Complexity: O(1)

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
function isMatch(s, p) {
 const dp = Array(s.length + 1).fill(null).map(() => Array(p.length + 1).fill(false));

 dp[0][0] = true;

 // Handle patterns like a*, a*b*, a*b*c*
 for (let j = 1; j <= p.length; j++) {
 if (p[j - 1] === '*') {
 dp[0][j] = dp[0][j - 2];
 }
 }

 for (let i = 1; i <= s.length; i++) {
 for (let j = 1; j <= p.length; j++) {
 if (p[j - 1] === '*') {
 // Two cases: 
 // 1. Zero occurrences of the character before *
 // 2. One or more occurrences
 dp[i][j] = dp[i][j - 2] || 
 (dp[i - 1][j] && (s[i - 1] === p[j - 2] || p[j - 2] === '.'));
 } else {
 dp[i][j] = dp[i - 1][j - 1] && 
 (s[i - 1] === p[j - 1] || p[j - 1] === '.');
 }
 }
 }

 return dp[s.length][p.length];
}

// Test cases
console.log(isMatch("aa", "a")); // false
console.log(isMatch("aa", "a*")); // true
console.log(isMatch("ab", ".*")); // true

// Time Complexity: O(m * n)
// Space Complexity: O(m * n)

/**
 * @param {number[]} height
 * @return {number}
 */
function trap(height) {
 if (height.length === 0) return 0;

 let left = 0;
 let right = height.length - 1;
 let leftMax = 0;
 let rightMax = 0;
 let water = 0;

 while (left < right) {
 if (height[left] < height[right]) {
 if (height[left] >= leftMax) {
 leftMax = height[left];
 } else {
 water += leftMax - height[left];
 }
 left++;
 } else {
 if (height[right] >= rightMax) {
 rightMax = height[right];
 } else {
 water += rightMax - height[right];
 }
 right--;
 }
 }

 return water;
}

// Test cases
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // 6
console.log(trap([4,2,0,3,2,5])); // 9

// Time Complexity: O(n)
// Space Complexity: O(1)

/**
 * Definition for a binary tree node.
 */
function TreeNode(val, left, right) {
 this.val = (val === undefined ? 0 : val);
 this.left = (left === undefined ? null : left);
 this.right = (right === undefined ? null : right);
}

/**
 * Encodes a tree to a single string.
 * @param {TreeNode} root
 * @return {string}
 */
function serialize(root) {
 const result = [];

 function preorder(node) {
 if (!node) {
 result.push('null');
 return;
 }

 result.push(node.val.toString());
 preorder(node.left);
 preorder(node.right);
 }

 preorder(root);
 return result.join(',');
}

/**
 * Decodes your encoded data to tree.
 * @param {string} data
 * @return {TreeNode}
 */
function deserialize(data) {
 const values = data.split(',');
 let index = 0;

 function buildTree() {
 if (index >= values.length || values[index] === 'null') {
 index++;
 return null;
 }

 const node = new TreeNode(parseInt(values[index]));
 index++;
 node.left = buildTree();
 node.right = buildTree();

 return node;
 }

 return buildTree();
}

// Test cases
const root = new TreeNode(1,
 new TreeNode(2),
 new TreeNode(3,
 new TreeNode(4),
 new TreeNode(5)
 )
);

const serialized = serialize(root);
console.log(serialized); // "1,2,null,null,3,4,null,null,5,null,null"

const deserialized = deserialize(serialized);
console.log(serialize(deserialized)); // "1,2,null,null,3,4,null,null,5,null,null"

// Time Complexity: O(n)
// Space Complexity: O(n)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
function rotate(nums, k) {
 k = k % nums.length;

 // Reverse entire array
 reverse(nums, 0, nums.length - 1);
 // Reverse first k elements
 reverse(nums, 0, k - 1);
 // Reverse remaining elements
 reverse(nums, k, nums.length - 1);
}

function reverse(nums, start, end) {
 while (start < end) {
 [nums[start], nums[end]] = [nums[end], nums[start]];
 start++;
 end--;
 }
}

// Test cases
const arr1 = [1,2,3,4,5,6,7];
rotate(arr1, 3);
console.log(arr1); // [5,6,7,1,2,3,4]

// Time Complexity: O(n)
// Space Complexity: O(1)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function findDisappearedNumbers(nums) {
 const result = [];

 for (let i = 0; i < nums.length; i++) {
 const index = Math.abs(nums[i]) - 1;
 if (nums[index] > 0) {
 nums[index] = -nums[index];
 }
 }

 for (let i = 0; i < nums.length; i++) {
 if (nums[i] > 0) {
 result.push(i + 1);
 }
 }

 return result;
}

// Test cases
console.log(findDisappearedNumbers([4,3,2,7,8,2,3,1])); // [5,6]
console.log(findDisappearedNumbers([1,1])); // [2]

// Time Complexity: O(n)
// Space Complexity: O(1)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function productExceptSelf(nums) {
 const n = nums.length;
 const result = new Array(n).fill(1);

 // Calculate left products
 let leftProduct = 1;
 for (let i = 0; i < n; i++) {
 result[i] = leftProduct;
 leftProduct *= nums[i];
 }

 // Calculate right products and multiply with left products
 let rightProduct = 1;
 for (let i = n - 1; i >= 0; i--) {
 result[i] *= rightProduct;
 rightProduct *= nums[i];
 }

 return result;
}

// Test cases
console.log(productExceptSelf([1,2,3,4])); // [24,12,8,6]
console.log(productExceptSelf([-1,1,0,-3,3])); // [0,0,9,0,0]

// Time Complexity: O(n)
// Space Complexity: O(1) (excluding output array)

/**
 * @param {number[]} nums
 * @return {number}
 */
function findMin(nums) {
 let left = 0;
 let right = nums.length - 1;

 while (left < right) {
 const mid = Math.floor((left + right) / 2);

 if (nums[mid] > nums[right]) {
 left = mid + 1;
 } else {
 right = mid;
 }
 }

 return nums[left];
}

// Test cases
console.log(findMin([3,4,5,1,2])); // 1
console.log(findMin([4,5,6,7,0,1,2])); // 0
console.log(findMin([11,13,15,17])); // 11

// Time Complexity: O(log n)
// Space Complexity: O(1)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function search(nums, target) {
 let left = 0;
 let right = nums.length - 1;

 while (left <= right) {
 const mid = Math.floor((left + right) / 2);

 if (nums[mid] === target) {
 return mid;
 }

 // Check which half is sorted
 if (nums[left] <= nums[mid]) {
 // Left half is sorted
 if (nums[left] <= target && target < nums[mid]) {
 right = mid - 1;
 } else {
 left = mid + 1;
 }
 } else {
 // Right half is sorted
 if (nums[mid] < target && target <= nums[right]) {
 left = mid + 1;
 } else {
 right = mid - 1;
 }
 }
 }

 return -1;
}

// Test cases
console.log(search([4,5,6,7,0,1,2], 0)); // 4
console.log(search([4,5,6,7,0,1,2], 3)); // -1
console.log(search([1], 0)); // -1

// Time Complexity: O(log n)
// Space Complexity: O(1)

/**
 * @param {string[]} strs
 * @return {string}
 */
function longestCommonPrefix(strs) {
 if (strs.length === 0) return "";

 let prefix = strs[0];

 for (let i = 1; i < strs.length; i++) {
 while (strs[i].indexOf(prefix) !== 0) {
 prefix = prefix.substring(0, prefix.length - 1);
 if (prefix === "") return "";
 }
 }

 return prefix;
}

// Test cases
console.log(longestCommonPrefix(["flower","flow","flight"])); // "fl"
console.log(longestCommonPrefix(["dog","racecar","car"])); // ""

// Time Complexity: O(n * m) where n is number of strings and m is min string length
// Space Complexity: O(1)

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
function isAnagram(s, t) {
 if (s.length !== t.length) return false;

 const charCount = {};

 for (const char of s) {
 charCount[char] = (charCount[char] || 0) + 1;
 }

 for (const char of t) {
 if (!charCount[char]) return false;
 charCount[char]--;
 }

 return true;
}

// Alternative: Using sorting
function isAnagramSorted(s, t) {
 return s.split('').sort().join('') === t.split('').sort().join('');
}

// Test cases
console.log(isAnagram("anagram", "nagaram")); // true
console.log(isAnagram("rat", "car")); // false

// Time Complexity: O(n)
// Space Complexity: O(1) (assuming fixed character set)

/**
 * @param {string} s
 * @return {number}
 */
function myAtoi(s) {
 s = s.trim();

 if (s.length === 0) return 0;

 let sign = 1;
 let result = 0;
 let i = 0;

 // Check for sign
 if (s[0] === '-' || s[0] === '+') {
 sign = s[0] === '-' ? -1 : 1;
 i++;
 }

 // Convert digits
 while (i < s.length && /\d/.test(s[i])) {
 const digit = parseInt(s[i]);

 // Check for overflow
 if (result > (Math.pow(2, 31) - 1) / 10 || 
 (result === Math.floor((Math.pow(2, 31) - 1) / 10) && digit > 7)) {
 return sign === 1 ? Math.pow(2, 31) - 1 : -Math.pow(2, 31);
 }

 result = result * 10 + digit;
 i++;
 }

 return sign * result;
}

// Test cases
console.log(myAtoi("42")); // 42
console.log(myAtoi(" -42")); // -42
console.log(myAtoi("4193 with words")); // 4193
console.log(myAtoi("words and 987")); // 0

// Time Complexity: O(n)
// Space Complexity: O(1)

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
function strStr(haystack, needle) {
 if (needle === "") return 0;
 if (haystack.length < needle.length) return -1;

 for (let i = 0; i <= haystack.length - needle.length; i++) {
 if (haystack.substring(i, i + needle.length) === needle) {
 return i;
 }
 }

 return -1;
}

// Test cases
console.log(strStr("hello", "ll")); // 2
console.log(strStr("aaaaa", "bba")); // -1
console.log(strStr("", "")); // 0

// Time Complexity: O(n * m)
// Space Complexity: O(1)

/**
 * @param {number} n
 * @return {string}
 */
function countAndSay(n) {
 if (n === 1) return "1";

 let prev = countAndSay(n - 1);
 let result = "";
 let count = 1;

 for (let i = 1; i < prev.length; i++) {
 if (prev[i] === prev[i - 1]) {
 count++;
 } else {
 result += count + prev[i - 1];
 count = 1;
 }
 }

 result += count + prev[prev.length - 1];
 return result;
}

// Test cases
console.log(countAndSay(1)); // "1"
console.log(countAndSay(4)); // "1211"

// Time Complexity: O(2^n)
// Space Complexity: O(2^n)

/**
 * @param {any} obj
 * @return {any}
 */
function deepClone(obj) {
 // Handle primitives and null
 if (obj === null || typeof obj !== 'object') {
 return obj;
 }

 // Handle Date
 if (obj instanceof Date) {
 return new Date(obj.getTime());
 }

 // Handle Array
 if (Array.isArray(obj)) {
 return obj.map(item => deepClone(item));
 }

 // Handle Object
 const clonedObj = {};
 for (const key in obj) {
 if (obj.hasOwnProperty(key)) {
 clonedObj[key] = deepClone(obj[key]);
 }
 }

 return clonedObj;
}

// Test cases
const original = {
 name: "John",
 age: 30,
 hobbies: ["reading", "coding"],
 address: {
 city: "New York",
 country: "USA"
 }
};

const cloned = deepClone(original);
cloned.name = "Jane";
cloned.hobbies.push("gaming");

console.log(original.name); // "John"
console.log(cloned.name); // "Jane"
console.log(original.hobbies); // ["reading", "coding"]
console.log(cloned.hobbies); // ["reading", "coding", "gaming"]

// Time Complexity: O(n) where n is total number of properties
// Space Complexity: O(n)

/**
 * @param {Object} target
 * @param {Object} source
 * @return {Object}
 */
function deepMerge(target, source) {
 const result = { ...target };

 for (const key in source) {
 if (source.hasOwnProperty(key)) {
 if (typeof source[key] === 'object' && source[key] !== null && !Array.isArray(source[key])) {
 result[key] = deepMerge(result[key] || {}, source[key]);
 } else {
 result[key] = source[key];
 }
 }
 }

 return result;
}

// Test cases
const obj1 = {
 a: 1,
 b: {
 x: 10,
 y: 20
 }
};

const obj2 = {
 b: {
 y: 30,
 z: 40
 },
 c: 3
};

const merged = deepMerge(obj1, obj2);
console.log(merged);
// { a: 1, b: { x: 10, y: 30, z: 40 }, c: 3 }

// Time Complexity: O(n) where n is total number of properties
// Space Complexity: O(n)

class LRUCache {
 constructor(capacity) {
 this.capacity = capacity;
 this.cache = new Map();
 }

 get(key) {
 if (!this.cache.has(key)) {
 return -1;
 }

 // Move to end (most recently used)
 const value = this.cache.get(key);
 this.cache.delete(key);
 this.cache.set(key, value);

 return value;
 }

 put(key, value) {
 // If key exists, delete it first
 if (this.cache.has(key)) {
 this.cache.delete(key);
 }

 // Add to cache
 this.cache.set(key, value);

 // If over capacity, remove least recently used (first item)
 if (this.cache.size > this.capacity) {
 const firstKey = this.cache.keys().next().value;
 this.cache.delete(firstKey);
 }
 }
}

// Test cases
const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 1
cache.put(3, 3); // evicts key 2
console.log(cache.get(2)); // -1
cache.put(4, 4); // evicts key 1
console.log(cache.get(1)); // -1
console.log(cache.get(3)); // 3
console.log(cache.get(4)); // 4

// Time Complexity: O(1) for both get and put
// Space Complexity: O(capacity)

class StackUsingQueues {
 constructor() {
 this.queue1 = [];
 this.queue2 = [];
 }

 push(x) {
 // Push to queue2
 this.queue2.push(x);

 // Move all elements from queue1 to queue2
 while (this.queue1.length > 0) {
 this.queue2.push(this.queue1.shift());
 }

 // Swap queues
 [this.queue1, this.queue2] = [this.queue2, this.queue1];
 }

 pop() {
 if (this.isEmpty()) {
 throw new Error("Stack is empty");
 }
 return this.queue1.shift();
 }

 top() {
 if (this.isEmpty()) {
 throw new Error("Stack is empty");
 }
 return this.queue1[0];
 }

 isEmpty() {
 return this.queue1.length === 0;
 }
}

// Test cases
const stack = new StackUsingQueues();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.top()); // 3
console.log(stack.pop()); // 3
console.log(stack.top()); // 2

// Time Complexity: O(n) for push, O(1) for pop and top
// Space Complexity: O(n)

class QueueUsingStacks {
 constructor() {
 this.stack1 = []; // For push
 this.stack2 = []; // For pop
 }

 push(x) {
 this.stack1.push(x);
 }

 pop() {
 if (this.isEmpty()) {
 throw new Error("Queue is empty");
 }

 // If stack2 is empty, move all elements from stack1
 if (this.stack2.length === 0) {
 while (this.stack1.length > 0) {
 this.stack2.push(this.stack1.pop());
 }
 }

 return this.stack2.pop();
 }

 peek() {
 if (this.isEmpty()) {
 throw new Error("Queue is empty");
 }

 if (this.stack2.length === 0) {
 while (this.stack1.length > 0) {
 this.stack2.push(this.stack1.pop());
 }
 }

 return this.stack2[this.stack2.length - 1];
 }

 isEmpty() {
 return this.stack1.length === 0 && this.stack2.length === 0;
 }
}

// Test cases
const queue = new QueueUsingStacks();
queue.push(1);
queue.push(2);
queue.push(3);
console.log(queue.peek()); // 1
console.log(queue.pop()); // 1
console.log(queue.peek()); // 2

// Time Complexity: O(1) amortized for push and pop
// Space Complexity: O(n)

/**
 * @param {number} n
 * @return {number}
 */
// Recursive (inefficient)
function fibRecursive(n) {
 if (n <= 1) return n;
 return fibRecursive(n - 1) + fibRecursive(n - 2);
}

// Memoization
function fibMemo(n, memo = {}) {
 if (n in memo) return memo[n];
 if (n <= 1) return n;

 memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
 return memo[n];
}

// Iterative (efficient)
function fibIterative(n) {
 if (n <= 1) return n;

 let prev = 0;
 let curr = 1;

 for (let i = 2; i <= n; i++) {
 const next = prev + curr;
 prev = curr;
 curr = next;
 }

 return curr;
}

// Test cases
console.log(fibMemo(10)); // 55
console.log(fibIterative(10)); // 55

// Time Complexity: O(n) for memoization and iterative
// Space Complexity: O(n) for memoization, O(1) for iterative

/**
 * @param {number} n
 * @return {number}
 */
// Recursive
function factorialRecursive(n) {
 if (n <= 1) return 1;
 return n * factorialRecursive(n - 1);
}

// Iterative
function factorialIterative(n) {
 let result = 1;
 for (let i = 2; i <= n; i++) {
 result *= i;
 }
 return result;
}

// Test cases
console.log(factorialRecursive(5)); // 120
console.log(factorialIterative(5)); // 120

// Time Complexity: O(n)
// Space Complexity: O(n) for recursive, O(1) for iterative

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
function myPow(x, n) {
 if (n === 0) return 1;
 if (n < 0) {
 x = 1 / x;
 n = -n;
 }

 let result = 1;
 let currentProduct = x;

 while (n > 0) {
 if (n % 2 === 1) {
 result *= currentProduct;
 }
 currentProduct *= currentProduct;
 n = Math.floor(n / 2);
 }

 return result;
}

// Test cases
console.log(myPow(2, 10)); // 1024
console.log(myPow(2.1, 3)); // 9.261
console.log(myPow(2, -2)); // 0.25

// Time Complexity: O(log n)
// Space Complexity: O(1)

/**
 * @param {number} n
 * @return {string[]}
 */
function generateParenthesis(n) {
 const result = [];

 function backtrack(current, open, close) {
 if (current.length === 2 * n) {
 result.push(current);
 return;
 }

 if (open < n) {
 backtrack(current + '(', open + 1, close);
 }

 if (close < open) {
 backtrack(current + ')', open, close + 1);
 }
 }

 backtrack('', 0, 0);
 return result;
}

// Test cases
console.log(generateParenthesis(3)); 
// ["((()))","(()())","(())()","()(())","()()()"]

// Time Complexity: O(4^n / sqrt(n))
// Space Complexity: O(n)

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function permute(nums) {
 const result = [];

 function backtrack(start) {
 if (start === nums.length) {
 result.push([...nums]);
 return;
 }

 for (let i = start; i < nums.length; i++) {
 // Swap
 [nums[start], nums[i]] = [nums[i], nums[start]];

 // Recurse
 backtrack(start + 1);

 // Backtrack
 [nums[start], nums[i]] = [nums[i], nums[start]];
 }
 }

 backtrack(0);
 return result;
}

// Test cases
console.log(permute([1, 2, 3]));
// [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

// Time Complexity: O(n! * n)
// Space Complexity: O(n! * n)

/**
 * @param {Array} array
 * @param {Function} callback
 * @return {Array}
 */
function map(array, callback) {
 const result = [];

 for (let i = 0; i < array.length; i++) {
 result.push(callback(array[i], i, array));
 }

 return result;
}

// Test cases
const numbers = [1, 2, 3, 4, 5];
console.log(map(numbers, x => x * 2)); // [2, 4, 6, 8, 10]
console.log(map(numbers, (x, i) => x + i)); // [1, 3, 5, 7, 9]

// Time Complexity: O(n)
// Space Complexity: O(n)

/**
 * @param {Array} array
 * @param {Function} callback
 * @return {Array}
 */
function filter(array, callback) {
 const result = [];

 for (let i = 0; i < array.length; i++) {
 if (callback(array[i], i, array)) {
 result.push(array[i]);
 }
 }

 return result;
}

// Test cases
const numbers = [1, 2, 3, 4, 5, 6];
console.log(filter(numbers, x => x % 2 === 0)); // [2, 4, 6]
console.log(filter(numbers, (x, i) => x > i)); // [1, 2, 3, 4, 5]

// Time Complexity: O(n)
// Space Complexity: O(n)

/**
 * @param {Array} array
 * @param {Function} callback
 * @param {*} initialValue
 * @return {*}
 */
function reduce(array, callback, initialValue) {
 let accumulator = initialValue;
 let startIndex = 0;

 if (initialValue === undefined) {
 accumulator = array[0];
 startIndex = 1;
 }

 for (let i = startIndex; i < array.length; i++) {
 accumulator = callback(accumulator, array[i], i, array);
 }

 return accumulator;
}

// Test cases
const numbers = [1, 2, 3, 4, 5];
console.log(reduce(numbers, (sum, x) => sum + x, 0)); // 15
console.log(reduce(numbers, (product, x) => product * x, 1)); // 120
console.log(reduce(['a', 'b', 'c'], (result, char) => result + char, '')); // "abc"

// Time Complexity: O(n)
// Space Complexity: O(1)

/**
 * @param {Function} fn
 * @return {Function}
 */
function curry(fn) {
 return function curried(...args) {
 if (args.length >= fn.length) {
 return fn.apply(this, args);
 }

 return function(...moreArgs) {
 return curried.apply(this, [...args, ...moreArgs]);
 };
 };
}

// Test cases
function add(a, b, c) {
 return a + b + c;
}

const curriedAdd = curry(add);
console.log(curriedAdd(1)(2)(3)); // 6
console.log(curriedAdd(1, 2)(3)); // 6
console.log(curriedAdd(1)(2, 3)); // 6

// Time Complexity: Depends on the function being curried
// Space Complexity: O(n) where n is number of arguments

/**
 * @param {Function} fn
 * @return {Function}
 */
function memoize(fn) {
 const cache = new Map();

 return function(...args) {
 const key = JSON.stringify(args);

 if (cache.has(key)) {
 return cache.get(key);
 }

 const result = fn.apply(this, args);
 cache.set(key, result);

 return result;
 };
}

// Test cases
function expensiveFunction(x) {
 console.log("Computing...");
 return x * 2;
}

const memoizedExpensive = memoize(expensiveFunction);
console.log(memoizedExpensive(5)); // "Computing..." then 10
console.log(memoizedExpensive(5)); // 10 (cached)
console.log(memoizedExpensive(10)); // "Computing..." then 20

// Time Complexity: O(1) for cached results, O(n) for first computation
// Space Complexity: O(n) where n is number of unique argument combinations

/**
 * @param {Promise[]} promises
 * @return {Promise}
 */
function promiseAll(promises) {
 return new Promise((resolve, reject) => {
 if (promises.length === 0) {
 resolve([]);
 return;
 }

 const results = new Array(promises.length);
 let completed = 0;

 promises.forEach((promise, index) => {
 Promise.resolve(promise)
 .then(value => {
 results[index] = value;
 completed++;

 if (completed === promises.length) {
 resolve(results);
 }
 })
 .catch(error => {
 reject(error);
 });
 });
 });
}

// Test cases
const promise1 = Promise.resolve(3);
const promise2 = 1337;
const promise3 = new Promise((resolve) => {
 setTimeout(() => resolve("foo"), 100);
});

promiseAll([promise1, promise2, promise3])
 .then(values => console.log(values)); // [3, 1337, "foo"]

// Time Complexity: O(n) where n is number of promises
// Space Complexity: O(n)

/**
 * @param {Promise[]} promises
 * @return {Promise}
 */
function promiseRace(promises) {
 return new Promise((resolve, reject) => {
 if (promises.length === 0) {
 // Never resolves
 return;
 }

 promises.forEach(promise => {
 Promise.resolve(promise)
 .then(resolve)
 .catch(reject);
 });
 });
}

// Test cases
const promise1 = new Promise(resolve => setTimeout(() => resolve('one'), 500));
const promise2 = new Promise(resolve => setTimeout(() => resolve('two'), 100));

promiseRace([promise1, promise2])
 .then(value => console.log(value)); // "two"

// Time Complexity: O(1) (returns as soon as first promise settles)
// Space Complexity: O(1)

/**
 * @param {Array<Function>} tasks
 * @param {number} concurrency
 * @return {Promise<Array>}
 */
async function parallel(tasks, concurrency = Infinity) {
 const results = [];
 const executing = [];

 for (const task of tasks) {
 const promise = task().then(result => {
 results.push(result);
 });

 executing.push(promise);

 if (executing.length >= concurrency) {
 await Promise.race(executing);
 }
 }

 await Promise.all(executing);
 return results;
}

// Test cases
const tasks = [
 () => new Promise(resolve => setTimeout(() => resolve(1), 100)),
 () => new Promise(resolve => setTimeout(() => resolve(2), 200)),
 () => new Promise(resolve => setTimeout(() => resolve(3), 300)),
 () => new Promise(resolve => setTimeout(() => resolve(4), 400)),
 () => new Promise(resolve => setTimeout(() => resolve(5), 500))
];

parallel(tasks, 2).then(results => console.log(results)); // [1, 2, 3, 4, 5]

// Time Complexity: O(n) where n is number of tasks
// Space Complexity: O(concurrency)

/**
 * @param {Function} fn
 * @param {Object} options
 * @return {Promise}
 */
async function retry(fn, options = {}) {
 const {
 maxAttempts = 3,
 delay = 1000,
 backoff = 2
 } = options;

 let lastError;

 for (let attempt = 1; attempt <= maxAttempts; attempt++) {
 try {
 return await fn();
 } catch (error) {
 lastError = error;

 if (attempt < maxAttempts) {
 const waitTime = delay * Math.pow(backoff, attempt - 1);
 console.log(`Attempt ${attempt} failed. Retrying in ${waitTime}ms...`);
 await new Promise(resolve => setTimeout(resolve, waitTime));
 }
 }
 }

 throw lastError;
}

// Test cases
let attempts = 0;
const flakyFunction = async () => {
 attempts++;
 if (attempts < 3) {
 throw new Error("Temporary failure");
 }
 return "Success!";
};

retry(flakyFunction, { maxAttempts: 5, delay: 100 })
 .then(result => console.log(result)) // "Success!"
 .catch(error => console.error(error));

// Time Complexity: O(maxAttempts * fnTime)
// Space Complexity: O(1)

/**
 * @param {Function} func
 * @param {number} wait
 * @return {Function}
 */
function debounce(func, wait) {
 let timeout;

 return function executedFunction(...args) {
 const later = () => {
 clearTimeout(timeout);
 func.apply(this, args);
 };

 clearTimeout(timeout);
 timeout = setTimeout(later, wait);
 };
}

// Test cases
const debouncedSearch = debounce((query) => {
 console.log("Searching for:", query);
}, 300);

debouncedSearch("javascript");
debouncedSearch("javascript tutorial");
debouncedSearch("javascript tutorial examples");
// After 300ms: "Searching for: javascript tutorial examples"

// Time Complexity: O(1) for each call
// Space Complexity: O(1)

/**
 * @param {HTMLElement} parent
 * @param {string} eventType
 * @param {string} selector
 * @param {Function} handler
 */
function delegateEvent(parent, eventType, selector, handler) {
 parent.addEventListener(eventType, function(event) {
 const target = event.target.closest(selector);

 if (target && parent.contains(target)) {
 handler.call(target, event);
 }
 });
}

// Test case
// HTML: <ul id="list"><li>Item 1</li><li>Item 2</li></ul>
const list = document.getElementById('list');

delegateEvent(list, 'click', 'li', function(event) {
 console.log('Clicked:', this.textContent);
 // Dynamically add new item
 const newItem = document.createElement('li');
 newItem.textContent = `Item ${list.children.length + 1}`;
 list.appendChild(newItem);
});

// Time Complexity: O(1) per event
// Space Complexity: O(1)

/**
 * @param {string} tag
 * @param {Object} attributes
 * @param {Array} children
 * @return {HTMLElement}
 */
function createElement(tag, attributes = {}, children = []) {
 const element = document.createElement(tag);

 // Set attributes
 for (const [key, value] of Object.entries(attributes)) {
 if (key === 'className') {
 element.className = value;
 } else if (key === 'style' && typeof value === 'object') {
 Object.assign(element.style, value);
 } else if (key.startsWith('on') && typeof value === 'function') {
 element.addEventListener(key.slice(2).toLowerCase(), value);
 } else {
 element.setAttribute(key, value);
 }
 }

 // Add children
 children.forEach(child => {
 if (typeof child === 'string') {
 element.appendChild(document.createTextNode(child));
 } else if (child instanceof HTMLElement) {
 element.appendChild(child);
 } else if (Array.isArray(child)) {
 child.forEach(c => element.appendChild(c));
 }
 });

 return element;
}

// Test cases
const button = createElement('button', {
 className: 'btn btn-primary',
 onclick: () => console.log('Clicked!')
}, ['Click Me']);

document.body.appendChild(button);

const card = createElement('div', {
 className: 'card',
 style: { padding: '20px', background: '#f0f0f0' }
}, [
 createElement('h2', {}, ['Card Title']),
 createElement('p', {}, ['Card content goes here...']),
 createElement('button', { className: 'btn' }, ['Action'])
]);

document.body.appendChild(card);

// Time Complexity: O(n) where n is number of children
// Space Complexity: O(n)

class Storage {
 constructor(prefix = 'app_') {
 this.prefix = prefix;
 }

 set(key, value) {
 try {
 const serialized = JSON.stringify(value);
 localStorage.setItem(this.prefix + key, serialized);
 return true;
 } catch (error) {
 console.error('Storage set error:', error);
 return false;
 }
 }

 get(key, defaultValue = null) {
 try {
 const item = localStorage.getItem(this.prefix + key);
 return item ? JSON.parse(item) : defaultValue;
 } catch (error) {
 console.error('Storage get error:', error);
 return defaultValue;
 }
 }

 remove(key) {
 localStorage.removeItem(this.prefix + key);
 }

 clear() {
 const keys = Object.keys(localStorage);
 keys.forEach(key => {
 if (key.startsWith(this.prefix)) {
 localStorage.removeItem(key);
 }
 });
 }

 has(key) {
 return localStorage.getItem(this.prefix + key) !== null;
 }
}

// Test cases
const storage = new Storage('myapp_');
storage.set('user', { name: 'John', age: 30 });
console.log(storage.get('user')); // { name: 'John', age: 30 }
console.log(storage.has('user')); // true
storage.remove('user');
console.log(storage.has('user')); // false

// Time Complexity: O(1) for get/set/remove, O(n) for clear
// Space Complexity: O(1)