practices.js

// Design an algorithm to compute a square root that handles perfect and non-perfect squares
function getSqrt(square) {
  return Math.round(Math.pow(square, 1/2) * 100) / 100;
}
console.log('getSqrt', getSqrt(25) === 5 && getSqrt(10) === 3.16);

// Given a sequence A of size N, find the length of the longest increasing subsequence from a given sequence.
function findLongsetIncreasing(arr) {
  arr.unshift(0);
  const res = arr.reduce((acc, mem, idx, arr) => {
    if (mem > arr[idx - 1]) {
      acc[acc.length - 1]++;
    } else {
      if (arr[idx - 1]) {
        acc.push(1);
      }
    }
    return acc;
  }, [0]);
  return Math.max(...res);
}
console.log('findLongsetIncreasing', findLongsetIncreasing([1,2,3,4,5,2,3,4,1,2,3,4,5,6,2,5]) === 6)

// Write a function for reverse of a string, and explain its edge cases
function reverse(str) {
  const arr = str.split('');
  let idx;
  let max = arr.length - 1;
  const reverse = [];
  for (idx = max; idx >= 0; idx--) {
    reverse.push(arr[idx]);
  }
  return reverse.join('');
}
console.log('reverse', reverse('HelloWorld') === 'dlroWolleH');

// Construct a binary tree
function constructBiTree(arr) {
  class Node {
    constructor(val,left,right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
  }
  function buildBiTree(arr, idx) {
    if (!arr[idx]) {
      return null;
    }
    const val = arr[idx];
    return new Node(val,
      buildBiTree(arr, 2 * idx + 1),
      buildBiTree(arr, 2 * idx + 2)
    );
  }
  return buildBiTree(arr, 0);
}
console.log('constructBiTree', constructBiTree([1,2,3,4,5]))

// Convert hex string to int and vice versa.
function hexIntConverter() {
  const hexMap = new Map([['A',10],['B',11],['C',12],['D',13],['E',14],['F',15]]);
  return {
    hexToInt(hex) {
      return hex.split('').map((char, idx, arr) => {
        const num = hexMap.get(char) ? hexMap.get(char) : Number(char);
        return num * Math.pow(16, arr.length - 1 - idx);
      }).reduce((acc, num) => {
        return acc + num;
      },0);
    },
    intToHex(int) {
      return int.toString(16);
    }  
  }
}
const seed = 36;
console.log('hexIntConverter', seed === hexIntConverter().hexToInt(hexIntConverter().intToHex(seed)));

// Write a function that takes an integer and counts the number of bits.
function getBits(int) {
  return int.toString(2).split('').length;
}
console.log('getBits', getBits(4))

// Given an array of unique integers, return a pair of integers that sum up to a target sum.
function findPairs(arr, target) {
  const map = new Map(arr.map((int) => [int, int])); // O(N)
  return arr.filter((int) => map.get(target - int)).map((int) => [int, map.get(target - int)]);  // O(N^2)
}
console.log('findPairs', findPairs([1,2,3,4,5,6,7,8,9,10,11,12], 4));

// Given a book, make a function to get the ten most popular words
function popularWords(book) {
  const populars = book.toLowerCase().replace(/(?:[a-z])/, '').split(' ')
    .reduce((acc, word) => {
      if (!acc[word]) acc[word] = 0;
      acc[word]++;
      return acc;
    }, {}); // O(N)
  return Object.keys(populars)
    .sort((a, b) => populars[a] === populars[b] ? 0 : populars[a] > populars[b] ? -1 : 1)
    .splice(0, 10); // O(N)
}
const book = "Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book. It has survived not only five centuries, but also the leap into electronic typesetting, remaining essentially unchanged. It was popularised in the 1960s with the release of Letraset sheets containing Lorem Ipsum passages, and more recently with desktop publishing software like Aldus PageMaker including versions of Lorem Ipsum.";
console.log('popularWords', popularWords(book));