Greatest on right side

Greatest on right side

  October 27, 2017    

---

Idea is to use maxHeap 
Pop ith position element.
peek for biggest element

Code:
public static void greatestOnRight(int arr[],int n)
{
PriorityQueue<Integer> q=new PriorityQueue<Integer>(Collections.reverseOrder());
for(int x:arr)
q.offer(x);
int i=0;
while(i<n-1 && !q.isEmpty())
{
q.remove(arr[i++]);
System.out.print(q.peek()+" ");
}
}
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    greatestOnRight(arr,n);
    System.out.println("-1");
}
}

Read More

MaxHeap Implementation in java

MaxHeap Implementation in java

  May 30, 2017    

---

As we know maxheap has highest element as root and have smaller elements as children (Separate MaxHeap)
Here i will tell how maxheap can be implemented by Array

Code and Explanation in comments:

import java.util.*;
class maxheap
{
public int heap[];
public static final int front=0;
public int size;
maxheap(int max_size)
{
this.heap[]=new int[max_size];
this.size=-1;
}
int getparent(int n)
{
return n/2;
}
int lchild(int n)
{
return 2*n;
}
int rchild(int n)
{
return 2*n+1;
}
public void swap(int pos1,int pos2)
{
int temp=heap[pos1];
heap[pos1]=heap[pos2];
heap[pos2]=temp;
}

//during insertion we will insert item in array and check whether parent is less than current item if so swap and repeat until item is not less
public void insert(int item)
{
heap[++size]=item;
int temp=size;
while(heap[getparent(temp) < heap[temp] )
{
swap(getparent(temp),size);
temp=getparent(temp);

}

}
//deletion is performed at the root and last node value becomes root and then again it is heapify so that it can hold maxheap property

public int delete(int pos)
{
int data=heap[0];
heap[0]=heap[size--];
heapify(0);
return data;
}
//it will work until node is leaf ,it will check whether the given position is less than child notes if so then swap
public void heapify(int pos)
{
if(leaf(pos))
return;
if(heap[pos]<heap[lchild(pos)])
{
swap(pos,lchild(pos);
heapify(lchild(pos));
}
if(heap[pos]<heap[rchild(pos)])
{
swap(pos,rchild(pos));
heapify(rchild(pos));
}
}
}

Read More

Median By Heap

Median By Heap

  May 25, 2017    

---

Problem ; Running Median
Problem : Find median in a stream

Solution :

Here we are using two heaps (Max ,min ) such that we will create two part of the numbers and numbers less than median stored in one heap and rest into another.

Methods :

First add numbers to heap 

Then Re balance heap structure

Store median for each value in array and return to main function.

Method 1:check if max heap is empty or number is smaller than max heap top then push into max heap else into min heap. (Here naming is little bit change from min to mix and vice versa).

Method 2: Re balance:check for smaller and bigger heap and check if length is 2 then switch element from bigger to smaller .Length won't be greater than 2 here.

method 3 : getmedian
here we will check if length of both the heaps and equal then return sum of both top/2elsereturn top of maximum number.

Code: 

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class median {

    public static void addnumber(int n,PriorityQueue<Integer> minheap,PriorityQueue<Integer> maxheap)

        {

        if(minheap.size()==0 || n<minheap.peek())

            minheap.offer(n);

        else

           maxheap.offer(n);

    }

    public static void rebalance(PriorityQueue<Integer> minheap,PriorityQueue<Integer> maxheap)

        {

        PriorityQueue<Integer> biggerheap=minheap.size()>maxheap.size()?minheap:maxheap;

        PriorityQueue<Integer> smallerheap=minheap.size()>maxheap.size()?maxheap:minheap;

        if(biggerheap.size()-smallerheap.size()>=2)

            {

            smallerheap.add(biggerheap.poll());

        }

    }

    public static double getMedian(PriorityQueue<Integer> minheap,PriorityQueue<Integer> maxheap)

        {

         PriorityQueue<Integer> biggerheap=minheap.size()>maxheap.size()?minheap:maxheap;

        PriorityQueue<Integer> smallerheap=minheap.size()>maxheap.size()?maxheap:minheap;

       if(biggerheap.size()==smallerheap.size())

           return((double)(biggerheap.peek()+smallerheap.peek()))/2;

                  else

                  return (biggerheap.peek());

    }

    public static double[] getmedian(int[] arr)

        {

        PriorityQueue<Integer> minheap=new PriorityQueue<Integer>(Collections.reverseOrder());

        PriorityQueue<Integer> maxheap=new PriorityQueue<Integer>();

        double median[]=new double[arr.length];

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

            {

            addnumber(arr[i],minheap,maxheap);

            rebalance(minheap,maxheap);

            median[i]=getMedian(minheap,maxheap);

        }

        return median;

    }

    public static void main(String args[] ) throws Exception {

        Scanner ab=new Scanner(System.in);

        int n=ab.nextInt();

        int arr[]=new int[n];

        int i=0;

        while(i<n){

            arr[i++]=ab.nextInt();

        }

        double res[]=getmedian(arr);

        for(double c:res)

            System.out.println(c);

        

    }

}

Read More

Use PriorityQueue for Maxheap

Use PriorityQueue for Maxheap

  May 25, 2017    

---

PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(
            new Comparator<Integer> () {
                public int compare(Integer a, Integer b) {
                return b - a;
            }
        });

Or

private static PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

Here we are comparing two integers using comparator to change the storing mechanism

Read More

Jesse and Cookies Solution

Jesse and Cookies Solution

  May 24, 2017    

---

Problem:

Given k you need to have elements greater than k 

if a element is less than k perform :

( Least no+2* 2nd least number).

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        PriorityQueue<Integer> heap=new PriorityQueue<Integer>();
        Scanner ab=new Scanner(System.in);
        int n=ab.nextInt();
        int k=ab.nextInt();
        int count=0;
         
            while(ab.hasNext())
            {
            heap.offer(ab.nextInt());
        }
        while(true)
            {
            if(heap.peek()<k)
                {
                count++;
                int temp=heap.poll();
                if(heap.size()<=0)
                    {
                    System.out.println("-1");
                    System.exit(0);
                }
                int temp2=heap.poll();
                heap.offer((temp+(2*temp2)));
            }
            else
                break;
        }
        System.out.println(count);
    }
}

Read More

QHEAP1 Hackerrank Solution

QHEAP1 Hackerrank Solution

  May 24, 2017    

---

Problem :
1: Add element k when 1 pressed
2: delete element K
3: Print minimum element

Solution:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        PriorityQueue<Integer> heap=new PriorityQueue<Integer>(); // implementing heap variable
        Scanner ab=new Scanner(System.in);
        int n=ab.nextInt();
        while(n-->0)
            {
            int k=ab.nextInt();
             int data;
            switch(k)
                {
                case 1:
                 data=ab.nextInt();
                heap.offer(data); // add data
                break;
                case 2:
                 data=ab.nextInt();
                heap.remove(data);
                break;
                case 3:
                System.out.println(heap.peek());
                break;
            }
        }
    }
}

Read More