Coin Change Problem: Dynamic Programming

package com.hackerrank.problems;

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class CoinChange {

    static long getWays(long n, long[] c){

        // Complete this function

        Map<String,Long> m =  new HashMap<>();

        

        return change(n, c, 0, m);

    }

    

    static long change(long n, long[] c, int index, Map<String, Long> map){

        

        if(n == 0){

            return 1;

        }

        

        if(index >= c.length){

            return 0;

        }

        

        long ways = 0;

        

        long amountWithCoin = 0;

        

        String key = n + "-" + index; 

        System.out.println("Key" + key);

        

        if(map.containsKey(key)){

            return map.get(key);

        }

        

      

        while(amountWithCoin <= n){

            long remaining = n - amountWithCoin;

            ways = ways + change(remaining, c,index+1,map);

            amountWithCoin = amountWithCoin + c[index];

            System.out.println("Amount With Coin" + amountWithCoin);

        }

        map.put(key, ways);

        return ways;

    }

    public static void main(String[] args) {

        

        int n = 35;

        

        long[] c = {2, 5, 3, 6};

        

        long ways = getWays(n, c);

        

        System.out.println(ways);

    }

}

HashSet vs LinkedHashSet

**HashSet** uses buckets to store data which is stored in the form of array.

**LinkedHashSet** uses *doubly linked list* internally to store the data.

Now when the iteration happens in the HashSet the time depends on the `capacity` of the `HashSet`.

In case of LinkedHashSet it depends on the number of elements present in the set.

So even if the number of elements are lesser in the HashSet it might take more time because of the buckets. Hence iteration in LinkedHashSet is faster than HashSet.

From [grepcode][1]:

> Performance is likely to be just slightly below that of HashSet, due
> to the added expense of maintaining the linked list, with one
> exception: Iteration over a `LinkedHashSet` requires time proportional
> to the size of the set, regardless of its capacity.  
> Iteration over a HashSet is likely to be more expensive, requiring time proportional to
> its capacity. A **linked hash set** has two parameters that affect its
> performance: *initial capacity and load factor*. They are defined
> precisely as for `HashSet`. Note, however, that the penalty for choosing an excessively high value for initial capacity is less severe for this class than for HashSet, as iteration times for this class are
> unaffected by capacity.


  [1]: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b27/java/util/LinkedHashSet.java/

Merge LinkedList

Node mergeLists(Node headA, Node headB) {
     // This is a "method-only" submission.
     // You only need to complete this method
    Node currentA = headA;
    Node currentB = headB;
    Node mergedListHead = new Node();
    Node currentMerged = mergedListHead;
   
    while(currentA != null || currentB != null){
        if(currentA != null && currentB != null){
             if(currentA.data < currentB.data){
                currentMerged.next = currentA;
                currentA = currentA.next;
             }else{
                currentMerged.next = currentB;
                currentB = currentB.next;
             }
        }else if(currentB == null){
            currentMerged.next = currentA;
            break;
        }else if(currentA == null){
            currentMerged.next = currentB;
            break;
        }
        currentMerged = currentMerged.next;
    }
   
   return mergedListHead.next;

}

Check for Palindrome in JavaScript

Here is the code:

(function(){

'use strict';

var testStringOne = "Madam";

var testStringTwo = "testing";

var testNull = null;

var testUndefined;

console.log(checkIfPalindrome(testStringOne));

console.log(checkIfPalindrome(testStringTwo));

console.log(checkIfPalindrome(testNull));

console.log(checkIfPalindrome(testUndefined));

function checkIfPalindrome(testStringOne){

if(!testStringOne){

return false;

}

var testArrayOne = testStringOne.toLowerCase().split("");

testArrayOne.reverse();

if(testArrayOne.toString() == testStringOne.toLowerCase().split("").toString()){

return true;

}else{

return false;

}

}

})();

Remove Duplicates in a String Java

Used a HashSet:

public class RemoveCharacters {

    public static void main(String[] args) {

        String testOne = "Remove Duplicate Characters";

        System.out.println(removeDuplicateCharacters(testOne));

    }

    public static String removeDuplicateCharacters(String str) {

        Set<Character> strUnique = calculateUniqueCharacters(str);

        return strUnique.toString();

    }

    public static Set<Character> calculateUniqueCharacters(String str) {

        Set<Character> uniqueCharacterSet = new HashSet<>();

        str = str.toLowerCase();

        str = str.replaceAll("\\s+", "");

        for (int i = 0; i < str.length(); i++) {

            uniqueCharacterSet.add(str.charAt(i));

        }

        return uniqueCharacterSet;

    }

}

All possible Permutation of a String

public class StringPermutation {

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        String testString = "abcd";

        System.out.println(permutation("",testString));

        

        Set<Character> charSet = new HashSet<>();

        

        for(int i = 0; i < testString.length(); i++){

            charSet.add(testString.charAt(i));

        }

    }

    public static String permutation(String prefix, String perm) {

        if (perm.length() == 0) {

            System.out.println(prefix);

        } else {

            for (int i = 0; i < perm.length(); i++) {

                String returnPrefix = prefix + perm.charAt(i);

                String returnPerm = perm.substring(0, i) + perm.substring(i + 1);

                permutation(returnPrefix, returnPerm);

            }

        }

        

        return prefix;

    }

}

Print Duplicate in Java

package com.string.problems;

import java.util.HashMap;
import java.util.Map;

public class PrintDuplicate {

    public static void main(String[] args) {
        System.out.println(printDuplicate("aabbbccddefghiii"));
        System.out.println(printDuplicate("iiii"));
        System.out.println(printDuplicate(""));
        System.out.println(printDuplicate(null));
        System.out.println(printDuplicate("abc"));
    }

    public static String printDuplicate(String str) {

        if (null == str) {
            return "";
        }

        if ("".equals(str)) {
            return str;
        }

        if (str.length() == 2) {
            if (str.charAt(0) == str.charAt(1)) {
                return str.substring(0);
            } else {
                return str;
            }
        }

        Map<Character, Integer> strCount = new HashMap<>();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < str.length(); i++) {
            Character ch = str.charAt(i);
            if (!strCount.containsKey(ch)) {
                strCount.put(ch, 1);
            } else {
                Integer count = strCount.get(ch);
                count = count + 1;
                strCount.put(ch, count);
            }
        }

        for (Character key : strCount.keySet()) {
            Integer count = strCount.get(key);
            if (count > 1) {
                sb.append(key);
            }
        }

        return sb.toString();
    }

}

Check if Two Strings are Anagrams?

package com.string.problems;

import java.util.HashMap;
import java.util.Map;

/*
 * How to check if two Strings are anagrams of each other?
 * */

public class CheckIfAnagrams {

    public static void main(String args[]) {
        System.out.println(checkIfAnagram("Army", "Mary"));
        System.out.println(checkIfAnagram("Check", "true"));
        System.out.println(checkIfAnagram("AAbbcc", "cAAbbc"));
        System.out.println(checkIfAnagram("", null));
    }

    public static boolean checkIfAnagram(String strOne, String strTwo) {
        if (strOne == null || strTwo == null) {
            return false;
        }
        strOne = strOne.toLowerCase();
        strTwo = strTwo.toLowerCase();

        strOne = strOne.trim();
        strTwo = strTwo.trim();

        if (strOne.equals(strTwo)) {
            return true;
        }

        boolean anagram = false;

        Map<Character, Integer> strOneMap = createCountMap(strOne);
        Map<Character, Integer> strTwoMap = createCountMap(strTwo);

        if (strOneMap.equals(strTwoMap)) {
            anagram = true;
        }

        return anagram;
    }

    public static Map<Character, Integer> createCountMap(String str) {

        Map<Character, Integer> strCountMap = new HashMap<>();

        for (int i = 0; i < str.length(); i++) {
            Character key = str.charAt(i);
            if (strCountMap.containsKey(key)) {
                int count = strCountMap.get(key);
                count = count + 1;
                strCountMap.put(key, count);
            } else {
                strCountMap.put(key, 1);
            }
        }

        return strCountMap;
    }
}

Use local Storage in Ionic

You can create a local storage factory in Ionic and use it.

Here is the factory:

var peerHealthApp = angular.module('PeerHealthApp');

    peerHealthApp.factory('$localStorage', ['$window', function($window) {

        return {

   store: function(key, value) {

$window.localStorage[key] = value;

    },

    get: function(key, defaultValue) {

        return $window.localStorage[key] || defaultValue;

    },

    storeObject: function(key, value) {

                $window.localStorage[key] = JSON.stringify(value);

    },

    getObject: function(key,defaultValue) {

         return JSON.parse($window.localStorage[key] || defaultValue);

    }

}

}]);

To Use it:

$localStorage.storeObject("userDetails.token", someValue);

Find Prime Factors of a Number

Code to find Prime Factors of a Number:

public class PrimeFactorsOfANumber {

    

    public static void main(String args[]){

        List<Integer> primeFactorList = findPrimeFactors(210);

        

        for(int i = 0; i< primeFactorList.size(); i++){

            System.out.println(primeFactorList.get(i));

        }

    }

    

    public static List<Integer> findPrimeFactors(int number){

        List<Integer> primeFactorsList = new ArrayList<>();

        

        if(number == 2){

            primeFactorsList.add(2);

            return primeFactorsList;

        }

        

        if(checkIfPrime(number)){

            primeFactorsList.add(number);

            

        }else{

            int range = (int) Math.sqrt(number);

            for(int i = 2; i <=range; i++){

                if(number%i == 0){

                    if(checkIfPrime(i)){

                        primeFactorsList.add(i);

                    }

                }

            }

        }

        return primeFactorsList;

    }

    

    public static boolean checkIfPrime(int number){

        if(number > -1 && number < 2){

            return false;

        }

        

        boolean isPrime = true;

        

        int range = (int) Math.sqrt(number);

        

        for(int i = 2; i <= range; i++){

            if(number%i == 0){

                return false;

            }

        }

        

        return isPrime;

        

    }

}

Linked List in JavaScript

A simple implementation of LinkedList along with traversal can be done like this in JavaScript:

(function(){
 'use strict';
 var LinkedList = function(){
  this.head = null;
 }
 
 LinkedList.prototype.appendToTail = function(data){
  var node = {
   "data":data,
   "next":null
  };
  
  if(this.head == null){
   this.head = node;
  }else{
   var current = this.head;
   while( current.next != null){
    current = current.next;
   }
   current.next = node;
  }
 }
  
  LinkedList.prototype.traverseList = function(){
      var current = this.head;
      while(current != null){
          console.log(current.data);
          current = current.next;
      }
  
  }
 
  var linkedList = new LinkedList();
  linkedList.appendToTail(20);
  linkedList.appendToTail(30);
  linkedList.appendToTail(40);
     
  linkedList.traverseList();
 
})()

JavaScript Fibonacci

Here is a Fibonacci series code in JavaScript that uses Memoization technique of Dynamic Programming.

(function(){
  //suppose we want to find the first 10 terms
  'use strict';
  var fibArray = [];
  
  findFibByRec(10);
  
  function findFibByRec(number){
     for(var i = 0; i <= number; i++){
         console.log(fibRec(i));
     }
  }
  
  function fibRec(num){
     if(num == 0){
       fibArray[0] = 0;
       return 0;
     }
     
     if(num == 1 || num == 2){
       fibArray[num] = 1;
     }
     
     if(fibArray[num]){
        return fibArray[num];
     }
     
     if(!fibArray[num]){
       
       fibArray[num] = fibRec(num -1) + fibRec(num -2);
       return fibArray[num];
     }
  
  }

})()