Live Coding

How to check if a JavaScript object is empty?

Explanation: An object is empty if it doesn't have any own enumerable properties. We can use Object.keys(obj) which returns an array of a given object's own enumerable property names. If the length of this array is 0, the object is empty.

function isEmpty(obj) {
  return Object.keys(obj).length === 0;
}

console.log(isEmpty({})); // true
console.log(isEmpty({ a: 1 })); // false

Write a function to reverse a given string.

Explanation: The simplest way is to convert the string into an array of characters, use the built-in reverse() method for arrays, and then join the characters back into a string.

function reverseString(str) {
  return str.split('').reverse().join('');
}

console.log(reverseString('hello')); // 'olleh'

Write a function that checks if a given string is a palindrome.

Explanation: A palindrome is a word or phrase that reads the same forwards and backward. We can check this by reversing the string (ignoring case and non-alphanumeric characters for a more robust check, but here we do a simple check) and comparing it to the original.

function isPalindrome(str) {
  const reversed = str.split('').reverse().join('');
  return str === reversed;
}

console.log(isPalindrome('racecar')); // true
console.log(isPalindrome('hello')); // false

Write a function to find the largest number in an array of numbers.

Explanation: You can iterate through the array, keeping track of the largest number found so far. Alternatively, you can use the Math.max() function along with the spread syntax (...) to pass array elements as arguments.

function findMaxNumber(arr) {
  if (arr.length === 0) return undefined; // Or throw an error
  return Math.max(...arr);
}

console.log(findMaxNumber([1, 5, 2, 9, 3])); // 9

Write a program that prints numbers from 1 to n. But for multiples of three, print 'Fizz' instead of the number and for the multiples of five, print 'Buzz'. For numbers which are multiples of both three and five, print 'FizzBuzz'.

Explanation: This classic problem tests basic loop and conditional logic. You need to iterate from 1 to n and use the modulo operator (%) to check for divisibility by 3 and 5.

function fizzBuzz(n) {
  for (let i = 1; i <= n; i++) {
    if (i % 3 === 0 && i % 5 === 0) {
      console.log('FizzBuzz');
    } else if (i % 3 === 0) {
      console.log('Fizz');
    } else if (i % 5 === 0) {
      console.log('Buzz');
    } else {
      console.log(i);
    }
  }
}

fizzBuzz(15);

Write a function that removes duplicate elements from an array.

Explanation: A modern and concise way to achieve this is by using a Set. Sets only store unique values. You can convert the array to a Set and then back to an array.

function removeDuplicates(arr) {
  return [...new Set(arr)];
}

console.log(removeDuplicates([1, 2, 2, 3, 4, 4, 5])); // [1, 2, 3, 4, 5]

Write a function to check if two strings are anagrams of each other.

Explanation: Anagrams are words formed by rearranging the letters of another. To check, we can clean, sort, and compare the strings. Cleaning involves removing non-alphanumeric characters and converting to a consistent case.

function isAnagram(str1, str2) {
  const clean = (str) => str.replace(/[^a-z0-9]/gi, '').toLowerCase();
  const sorted = (str) => clean(str).split('').sort().join('');
  
  return sorted(str1) === sorted(str2);
}

console.log(isAnagram('listen', 'silent')); // true
console.log(isAnagram('hello', 'world')); // false

Write a function to calculate the factorial of a non-negative integer.

Explanation: The factorial (n!) of a number is the product of all positive integers less than or equal to n. We can calculate this iteratively by multiplying numbers from 1 up to n.

function factorial(n) {
  if (n < 0) return undefined; // Factorial is not defined for negative numbers
  if (n === 0) return 1;
  let result = 1;
  for (let i = 1; i <= n; i++) {
    result *= i;
  }
  return result;
}

console.log(factorial(5)); // 120

Write a function that returns the sum of all numbers in an array.

Explanation: You can use the reduce method, which is ideal for accumulating a single value from an array. It takes a callback function and an initial value (0 for summation).

function sumArray(arr) {
  return arr.reduce((accumulator, currentValue) => accumulator + currentValue, 0);
}

console.log(sumArray([1, 2, 3, 4])); // 10

Write a function to flatten a nested array. For simplicity, assume only one level of nesting.

Explanation: For a single level of nesting, you can use Array.prototype.concat() with the spread operator or the flat() method (ES2019).

function flattenArray(arr) {
  // Using flat() (simpler if ES2019+ is okay)
  // return arr.flat();

  // Using reduce and concat
  return arr.reduce((acc, val) => acc.concat(val), []);
}

console.log(flattenArray([1, [2, 3], 4, [5]])); // [1, 2, 3, 4, 5]

Write a function that counts the number of vowels (a, e, i, o, u) in a given string.

Explanation: Iterate through the string (case-insensitively) and check if each character is a vowel. Maintain a counter.

function countVowels(str) {
  const vowels = 'aeiou';
  let count = 0;
  for (let char of str.toLowerCase()) {
    if (vowels.includes(char)) {
      count++;
    }
  }
  return count;
}

console.log(countVowels('Hello World')); // 3

Write a function that converts a sentence into title case (each word's first letter capitalized).

Explanation: Split the sentence into words, then iterate through each word, capitalizing the first letter and making the rest lowercase. Finally, join the words back.

function titleCase(str) {
  return str.toLowerCase().split(' ').map(word => {
    return word.charAt(0).toUpperCase() + word.slice(1);
  }).join(' ');
}

console.log(titleCase('i am a little tea pot')); // 'I Am A Little Tea Pot'

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Explanation: A common approach is to use a hash map (or a JavaScript object) to store numbers and their indices as you iterate. For each number, check if target - current_number exists in the map.

function twoSum(nums, target) {
  const map = {};
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map[complement] !== undefined) {
      return [map[complement], i];
    }
    map[nums[i]] = i;
  }
  return []; // Or null, or throw error if no solution
}

console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

Create a function that returns a counter function. Each time the returned function is called, it should increment and return a count.

Explanation: This demonstrates closures. The inner function has access to the count variable of the outer function's scope, even after the outer function has finished executing.

function createCounter() {
  let count = 0;
  return function() {
    count++;
    return count;
  };
}

const counter1 = createCounter();
console.log(counter1()); // 1
console.log(counter1()); // 2
const counter2 = createCounter();
console.log(counter2()); // 1

Write a function that finds the first non-repeating character in a string.

Explanation: You can use a hash map to count character frequencies. First, iterate through the string to build the frequency map. Then, iterate through the string again and return the first character with a count of 1.

function firstNonRepeatingChar(str) {
  const charCount = {};
  for (const char of str) {
    charCount[char] = (charCount[char] || 0) + 1;
  }
  for (const char of str) {
    if (charCount[char] === 1) {
      return char;
    }
  }
  return null; // Or some indicator if all repeat
}

console.log(firstNonRepeatingChar('aabbcdeeff')); // 'c'
console.log(firstNonRepeatingChar('swiss')); // 'w'

Write a function that splits an array into groups of a specified size.

Explanation: Iterate through the array, taking slices of the specified size and pushing them into a new array. Handle the case where the last chunk might be smaller.

function chunkArray(arr, size) {
  const chunked = [];
  let index = 0;
  while (index < arr.length) {
    chunked.push(arr.slice(index, index + size));
    index += size;
  }
  return chunked;
}

console.log(chunkArray([1, 2, 3, 4, 5, 6, 7], 3)); // [[1, 2, 3], [4, 5, 6], [7]]

Write a function to determine if a given number is a prime number.

Explanation: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Iterate from 2 up to the square root of the number, checking for divisibility. Handle edge cases like 1 and 2.

function isPrime(num) {
  if (num <= 1) return false;
  if (num <= 3) return true;

  if (num % 2 === 0 || num % 3 === 0) return false;

  for (let i = 5; i * i <= num; i = i + 6) {
    if (num % i === 0 || num % (i + 2) === 0) return false;
  }

  return true;
}

console.log(isPrime(7)); // true
console.log(isPrime(10)); // false

Write a function that finds the longest word in a sentence.

Explanation: Split the string into an array of words. Then, iterate through the array, keeping track of the longest word found so far (or its length).

function findLongestWord(str) {
  const words = str.split(' ');
  let longestWord = '';
  for (const word of words) {
    // Clean words if needed (e.g., remove punctuation)
    if (word.length > longestWord.length) {
      longestWord = word;
    }
  }
  return longestWord;
}

console.log(findLongestWord('The quick brown fox jumped over the lazy dog')); // 'jumped'

Implement your own version of the Array.prototype.map function.

Explanation: The map function takes a callback and creates a new array by applying the callback to each element of the original array. Your function should iterate through the array and build the new array.

function myMap(arr, callback) {
  const mappedArray = [];
  for (let i = 0; i < arr.length; i++) {
    mappedArray.push(callback(arr[i], i, arr));
  }
  return mappedArray;
}

const numbers = [1, 4, 9];
const roots = myMap(numbers, Math.sqrt);
console.log(roots); // [1, 2, 3]

Implement your own version of the Array.prototype.filter function.

Explanation: The filter function takes a callback and creates a new array with all elements that pass the test implemented by the provided callback function.

function myFilter(arr, callback) {
  const filteredArray = [];
  for (let i = 0; i < arr.length; i++) {
    if (callback(arr[i], i, arr)) {
        filteredArray.push(arr[i]);
    }
  }
  return filteredArray;
}

const words = ['spray', 'limit', 'elite', 'exuberant', 'destruction', 'present'];
const result = myFilter(words, word => word.length > 6);
console.log(result); // ['exuberant', 'destruction', 'present']

Implement your own version of the Array.prototype.reduce function.

Explanation: The reduce function executes a user-supplied 'reducer' callback function on each element of the array, passing in the return value from the calculation on the preceding element. The final result of running the reducer across all elements of the array is a single value. Handle the initial value argument.

function myReduce(arr, callback, initialValue) {
  let accumulator = initialValue;
  let startIndex = 0;

  if (initialValue === undefined) {
      if (arr.length === 0) throw new TypeError('Reduce of empty array with no initial value');
      accumulator = arr[0];
      startIndex = 1;
  }

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

const array1 = [1, 2, 3, 4];
const sum = myReduce(array1, (acc, curr) => acc + curr, 0);
console.log(sum); // 10

Implement a Fibonacci function using memoization to optimize performance.

Explanation: The Fibonacci sequence involves repeated calculations. Memoization stores the results of expensive function calls and returns the cached result when the same inputs occur again.

function memoizedFib() {
  const cache = {};

  function fib(n) {
    if (n in cache) {
      return cache[n];
    }
    if (n <= 1) {
      return n;
    }
    const result = fib(n - 1) + fib(n - 2);
    cache[n] = result;
    return result;
  }
  return fib;
}

const fibonacci = memoizedFib();
console.log(fibonacci(10)); // 55
console.log(fibonacci(40)); // 102334155 (much faster than non-memoized)

Write a function to check if a string containing brackets {}[]() is balanced.

Explanation: Use a stack. When you encounter an opening bracket, push it onto the stack. When you encounter a closing bracket, check if the stack is empty or if the top element is the matching opening bracket. If it matches, pop the stack. If not, or if the stack is empty, it's unbalanced. At the end, an empty stack means balanced.

function isBalanced(str) {
  const stack = [];
  const map = { '(': ')', '{': '}', '[': ']' };

  for (let char of str) {
    if (map[char]) {
      stack.push(char);
    } else if (Object.values(map).includes(char)) {
      if (stack.length === 0) return false;
      const lastOpen = stack.pop();
      if (map[lastOpen] !== char) return false;
    }
  }
  return stack.length === 0;
}

console.log(isBalanced('({[]})')); // true
console.log(isBalanced('([)]')); // false

Implement a Queue data structure with enqueue (add to back) and dequeue (remove from front) methods.

Explanation: A queue follows the First-In, First-Out (FIFO) principle. An array can be used, with push for enqueue and shift for dequeue.

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) return 'Underflow';
    return this.items.shift();
  }

  front() {
    if (this.isEmpty()) return 'No elements in Queue';
    return this.items[0];
  }

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

const q = new Queue();
q.enqueue(10);
q.enqueue(20);
console.log(q.dequeue()); // 10
console.log(q.front()); // 20

Implement a Stack data structure with push (add to top) and pop (remove from top) methods.

Explanation: A stack follows the Last-In, First-Out (LIFO) principle. An array can be used, with push and pop methods.

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) return 'Underflow';
    return this.items.pop();
  }

  peek() {
    return this.items[this.items.length - 1];
  }

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

const s = new Stack();
s.push(10);
s.push(20);
console.log(s.pop()); // 20
console.log(s.peek()); // 10

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Explanation: The sum of numbers from 0 to n can be calculated using the formula n*(n+1)/2. The actual sum of the array elements can be calculated. The difference between these two sums will be the missing number.

function findMissingNumber(nums) {
  const n = nums.length;
  const expectedSum = n * (n + 1) / 2;
  const actualSum = nums.reduce((sum, num) => sum + num, 0);
  return expectedSum - actualSum;
}

console.log(findMissingNumber([3, 0, 1])); // 2
console.log(findMissingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1])); // 8

Implement a debounce function. Debouncing ensures that a function is not called again until a certain amount of time has passed without it being called.

Explanation: Use setTimeout and clearTimeout. Each time the debounced function is called, clear the previous timeout and set a new one. The actual function call happens only when the timeout completes.

function debounce(func, delay) {
  let timeoutId;
  return function(...args) {
    clearTimeout(timeoutId);
    timeoutId = setTimeout(() => {
      func.apply(this, args);
    }, delay);
  };
}

// Example usage:
const sayHello = () => console.log('Hello!');
const debouncedHello = debounce(sayHello, 1000);
debouncedHello(); // Called after 1 sec (if not called again)
debouncedHello(); // Resets timer
debouncedHello(); // Resets timer, will actually run 1 sec after this call.

Implement a throttle function. Throttling ensures that a function is called at most once in a specified time interval.

Explanation: Use a flag to indicate if a call is allowed. When called, if allowed, execute the function, set the flag to false, and use setTimeout to reset the flag after the interval.

function throttle(func, limit) {
  let inThrottle = false;
  return function(...args) {
    if (!inThrottle) {
      func.apply(this, args);
      inThrottle = true;
      setTimeout(() => inThrottle = false, limit);
    }
  };
}

// Example usage:
const logScroll = () => console.log('Scrolling...');
const throttledScroll = throttle(logScroll, 1000);
// window.addEventListener('scroll', throttledScroll); // Will log at most once per second.

Write a function that takes a function with two arguments and returns a curried version of it.

Explanation: Currying transforms a function with multiple arguments into a sequence of functions, each taking a single argument. f(a, b) becomes f(a)(b).

function curry(fn) {
  return function(a) {
    return function(b) {
      return fn(a, b);
    };
  };
}

function add(a, b) {
  return a + b;
}

const curriedAdd = curry(add);
const add5 = curriedAdd(5);
console.log(add5(3)); // 8
console.log(curriedAdd(10)(20)); // 30

Write a function to perform a deep clone of a JavaScript object.

Explanation: A shallow clone copies only the top-level properties. A deep clone recursively copies all properties, including nested objects and arrays. A simple way (with limitations, e.g., doesn't handle functions, dates, regex well) is using JSON.parse(JSON.stringify(obj)). A recursive approach is more robust.

function deepClone(obj) {
  // Simple version (with limitations)
  try {
      return JSON.parse(JSON.stringify(obj));
  } catch (e) {
      console.error("Cloning failed:", e);
      return null;
  }
  
  // More robust recursive (basic example):
  /*
  if (obj === null || typeof obj !== 'object') {
      return obj;
  }
  let clone = Array.isArray(obj) ? [] : {};
  for (let key in obj) {
      if (Object.prototype.hasOwnProperty.call(obj, key)) {
          clone[key] = deepClone(obj[key]);
      }
  }
  return clone;
  */
}

const original = { a: 1, b: { c: 2 } };
const cloned = deepClone(original);
cloned.b.c = 3;
console.log(original.b.c); // 2 (proves it's a deep clone)
console.log(cloned.b.c); // 3

How to get an array of keys from an object?

Explanation: Use Object.keys(obj).

function getKeys(obj) {
  return Object.keys(obj);
}
console.log(getKeys({a: 1, b: 2})); // ['a', 'b']

How to get an array of values from an object?

Explanation: Use Object.values(obj).

function getValues(obj) {
  return Object.values(obj);
}
console.log(getValues({a: 1, b: 2})); // [1, 2]

How to check if an array contains a specific value?

Explanation: Use Array.prototype.includes(value).

function checkIncludes(arr, val) {
  return arr.includes(val);
}
console.log(checkIncludes([1, 2, 3], 2)); // true

How to merge two arrays into one?

Explanation: Use the spread syntax (...) or Array.prototype.concat().

function mergeArrays(arr1, arr2) {
  return [...arr1, ...arr2];
}
console.log(mergeArrays([1, 2], [3, 4])); // [1, 2, 3, 4]

What does this refer to in the global scope in a browser?

Explanation: In the global execution context (outside any function), this refers to the global object, which is window in web browsers.

console.log(this === window); // true (in a browser environment)

What does this refer to when used inside an object method?

Explanation: When a function is called as a method of an object, this refers to the object the method is called on.

const myObject = {
  prop: 'Hello',
  greet() {
    return this.prop;
  }
};
console.log(myObject.greet()); // 'Hello'

How do arrow functions handle this?

Explanation: Arrow functions do not have their own this context. Instead, they inherit this from the surrounding (lexical) scope where they are defined.

function MyClass() {
  this.value = 42;
  setTimeout(() => {
    console.log(this.value); // Logs 42 because 'this' is inherited
  }, 100);
}
new MyClass();

What are the main differences between let, const, and var?

Explanation: var is function-scoped and hoisted. let and const are block-scoped and hoisted but are in a 'temporal dead zone' until declaration. const must be initialized and cannot be reassigned.

function scopeTest() {
  var a = 1;
  let b = 2;
  const c = 3;
  if (true) {
    var a = 10; // Re-declares and affects outer 'a'
    let b = 20; // New 'b' within block
    // const c = 30; // Would be a new 'c'
    console.log(a, b, c); // 10, 20, 3
  }
  console.log(a, b, c); // 10, 2, 3
}
scopeTest();

Explain what a Promise is in JavaScript.

Explanation: A Promise is an object representing the eventual completion (or failure) of an asynchronous operation and its resulting value. It can be in one of three states: pending, fulfilled, or rejected.

const myPromise = new Promise((resolve, reject) => {
  setTimeout(() => {
    resolve('Success!');
    // reject('Error!');
  }, 1000);
});

myPromise
  .then(result => console.log(result))
  .catch(error => console.error(error));

How do async and await simplify working with Promises?

Explanation: async/await provides syntactic sugar over Promises, making asynchronous code look and behave a bit more like synchronous code. An async function always returns a Promise, and await pauses execution until a Promise settles.

function delay(ms) {
  return new Promise(resolve => setTimeout(resolve, ms));
}

async function run() {
  console.log('Starting...');
  await delay(1000);
  console.log('Waited 1 second.');
  await delay(500);
  console.log('Waited another 0.5 seconds.');
  return 'Finished!';
}

run().then(console.log);

How to convert a string to a number?

Explanation: Use parseInt(), parseFloat(), or the unary plus operator (+).

const str = '123.45';
console.log(parseInt(str)); // 123
console.log(parseFloat(str)); // 123.45
console.log(+str); // 123.45

How to convert a number to a string?

Explanation: Use String(), number.toString(), or string concatenation.

const num = 123;
console.log(String(num)); // '123'
console.log(num.toString()); // '123'
console.log('' + num); // '123'

What does JSON.stringify do?

Explanation: It converts a JavaScript object or value to a JSON string.

const obj = { name: 'Alice', age: 30 };
const jsonString = JSON.stringify(obj);
console.log(jsonString); // '{"name":"Alice","age":30}'

What does JSON.parse do?

Explanation: It parses a JSON string, constructing the JavaScript value or object described by the string.

const jsonString = '{"name":"Alice","age":30}';
const obj = JSON.parse(jsonString);
console.log(obj.name); // 'Alice'

How is the spread operator used with arrays?

Explanation: It allows an iterable (like an array) to be expanded in places where zero or more arguments or elements are expected. Useful for copying, merging, and adding elements.

const arr1 = [1, 2];
const arr2 = [3, 4];
const combined = [...arr1, ...arr2]; // [1, 2, 3, 4]
const copy = [...arr1]; // [1, 2]

How is the spread operator used with objects?

Explanation: It allows copying and merging object properties.

const obj1 = { a: 1, b: 2 };
const obj2 = { b: 3, c: 4 };
const merged = { ...obj1, ...obj2 }; // { a: 1, b: 3, c: 4 }
const copy = { ...obj1 }; // { a: 1, b: 2 }

Explain array destructuring with an example.

Explanation: It's a syntax that makes it possible to unpack values from arrays into distinct variables.

const [a, b] = [10, 20];
console.log(a); // 10
console.log(b); // 20

const [x, , z] = [1, 2, 3];
console.log(z); // 3

Explain object destructuring with an example.

Explanation: It makes it possible to unpack properties from objects into distinct variables.

const person = { name: 'Bob', age: 25 };
const { name, age } = person;
console.log(name); // 'Bob'
console.log(age); // 25

const { name: personName } = person;
console.log(personName); // 'Bob'

How could you implement a basic version of Function.prototype.call?

Explanation: call invokes a function with a specified this value and arguments provided individually. You can attach the function to the this context, call it, and then remove it.

Function.prototype.myCall = function(context, ...args) {
  context = context || window;
  const uniqueId = Symbol(); // Use a unique key
  context[uniqueId] = this;
  const result = context[uniqueId](...args);
  delete context[uniqueId];
  return result;
}

function greet(greeting, punctuation) {
  console.log(`${greeting}, ${this.name}${punctuation}`);
}

greet.myCall({ name: 'Charlie' }, 'Hi', '!'); // Hi, Charlie!

How could you implement a basic version of Function.prototype.apply?

Explanation: apply is similar to call, but it accepts arguments as an array.

Function.prototype.myApply = function(context, argsArray) {
  context = context || window;
  const uniqueId = Symbol();
  context[uniqueId] = this;
  const result = context[uniqueId](...(argsArray || []));
  delete context[uniqueId];
  return result;
}

function greet(greeting, punctuation) {
  console.log(`${greeting}, ${this.name}${punctuation}`);
}

greet.myApply({ name: 'David' }, ['Hello', '.']); // Hello, David.

Spiega brevemente l'Event Loop di JavaScript.

Spiegazione: JavaScript è a singolo thread, ma raggiunge la concorrenza usando un event loop. Lo stack di chiamate gestisce il codice sincrono. Le API web gestiscono operazioni asincrone (come setTimeout, fetch). Quando un'operazione asincrona termina, la sua callback va alla coda delle callback (o microtask queue per le Promise). L'event loop controlla costantemente se lo stack di chiamate è vuoto; se lo è, sposta la callback successiva dalla coda allo stack per l'esecuzione.

console.log('Start');

setTimeout(() => {
  console.log('Timeout Callback'); // Goes to Callback Queue
}, 0);

Promise.resolve().then(() => {
  console.log('Promise Resolved'); // Goes to Microtask Queue
});

console.log('End');

// Output Order: Start, End, Promise Resolved, Timeout Callback
// (Microtasks run before Macrotasks/Callbacks)

Implementa una funzione di ricerca binaria per un array ordinato.

Spiegazione: La ricerca binaria trova efficientemente un elemento in un array ordinato dividendo ripetutamente l'intervallo di ricerca a metà. Se il valore della chiave di ricerca è inferiore all'elemento al centro dell'intervallo, si restringe l'intervallo alla metà inferiore. Altrimenti, lo si restringe alla metà superiore. Si esegue questa operazione finché il valore non viene trovato o l'intervallo è vuoto.

function binarySearch(sortedArray, key) {
  let start = 0;
  let end = sortedArray.length - 1;

  while (start <= end) {
    let middle = Math.floor((start + end) / 2);

    if (sortedArray[middle] === key) {
      return middle; // Found
    } else if (sortedArray[middle] < key) {
      start = middle + 1; // Search right half
    } else {
      end = middle - 1; // Search left half
    }
  }
  return -1; // Not found
}

console.log(binarySearch([1, 3, 5, 7, 9, 11], 7)); // 3
console.log(binarySearch([1, 3, 5, 7, 9, 11], 2)); // -1

Implementa l'algoritmo Merge Sort.

Spiegazione: Merge Sort è un algoritmo divide-et-impera. Divide l'array di input in due metà, si richiama su entrambe le metà, quindi unisce le due metà ordinate. La funzione di unione è cruciale; combina due sottoarray ordinati in un unico array ordinato.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10])); // [3, 9, 10, 27, 38, 43, 82]

Implementa l'algoritmo Quick Sort.

Spiegazione: Quick Sort è anch'esso un algoritmo divide-et-impera. Sceglie un elemento come pivot e partiziona l'array dato attorno al pivot scelto. Gli elementi più piccoli del pivot vanno a sinistra, e gli elementi più grandi vanno a destra. Quindi ordina ricorsivamente i sottoarray.

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

console.log(quickSort([10, 8, 2, 1, 6, 3, 9, 4, 7, 5])); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Implementa l'algoritmo Bubble Sort.

Spiegazione: Bubble Sort è un semplice algoritmo di ordinamento che scorre ripetutamente la lista, confronta gli elementi adiacenti e li scambia se sono nell'ordine sbagliato. Il passaggio attraverso la lista viene ripetuto finché la lista non è ordinata.

function bubbleSort(arr) {
  let n = arr.length;
  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < n - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]; // Swap
        swapped = true;
      }
    }
    n--; // Optimization: last element is already in place
  } while (swapped);
  return arr;
}

console.log(bubbleSort([64, 34, 25, 12, 22, 11, 90])); // [11, 12, 22, 25, 34, 64, 90]

Data una stringa, trova la lunghezza della sottostringa più lunga senza caratteri ripetuti.

Spiegazione: Utilizza la tecnica della 'finestra scorrevole'. Mantieni una finestra (sottostringa) e un set di caratteri in quella finestra. Espandi la finestra spostando il puntatore destro. Se viene trovato un carattere ripetuto, restringi la finestra da sinistra finché il carattere ripetuto non viene rimosso.

function lengthOfLongestSubstring(s) {
  let maxLength = 0;
  let start = 0;
  const charMap = {};

  for (let end = 0; end < s.length; end++) {
    const char = s[end];
    if (charMap[char] >= start) {
        start = charMap[char] + 1;
    }
    charMap[char] = end;
    maxLength = Math.max(maxLength, end - start + 1);
  }
  return maxLength;
}

console.log(lengthOfLongestSubstring('abcabcbb')); // 3 ('abc')
console.log(lengthOfLongestSubstring('bbbbb')); // 1 ('b')
console.log(lengthOfLongestSubstring('pwwkew')); // 3 ('wke')

Implementa una Lista Collegata Singolarmente con i metodi add e print.

Spiegazione: Una lista collegata è una struttura dati lineare dove gli elementi non sono memorizzati in posizioni di memoria contigue. Ogni elemento (nodo) punta al successivo. Hai bisogno di una classe Node e di una classe LinkedList per gestire la testa e l'aggiunta di nuovi nodi.

class Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  add(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
  }

  print() {
    let current = this.head;
    let list = '';
    while (current) {
      list += current.data + ' -> ';
      current = current.next;
    }
    console.log(list + 'null');
  }
}

const list = new LinkedList();
list.add(10);
list.add(20);
list.add(30);
list.print(); // 10 -> 20 -> 30 -> null

Implementa un Albero di Ricerca Binario con i metodi insert e find.

Spiegazione: Un BST è una struttura dati ad albero binario basata su nodi che ha le seguenti proprietà: il sottoalbero sinistro di un nodo contiene solo nodi con chiavi minori della chiave del nodo. Il sottoalbero destro di un nodo contiene solo nodi con chiavi maggiori della chiave del nodo. Entrambi i sottoalberi devono essere anche alberi di ricerca binari.

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(data) {
    const newNode = new Node(data);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    this._insertNode(this.root, newNode);
  }

  _insertNode(node, newNode) {
    if (newNode.data < node.data) {
      if (!node.left) node.left = newNode;
      else this._insertNode(node.left, newNode);
    } else {
      if (!node.right) node.right = newNode;
      else this._insertNode(node.right, newNode);
    }
  }

  find(data) {
    return this._findNode(this.root, data);
  }

  _findNode(node, data) {
    if (!node) return null;
    if (data < node.data) return this._findNode(node.left, data);
    else if (data > node.data) return this._findNode(node.right, data);
    else return node;
  }
}

const bst = new BST();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(7);
console.log(bst.find(7)); // Node { data: 7, left: null, right: null }
console.log(bst.find(12)); // null

Scrivi una funzione per ruotare un array a destra di k passi.

Spiegazione: Ruotare un array significa spostare i suoi elementi. Per una rotazione a destra, l'ultimo elemento diventa il primo. Ripetere questo k volte funziona ma è inefficiente. Un modo migliore è usare la manipolazione dell'array o calcolare le nuove posizioni.

function rotateArray(nums, k) {
  k = k % nums.length; // Handle cases where k > length
  if (k === 0) return nums;

  const partToMove = nums.splice(nums.length - k);
  nums.unshift(...partToMove);
  return nums;
}

console.log(rotateArray([1, 2, 3, 4, 5, 6, 7], 3)); // [5, 6, 7, 1, 2, 3, 4]

Dati due array, scrivi una funzione per calcolare la loro intersezione (elementi comuni ad entrambi).

Spiegazione: Un buon approccio è convertire un array in un Set per ricerche in tempo medio O(1). Quindi, iterare attraverso il secondo array e controllare se ogni elemento esiste nel set. Raccogli le corrispondenze.

function intersection(nums1, nums2) {
  const set1 = new Set(nums1);
  const resultSet = new Set();

  for (const num of nums2) {
    if (set1.has(num)) {
      resultSet.add(num);
    }
  }

  return [...resultSet];
}

console.log(intersection([1, 2, 2, 1], [2, 2])); // [2]
console.log(intersection([4, 9, 5], [9, 4, 9, 8, 4])); // [9, 4]

Dato un array di stringhe, raggruppa gli anagrammi insieme.

Spiegazione: La chiave è trovare una firma unica per ogni gruppo di anagrammi. Un modo comune è ordinare ogni parola alfabeticamente. Le parole che risultano nella stessa stringa ordinata sono anagrammi. Usa una hash map dove le chiavi sono parole ordinate e i valori sono array di parole originali.

function groupAnagrams(strs) {
  const map = {};
  for (const str of strs) {
    const sortedStr = str.split('').sort().join('');
    if (!map[sortedStr]) {
      map[sortedStr] = [];
    }
    map[sortedStr].push(str);
  }
  return Object.values(map);
}

console.log(groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat'])); 
// Output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Dato un array nums, scrivi una funzione per spostare tutti gli 0 alla fine mantenendo l'ordine relativo degli elementi non zero.

Spiegazione: Utilizza un approccio 'a due puntatori' o 'a palla di neve'. Un puntatore tiene traccia della posizione in cui dovrebbe andare il prossimo elemento non zero. Itera attraverso l'array; se un elemento non è zero, posizionalo nella posizione del puntatore e incrementa il puntatore. Infine, riempi il resto con zeri.

function moveZeroes(nums) {
  let nonZeroIndex = 0;

  // Move all non-zero elements to the front
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      nums[nonZeroIndex] = nums[i];
      nonZeroIndex++;
    }
  }

  // Fill the rest with zeros
  for (let i = nonZeroIndex; i < nums.length; i++) {
    nums[i] = 0;
  }

  return nums;
}

console.log(moveZeroes([0, 1, 0, 3, 12])); // [1, 3, 12, 0, 0]

Dato un array di interi nums, trova il sottoarray contiguo (contenente almeno un numero) che ha la somma maggiore e restituisci la sua somma.

Spiegazione: L'algoritmo di Kadane è un modo efficiente per risolvere questo problema. Itera attraverso l'array, tenendo traccia della somma currentMax che termina nella posizione corrente e della somma globalMax trovata finora. Se currentMax diventa negativo, resettalo a 0 (o piuttosto, all'elemento corrente).

function maxSubArray(nums) {
  let globalMax = -Infinity;
  let currentMax = 0;

  for (let i = 0; i < nums.length; i++) {
    currentMax = Math.max(nums[i], currentMax + nums[i]);
    if (currentMax > globalMax) {
      globalMax = currentMax;
    }
  }
  return globalMax;
}

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6 (from [4, -1, 2, 1])