How to find integer pairs with given sum

How to find integer pairs with given sum

Pair of given sum  

Given an array of integers, and a number ‘sum’, find the number of pairs of integer in the array whose sum is equal to ‘sum’.

Array can be a combination of +ve, -ve and duplicate elements. Where we need to get the list of all unique pairs from the given array which makes sum is equal to given number. Easy solution with O(N) time complexity will be 

• Iterate each element from array and store it in Set.
• Compare the elements difference from sum as whether present in the Set or not. If present then print the pair with element and sum difference. 
• Remove the difference element from Set to avoid generating duplicate pair. 

Lets see simple Java solution

import java.util.HashSet;

public class PairSum {

 public static void main(String[] args) {

  int[] val = new int[] { 1, 7, 3, 3, 3, 4, 3, -1, 3, 6, 6, 6, 6, 2, 6, 3, 3, 5, 8, 10 };
  PairSum obj = new PairSum();
  obj.getPairs(val, 9);
 }

 public void getPairs(int[] val, int sum) {
  
  HashSet<Integer> set = new HashSet<Integer>();
  int count = 0;
  for (int i : val) {
   if (set.contains(sum - i)) {
    System.out.println("Pair : (" + (sum - i) + ", " + i + ")");
    set.remove(sum - i); // Removing existing value from set to avoid duplicate pair to print
    count++;
   }
   set.add(i);
  }
  
  System.out.println("\nNo. of pairs : "+count);
 }
}

OUTPUT:

Pair : (3, 6)
Pair : (7, 2)
Pair : (6, 3)
Pair : (4, 5)
Pair : (1, 8)
Pair : (-1, 10)

No. of pairs : 6

How to Design a simple LRU cache in Java

How to Design a simple LRU cache in Java

LRU  

Design and implement a data structure for Least Recently Used (LRU) cache by supporting set() and get() operations with O(1) complexity. 

Least Recently Used (LRU) Cache?

Its a caching mechanism where we evicts least recently used items from the cache to accommodate new entries at top. So in that case in cache we maintain only the recently used data and least used entries will be evicted once we need to set new value in cache. 

How to implement simple LRU Cache?

We can implement by using multiple data structure like stack, Queue, LinkedList etc., 
Now in this tutorial lets see how to implement by using Doubly LinkedList and map to hold the LinkedList nodes which makes O(1) complexity for our read / get() operation.

Steps:

• NodeLRU class which holds the data, next and previous node values.
• In LRUCache setting cache size as 5 to make it simple 
• set() method will check already value present in map or not. If its present remove the existing value from map and LinkedList and add the new value in LinkedList and map.
• get() method will fetch node if present in map and return the values or else return -1 if not present. 
• Once we get the value the node will be shifted to the head of LinkedList to make it as recently used. 

By this way we can implement the LRU cache with simple logic by using LinkedList and map. Lets see the java implementation for the same

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

/*
 * LinkedList node to hold the cached data
 */
class NodeLRU {
 int data;
 NodeLRU next;
 NodeLRU previous;

 public NodeLRU(int data) {
  this.data = data;
  this.next = null;
  this.previous = null;
 }
}

/**
 * Implementing LRU Cache using LinkedList and HashMap to get() value with O(1) 
 * time complexity.
 */
class LRUCache {

 // Total cache size 
 private final static int CACHE_SIZE = 5;

 // Map to hold the cached nodes
 private HashMap<Integer, NodeLRU> map = new HashMap<Integer, NodeLRU>(CACHE_SIZE);
 
 // Doubly LinkedList head and tail node pointer
 private NodeLRU head = null;
 private NodeLRU tail = null;

 /*
  * Set method which will add data into LinkedList
  * and if already key present then remove and ADD as new element.
  */
 public void set(int key, int val) {
  if (map.containsKey(key)) {
   removeExistingNode(key, val);
   set(key, val);
  } else {
   addNode(key, val);
  }
 }

 /*
  * Get method which will return node data if present
  * else returns -1. Once if data node present in map then
  * Fetch the node and place it @ head location. 
  */
 public int get(int key) {
  if (map.containsKey(key)) {
   NodeLRU node = map.get(key);
   makeAsRecentUsed(node);
   return node.data;
  }
  return -1;
 }
 
 /*
  * One if node present via get() method then 
  * pick out the node and stitch with head location as first node.
  * 
  */
 private void makeAsRecentUsed(NodeLRU node) {
  if (node.equals(head)) {
   return;
  } else if (node.equals(tail)) {
   tail.previous.next = null;
   tail = tail.previous;
  } else {
   node.previous.next = node.next;
   node.next.previous = node.previous;
  }
  node.previous = null;
  node.next = head;
  head.previous = node;
  head = node;
 }

 /*
  * Delete the least used node frm LinkedList and map
  */
 private void removeExistingNode(int key, int val) {
  NodeLRU tmp = map.get(key);
  if (tmp.next != null && tmp.previous != null) {
   tmp.previous.next = tmp.next;
   tmp.next.previous = tmp.previous;
  } else if (tmp.equals(tail)) {
   removeLeastUsed();
  } else if (tmp.equals(head)) {
   removeHeadNode();
  }
 }

 /*
  * Removing 1st node
  */
 private void removeHeadNode() {
  NodeLRU firstNode = head;
  tail = tail.next;
  tail.previous = null;
  removeFromMap(firstNode);
 }
 
 /*
  * Adding new node to LinkedList
  */
 private void addNode(int key, int val) {
  if (map.size() < CACHE_SIZE) {
   NodeLRU tmp = new NodeLRU(val);
   if (head == null && tail == null) {
    head = tail = tmp;
   } else {
    head.previous = tmp;
    tmp.next = head;
    head = tmp;
   }
   map.put(key, tmp);
  } else {
   removeLeastUsed();
   addNode(key, val);
  }
 }

 /*
  * Removing least/ last node from LinkedList
  */
 private void removeLeastUsed() {
  NodeLRU leastUsed = tail;
  tail = tail.previous;
  tail.next = null;
  removeFromMap(leastUsed);
 }

 /*
  * Removing from map also based on value node
  */
 private void removeFromMap(NodeLRU node) {
  for (Entry<Integer, NodeLRU> entry : map.entrySet()) {
   if (entry.getValue().equals(node)) {
    map.remove(entry.getKey());
    return;
   }
  }
 }

 /*
  * Method to print all LinkedList nodes data
  */
 public void printValueFromCache() {
  NodeLRU tmp = head;
  System.out.print("CACHE VALUES : ");
  while (tmp != null) {
   System.out.print(tmp.data + ", ");
   tmp = tmp.next;
  }
  System.out.println();
 }

 public static void main(String[] args) {

  LRUCache obj = new LRUCache();
  
  // Adding 1 to 5 values to cache
  obj.set(1, 11);
  obj.set(2, 12);
  obj.set(3, 13);
  obj.set(4, 14);
  obj.set(5, 15);

  obj.printValueFromCache();
  
  /*
   *  Reading value with key (1) which we adding 1st and
   *  placed last in LL. Once we read same value (Node) should 
   *  be placed as recent and moved to top of linked List.
   */
  
  int val = obj.get(1);
  System.out.println("READ VALUE : "+val);

  obj.printValueFromCache();
  
  /*
   * Adding some more values to Cache. Since we set cache size as 5
   * least used 3 nodes like (2,3,4) need to removed and (6,7,8)
   * values need to added to linked list 
   */
  obj.set(6, 66);
  obj.set(7, 77);
  obj.set(8, 88);

  obj.printValueFromCache();
  
  /*
   * Reading again with key (5) which makes node to shift to head
   * which will be recently used
   */
  val = obj.get(5);
  System.out.println("READ VALUE : "+val);

  obj.printValueFromCache();

 }
}

OUTPUT:

CACHE VALUES : 15, 14, 13, 12, 11, 
READ VALUE : 11
CACHE VALUES : 11, 15, 14, 13, 12, 
CACHE VALUES : 88, 77, 66, 11, 15, 
READ VALUE : 15
CACHE VALUES : 15, 88, 77, 66, 11, 

How to get Maximum Subarray Sum in optimal way

How to get Maximum Subarray Sum in optimal way

Maximum sub array  

Given an array with both positive and negative integers and need to find the sum of contiguous subarray of numbers which has the largest sum along with the index values like start and end index from the given array. Also time complexity with O(N)

For example, if the given array is {-2, 5, 4, -3, 6, 9, -1}, then the maximum subarray sum is 21 and array index from 1 to 5 which is  5 + 4 + -3 + 6 + 9 = 21.

Solution:

• Define each 2 variables for sum, start index and for end index. 
• 1st sum and index points will hold each block of sum until its values <= 0. 
• If any negative value comes in iteration then compare the 1st sum with 2nd (which holds the maximum subarray sum) sum and copy if its greater. 
• Iterate until array end and get the maximum subarray sum with the complexity of O(N)

If there are any better solution please post it under below comments section and sharing makes better.

public class SubArray {

 public static void main(String[] args) {

  int array[] = new int[] { -2, 5, 4, -3, 6, 9, -1 };

  SubArray obj = new SubArray();

  obj.getMaximumSumSubArray(array);
 }

 public void getMaximumSumSubArray(int[] array) {

  int start = 0, end = 0, sum = 0, finalSum = 0, fStart = 0, fEnd = 0;

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

   // Avoid initial array with negative
   if (array[i] > 0 && sum == 0) {
    start = end = i;
    sum = array[i];

    // Add current value with sum
   } else if (array[i] > 0) {
    end = i;
    sum += array[i];

   } else {
    // Copy sum to finalSum if sum > finalSum
    if (sum > finalSum) {
     finalSum = sum;
     fStart = start;
     fEnd = end;
    }

    // If sum + current <= 0 then start new sum
    if ((array[i] + sum) <= 0) {
     sum = 0;

    } else {
     sum += array[i];
    }
   }
  }

  // Last compare, sum and finalSum
  if (sum > finalSum) {
   finalSum = sum;
   fStart = start;
   fEnd = end;
  }

  System.out.println("Sum         : " + finalSum);
  System.out.println("Start Index : " + fStart);
  System.out.println("End Index   : " + fEnd);

 }
}

OUPUT:

Sum         : 21
Start Index : 1
End Index   : 5

How to do Level order traversal in Binary Search Tree

How to do Level order traversal in Binary Search Tree

Level order traversal  

We have see lot of tutorials based on Binary tree and also other traversals like Inorder, Preorder and Postorder etc.,

Now in this tutorial lets see how to do Level order traversal of Binary Search Tree using Queue. From the given below tree we need to get output as F, D, J, B, E, G, K, A, C I, H

Solution:

• Place the root node in Queue.
• Iterate Queue until queue becomes empty. Dequeue the first node from Queue and print the value of that node.
• Next Enqueue the child nodes left and right nodes inside same queue. 
• Repeat the process until each leaf node. 

Here in above example first we need to place 'F' node inside queue. Next in loop we need to print 'F' and get the child nodes 'D' and 'J' and enqueue inside same queue. Repeat the process until all leaf nodes and when Queue becomes empty.

class Node {
 Node left, right;
 int data;

 public Node(int data) {
  this.data = data;
 }
}

public class LevelOrderTraversal {
 
 public static void main(String[] args) {

  int a[] = { 11, 6, 19, 4, 8, 5, 43, 49, 10, 31, 17, 5 };

  Node root = null;
  LevelOrderTraversal tree = new LevelOrderTraversal();

  for (int i = 0; i < a.length; i++) {
   root = tree.insertNode(root, a[i]);
  }
  tree.levelOrderTraversal(root);
 }

 public void levelOrderTraversal(Node root) {

  if (root == null)
   return;

  Queue<Node> queue = new LinkedList<Node>();
  queue.add(root);
  System.out.println(root.data);

  while (queue.size() > 0) {
   Node current = queue.poll();
   if (current.left != null) {
    System.out.println(current.left.data);
    queue.add(current.left);
   }
   if (current.right != null) {
    System.out.println(current.right.data);
    queue.add(current.right);
   }
  }
 }

 public Node insertNode(Node root, int data) {
  Node currentNode = new Node(data);
  if (root == null) {
   root = currentNode;
  } else {
   insertData(currentNode, root);
  }
  return root;
 }

 public Node insertData(Node newNode, Node root) {

  if (root.data < newNode.data) {
   if (root.right == null) {
    root.right = newNode;
   } else {
    return insertData(newNode, root.right);
   }
  } else if (root.data > newNode.data) {
   if (root.left == null) {
    root.left = newNode;
   } else {
    return insertData(newNode, root.left);
   }
  }
  return root;
 }
}

OUTPUT:

11
6
19
4
8
17
43
5
10
31
49

How to get height of BST using recursive way

How to get height of BST using recursive way

Interview Questions  

The height of a Binary Search Tree is the length of the longest downward path to a leaf from root node. This is commonly needed in the manipulation of the various self-balancing trees, AVL Trees in particular. The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.
In below example the height of the tree is 5, i.e., from root(10) which goes to 3 -> 5 -> 7 -> 8 -> 9. So maximum height of the tree is 5

Lets see simple Java code to get the height of a BST tree using recursion.

class Node {
 Node left, right;
 int data;

 public Node(int data) {
  this.data = data;
 }
}

public class TreeHeight {

 public static void main(String[] args) {

  int a[] = { 1, 2, 3, 4, -1, -2, -3, -4, -5 };
  //int a[] = { 10,3,15,2,5,19,7,8,9,20,1 };
  
  Node root = null;
  TreeHeight tree = new TreeHeight();

  for (int i = 0; i < a.length; i++) {
   root = tree.insertNode(root, a[i]);
  }

  int height = tree.getBSTHeight(root);
  System.out.println("Binary Tree maximum height : " + height);
 }


 public int getBSTHeight(Node node) {
  if (node != null)
   return Math.max(getBSTHeight(node.left), 

                                        getBSTHeight(node.right)) + 1;
  else
   return -1;
 }
 
 public Node insertNode(Node root, int data) {
  Node currentNode = new Node(data);
  if (root == null) {
   root = currentNode;
  } else {
   insertData(currentNode, root);
  }
  return root;
 }

 public Node insertData(Node newNode, Node root) {

  if (root.data < newNode.data) {
   if (root.right == null) {
    root.right = newNode;
   } else {
    return insertData(newNode, root.right);
   }
  } else if (root.data > newNode.data) {
   if (root.left == null) {
    root.left = newNode;
   } else {
    return insertData(newNode, root.left);
   }
  }
  return root;
 }
}

OUTPUT:

Binary Tree maximum height : 5

How to do Iterative Postorder Traversal in BST

How to do Iterative Postorder Traversal in BST

Postorder  

Earlier we have seen lot of tutorials related to Binary Search Tree like

How to find the diameter of a binary tree
Converting a Binary Tree into its Mirror Tree
Inorder Predecessor and Successor of Binary Search Tree
How to find all leaf nodes in Binary Search Tree

In this tutorial we will see how to do postorder traversal using iterative method instead of recrusive algorithm. We are going to use single stack to store nodes and applying our logic over it to get postorder traversal.

Simple Java code to create Binary Search Tree and doing postorder traversal using iterative method.

import java.util.Stack;

class Node {
 Node left, right;
 int data;

 public Node(int data) {
  this.data = data;
 }
}

public class PostOrderTraversal {

 public static void main(String[] args)  {

  int a[] = { 4, 5, 8, 100, 3, 2, 9, 1, 7, 6 };
  Node root = null;
  PostOrderTraversal tree = new PostOrderTraversal();

  for (int i = 0; i < a.length; i++) {
   root = tree.insertNode(root, a[i]);
  }

  System.out.println("\n\nBy Stack : ");
  tree.postOrderTraversal(root);

 }

 /*
  * Postorder traversal using iteration and single stack
  */
 public void postOrderTraversal(Node root)  {

  //Stack to store each node
  Stack<Node> stack = new Stack<Node>();

  //Strong all left node from root into stack
  while (root != null) {
   stack.push(root);
   root = root.left;
  }
  Node node = null;

  while (stack.size() > 0) {

   // Boolean flag to check left and right nodes are visited or not
   boolean leftVisited = false, rightVisited = false;

   // Checking whether current node is equal to roots left node (1)
   if (node != null && stack.peek().left == node) {
    leftVisited = true;

   // Checking whether current node is equal to roots right node (2)
   } else if (node != null && stack.peek().right == node) {
    leftVisited = rightVisited = true;

   }
   node = stack.peek();

   // if above check (1) fails then push current nodes left node into stack
   if (node.left != null && !leftVisited) {
    stack.push(node.left);
   // if above check (2) fails then push current nodes right node into stack
   } else if (node.right != null && !rightVisited) {
    stack.push(node.right);

   } else {
    node = stack.pop();
    System.out.print(node.data + ", ");
   }
  }
 }

 public Node insertNode(Node root, int data) {
  Node currentNode = new Node(data);
  if (root == null) {
   root = currentNode;
  } else {
   insertData(currentNode, root);
  }
  return root;
 }

 public Node insertData(Node newNode, Node root) {

  if (root.data < newNode.data) {
   if (root.right == null) {
    root.right = newNode;
   } else {
    return insertData(newNode, root.right);
   }
  } else if (root.data > newNode.data) {
   if (root.left == null) {
    root.left = newNode;
   } else {
    return insertData(newNode, root.left);
   }
  }
  return root;
 }
}

OUTPUT:

By Stack : 
1, 2, 3, 6, 7, 9, 100, 8, 5, 4,