Pyramid Glass Drop

Pyramid Glass Drop

  October 13, 2018    

---

Problem:
We are given a pyramid of glasses , we need to find out how many glasses will fall down if one glass is removed.

Example if we remove 8 then 5 (4,5,2,3,1)glassed will fall down.


Intuition:

If we got to know the row number (in which row we are) then above two connected glasses will fall down
Hence recur for above glasses (but only once ,take 5 as example -> 2,3 ->1).

Idea is to use BFS/DFS.

DFS based solution:

import java.util.*;
import java.lang.*;
import java.io.*;
class solution
 {
   //can be optimized using bSearch
   public static int getRow(int n)
   {
     int row=1;
     while(row*(row+1)/2<n)
     ++row;
     return row;
   }
   public static int deleteBox(int cur,int row,boolean visited[])
   {
     if(cur<=0)
     return 0;
     if(cur==1 || row==1)
     {
       if(!visited[cur])
       {visited[cur]=true;
       return 1;}
     return 0;}
     if(row==0)
     return 1;
     visited[cur]=true;
     if(startOfRow(row,cur))
     {
       int r=getRight(cur,row);
       if(!visited[r])
       return 1+deleteBox(r,row-1,visited);
     }
     else if(endOfRow(row,cur))
     {
       int r=getLeft(cur,row);
       if(!visited[r])
       return 1+deleteBox(r,row-1,visited);
     }
     else
        {  int l=getLeft(cur,row);
          int r=getRight(cur,row);
          int res=0;
          if(!visited[l])
          res= 1+deleteBox(l,row-1,visited);
          if(!visited[r])
          res+= 1+deleteBox(r,row-1,visited);
          return res;}
          return 0;
   }
   public static boolean endOfRow(int n,int cur)
   {
     return n*(n+1)/2==cur;
   }
   public static boolean startOfRow(int n,int cur)
   {
     --n;
     return n*(n+1)/2==cur-1;
   }
   public static int fn(int n,boolean visited[])
   {
     int row=getRow(n);
     return deleteBox(n,row,visited)-1;
   }
   public static int getLeft(int n,int row)
   {
     return n-row;
   }

   public static int getRight(int n,int row)
   {
     return n-row+1;
   }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();;
      boolean visited[]=new boolean[n+1];
    System.out.println(fn(n,visited));
}
}
}

Read More

Word Break 2 solution

Word Break 2 solution

  July 11, 2018    

---

Problem:
make sentence from a sequence of chars from given dictionary.

Idea is to find every matching substring in dictionary try to match rest of substring , if found then print.

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
    static boolean found=false;
     public static boolean dictionary(String a[],String b)
     {
         for(int i=0;i<a.length;++i)
            if(a[i].compareTo(b)==0)
            return true;
            return false;
     }
  public static void fn(String a[],int n,String b,int start,String res)
  {
      int m=b.length();
      if(start>=m)
      return;
      for(int i=start+1;i<=m;++i)
      {
          if(dictionary(a,b.substring(start,i)))
          {
              if(i==m)
              {System.out.print("("+res+b.substring(start,i)+")");
                  found=true;
              }
              else
               {
                   fn(a,n,b,i,res+b.substring(start,i)+" ");
                   
               }
          }
      }
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    found=false;
    int n=ab.nextInt();
    String arr[]=new String[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.next();
    fn(arr,n,ab.next(),0,"");
    if(!found)
    System.out.print("Empty");
    System.out.println();
}
}
}

Read More

Count no. of subset having sum k

Count no. of subset having sum k

  May 26, 2018    

---

it is same like subset sum problem
We have modified that approach by having int value

Code memoized:

public static int fn(int a[],int i,int n,int sum,int memo[][])
  {
      if(sum<0)
      return 0;
      if(memo[i][sum]!=0)
      return memo[i][sum];
      if(sum==0) 
        {
            return memo[i][sum]=1;}
      if(i==n ) return 0;
      int s=1;
            return memo[i][sum]=fn(a,i+1,n,sum,memo)+fn(a,i+1,n,sum-a[i],memo);
      
  }
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();
    int k=ab.nextInt();
    int memo[][]=new int[n+1][k+1];
    System.out.println(fn(arr,0,n,k,memo));
}

}

Code DP:

  public static int fn(int a[],int n,int sum)
  {
     int dp[][]=new int[n+1][sum+1]; // denotes no. of subset till n having sum=sum
     for(int i=0;i<=n;++i)
     dp[i][0]=1;
     for(int i=1;i<=n;++i)
     {
         for(int j=1;j<=sum;++j)
         {
             dp[i][j]=dp[i-1][j];//do not include 
             if(a[i-1]<=j)
             dp[i][j]+=dp[i-1][j-a[i-1]]; // include sum
         }
     }
     return dp[n][sum];
  }
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();
    int k=ab.nextInt();
    int memo[][]=new int[n+1][k+1];
    System.out.println(fn(arr,n,k));
}
}
}

Read More

sum of leaf nodes tree

sum of leaf nodes tree

  January 03, 2018    

---

int sumLeaf(Node* root)
{
    if(root==NULL)
    return 0;
    if(root->left==NULL && root->right==NULL)
    return root->data;
    return sumLeaf(root->left)+sumLeaf(root->right);
}

Read More

Count Non Leaf Node Tree

Count Non Leaf Node Tree

  January 03, 2018    

---

int countNonLeafNodes(Node* root)
{
    int c=1;
    if(root==NULL || (root->left==NULL && root->right==NULL))
    return 0;
    c+=countNonLeafNodes(root->left);
    c+=countNonLeafNodes(root->right);
    return c;
}

Read More

Distinct Occurrence of a string

Distinct Occurrence of a string

  December 31, 2017    

---

Code:

class dmg
{
int count(String a,String b,int i,int j,int l1,int l2)
{
if(j==l2)
return 0;
int c=0;
while(i<l1 && (l1-i)>=(l2-j))
{
if(a.charAt(i)==b.charAt(j))
{
if(j==l2-1)
++c;
else
c+=count(a,b,i+1,j+1,l1,l2);
}
++i;
}
return c;
}
    int subsequenceCount(String S, String T)
    {
return count(S,T,0,0,S.length(),T.length());
    }
}

Read More

Root to leaf path sum

Root to leaf path sum

  September 08, 2017    

---

Problem:

You are given root of tree and sum k,
Find if k==sum of path from root to leaf

Code:

 boolean isLeaf(Node node)
    {
        if(node.left==null && node.right==null)
        return true;
        return false;
    }
    boolean hasPathSum(Node node, int sum)
    {
        if(node==null || sum<0)
        return false;
        if(sum==node.data && isLeaf(node))
        return true;
       return  hasPathSum(node.left,sum-node.data) || hasPathSum(node.right,sum-node.data);
    }

Read More

Pattern till N

Pattern till N

  August 03, 2017    

---

Problem :

Print a sequence of numbers starting with N, without using loop, in which  A[i+1] = A[i] - 5,  if  A[i]>0, else A[i+1]=A[i] + 5  repeat it until A[i]=N.

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class hackerranksolutionc
 {
     public static void show(int n,int cur,Stack<Integer> st)
     {
         if(cur<=0)
        {
             st.push(cur);
            return;}
         st.push(cur);
         System.out.print(cur+" ");
         show(n,cur-5,st);
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   int n=ab.nextInt();
   Stack<Integer> st=new Stack<Integer>();
   show(n,n,st);
   while(st.size()>0)
   System.out.print(st.pop()+" ");
    System.out.println();
}
}
}

Read More

Print all possible string formed from keys

Print all possible string formed from keys

  August 03, 2017    

---

Like old phone , alphabets were assigned to a number , print all possible string from those number'


Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
// static in=5;
    static String hashTable[] = {"", "", "abc", "def", "ghi", "jkl","mno", "pqrs", "tuv", "wxyz"};
public static void show(int arr[],StringBuffer Output,int cur,int n)
{
   if(cur>=n)
   {
       System.out.print(Output+" ");
       return;}
   else
   {
// loop of key 1 with all alphabets recursively
       for(int i=0;i<hashTable[arr[cur]].length();i++)
       {
           if(Output.length()>cur)
           Output.setCharAt(cur,hashTable[arr[cur]].charAt(i));
           else
           Output.append(hashTable[arr[cur]].charAt(i));
           show(arr,Output,cur+1,n);// go for next key 
       }
   }
}
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();
   StringBuffer g=new StringBuffer();
   show(arr,g,0,n);
   System.out.println();
}
}
}

Read More

DFS Graph

DFS Graph

  July 26, 2017    

---

Problem ;

Print Depth first traversal of graph

Solution:

It is similar to tree except it may have cycle so we need to check whether node has been already visited.

Set iterator through linked list having details of connected vertices and check if it is  not visited then recur and print , do till all nodes are visited


Code;

  public void DFS(int v,LinkedList<Integer> adj[],boolean visited[])
    {
      visited[v]=true;
          System.out.print(v+" ");
      Iterator<Integer> itr=adj[v].iterator();
      while(itr.hasNext())
      {
          int item=itr.next();
          if(!visited[item])
          {
          DFS(item,adj,visited);
          }
      }
    }

Read More

Check if Linked List is Palindrome Geeks solution

Check if Linked List is Palindrome Geeks solution

  July 22, 2017    

---

Problem :

write a function which returns true if the given list is palindrome, else returns false.

Ex : 
A list having data
1 2 3 2 1 is palindrome 

Idea 

STL of linkedlist is being created by traversing each node.
Call function which removes first and last element of LL and check whether they are equal or not.

Code:

/* Structure of class Node is
class Node
{
int data;
Node next;

Node(int d)
{
data = d;
next = null;
}
}*/
class hackerranksolutionc
{
    boolean isPalindrome(Node head) 
    {
        int count=0;
        LinkedList<Integer> q=new LinkedList<Integer>();
        while(head!=null)
        {
            q.add(head.data);
            head=head.next;
            count++;
        }
        while(q.size()>1)
        {
            if(q.removeFirst()!=q.removeLast())
            return false;
        }
        return true;
    }    

}

Code using recursion (More Optimized)

boolean isPalindromeUtil(Node right) 
    {
        left = head;
         
        /* stop recursion when you are at last node */
        if (right == null)
            return true;

        /* If sub-list is not palindrome then no need to
           check for current left and right, return false */
        boolean isp = isPalindromeUtil(right.next);
        if (isp == false)
            return false;

        /* Check values at current left and right */
        boolean isp1 = (right.data == left.data);

        /* Move left to next node */
        left = left.next;

        return isp1;
    }

Read More

Print Common Nodes in BST Geeks solution

Print Common Nodes in BST Geeks solution

  July 22, 2017    

---

Problem :
 Given two Binary Search Trees, task is to complete the function printCommon, which print's the common nodes in them. In other words, find intersection of two BSTs.

Solution : FInd inorder of both trees and save them in 2 arraylist and check with a loop for common elements

Code:



/*Complete the function below
Node is as follows:
class Node{
int data;
Node left,right;
Node (int d){
data=d;
left=right=null;
}
}
*/
class hackerranksolutionc
{
    List<Integer> arr=new ArrayList<Integer>();
    List<Integer>arr2=new ArrayList<Integer>();
    public void inorder(Node root,boolean flag)
    {
        if(root==null)
        return;
        if(flag)
        arr.add(root.data);
        else
        arr2.add(root.data);
        inorder(root.left,flag);
        inorder(root.right,flag);
       
    }
public void printCommon(Node root1,Node root2)
         {
         inorder(root1,false);
         inorder(root2,true);
         Collections.sort(arr2);
         for(int i=0;i<arr2.size();i++)
         {
             if(arr.contains(arr2.get(i)))
             System.out.print(arr2.get(i)+" ");
         }
         }
}

Read More

Permutations of a given string geeks solution java

Permutations of a given string geeks solution java

  July 22, 2017    

---

Problem : Print all the permutations (string can be made by swapping their value)

Idea was to use backtrack , here we will swap the values and recur for the new string and again backtrack to original string for the function and recur for that string.


Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
    private static List<String> arr=new ArrayList<String>();
     public static void swap(StringBuffer str,int i,int j)
     {
         char tmep=str.charAt(i);
         char te=str.charAt(j);
         str.setCharAt(i,te);
         str.setCharAt(j,tmep);
     }
     public static void permute(StringBuffer str,int f,int n)
     {
         if(f==n)
         arr.add(String.valueOf(str));
         else{
         for(int i=f;i<=n;i++)
         {
             swap(str,f,i);
             permute(str,f+1,n);
             swap(str,f,i);
         }}
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   StringBuffer str=new StringBuffer(ab.next());
   arr.clear();
   permute(str,0,str.length()-1);
  Collections.sort(arr);
   while(arr.size()!=0)
   System.out.print(arr.remove(0)+" ");
   System.out.println();
}
}
}

Read More

print all possible string geeks solution

print all possible string geeks solution

  July 21, 2017    

---

Problem: input : abc

process like :
               abc
                ab c
                a bc
                a b c

Code:


/*You have to complete this function*/
class GfG
{
    void print(String str,char temp[],int i,int j,int n)
    {
        if(i==n)
        {
            temp[j]='$';
            for(int p=0;p<=j;p++)
            System.out.print(temp[p]);
            return;
        }
        temp[j]=str.charAt(i);
        print(str,temp,i+1,j+1,n);
        temp[j]=' ';
         temp[j+1]=str.charAt(i);
        print(str,temp,i+1,j+2,n);
    }
    void printSpace(String str)
    {
        // Your code here
        char temp[]=new char[str.length()*2];
        temp[0]=str.charAt(0);
        print(str,temp,1,1,str.length());
    }
}

Read More

Flood Fill Algorithm Geeks

Flood Fill Algorithm Geeks

  July 19, 2017    

---

Problem:
Given a 2D screen, location of a pixel in the screen ie(x,y) and a color(K), your task is to replace color of the given pixel and all adjacent same colored pixels with the given color K.

Idea is to recursively track all the vertices adjacent to the current vertex.

Code:
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
     private static int m,n;
     public static void change(int graph[][],int x,int y,int k,int old)
     {
         if(x<0 || y>=n || x>=m || y<0)
         return;
         if(graph[x][y]!=old)
         return;
            graph[x][y]=k;
            change(graph,x+1,y,k,old);
            change(graph,x-1,y,k,old);
            change(graph,x,y+1,k,old);
            change(graph,x,y-1,k,old);
       
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    m=ab.nextInt();
    n=ab.nextInt();
   int graph[][]=new int[m][n];
   for(int i=0;i<m;i++)
   for(int j=0;j<n;j++)
   graph[i][j]=ab.nextInt();
   int x=ab.nextInt();
   int y=ab.nextInt();
   change(graph,x,y,ab.nextInt(),graph[x][y]);
    for(int i=0;i<m;i++)
   for(int j=0;j<n;j++)
   System.out.print(graph[i][j]+" ");
   System.out.println();
}
}
}

Read More

Next Permutation Java

Next Permutation Java

  July 13, 2017    

---

Idea was to fix a character at a index by swap and call recursively until all the permutation found i,e when last element is also fixed.

Code:
import java.util.*;
class nextpermutation
{
public static void swap(StringBuffer str,int i,int j)
{
char l=str.charAt(i);
char k=str.charAt(j);
str.setCharAt(i,k);
str.setCharAt(j,l);
}
public static void permute(StringBuffer str,int l,int r)
{
if(l==r)
System.out.println(str);
else
{
for(int i=l;i<=r;i++)
{
swap(str,l,i);
permute(str,l+1,r);
swap(str,l,i); // bring string back to original position
}
}
}
public static void main(String args[])
{
StringBuffer str=new StringBuffer("abc");
permute(str,0,str.length()-1);
}
}

Reference : http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

Read More

Print all possible strings

Print all possible strings

  June 22, 2017    

---

Ex:
                abc
                ab c
                a bc
                a b c

/*You have to complete this function*/
class GfG
{
    void print(String str,char temp[],int i,int j,int n)
    {
        if(i==n)
        {
            temp[j]='\0';
            System.out.print(temp);
             System.out.print("$");
            return;
        }
        temp[j]=str.charAt(i);
        print(str,temp,i+1,j+1,n);
        temp[j]=' ';
        temp[j+1]=str.charAt(i);
        print(str,temp,i+1,j+2,n);
    }
    void printSpace(String str)
    {
        char temp[]=new char[str.length()*2];
        temp[0]=str.charAt(0);
        print(str,temp,1,1,str.length());
    }
}

Read More

Recursively remove all adjacent duplicates geeks solution java

Recursively remove all adjacent duplicates geeks solution java

  June 22, 2017    

---

problem : 
remove all adjacent duplicates in a string


Input
2
grrrrrrrrrrrrrgr
acbbcddeeffggfc


output:
r
afc


Code:
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
     public static void check(String str)
     {
         if(str.length()<=1)
         {
             System.out.println(str);
             return;
         }
       //  System.out.println(str);
         String n=new String();
         int count=0;
         for(int i=0;i<str.length();i++)
         {
             while(i<str.length()-1 && str.charAt(i)==str.charAt(i+1))
             {
                 if(i<str.length()-2 &&str.charAt(i)!=str.charAt(i+2))
                 i+=2;
                 else
                 i++;
                 count++;
             }
             if(i!=str.length()-1)
             n=n+str.charAt(i);
             else
             {if(i==str.length()-1 && str.charAt(i)!=str.charAt(i-1))
                 n=n+str.charAt(i);
             }
         }
         if(count>0)
         check(n);
         else
         System.out.println(n);
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   String str=ab.next();
   check(str);
  // System.out.println();
}
}
}

Read More

Sort a stack

Sort a stack

  June 22, 2017    

---

class stacksort{
    public void insert(Stack<Integer> s,int x)
    {
        if(s.isEmpty() || x>s.peek())
        {
            s.push(x);
            return;
        }
        int temp=s.pop();
        insert(s,x);
        s.push(temp);
    }
public Stack<Integer> sort(Stack<Integer> s)
{
        if(!s.isEmpty())
        {
            int x=s.pop();
            sort(s);
            insert(s,x);
           
        }
        return s;
}
}

Read More

Recursive sequence Geeks solution

Recursive sequence Geeks solution

  June 21, 2017    

---

Problem: F(n)= (1) +(2*3) + (4*5*6) ... n.
find F(n)


import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
     public static void check(int n,long sum,int time,int number)
     {
         long sum2=1;
         if(n==1)
         System.out.println("1");
         else if(n==time-1)
         System.out.println(sum);
         else
         {
         for(int i=0;i<time;i++)
         {
             sum2*=number++;
         }
       
       check(n,sum+sum2,++time,number)  ;
     }
       
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   check(ab.nextInt(),1,2,2);
}
}
}

Read More