DSA

Question 1

bubble sort

Answer 1

const bubble = (arr) => {
// start looping the outer
for(let i = 0; i < arr.length; i++) {
// start looping the inner and compare 2 values
for (let j = 0; j < arr.length - 1; j++) {
// if the first value is greater than the 2nd value, swap their position
if(arr[j] > arr[j + 1]) {
var temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
}
}
}

console.log(arr) }

bubble([10, 24, 100, 85, 66, 1, 23, 68, 54])

Question 2

selection sort

Answer 2

function sselectionSort(arr){
for(var i = 0; i < arr.length; i++){
var lowest = i;
for(var j = i+1; j < arr.length; j++){
if(arr[j] < arr[lowest]){
lowest = j;
}
}
if(i !== lowest){
//SWAP!
var temp = arr[i];
arr[i] = arr[lowest];
arr[lowest] = temp;
}
}
return arr;
}

Question 3

naive string search

Answer 3

const search = (long, short) => {
let count = 0
// loop long string
for (let i = 0; i < long.length; i++) {
// loop short string
for (let j =0; j < short.length; j++) {

       // if short subs str is equal to long sub str, look for the next sub str in long, else break the inner loop
       if(short[j] !== long[i+j]) break

       // if j is in the same length as short return count or increment coubt
       if(j === short.length - 1) count++
    }    }    return count

}

console.log(search(“lorie loled”, “lol”))

Question 4

fibonacci (loop)

Answer 4

static int fib2(int target) {
var pos1 = 0;
var pos2 = 1;
var ans = 0;
for (var i = 0; i <= target; i++) {
ans = pos1 + pos2;
pos1 = pos2;
pos2 = ans;
}

    return ans;
}

Question 5

binary search

Answer 5

const findNum = (arr, target) =>{
// init pointers
let start = 0
let end = arr.length - 1
let middle = Math.floor((start + end) / 2)

// if middle and target is not the same go loop
while (middle !== target && start <= end) {
    // if middle is greater than the target, change the end to middle then - 1
    if (middle > target) {
        end = middle - 1
    // if middle is less than the target, change the start to middle then + 1
    } else {
        start = middle + 1
    }

    middle =  Math.floor((start + end) / 2)

}

// if middle is the same as target return num
if(middle === target) {
    return middle - 1
} else {
    return -1
} }

console.log(findNum([1, 2, 3, 4, 5, 6, 7, 8, 9], 221))

Question 6

same set of numbers by power of 2 using frequency counter

// [1,2,3,2,5], [9,1,4,4,25] return true
// [1,2,3,2,5], [9,1,4,4,11] return false

Answer 6

function same(arr1, arr2){
if(arr1.length !== arr2.length){
return false;
}
let frequencyCounter1 = {}
let frequencyCounter2 = {}
for(let val of arr1){
frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1
// console.log(frequencyCounter1[val])
}
for(let val of arr2){
frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1
}
console.log(frequencyCounter1);
// console.log(frequencyCounter2);
for(let key in frequencyCounter1){
console.log(key ** 2)
if(!(key ** 2 in frequencyCounter2)){
return false
}
if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
return false
}
}
return true
}

same([1,2,3,2,5], [9,1,4,4,25])

Question 7

check if anagram using frequency counter

// return true if correct, false if not

Answer 7

const anagram = (str1, str2) => {
// compare two strings (anagram) if it matches per character
// if two str is is empty return true
if(str1 === “” && str2 === “”) {
return true
}

// if two str length is not the same return false
if(str1.length !== str2.length) {
    return false
}

const freq1 = {}

for(let i = 0; i < str1.length; i++) {
    let letter = str1[i];
    freq1[letter] = (freq1[letter] || 0) + 1
}

console.log(freq1)

for(let i = 0; i < str2.length; i++) {
    let letter = str2[i];
    if (!freq1[letter]) {
        return false;
    } else {
        freq1[letter] -= 1;
    }
}

// // if two str is not the same return false

return true }

console.log(anagram(“dad”, “adds”))

Question 8

sum of zero (multiple pointers)

Answer 8

const sumZero = (arr) => {
let left = 0;
let right = arr.length - 1

while (left < right ) {
  // get the sum of first and last idx
  let sum = arr[left] + arr[right]
  console.log(arr[left], arr[right],`ans ${arr[left] + arr[right]}`)
  // compare if equal to zero and return
  // -2 2 ans 0
  if(sum === 0) {
    return [arr[left], arr[right]]
  
  // if sum is higher than zero, decrement the right
  // -3 4 ans 1
  // -3 4 ans 1
  
  } else if (sum > 0) {
    right--
  
  // if sum is lower than zero, increment left
  // -3 2 ans -1
  } else {
    left++
  }
}   }

// console.log(sumZero([-3, -2, -1, 0, 1, 2, 4, 4]))

Question 9

count unique values (multiple pointers)

Answer 9

const countUniqueValues = (arr) => {
if(arr.length === 0) {
return undefined
}

let i = 0
for (let j = 1; j < arr.length; j++) {
    if(arr[i] !== arr[j]) {
        i++
        arr[i] = arr[j]
    }
}
return i + 1 } console.log(countUniqueValues([1, 1, 1, 2])) console.log(countUniqueValues([-2, -1, -1, 0, 1])) console.log(countUniqueValues([1, 2, 3, 4,4,4,7,7,12,12,13]))

Question 10

sum of sub array (sliding window)

Answer 10

function maxSubarraySum(arr, num){
let maxSum = 0;
let tempSum = 0;
if (arr.length < num) return null;
// calculate the first 3 idx sum: 2,6,9 = 17
for (let i = 0; i < num; i++) {
maxSum += arr[i];
}

// store the sum
tempSum = maxSum;
for (let i = num; i < arr.length; i++) {
  // 17 - 2 (first index) + 2 (4th index)
  // next iteration will subtract the tempSum from the arr 2nd index and add the arr 4th index and so on.
  tempSum = tempSum - arr[i - num] + arr[i];

  // will get the max value
  maxSum = Math.max(maxSum, tempSum);
}
return maxSum;   }

maxSubarraySum([2,6,9,2,1,8,5,6,3],3)