Create a mirror of a binary tree

Example
Input

Output

Implementation

public static Tree mirror(Tree root){

if(root == null)

return null;

Tree leftTree = null, rightTree = null;

if(root.left != null)

leftTree = mirror(root.left);

 

     if(root.right != null)

rightTree = mirror(root.right);

root.left = rightTree;

root.right = leftTree;

return root;

}

Find the merging point in given 2 linked lists

Example:
Input :







Output : 4

Algorithm
     1) Find lengths of both lists
     2) take the difference d of the lengths
     3) make d steps in longer list
     4) step in both lists in parallel until links to next node match

Implementation

class FindTheMergingPoingInGiven2LinkedList{
    static class LinkedList{
        int data;
        LinkedList next = null;
     
        public LinkedList(int data){
            this.data = data;
        }
     
        public void insertAtEnd(int data){
            LinkedList head = this;
            LinkedList newNode = new LinkedList(data);
         
            if(head == null){
                head = newNode;
                return;
            }
         
            while(head.next != null){
                head = head.next;
            }
            head.next = newNode;
        }
     
        public void print(LinkedList head){
            while(head != null){
                System.out.print(head.data + " ");
                head = head.next;
            }
            System.out.println();
        }
     
        //time : O(N)
        public static int length(LinkedList head){
            int length = 0;
            while(head != null){
                length++;
                head = head.next;
            }
            return length;
        }
                   
        public static LinkedList findMergingPoint(LinkedList head, LinkedList head2){
            //Base condition
            if(head == null && head2 == null)
                return null;
            
            int length = length(head);  //length of first list
            int length2 = length(head2);  //length of second list
            
            int diff;  //difference d of the lengths
            LinkedList bigList, smallList;
            if(length > length2){
                diff = length - length2;
                bigList = head;
                smallList = head2;
            }else{
                diff = length2 - length;
                bigList = head2;
                smallList = head;
            }
            
             //make d steps in longer list
            for(int i = 0; i < diff; i++)
                bigList = bigList.next;
            
            //make step in both lists in parallel until links to next node match      
           //or null     
            while(bigList != null && smallList != null){
                if(bigList == smallList) 
                    return bigList; 
                
                bigList = bigList.next;
                smallList = smallList.next;
            }
            return null;
        }
    }
 
    public static void main(String []args){
        LinkedList head = new LinkedList(1);
        head.insertAtEnd(2);
        head.insertAtEnd(3);
        head.insertAtEnd(4);
        head.insertAtEnd(5);
        head.insertAtEnd(6);
     
        LinkedList head2 = new LinkedList(7);
        head2.insertAtEnd(8);
        head2.next.next = head.next.next.next;     //merging the lists
     
     
        head2.print(head);
        head2.print(head2);
     
        LinkedList mergePoint = LinkedList.findMergingPoint(head, head2);
        System.out.println(mergePoint.data);
    }

}

Time Complexity: O(max(m, n))
Space Complexity : O(1)

Substract two numbers represented as linked list and return result as linked list

Example:
Input : 7->1->6 (617)
           5->9->2 (295)
Output : 2->2->3 (322)

class SubtractionOfLinkedList{
//List Node
static class Node{
int data;
Node next = null;

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

//insert in list at end
public void insert(int data){
Node n = this;
Node newNode = new Node(data);

while(n.next != null){
n = n.next;
}
n.next = newNode;
}

//Utility function to print the list
public static void print(Node n){
while(n != null){
if(n.next == null)
System.out.println(n.data);
else
System.out.print(n.data + "->");
n = n.next;
}
}
}

//Utility function to subtract given lists
static Node subtract(Node n1, Node n2, int borrow){
                  //Base condition
if(n1 == null && n2 == null && borrow == 0)
return null;

Node result = new Node(borrow);
int value = borrow;
 
                  if(n1.data >= n2.data){
value += n1.data - n2.data;
borrow = 0;
}else{
if(n1.next != null){
value += (n1.data)+10 - n2.data;
borrow = -1;
}else{
value += (n1.data)+10 - n2.data;
value = value*(-1);
borrow = 0;
}
}
result.data = value;
 
  //Recurse
if(n1.next!=null || n2.next!=null || borrow<0){
Node more = subtract(n1.next != null ? n1.next : null,
                                                      n2.next != null ? n2.next : null,
                                                      borrow < 0 ? -1 : 0);

result.next = more;
}
return result;
}

public static void main(String... args){
Node n1 = new Node(7);
n1.insert(1);
n1.insert(6);

Node n2 = new Node(5);
n2.insert(9);
n2.insert(2);

Node result = subtract(n1, n2, 0);
Node.print(result);
}
}

Output : 2->2->3

Naive Pattern Searching Algorithm

class StringMatchingAlgorithms{
static boolean isFoundHelper(char[] target, char[] pattern){
int targetLen = target.length;
int patternLen = pattern.length;
int k,l;
for(int i = 0; i < targetLen-patternLen+1; i++){
k = 0;l = i;
for(int j = 0; j < patternLen; j++){
if(target[l] == pattern[j]){
k++;l++;
                          }else
break;
}
if(k == patternLen)  //Pattern found, return true
                           return true;
}
return false;
}

static boolean isFound(String s, String p){
return isFoundHelper(s.toCharArray(), p.toCharArray());
}

public static void main(String []args){
String source = "abcdefab";
String pattern = "cde";

System.out.println("Result : "+isFound(source, pattern));
}
}

Time Complexity : O(N^2)
Space Complexity : O(1)

Combinations of coins

Write a function that takes an integer number and return the count of unique combinations of coins.
(Note : coins = {1, 2, 5, 10})
Example
Input : 3
Output : 2 (because we can make 3 by 1+1+1 or 1+2)

Input : 5
Output : 4 (because we can make 5 by 1+1+1+1+1, 1+1+1+2, 1+2+2, 5)

Implementation

class MakeChange{
static int makeChange2(int n, int denom){
//Base condition
if(n == 0)
return 1;

if(n < 0 || denom == 0)
return 0;

int nextDenom = getNextDenom(denom); //get the next denominator
//either take the current denominator or eliminate it
return makeChange2(n - denom, denom) + makeChange2(n, nextDenom);
}

//Utility function to get the next denominator
static int getNextDenom(int denom){
if(denom == 1)
return 2;
else if(denom == 2)
return 5;
else if(denom == 5)
return 10;
else
return 0;
}

public static void main(String... args){
int n = 5;
int change = makeChange2(n, 1);
System.out.println(change);
}
}

Rotate the array

Example
Input : {1, 2, 3, 4, 5},  rotate Index = 2
Output: {3, 4, 5, 1, 2}

Algorithm :
   1. Divide the given array into 2 groups at given rotate-index.(Group-A and Group-B)
   2. Group-A' = Reverse first group Group-A.
   3. Group-B' = Reverse second group Group-B.
   4. Reverse {Group-A', Group-B'}

How?:
let us consider the array = {1, 2, 3, 4, 5} and rotated index = 2.
then Group-A = {1, 2}
Group-B ={3, 4, 5}
{1, 2, 3, 4, 5} = {Group-A, Group-B}

Now reverse first group Group-A :
  Group-A' = reverse(Group-A)
  Group-A' = {2, 1}

Now reverse second group Group-B :
  Group-B' = reverse(Group-B)
  Group-B' = {5, 4, 3}

Now reverse {Group-A' , Group-B'} = {3, 4, 5, 1, 2}

Implementation

class RotateArray{
        public static void rotate(int []a, int k){
               reverse(a, 0, k-1);   //reverse the first group
               reverse(a, k, a.length - 1);   //reverse the second group
               reverse(a, 0, a.length - 1);  //reverse the array
        }
    
        public static void reverse(int []a, int start, int end){
               if( a.length < end-start)
                     return;
        
               for(; start < end; start++, end--){
                     int t = a[end];
                     a[end] = a[start];
                     a[start] = t;
               }
        }
    
        public static void main(String []args){
               int []a = {1,2,3,4,5};
               rotate(a,2);
              System.out.println(java.util.Arrays.toString(a));
        }  
}

Output : 3, 4, 5, 1, 2

Find two elements in the array add up to given number

Example:
Input : {1,2,4,5,3},  number = 8
Output : 5, 3 (because 5+3 = 8(given number))

Implementation

Method 1:

public static void findSum3(int []a, int sum){
        if(array == null || array.length == 0)
               return ;

for(int i = 0; i < a.length; i++){
for(int j = i+1; j < a.length; j++){
if(a[i] + a[j] == sum){
System.out.println(a[i] + " "+a[j]);
break;
}
}
}
}

Time Complexity : O(N^2)
Space Complexity : O(1)

Method 2:
public static void findSum(int []a, int sum){
        if(array == null || array.length == 0)
               return ;
 
        Hashtable h = new Hashtable();

for(int i = 0; i < a.length; i++){
               //if sum-a[i] is in hashtable then we already found the pair.
if(h.containsKey(sum - a[i])){       
System.out.println(a[i] +" "+(sum - a[i]));
}
else{   //put the element of array into hashtable, if it doesnot have it.
h.put(a[i], true);             
}
}
}

Time Complexity : O(N)
Space Complexity : O(N)

Method 3:

public static void findSum2(int []a, int sum){
     if(array == null || array.length == 0)
               return ;

//sort the array
Arrays.sort(a);

int first = 0;
int last = a.length - 1;       //last element
 
     while(first < last){
int s = a[first] + a[last]; //sum of first and last element of array
if(s == sum){
System.out.println(a[first] +" "+ a[last]);
first++;
last--;
}else{
if(s < sum)
first++;
else
last--;
}
}
}

Time Complexity : O(NlogN)
Space Complexity: O(1)

Find the maximum repeating number in the array

Given an array of size n, the array contains numbers in range from 0 to k-1 where k is a positive integer and k <= n. Find the maximum repeating number in this array. For example, let k be 8 the given array be arr[] = {2, 3, 3, 5, 3, 4, 1, 7};  the maximum repeating number would be 3.

Implementation

Method 1:

static int findMaxRepeatingNumber(int []array, int k){
     //Boundary condition
if(array == null || array.length == 0)
return -1;

int maxCount = Integer.MIN_VALUE;  //max count
int number = -1;
     //Iterate over all the elements of the array
for(int i = 0; i < array.length; i++){
int count = 1; //count of current number
for(int j = 1; j < array.length; j++){
if(array[i] == array[j])
count++;
}
if(count > maxCount){
maxCount = count;
number = array[i];
}
}
return number;  //return the maximum repeating number
}

Time Complexity : O(N^2)
Space Complexity : O(1)

Method 2:

static int findMaxRepeatingNumber2(int []array, int k){
      //Boundary condition
if(array == null || array.length == 0)
return -1;

int []count = new int[k]; //hold the count of number
 
      for(int i = 0; i < array.length; i++){
count[ array[i] ] ++;
}

//get the max count
int max = Integer.MIN_VALUE;
int number = -1;
 
      for(int i = 0; i < k; i++){
if(max < count[i]){
max = count[i];
number = i;
}
}
return number;
}

Time Complexity : O(N)
Space Complexity : O(K)

Given a float number, convert it into the string WITHOUT using any inbuilt function/library.

Implementation

class BinaryRepreOfRealNumberEx{
//function to convert integer into binary format
//Example : Input 2
//         Output : 10
public static String convertIntegerIntoBinaryFormat(int n){
StringBuffer binary = new StringBuffer();
while(n > 0){
binary.append( n & 1);
n = n >> 1;
}
binary.reverse();
return new String(binary);
}

//function to convert double into binary format
public static String convertDoubleIntoBinaryFormat(double n){
if(n >= 1 || n <= 0 )
return "error";

StringBuilder result = new StringBuilder();
result.append(".");

while(n > 0){
double r = n*2;
if(r >= 1){
result.append(1);
n = r - 1;
}else{
result.append(0);
n = r;
}
}
return result.toString();
}

//function to convert number into binary format
public static String convertIntoBinaryFormat(double number){
int t = (int)number;
String intPart = binary(t);

double d = number - t;
String doublePart = printBinary(d);

return intPart + doublePart;
}

public static void main(String []args){
String result = "";
double n = 2.2;

result = convertIntoBinaryFormat(n);
System.out.println("Binary Representation of "+ n +" "+result );
}
}

Reverse a linked list

Reverse a linked list
Example :
Input : 1->2->3
Output 3->2->1

Implementation

class ReverseLinkedListEx{
//Tree
static class Node{
int data;
Node next = null;

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

               //Utility to create a list
public void insert(int data){
Node newNode = new Node(data);

Node n = this;
if(n == null)
n = newNode;

while(n.next != null){
n = n.next;
}
n.next = newNode;
}

                //function to reverse the given list
public Node reverse(Node head){
Node previous = null;
Node current = head;
Node forward;

while(current !=null){
forward = current.next;
current.next = previous;
previous = current;
current = forward;
}
return previous;
}

public void display(){
Node head = this;

if(head == null)
return;

while(head != null){
System.out.println(head.data);
head = head.next;
}
}
}

public static void main(String[] args){
Node root = new Node(1);
root.insert(2);
root.insert(3);

System.out.println("Reversed list :");
                  Node rev = root.reverse(root);
rev.display();
}
       }

Output: 3->2->1

Time Complexity : O(N)
Space Complexity : O(1)

Add two numbers represented as linkedlist

Add two numbers represented as linkedlist.

Example
Input : list1: 7->1->6   (617)
          list2: 5->9->2    (295)
 Output: 2->1->9   (915)

Implementation

class AddLinkedListNumber{
//LinkedList
static class Node{
int data;
Node next = null;

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

//Utility to add new linkedlist node at the end of existing list
public void insertAtEnd(int data){
Node newNode = new Node(data);
Node n = this;

while(n.next != null){
n = n.next;
}
n.next = newNode;
}

//method to add 2 lists
public static Node addLists(Node n1 , Node n2 , int carry){
//Boundary Condition
if(n1 == null && n2 == null && carry == 0)
return null;

Node result = new Node(carry);
int value = carry;
 
                        if(n1 != null)
value += n1.data;

if(n2 !=null)
value += n2.data;

result.data = value%10; //second digit of number

//recurse
if(n1 != null || n2 !=null || value >= 10){
Node more = addLists(n1 == null ? null:n1.next,
n2 == null ? null:n2.next,
value >=10 ? 1 : 0);

result.next = more;
}
return result;
}

//Utility to display linkedlist
public void display(){
Node head = this;

while(head != null){
if(head.next !=null)
System.out.print(head.data+"->");
else
System.out.print(head.data);
head = head.next;
}
}
}

public static void main(String []args){
Node list = new Node(7);;
Node list2 =  new Node(5);

list.insertAtEnd(1);
list.insertAtEnd(6);

list2.insertAtEnd(9);
list2.insertAtEnd(2);

  Node result = Node.addLists(n1,n2,0);
result.display();
}
 }

Output:
2->1->9

Multiply two number represented as Linked List and return the result as Linked list

Ex :
Input : list = 9->9->9
          list2 = 1->2->3

Output : 1228->7->7

class MultiplyLinkedListNumber{
//Tree
static class Node{
int data;
Node next = null;

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

//Utility to insert new node at the end of given list
public void insertAtEnd(int data){
Node newNode = new Node(data);
Node n = this;
while(n.next != null){
n = n.next;
}
n.next = newNode;
}

//Utility function to print the given list
public void display(){
Node head = this;

while(head != null){
if(head.next !=null)
System.out.print(head.data+"->");
else
System.out.print(head.data);
head = head.next;
}
}
}

//Function to multiply two given lists 
//return resulted list
static Node multiply(Node head, Node head1){
//Base Condition
if(head == null || head1 == null)
return null;

int number = getNumber(head);  //convert one list into number

//traverse the second list and multiply the number with the current element of the list and store in the new list.
Node current = head1; Node result = null;
while(current != null){
if(result == null){
result = new Node(current.data * number);
}else{
                               //multiply current element with the "number" and store in the new list node
Node temp = new Node(current.data * number);  
temp.next = result;
result = temp;
}
current = current.next;  
}
return process(result);
}

//Utility function
static Node process(Node list){
Node head = list;
int carry = 0, i = 0;
//traverse the given list
while(head != null && head.next != null){
i = head.data;
head.data = (carry + i)%10;
carry = (i+carry)/10;
head = head.next;
}
head.data = head.data + carry;
return reverse(list);
}

//Utility function to reverse the given list
//Ex: Input : 1->2->3
//Output : 3->2->1
static Node reverse(Node list){
if(list == null)
return null;

Node current = list, previous = null, forward;
while(current != null){
forward = current.next;
current.next = previous;
previous = current;
current = forward;
}
return previous;
}

//Utility function to convert list into number
//Ex : Input = 1->2->3
//Output = 123
static int getNumber(Node head){
int number = 0;
while(head != null){
number = 10*number + head.data;
head = head.next;
}
return number;
}

public static void main(String... args){
//create the first list
Node list = new Node(9);
list.insertAtEnd(9);
list.insertAtEnd(9);

//create the second list
Node list1 = new Node(1);
list1.insertAtEnd(2);
list1.insertAtEnd(3);

//call the multiply method
Node result = multiply(list, list1);
 
//print the list
result.display();
}
   }

Output : 1228->7->7

Time Complexity : O(N)
Space Complexity : O(1)

Find the kth largest element in a Binary Search Tree

Find the kth largest element in a Binary Search Tree.

Let us consider the below binary search tree:

if k = 2, then 2nd largest element is 6
if k = 4, then 4th largest element is 4

Solution: We traverse the tree in descending order and keep a count of number of nodes visited. When this count is equal to 'k', print the element.

Implementation:

class KthLargestElementInBST{
static class Tree{
int data;
Tree left = null;
Tree right = null;

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

//Utility function to create minimal bst
public static Tree createBST(int []a, int left, int right){
if(right < left)
return null;

int mid = (left + right)/2;
Tree root = new Tree(a[mid]);
root.left = createBST(a, left, mid - 1);
root.right = createBST(a, mid + 1, right);

return root;
}

//method to get the kth largest value in BST
static int index = 0; //Counter variable
public static void getElement(Tree root, int k){
                      //Base condition
if(root == null)
return;

getElement(root.right, k);   //first traverse the right sub tree
if(++index == k){
                              System.out.println(root.data);
return;
                      }
getElement(root.left, k);    //then traverse the left sub tree
}
}

public static void main(String... args){
int []a = {1,2,3,4,5,6,7};
Tree root = Tree.createBST(a, 0, a.length - 1);
           Tree.getElement(root, 2);
}
 }

Output: 6

Reverse Given String Without Using Temporary Variable

Reverse Given String Without Using Temporary Variable.

Example:
Input : hello
Output: olleh

Input : abcd
Output : dcba

Implementation

class ReverseStringWithoutUsingTemporaryVariable{
static String reverse(char []array){
int start = 0;
int end = array.length-1;
while(start < end){
array[start] ^= array[end];
array[end] ^= array[start];
array[start] ^= array[end];
start++; 
end--;
}
return new String(array);
}

static String reverseUtil(String str){
//Boundary Condition
if(str == null || str.length() == 0)
return null;

return reverse(str.toCharArray());
}

public static void main(String... args){
String str = "hello";
String reverse = reverseUtil(str);
System.out.println(reverse);
}
  }

Output: hello

Count the number of 1s in bits of given number

Count he number of 1s in bits of given number.

Example:
Input:  3
Output : 2 (because the binary representation of 3 is 0011, so the number of 1s are 2)

Input : 15
Output : 4 (because the binary representation of 15 is 1111, so the number of 1s are 4)

Implementation

Method 1:

          int setBits(int n){
int count = 0;

while(n > 0){
if( (n&1) == 1)
count++;

n = n >> 1;
}
return count;
         }
         Time Complexity : Theta of logN

Method  2:

          int setBits2(int n){
int count = 0;
while( n > 0){
count++;
n = n&(n-1);
}
return count;
         }
         Time Complexity : O(logN)
         This algorithm goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop. In the worst case, it will pass             once per bit. An integer n has log(n) bits, hence the worst case is O(log(n)).

Cartesian Tree

Given a sequence of numbers, there exists a binary min-heap whose inorder traversal is that sequence. This is known as the Cartesian tree for that sequence.

For more detail, click here

Implementation

class CartesionTree{
static class Tree{
int data;
Tree left = null;
Tree right = null;

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

//cartesian tree
public static Tree createTree(int []a, int left, int right){
if(right < left)
return null;

int min = Integer.MAX_VALUE;
int minIndex = -1;

for(int i = left; i <= right; i++){
if(a[i] < min){
min = a[i];
minIndex = i;
}
}

Tree root = new Tree(a[minIndex]);
root.left = createTree(a, left, minIndex - 1);
root.right = createTree(a, minIndex + 1, right);

return root;
}

//in-order traversal
public static void inorder(Tree root){
if(root != null){
inorder(root.left);
System.out.println(root.data);
inorder(root.right);
}
}
}

public static void main(String []args){
int a[] = {9,3,7,1,8,12,10,20,15,18,5};

Tree root = Tree.createTree(a, 0, a.length - 1);
Tree.inorder(root);
}
}

Check whether a given tree is symmetric with structure wise or not

How will you check whether a given tree is symmetric with structure wise or not.

Ex:
Symmetric (structure wise)
            5
          /   \
         3    9
         \   /
         4  8

 Not symmetric

            5
          /   \
         5     9
        /      /
       3     8

Implementation

class CheckForSymmetricTree{
static class Tree{
int data;
Tree left = null;
Tree right = null;

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

//create minimal bst
public static Tree createBST(int []a, int left, int right){
if(right < left)
return null;

int mid = (left + right)/2;
Tree root = new Tree(a[mid]);
root.left = createBST(a, left, mid - 1);
root.right = createBST(a, mid + 1, right);

return root;
}
}

public static boolean isSymmetric(Tree root){
if(root == null)
return true;

return isSymmetric(root.left, root.right);
}

public static boolean isSymmetric(Tree r1, Tree r2){
if(r1==null && r2==null)
return true;

if(r1==null || r2==null)
return false;

return (isSymmetric(r1.left, r2.right) && isSymmetric(r1.right, r2.left));
}

public static void main(String []args){
int []a = {1,2,3,4,5,6,7};

Tree root = Tree.createBST(a, 0, a.length - 1);

boolean result = isSymmetric(root);

if(result)
System.out.println("Given tree is a symmetric tree");
else
System.out.println("Given tree isn't a symmetric tree");
}

}

Output : Given tree is a symmetric tree