Print Tree nodes at distance K from random node

Problem:
Given pointer to root of the binary tree and pointer to random node in the tree. Find all nodes that are at distance K from the random node.

Solution:

Algorithm:
a. If root is the random node then print all nodes from the root that are at distance K. Printing of nodes can be done recursively.
b. Search the random node in left sub tree of root. If node is found in left sub-tree and let say distance of random node from root is X. If X <= K, then print all nodes in the right sub-tree of the root that are are at distance K - X from the root.
c. If node is not found in the left sub-tree of the root then search the random node in right sub-tree of the root. Let us say that distance of random node in right sub-tree is X from the root. If X <= K, then print all nodes in the left sub-tree of the root that are are at distance K - X from the root.
d. Move one step closer toward the random node. i.e. if random node exist in left sub-tree of the root then set root = root.left, otherwise set root = root.right. Repeat step (a) to step (c).

This algorithm described above will be O(n^2) but if we use recursion carefully then we can make same solution O(n). In same recursion keep searching the node by moving towards the node and also printing the nodes in relevant sub-tree.

Working code for O(n) solution.

 public class PrintNodesAtK {  
      public static void main(String[] args) {  
           Tree root = new Tree(1);  
           Tree p1 = new Tree(2);  
           Tree p2 = new Tree(3);  
           Tree p3 = new Tree(4);  
           Tree p4 = new Tree(5);  
           Tree p5 = new Tree(6);  
           Tree p6 = new Tree(7);  
           Tree p7 = new Tree(8);  
           Tree p8 = new Tree(9);  
           Tree p9 = new Tree(10);  
           Tree p10 = new Tree(11);  
           Tree p11 = new Tree(12);  
           Tree p12 = new Tree(13);  
           root.left = p1;  
           root.right = p2;  
           p1.left = p3;  
           p1.right = p4;  
           p2.left = p5;  
           p2.right = p6;  
           p3.left = p7;  
           p4.left = p8;  
           p4.right = p9;  
           p6.left = p10;  
           p6.right = p11;  
           p10.right = p12;  
           searchNode(root, p6, 5);  
      }  
      public static int searchNode(Tree root, Tree random, int k) {  
           if (k == 0 || root == null) {  
                return -1;  
           } else if (random == root) {  
                printNodeAtK(root, k);  
                return 0;  
           } else {  
                int p = searchNode(root.left, random, k);  
                if (p != -1 && p + 1 <= k) {  
                     // Print root if d = 0  
                     int d = k - p - 1;  
                     if (d == 0) {  
                          System.out.println(root.value);  
                     } else {  
                          printNodeAtK(root.right, d - 1);  
                     }  
                } else if (p == -1) {  
                     p = searchNode(root.right, random, k);  
                     if (p != -1 && p + 1 <= k) {  
                          // Print root if d = 0  
                          int d = k - p - 1;  
                          if (d == 0) {  
                               System.out.println(root.value);  
                          } else {  
                               printNodeAtK(root.left, d - 1);  
                          }  
                     }  
                }  
                return p == -1 ? -1 : p + 1;  
           }  
      }  
      public static void printNodeAtK(Tree root, int k) {  
           if(root == null) {  
                return;  
           } else if (k == 0) {  
                System.out.println(root.value);  
           } else {  
                printNodeAtK(root.left, k - 1);  
                printNodeAtK(root.right, k - 1);  
           }  
      }  
 }  
 class Tree {  
      int value;  
      Tree left;  
      Tree right;  
      public Tree(int value) {  
           this.value = value;  
           left = null;  
           right = null;  
      }  
 }  

Display top 10 trending words

Problem:
There is a big file of words which is dynamically changing. We are continuously adding some words into it. How would you keep track of top 10 trending words at each moment?

Solution:
To solve this problem efficiently we need to look at two aspects:
a. We  must be able to detect if the word is a new word or it occurred previously. This can be done using data structure like Binary Search tree, Hash map, tries etc.
b. At any moment we must be able to retrieve top 10 words. This can be achieved using data structures like linked list, min heap or sorted array list.

The code mentioned below use hashmap and linked list. The linked list contain one node for every unique word and also maintain frequency of that word. The list is sorted at any given point of time, so first 10 nodes will be top 10 trending words.

To maintain mapping of nodes in the linked list and word, we use a hash map.

Adding new word : o(words)

 import java.util.HashMap;  
 import java.util.Scanner;  
 public class Top10Words {  
   public static void main(String[] args) {  
     Scanner s = new Scanner(System.in);  
           while(true) {  
                String word = s.next();  
                if(word.equals("-1")) {  
                     break;  
                } else if (word.equals("-2")) {  
                  printTopTen();  
                }else {  
                  addWord(word);  
                }  
           }  
           s.close();  
   }  
   public static HashMap<String,Node> nodeMap = new HashMap<String,Node>();  
   public static Node head = null;  
   public static Node tail = null;  
   public static void addWord(String word) {  
     if(nodeMap.containsKey(word)) {  
       Node p = nodeMap.get(word);  
       p.count++;  
       // move this node up the list if needed  
       while(p.prev != null && p.count > p.prev.count) {  
               Node t = p.prev;  
                  if(t.prev != null) {  
                   t.prev.next = p;  
                  }  
                  if(p.next != null) {  
                   p.next.prev = t;  
                  }  
                  t.next = p.next;  
                  p.prev = t.prev;  
                  p.next = t;  
                  t.prev = p;  
                  if(tail == p) {  
                   tail = t;  
                  }  
                  if(head == t) {  
                   head = p;  
                  }  
             }  
     } else {  
                // add new node to list and make entry in node map  
                Node newNode = new Node(word);  
                if(tail == null) {  
                     tail = newNode;  
                     head = newNode;  
                } else {  
                     tail.next = newNode;  
                     newNode.prev = tail;  
                     tail = newNode;  
       }  
       nodeMap.put(word,newNode);  
     }  
   }  
   public static void printTopTen() {  
     if(head == null) {  
         System.out.println("No Words till now.");  
        } else {  
          Node iter = head;  
             int i=0;  
             while(iter != null && i < 10) {  
              i++;  
                 System.out.println("Word: " + iter.word + " freq: " + iter.count);  
                 iter = iter.next;  
             }  
       }  
   }   
 }  
 class Node {  
   int count;  
   String word;  
   Node next;  
   Node prev;  
   public Node(String word) {  
    this.word = word;  
    this.count = 0;  
    this.next = null;  
    this.prev = null;  
   }   
 }  

As a improvement to above solution, we can modify the information that is stored in the hash map and linked list.

In the hashmap, store following information along with the word as key.
a. Frequency of the word
b. Reference to the node in the list. This will be null if the word is not currently stored in the list.

The linked list (doubly linked list) will have 10 nodes. Also maintain pointer to the head and tail of node.

Algorithm to add a new word:
a. If word does not exist in the hash map then add word to the hash map with frequency as 1. Also check if word should be added to the list (comparing with tail of the list). If word is added to the list, set node reference to the node in the list otherwise null.
b. If word exist in both hash map and list , increment the frequency by 1 in hash map and linked list.Update the linked list to maintain sorted order.
c. If word exist in hash map but not in linked list. Increment the frequency by 1 in hash map. Compare the tail value with new word frequency and check if word should be added to list by replacing the tail node. Readjust the linked list if required.
Note: When a node is deleted from linked list, set the node reference of corresponding hash map entry as null.

There are other possible solutions as well using other data structures. Trie can be used in place of hash map. Sometime it is not good practice to store lots of word in hash map. In such situations trie can be used.

In place of linked list we can also use min heap. It will reduce the complexity of adding new word from O(n) to O(log n). It will be more beneficial if we have to keep track of more words.

Solution using Trie and min Heap

Trie will be used to search for the word. It will also maintain frequency of the word.

Min Heap will be used to maintain top 10 words at any moment.

Algorithm:

• Search the word in the Trie. If word exists, increment the frequency count.
• Call min heapify function from index at which current word is stored in heap. If any node is pushed down/up the heap, keep updating reference index in the trie that indicate position of node in heap.
• If Word does not exist, add the word and make frequency count 1
• Compare the frequency of min element in heap with the new word. 
• If the frequency is less than current word frequency or the size of the heap is less than maximum size of heap
• Set the reference of min heap element to -1 indicate that it is no longer part of heap.
• Add the node to the heap at index 1 and call min heapify function from index 1. If any node is pushed down the heap, keep updating reference index in the trie that indicate position of node in heap.

At any moment element in min heap represent top 10 trending words.

 import java.util.Scanner;  
 public class DisplayTop10TrendingWord {  
      public static void main(String[] args) {  
           Scanner s = new Scanner(System.in);  
           Heap heap = new Heap(4);  
           while (s.hasNext()) {  
                String word = s.next();  
                TrieNode node = Trie.getWordNode(word);  
                node.frequency++;  
                if (node.reference != -1) {  
                     heap.minHeapify(node.reference);  
                } else {  
                     heap.addNodeToHeap(node);  
                }  
                for (int i = 1; i <= heap.heapsize; i++) {  
                     System.out.print(heap.heap[i].word + "("  
                               + heap.heap[i].frequency + ") ");  
                }  
                System.out.println();  
           }  
           s.close();  
      }  
 }  
 class TrieNode {  
      int frequency;  
      TrieNode[] childs;  
      int reference;  
      String word;  
      public TrieNode() {  
           this.frequency = 0;  
           this.childs = new TrieNode[26];  
           this.reference = -1;  
           this.word = null;  
      }  
 }  
 class Trie {  
      private static final TrieNode root = new TrieNode();  
      public static TrieNode getWordNode(String word) {  
           TrieNode node = root;  
           for (int i = 0; i < word.length(); i++) {  
                char ch = word.charAt(i);  
                if (node.childs[ch - 'a'] == null) {  
                     TrieNode child = new TrieNode();  
                     node.childs[ch - 'a'] = child;  
                }  
                node = node.childs[ch - 'a'];  
           }  
           node.word = word;  
           return node;  
      }  
 }  
 class Heap {  
      TrieNode[] heap;  
      int maxSize;  
      int heapsize;  
      public Heap(int maxSize) {  
           this.maxSize = maxSize;  
           this.heapsize = 0;  
           heap = new TrieNode[maxSize + 1];  
      }  
      public static int parent(int index) {  
           return index / 2;  
      }  
      public static int left(int index) {  
           return index * 2;  
      }  
      public static int right(int index) {  
           return index * 2 + 1;  
      }  
      public void minHeapify(int index) {  
           int minIndex = index;  
           int left = left(index);  
           int right = right(index);  
           if (left <= heapsize && heap[left].frequency < heap[minIndex].frequency) {  
                minIndex = left;  
           }  
           if (right <= heapsize  
                     && heap[right].frequency < heap[minIndex].frequency) {  
                minIndex = right;  
           }  
           if (minIndex != index) {  
                TrieNode temp = heap[index];  
                heap[index] = heap[minIndex];  
                heap[index].reference = index;  
                heap[minIndex] = temp;  
                heap[minIndex].reference = minIndex;  
                minHeapify(minIndex);  
           }  
      }  
      public void addNodeToHeap(TrieNode node) {  
           if (heapsize >= maxSize && heap[1].frequency >= node.frequency) {  
                node.reference = -1;  
           } else if (heapsize < maxSize) {  
                heap[++heapsize] = node;  
                int index = heapsize;  
                node.reference = index;  
                while (index > 1  
                          && heap[parent(index)].frequency > heap[index].frequency) {  
                     TrieNode temp = heap[parent(index)];  
                     heap[parent(index)] = heap[index];  
                     heap[parent(index)].reference = parent(index);  
                     heap[index] = temp;  
                     heap[index].reference = index;  
                     index = parent(index);  
                }  
           } else {  
                int index = 1;  
                heap[index].reference = -1;  
                heap[index] = node;  
                node.reference = index;  
                minHeapify(index);  
           }  
      }  
 }  

Clone linked list with random pointers

Clone linked list where a node also has a random pointer apart from next pointer.

e.g.



The problem of cloning a linked list with only next pointer is fairly simple problem. But the trickier part here is to clone random pointer since while cloning the next pointers we don't have a way to determine the node that will be clone of the node random pointer points to.

So the basic ides to solve this problem is to clone the next pointers in the first pass while maintaining a mapping of actual node and cloned node.
In second pass, clone all the next pointers.

The mapping of actual node and cloned node can be achieved by following two ways depending upon problem constraints.
a. If use of extra memory other than memory for cloned nodes is allowed then simplest way is to use hash map to maintain mapping of actual nodes and cloned node. In first pass clone next pointers and keep storing each cloned node in the hash map. In second pass, clone the random pointers.

b. If use of extra memory is not allowed, then we can follow approach of adding cloned node between actual nodes. For example insert 5` (clone of node 5) between node 5 and node 4.

• In first pass keep inserting cloned node between actual node. For above example linked list after first pass will look like:

          5--5'--4--4'--3--3'--2--2'--1--1'

• In second pass clone the random pointers and jumping 2 steps in each iteration.

          For example random pointer of 5' should be next of random pointer of 5. Jump 2 steps to node 4 at the end of iteration

• In third pass, restore all the pointers to split cloned and actual nodes.

Working code:

 import java.util.HashMap;  
 import java.util.Map;  
 /**  
  * Clone a linked list where each node has a next pointer and a random pointer  
  * to any node in the list.  
  *   
  * @author sanahuja  
  *   
  */  
 public class CloneList {  
      static Map<Node, Node> cloneNodes = new HashMap<Node, Node>();  
      public static void main(String[] args) {  
           Node head = new Node(5);  
           Node p1 = new Node(4);  
           Node p2 = new Node(3);  
           Node p3 = new Node(2);  
           Node p4 = new Node(1);  
           head.next = p1;  
           p1.next = p2;  
           p2.next = p3;  
           p3.next = p4;  
           head.random = p4;  
           p1.random = head;  
           p4.random = p3;  
           p2.random = p3;  
           printList(head);  
           Node newHead = cloneUsingHashMap(head);  
           printList(newHead);  
           Node newHead1 = cloneWithoutExtraMemory(head);  
           printList(newHead1);  
      }  
      private static void printList(Node head) {  
           Node t = head;  
           while (t != null) {  
                if (t.random != null) {  
                     System.out.print(t.value + "(" + t.random.value + ") -- ");  
                } else {  
                     System.out.print(t.value + " -- ");  
                }  
                t = t.next;  
           }  
           System.out.print("null");  
           System.out.println();  
      }  
      public static Node cloneNext(Node head) {  
           if (head == null) {  
                return null;  
           }  
           Node newHead = new Node(head.value);  
           cloneNodes.put(head, newHead);  
           // clone recursively  
           newHead.next = cloneNext(head.next);  
           return newHead;  
      }  
      public static Node cloneUsingHashMap(Node head) {  
           Node newHead = cloneNext(head);  
           Node t1 = head;  
           Node t2 = newHead;  
           while (t1 != null) {  
                t2.random = cloneNodes.get(t1.random);  
                t1 = t1.next;  
                t2 = t2.next;  
           }  
           return newHead;  
      }  
      // Without using hashmap or extra memory apart from node memories.  
      public static Node cloneWithoutExtraMemory(Node head) {  
           Node t1 = head;  
           while (t1 != null) {  
                Node newNode = new Node(t1.value);  
                newNode.next = t1.next;  
                t1.next = newNode;  
                t1 = t1.next.next;  
           }  
           // clone random pointers  
           t1 = head;  
           while (t1 != null) {  
                t1.next.random = t1.random;  
                t1 = t1.next.next;  
           }  
           // split clone nodes  
           Node newHead = head.next;  
           t1 = head;  
           Node t2 = head.next;  
           while (t2 != null) {  
                t1.next = t2.next;  
                t2.next = (t1.next == null) ? null : t1.next.next;  
                t1 = t1.next;  
                t2 = t2.next;  
           }  
           return newHead;  
      }  
 }  
 class Node {  
      int value;  
      Node next;  
      Node random;  
      public Node(int value) {  
           this.value = value;  
           this.next = null;  
           this.random = null;  
      }  
 }  

Serialize and deserialize N-ary tree (JAVA)

Write Java code to serialize and deserialize a N-ary tree

Encoding:

Data of each node will be represented using begin '.' and end '.'

')' will represent no more child for the node.

The basic idea is pack the tree using DFS, ')' will be written whenever current node's all child are written



The output will be :
.5..8..13..18..20..22.)))).17..23.))).9.).11..25..28..32.)).31..33.).34.).29.))).27.)))

Working code:

 import java.io.UnsupportedEncodingException;  
 import java.util.ArrayList;  
 import java.util.List;  
 import java.util.Stack;  
 public class SerializeNaryTree {  
      public static void main(String[] args) throws UnsupportedEncodingException {  
           Node root = new Node("5");  
           Node ch1 = new Node("8");  
           Node ch2 = new Node("9");  
           Node ch3 = new Node("11");  
           root.addChild(ch1);  
           root.addChild(ch2);  
           root.addChild(ch3);  
           Node ch4 = new Node("13");  
           Node ch5 = new Node("17");  
           Node ch6 = new Node("18");  
           Node ch7 = new Node("20");  
           Node ch8 = new Node("22");  
           ch1.addChild(ch4);  
           ch1.addChild(ch5);  
           ch4.addChild(ch6);  
           ch6.addChild(ch7);  
           ch7.addChild(ch8);  
           Node ch9 = new Node("23");  
           Node ch10 = new Node("25");  
           Node ch11 = new Node("27");  
           Node ch12 = new Node("28");  
           Node ch13 = new Node("32");  
           Node ch14 = new Node("31");  
           Node ch15 = new Node("33");  
           Node ch16 = new Node("34");  
           Node ch17 = new Node("29");  
           ch5.addChild(ch9);  
           ch3.addChild(ch10);  
           ch3.addChild(ch11);  
           ch10.addChild(ch12);  
           ch10.addChild(ch14);  
           ch12.addChild(ch13);  
           ch14.addChild(ch15);  
           ch14.addChild(ch16);  
           ch14.addChild(ch17);  
           String packed = Node.serialize(root);  
           System.out.println(packed);  
           Node compareTo = Node.deserialize(packed);  
           System.out.println(root.equals(compareTo));  
      }  
 }  
 class Node {  
      String key;  
      List<Node> childs = null;  
      public Node(String key) {  
           this.key = key;  
           this.childs = new ArrayList<Node>();  
      }  
      public void addChild(Node child) {  
           this.childs.add(child);  
      }  
      public static String serialize(Node root) {  
           StringBuilder result = new StringBuilder();  
           if (null != root) {  
                result.append(".");  
                result.append(root.key);  
                result.append(".");  
                for (Node child : root.childs) {  
                     result.append(Node.serialize(child));  
                }  
                result.append(")");  
           }  
           return result.toString();  
      }  
      public static Node deserialize(String node)  
                throws UnsupportedEncodingException {  
           Node result = null;  
           Stack<Node> stack = new Stack<Node>();  
           boolean isData = false;  
           StringBuilder data = null;  
           for (int i = 0; i < node.length(); i++) {  
                if (node.charAt(i) == '.') {  
                     isData = !isData;  
                     if (isData) {  
                          data = new StringBuilder();  
                     } else {  
                          Node child = new Node(data.toString());  
                          if (!stack.isEmpty()) {  
                               Node parent = stack.peek();  
                               parent.addChild(child);  
                          } else {  
                               result = child;  
                          }  
                          stack.push(child);  
                     }  
                } else {  
                     if (isData) {  
                          data.append(node.charAt(i));  
                     } else if (node.charAt(i) == ')') {  
                          stack.pop();  
                     } else {  
                          throw new UnsupportedEncodingException(  
                                    "Format not recognized.");  
                     }  
                }  
           }  
           return result;  
      }  
      public boolean equals(Node compareTo) {  
           if (null == compareTo) {  
                return false;  
           }  
           if (this.key.equals(compareTo.key)) {  
                boolean result = true;  
                for (int i = 0; i < this.childs.size(); i++) {  
                     result = result  
                               && this.childs.get(i).equals(compareTo.childs.get(i));  
                }  
                return result;  
           } else {  
                return false;  
           }  
      }  
 }  

Return the change

Given set of coins find the minimum number of coins required to return sum 'S'.
Let available set of coins be represented by array Coins. If sum can not be returned print -1
Assuming coins array is sorted.

Solution: O(N^2) where N is number of coins.

Sum[i] = min { Sum[i-Coin[j]] }  + 1, Sum[i-Coin[j]] != -1 && Coin[j] < i
if for all Sum[i-Coin[j]] == -1, Sum[i] = -1;

Test case

Coins: 1 3 4 5
Sum: 7
Min coin: 2

Sum:9
Min coin:2

Coins: 2 5 8 19
Sum:1
Min coin -1

Sum: 24
Min coin:2

Sum:23
Min coin: -1

Working code

 #include <stdio.h>  
  #include <iostream>  
  #define max(a,b) a>b?a:b  
  using namespace std;  
  int main() {  
  int n;  
  cin>>n;  
  int coin[n];  
  for(int i=0;i<n;i++) {  
  cin>>coin[i];  
  }  
  int s;  
  cin>>s;  
  int found = 0,min;  
  int sum[s+1];  
  sum[0] = 0;  
  for(int i=1;i<=s;i++) {  
  found = 0;  
  min = i;  
  for(int j=0;j<n && coin[j] <= i;j++) {  
   if(sum[i-coin[j]] != -1) {  
   found = 1;  
   if(sum[i-coin[j]] < min) {  
   min = sum[i-coin[j]];  
   }  
   }  
  }  
  if(!found) {  
   sum[i] = -1;  
  } else {  
   sum[i] = min + 1;  
  }  
  }  
  cout<<sum[s]<<endl;  
  return 0;  
  }  

Finding character with most occurrence in a continuous stream.

Problem: Given a continuous character stream, at any stage find and remove (set its occurance count to 0) the character that has occured highest number of time.

Solution: The problem can be solved efficient using combination of hash map and linked list (or max heap). The below code is using hash map and linked list.

The information that should stored in hash map is reference to the node (linked list or max heap). The key in the hash map is the character. If problem is limited to the smaller set of alphabet then array can also be used in place of hash map.

Whenever a character is read from the stream, then reference (linked list or max heap) is retrieved from the hash map. If reference does not exist then a new node will be created and inserted in the linked list or hash map. Otherwise, frequency of character is updated in the node retrieved using reference from hash map.

After the frequency of node is updated, linked list must be worked upon to ensure sorted order is maintained ( O(n) operation). If max heap is used then maxHeapify operation must be run to ensure heap property is maintained.

For retrieving most occurred character return and remove head of linked list or root of the max heap.

 import java.io.BufferedInputStream;  
 import java.io.IOException;  
 import java.io.InputStream;  
 import java.util.HashMap;  
 import java.util.Map;  
 /**  
  * Given a continuous character stream, at any stage find and remove (set its  
  * occurance count to 0) the character that has occured highest number of time.  
  *   
  * @author sanahuja  
  *   
  */  
 public class DoublyList {  
      private static Node head = null;  
      private static Node tail = null;  
      private static Map<Character, Node> chars = new HashMap<Character, Node>();  
      public static void main(String[] args) throws IOException {  
           InputStream s = new BufferedInputStream(System.in);  
           while (true) {  
                char c = (char) s.read();  
                if (c == '\r' || c == '\t' || c == ' ' || c == '\n') {  
                     continue;  
                } else if (c == '-') {  
                     if (head == null) {  
                          System.out.println("No char yet.");  
                     } else {  
                          // find and remove highest frequency char  
                          System.out.println("Highest char " + head.c  
                                    + " with count " + head.frequency);  
                          chars.remove(head.c);  
                          if (head == tail) {  
                               head = null;  
                               tail = null;  
                          } else {  
                               Node t = head;  
                               head = t.next;  
                               t.next = null;  
                               head.prev = null;  
                          }  
                     }  
                } else if (c == '$') {  
                     break;  
                } else {  
                     // add the char to list  
                     if (chars.containsKey(c)) {  
                          // update existing  
                          Node n = chars.get(c);  
                          n.frequency++;  
                          while (n.prev != null && n.frequency > n.prev.frequency) {  
                               Node p = n.prev;  
                               if (p.prev != null) {  
                                    p.prev.next = n;  
                               }  
                               p.next = n.next;  
                               if (n.next != null) {  
                                    n.next.prev = p;  
                               }  
                               n.prev = p.prev;  
                               p.prev = n;  
                               n.next = p;  
                               if (tail == n) {  
                                    tail = p;  
                               }  
                          }  
                          if (n.prev == null) {  
                               head = n;  
                          }  
                     } else {  
                          // add new node  
                          Node n = new Node(c);  
                          if (tail == null) {  
                               tail = n;  
                          } else {  
                               tail.next = n;  
                               n.prev = tail;  
                               tail = n;  
                          }  
                          if (head == null)  
                               head = n;  
                          chars.put(c, n);  
                     }  
                }  
           }  
           s.close();  
      }  
 }  
 class Node {  
      public char c;  
      public int frequency;  
      Node next;  
      Node prev;  
      public Node(char c) {  
           this.c = c;  
           this.frequency = 1;  
           next = null;  
           prev = null;  
      }  
 }  

For given array X[1..m] and Y[1..n] , find number of pairs such that x^y > y^x

Reference: http://www.geeksforgeeks.org/find-number-pairs-xy-yx/

Solution: a) Brute force O(m*n)
b) if y > x then x^y > y ^ x (with some exceptions which should not be counted) (rule a)
    if y <= x then x^y <= y^x (with some exceptions which should be counted) (rule b)

To find exceptions, try different values of x
Case x = 0: {Nothing should be counted}
    clearly for no value of y, 0 (0^y) will be greater then 1 (y^0), hence if x = 0 no such pair exist.
Case x = 1: {0s in y should be counted}
    Case y = 0: Exception of rule b
    Case y = 1: fine.
    Case y>1 : Exceptions of rule a
Case x = 2:
    Case y = 0: Exception of rule b
    Case y = 1: Exception of rule b
    Case y = 2: fine
    Case y = 3: exception of rule a
    Case y = 4: exception of rule a
    Case y > 4: fine
Case x = 3:
    Case y = 0: Exception of rule b
    Case y = 1: Exception of rule b
    Case y = 2: Exception of rule b
    Case y = 3: fine
    Case y >= 4: fine
Case x > 4:
    Case y = 0: Exception of rule b
    Case y = 1: Exception of rule b
    Case y > x: fine

Thus sort Y and count number of 0s,1s,2s,3s,4s O(mlogm + m) let it be y0,y1,y2,y3,y4
count = 0
for each X:
  if(x ==0){
  } else if(x==1) {
     count += y0;
  } else if (x==2) {
     count += y0 + y1;
     //binary search in y to fine least value greater than x, let it be i
      count += (n-i - y3-y4);
  } else if (x==3) {
     count += y0 + y1 + y2;
     //binary search in y to fine least value greater than x, let it be i
     count += (n-i);
  } else {
      count += y0 + y1;
       //binary search in y to fine least value greater than x, let it be i
       count += (n-i);
  }