js-algorithms-and-data-structures-masterclass snippets/notes

10.1 - searching algorithems.js

linear search, bigO(n)
pivot point then look right and left if it was sorted!

2.big-o.js

/**
Big O notation
the big o is mainly to analyze algorithems and 
compare an algorithem to the other
many solutions that doese the job, compared by the Big O. Eg, reverse a string.
vocabulary to talk about the code and how it performs.
Which is better? counting the operations. f(n) could be linear, =1 , quadratic or worse..
Auxiliary Space Complexity.
just the general trends.
logs appear with the sorting, searching algo and the recursion
**/

4,5 - problem-solving approahces.js

let instructor = {
    firstName: "kelly",
    isInstrcutor: true,
    favoriteNumbers: [1,2,3,4]
}
    
/**
anayltics

ojects
-------

insertion - o(1)
searching - o(n)
removal - o(1)
access - o(1)


arrays
-------

access - o(1)
insertion last/first (push/pop)- o(1)
insertion with movements (shift/unshift) - o(n)
searching - o(n)
sort- o(N*log N)

*/


/**
Problem Solving


algorithem : set of steps to accomplish a certain task.

how to approach, how do you imprpove?
- devise a plan for solving problems.
- master common patterns.

PS strategies:
George Poly - How to solve it!

- understand the problem 
   1. own words (implement addition)
   2. inputs (numbers? their length , the nmber in)
   3. outputs (the sum)
   4. enough information?
    
   5. terminology of the data
       num1,num2 to sum.
- explore concrete examples 
  sanity checks, you know the in/out.
  
- break it down
  comments/thoughts on how you will approach it. 
- solve/simplify
  Solve a simpler problem.. don't get stuck with smth difficult. then handle it later!

*/
// input string
// output object  result that contains each char and it's count
function charCount(str){
   
   var result = {};
   for(var i = 0 ; i < str.length; i++){
       var character = str[i].toLowerCase();
       if( result.hasOwnProperty(character))
       result[character] +=1;
       else 
       result[character] = 1;
   }

    return result;
}

charCount('resu22321ltSSS')
/**
1: 1
2: 3
3: 1
e: 1
l: 1
r: 1
s: 4
t: 1
u: 1
*/

- look back and refactor
there could be another solution, there could be an issue!
and maybe the performance, make it better! follow the style guide! rethink of another approach.
// only alphabets
...
  var character = str[i].toLowerCase();
       // only the alphanumeric ones.
       // 
       if(/[0-9a-z]/.test(character))
        {
           if( result.hasOwnProperty(character))
                result[character] +=1;
           else 
                result[character] = 1;
        }

...
// another refactor could be for (char of str)
...
   for(char of str){
       var character = char.toLowerCase();
...

// another fancier refactor
...
 result[char] = ++result[char]||1; // check if the object has the char then +1
...

// another thing is to use some custom function instead of the regext since it's performance ain't so good!

// understand the problem
// explore the examples
// break it down
// solve/simplify
// refactor!
 

# 5. common patterns

- counter frequency pattern, simply create an object to profile your data.

#problem 5.1


arr1 = [1,3,5]
arr2 = [25,2,9]

function sameSquared(arr1, arr2){
    for( var i of arr1)
        if(!arr2.includes(i**2)) return false;
  return true;
}
sameSquared(arr1,arr2)

// arr1 = [1,2,2]
arr2 = [1,4,4,4,4]

// the second has the first ones squared. each has it's corresponding squared element.

// examples
// [1,2,3]  &  [5,7,9,4] false
// [1,3,3] & [1,4,4,9] false
// [1,3,2] & [1,4,4,9] true
// [] & [] true

function sameSquared(arr1, arr2){
 if(arr1.length > arr2.length)
   return false;
  
 for(var i of arr1){
   var index = arr2.indexOf(i**2);
   if(index != -1 )
     arr2.splice(index, 1);
   else
     return false
 }
 return true;
}
sameSquared(arr1,arr2)


function sameSquaredFreq (arr1, arr2){
  var a1 = {};
  var a2= {};
  for(var i of arr1)
    a1[i**2] = a1[i**2]? ++a1[i**2]: 1;
  for(var i of arr2)
    a2[i] = a2[i]? ++a2[i]: 1;

  for( var prop in a1){
    if(a1[prop] != a2[prop])
    return false;
  }
  return true
}

// same equal
arr1 = [1,2,2]
arr2 = [1,4,4]

sameSquaredFreq(arr1, arr2)


#problem 5.2
DONE!: solve the anagram problem
function validAnagram(o1, o2){
  // add whatever parameters you deem necessary - good luck!
  if(o1.length != o2.length)
  return false;
  var s1 = {}
  var s2 = {}
  for(var ch of o1)
  s1[ch] = s1[ch]? ++s1[ch] : 1;
  for(var ch of o2)
  s2[ch] = s2[ch]? ++s2[ch] : 1;
  
 for(var prop in s1){
     if(s1[prop] != s2[prop])
         return false;   
 }

  return true;
}

#problem 5.3 

DONE!: solve the MaxSupArraySum problem. w/z w/zout the slide window pattern:
// problem
// testing examples 
// [1,2,5,2,8,1,5],2 -> 10 x
// [1,2,5,2,8,1,5] -> 4
// [4,2,1,6],1 -> 6
// [4,2,1,6,2],4 ->13   x
// question to be asked? are there any negatives? no!
// [], 4 -> null


/** A naive solution.
 * loop over the array, loop over the span starting from ith {element} and ending with the span limit, then sum and compare to the max sum variable.
 */

function maxSupArraySum(arr , span){
 console.time('process1');
    var len = arr.length;
    if( !len){
        return null;
    }
    
   var max = -Infinity ;
   for(var i = 0 ; i < len- span+1 ; i++){
       var sum = 0;
       for(var j = i; j < span + i  ; j++){
            sum+=arr[j];
       }
        if(sum > max)
        max = sum;
   }
       console.timeEnd('process1');

    return max;
}


// maxSupArraySum([4,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,2],100)


/** The slide window approach
*   - get the first span and add it to the max sum.
*   - loop over the array, temp sum will equal the new span subtracted from the ith - span -1 element and added the ith +1 element
*/
function maxSupArraySumSlide(arr , num){
    console.time('process2');

    let maxSum = 0;
    let tempSum = 0;
    let len = arr.length;
    for(let i =0 ; i<num ; i++)
       maxSum+= arr[i];
    tempSum = maxSum;
    for( let i = num; i < len ; i++){
        tempSum = tempSum - arr[i - num] + arr[i];
        maxSum = Math.max(tempSum, maxSum);
    }
    console.timeEnd('process2');

    return maxSum;
}


maxSupArraySumSlide([4,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,2],10 );  // 13
maxSupArraySum([4,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,24,2,1,6,2],10 ) // 13


//  analysis

// process2: 0.037109375ms totally faster!!
// process1: 0.2080078125ms

6.problems-patterns.js

// same frequency problem1 
function sameFrequency(a1, a2){
    a1 = ''+a1;
    a2 = ''+a2;
    if(a1.length != a2.length)
    return false;
    var o1 = {} ;
    for(var char of a1)
        o1[char]? ++o1[char] : o1[char] = 1;
    for(var char of a2){
        var x = o1[char]? --o1[char] : false;
        if(x === false)
            return false;
    }

    return true;
    
}
sameFrequency(2221,1222)


// are there duplicates.
function areThereDuplicates(...args){
    var o={};
    for(var i of args){
        o[i]? ++o[i]: o[i]=1;
    }
    for(var i in o){
        if(o[i] > 1)
        return true;
    }
    return false;
}