Has SubSet with sum

Given an array A of N integers and a sum S. Can elements of this array, be added in any order to get sum S? each element can be used only once.

• Run through all possibilities.

• Have a boolean as the flag and for all possible do 'OR' operations, if you get a solution it will be true.

public class HasSubSetWithSum {
    public static boolean hasSubSetWithSum(int arr[], int sum, int i) {
        if (sum == 0) {
            return true;
        }
        if (i >= arr.length){
            return false;
        } else {
            boolean result = false;
            result = result || hasSubSetWithSum(arr, sum-arr[i], i+1);
            result = result || hasSubSetWithSum(arr, sum, i+1);
            return result;
        }
    }
    public static void main(String[] args) {
        int set[] = { 3, 34, 4, 12, 5, 2 };
        int sum = 9;
        System.out.println(hasSubSetWithSum(set, sum, 0));
    }
}

Are Binary trees are identical

public class AreTreeIdentical {

    class BSTNode {
        int data;
        BSTNode left, right;

        public BSTNode(int data) {
            this.data = data;
            this.left = this.right = null;
        }
    }
    public static boolean areTreesIdentical(BSTNode tree1, BSTNode tree2) {

        if (tree1.left == null && tree2.right == null){
            return true;
        } else if (tree1.left != null && tree2.right == null) {
            return tree1.data == tree2.data && areTreesIdentical(tree1.right, tree2.left) && areTreesIdentical(tree1.left, tree2.left);
        }
        return false;
    }
}

Print Level Order Traversal

static void printLevelOrder(Node root)
    {
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (queue.size() != 0){

            Node currentNode = queue.poll();
            System.out.println(currentNode.data + " ");

            if (currentNode.left != null) {
                queue.add(currentNode.left);
            }
            if (currentNode.right != null){
                queue.add(currentNode.right);
            }

        }
    }

Check two strings are anagrams

boolean areAnagrams(String first, String second) {

         if (first.length() != second.length()){
             return false;
         }
         HashMap<Character, Integer> map = new HashMap<>();
         first= first.toLowerCase();
        second = second.toLowerCase();
         for(int i=0 ;i< first.length();i++){
             map.put(first.charAt(i), map.getOrDefault(first.charAt(i), 0)+1);
         }
         System.out.println(map);
         for(char ch : second.toCharArray()){
             if (map.containsKey(ch)){
                 map.put(ch, map.get(ch)-1);
                 if (map.get(ch) == 0) {
                     map.remove(ch);
                 }
             }else {
                 return false;
             }
             System.out.println(map);
         }
         if (map.size() == 0){
             return true;
         }else {
             return false;
         }
    }

First Non-Repeating Character

 int firstNonRepeating(int [] arr,int size) {
        Set<Integer> s = new HashSet<>();

        for (Integer n : arr) {
            if (!s.contains(n)){
                s.add(n);
            }else {
                return n;
            }
        }
        return -1;
    }

Binary Search

int BinarySearch(int arr[], int k) {
    // TODO:  Return Index of unique element
   int l = 0 ;
   int r = arr.length-1 ;
   int mid;
   while(l<=r){
    mid = l + (r-l)/2 ;
    if(arr[mid] == k)
      return mid;
    if(arr[mid] > k)
      r = mid-1;
    else
      l = mid+1;
   }
  return -1;

}

BSTNode searchBSTNode(BSTNode root, int d) {
        if (root == null){
            return null;
        }
        if (root.data == d){
            return root;
        }

        if (d < root.data){
            return searchBSTNode(root.left, d);
        }else {
            return searchBSTNode(root.right,d);
        }
    }

Traversals Use

Inorder traversal

Kandane's Algorithm Intuition

• Logically, why would you add the next number to the current answer? Only if that increases your sum, right? Like below:

• The current element increases the sum if it is positive. But, what if the number is negative? Well, it decreases the sum,Seems logical right?

• Well yes, but logically no

• [5,6,7,10,-11,20]

• What if the negative number is followed by a next number that increases the sub-array sum, then we need to consider the the full sub-array. Like below:

• But, we don’t know yet whether that would happen. Thus, we need to calculate the contiguous sum anyhow and have an additional variable to see if the sum ending at that number is greater than the current maximum value of the sum or not.