Some Concepts.txt

---------------------------------Mathematical concepts-----------------------
1. We have to add digits until it becomes only a single digit => 38 -> 11 -> '2'

In Digital Root Formula See Wikipedia:

num == 0 => sum = 0
num % 9 == 9 => sum = 9
num % 9 != 9 =>sum = num % 9

shortcut for that ->        return 1 + (n-1)%9;
 
----------------------------------------->
2. Hashing
-> Hashing works in a way like make a hashtable, and suppose if we have some key firstly we convert that key in hash using a hash function which will give the address of the given key in the hashtable for constant access. same happens in case of insert,remove,search.

To Reduce Collisions in hashing
-> we can use a prime no table size  like  Hash value of a string/integer = (hash value)%(prime no table size).

Problems with String hash functions
a) Anagrams
-> cat, act
b) Non uniform Distribution
-> cat,sad,rat,bat <-this will only take small region of table, so no uniform distribution.     

-> Can be resolved by making Stronger hash function h = pow(d,m-1) where m is no of letters in the character.
-> If again collision happens then the same key will have multiple values in the form linkedList
-> But make sure the size of linkedlist should be min as it does not exceed loading factor of hashtables.
-> If it exceeds then there will be rehashing by double the size of hashtable.

Design HashMap->
class MyHashMap {

    final ListNode[]nodes;
    
    public MyHashMap() {
        nodes = new ListNode[10000];    
    }
    
    public void put(int key, int value) {
        int i = idx(key);
        if(nodes[i]==null){
            nodes[i]=new ListNode(-1,-1);
        }
        ListNode prev = find(nodes[i],key);
        if(prev.next==null){
            prev.next = new ListNode(key,value);
        }else{
            prev.next.val = value; //updating key's value
        }
    }
    
    public int get(int key) {
        int i = idx(key);
        if(nodes[i]==null){
            return -1;
        }else{
            ListNode prev = find(nodes[i],key);
            return (prev.next==null)?-1:prev.next.val;
        }
    }
    
    public void remove(int key) {
        int i = idx(key);
        if(nodes[i]==null){
            return;
        }else{
            ListNode prev = find(nodes[i],key);
            if(prev.next!=null){
                prev.next = prev.next.next;
            }
        }
    }
    
    public int idx(int key){return Integer.hashCode(key) % nodes.length;}
    
    public ListNode find(ListNode bucket,int key){
        ListNode node = bucket, prev = null;
        for(;node!=null && node.key!=key; node=node.next){
            prev = node;
        }
        return prev;
    }
    public class ListNode{
        int key;
        int val;
        ListNode next;
        public ListNode(int k,int v){
            key=k;
            val=v;
        }
    }
}
----------------------------------------------------------------------------------->
3. Shortcut
-> to convert list into array => res.stream().mapToInt(i->i).toArray();
---------------------------------------------------------------------------------->
4. Integer Break (LC-343)
-> Divide a number into 2 or more parts such that its sum makes the number itself, and product will be maximum.
-> Dry run to understand the pattern.
-> Mathematical proof -> https://leetcode.com/problems/integer-break/discuss/80689/A-simple-explanation-of-the-math-part-and-a-O(n)-solution

public int integerBreak(int n) {
        if(n == 2)
            return 1;
        else if(n == 3)
            return 2;
        else if(n%3 == 0)
            return (int)Math.pow(3, n/3);
        else if(n%3 == 1)
            return 2 * 2 * (int) Math.pow(3, (n - 4) / 3);
        else 
            return 2 * (int) Math.pow(3, (n-2)/3);
    }

---------------------------------------------------------------------------------->
5. Opposite of split is join in String.
  
   String []s = text.toLowerCase().split(" ");
   Arrays.sort(s, (a,b) ->  a.length() - b.length());
   String ans = String.join(" ", s);
---------------------------------------------------------------------------------->
6. Find number of times a string occurs as a subsequence in given string
-> Use LCS for this

// If last characters are same
        // Recur for remaining strings by
        // 1. considering last characters of
        // both strings
        // 2. ignoring last character of
        // first string
if (a.charAt(m - 1) == b.charAt(n - 1))
            return count(a, b, m - 1, n - 1) +
                   count(a, b, m - 1, n);
        else
            // If last characters are different, 
            // ignore last char of first string
            // and recur for  remaining string
            return count(a, b, m - 1, n);
---------------------------------------------------------------------------------->
---------------------------------------------------------------------------------->
---------------------------------------------------------------------------------->
---------------------------------------------------------------------------------->
---------------------------------------------------------------------------------->
---------------------------------------------------------------------------------->
---------------------------------------------------------------------------------->