Algos.

001. Algos

This Gist contain solutions for JavaScript problems

1. Rotate Array
2. Anagrams
3. Conitous v or w : min and max
4. Minimum swaps to sort array
5. Rotation
6. Create 1...n array
7. Power set of an arrray
8. Number of occurances
9. Frequency of item an array as a map result
10. Maximum alternate sum using DP
11. Tree traverlsals

anagram.js

main(){
    const words = ['map', 'art', 'how', 'rat', 'tar', 'who', 'pam', 'shoop'];
    let anagramMap = anagramGrouper(words);
    console.log(anagramMap)
}

function anagramGrouper(words) {
    const anagrams = {}
    words.forEach((word) => {
        const sortedWord = alphabetize(word)
        if (anagrams[sortedWord]) {
            return anagrams[sortedWord].push(word)
        }
        else {
            anagrams[sortedWord] = [word];
        }

    })

    return anagrams;
}
function alphabetize(word) {
    if (!word) {
        return;
    }
    word = word.split('')
    word = word.sort();
    word = word.join('');
    return word
}

closures

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Closures

A closure is the combination of a function and the lexical environment within which that function was declared. This environment consists of any local variables that were in-scope at the time the closure was created.

function makeAdder(x) {
  return function(y) {
    return x + y;
  };
}

var add5 = makeAdder(5);
var add10 = makeAdder(10);

console.log(add5(2));  // 7
console.log(add10(2)); // 12

In this example, we have defined a function makeAdder(x), which takes a single argument, x, and returns a new function. The function it returns takes a single argument, y, and returns the sum of x and y.

In essence, makeAdder is a function factory — it creates functions which can add a specific value to their argument. In the above example we use our function factory to create two new functions — one that adds 5 to its argument, and one that adds 10.

add5 and add10 are both closures. They share the same function body definition, but store different lexical environments. In add5's lexical environment, x is 5, while in the lexical environment for add10, x is 10.




another example:


function getCounter() {
  let counter = 0;
  return function() {
    return counter++;
  }
}
console.log(getCounter()());  // 0
console.log(getCounter()());  // 0
console.log(getCounter()());  // 0



let count = getCounter();
console.log(count());  // 0
console.log(count());  // 1
console.log(count());  // 2

continousVorW.js

let input = "5\navwvvb"
    let s = input.split('\n')[1].split('')
    let minCounter = 0
    let maxCounter = 0
    
    let continous = 0
    
    s.forEach((elt,i)=> {
        // avwvvb
       // min : 0,1,1
       // max :0,1,1
       // con : 0,1,3,4
        if(elt == 'v' || elt == 'w'){
            
           if( ( s[i-1] == 'v' || s[i-1] == 'w' ) ){
               if(s[i-1]=='v'){
                   continous++
               }
               else{
                   continous = continous + 2
               }
                             
           }
           else{
               minCounter = minCounter + Math.ceil(continous / 2)
               maxCounter = maxCounter + continous
           }
        }
        else if( i != 0 && ( s[i-1] == 'v' || s[i-1] == 'w' ) ){
             if(s[i-1]=='v'){
                   continous++
               }
               else{
                   continous = continous + 2
               }
            minCounter = minCounter + Math.ceil(continous / 2) + 1
            maxCounter = maxCounter + continous + 1
        }
        else{
            minCounter++
            maxCounter++
        }
       
    })
    console.log(minCounter + " " + maxCounter)

createConsecutiveArray1_n.js

 let a = Array.from({length: n}, (v, k) => k+1);

freqArray.js

result = { };
for(var i = 0; i < a.length; ++i) {
    if(!result[a[i]])
        result[a[i]] = 0;
    ++result[a[i]];
}

Maximum alternate sum

Given an array of integers, find the subset of non-adjacent elements with the maximum sum.

function maxSubsetSum(arr) {
    var i;
    if(arr.length == 0)return 0;
    arr[0] = Math.max(0, arr[0]);
    if(arr.length ==1) return arr[0];
    arr[1] = Math.max(arr[0], arr[1]);
    if(arr.length == 2)return arr[1];
    for(i=2;i<arr.length;i++){
        arr[i]=Math.max(arr[i-1], arr[i-2]+ arr[i]);
    }
    return arr[i-1]
}

minimumSwapsToSortAnArray.js

function minimumSwaps(arr) {
    let minValue = Math.min(...arr)
    console.log(minValue)
    let buffer, newPosition, swapCount = 0
    let index = 0;
    while( index < arr.length){
        newPosition = arr[index] - minValue
        console.log('newpos'+newPosition)
        if ( newPosition === index) {
            index++     
        }
        else {
            buffer = arr[newPosition]
            arr[newPosition] = arr[index]
            arr[index] = buffer
            swapCount++
        }
    }
    return swapCount
}

numOccurances.js

("this is foo bar".match(/o/g)||[]).length

Overlapping ranges to same

void main() {
  List<MapEntry> input = [
    MapEntry(1, 3),
    MapEntry(6, 9),
    MapEntry(9, 10),
    MapEntry(2, 4),
  ];

  input.sort((a, b) => a.key < b.key ? -1 : 1);
  print(input);
  
  List<MapEntry> stack = List();
  input.forEach((entry){
    if(stack.isNotEmpty){
      final top = stack.last;
      final topStart = top.key;
      final topEnd = top.value;
      final entryStart = entry.key;
      final entryEnd = entry.value;
      if( entryStart >= topStart && entryStart <= topEnd ){
        if(entryEnd > topEnd){
          stack.removeLast();
          stack.add(MapEntry(topStart, entryEnd));
        }
      }else{
         stack.add(entry);
      }
    }else{
      stack.add(entry);
    }
  });
  
  print(stack);
}

Power set.js

function powerSet( list ){
    var set = [],
        listSize = list.length,
        combinationsCount = (1 << listSize),
        combination;

    for (var i = 1; i < combinationsCount ; i++ ){
        var combination = [];
        for (var j=0;j<listSize;j++){
            if ((i & (1 << j))){
                combination.push(list[j]);
            }
        }
        set.push(combination);
    }
    return set;
}

rotate.js

//rotate array a, d times left
function rotLeft(a, d) {
    for (let i = 0; i < d; i++){
        a.push(a.shift())
    }
    return a
}

Sort two sorted arrays without extra space.

void main() {
  final List<int> arr1 = [1, 5, 9, 10, 15, 20];
  final List<int> arr2 = [0, 9, 72, 90];
  for(int i=arr2.length -1;i>=0 ;i--){
    final firstArrayLastItem = arr1.last;
    final secondArrayItem = arr2[i];
    
    int j;
   
    bool addedToFirstArray = false;
    for(j=arr1.length -1;j>=0;j--){
      final thisItem = arr1[j];
      if(secondArrayItem < thisItem){
        if(j == 0){
         arr1[0]=secondArrayItem;
         addedToFirstArray = true;
          break;
        }else{
          arr1[j]=arr1[j-1];
        }
      }else{
        if(j == arr1.length -1){
          break;
        }
        arr1[j+1] = secondArrayItem;
        addedToFirstArray = true;
        break;
      }
    }
    if(addedToFirstArray){
      arr2[i] = firstArrayLastItem;
    }
  }
  print(arr1);
  print(arr2);
}

Tree traversal

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

  function inOrder(root) {
    if (root.left != null) inOrder(root.left)
    console.log(root.data)
    if (root.right != null) inOrder(root.right)
  }

  function postOrder(root) {
    if (root.left != null) postOrder(root.left)
    if (root.right != null) postOrder(root.right)
    console.log(root.data)
  }


  var node1 = new Node(1);
  var node2 = new Node(2);
  var node3 = new Node(3);
  var node4 = new Node(4);
  var node5 = new Node(5);
  var node6 = new Node(6);
  var node7 = new Node(7);
  var node8 = new Node(8);

  node1.left = node2;
  node1.right = node3;
  node2.left = node4;
  node2.right = node5;
  node5.right = node6;
  node3.right = node7;
  node7.left = node8;

  console.log("Inorder")
  inOrder(node1);

  console.log("PostOrder")
  postOrder(node1);