Phone directory geeks solution

Phone directory geeks solution

  September 08, 2018    

---

Problem:
As we see in our phone contact book when we type name of person it shows suggestions for every character typed by us in that name

Idea is to use TRIE.
Loop for every substring starting from 0 to 1..n
Search suggestions for that substring

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class trie
{
  HashMap<Character,trie> child;;
  boolean isEnd;
  trie()
  {
    isEnd=false;
    child=new HashMap<>();
  }
  void add(String a,trie root)
  {
  trie cur=root;
  for (int i=0;i<a.length() ;++i ) {
    if(cur.child.containsKey(a.charAt(i)))
    cur=cur.child.get(a.charAt(i));
    else
    {cur.child.put(a.charAt(i),new trie());
      cur=cur.child.get(a.charAt(i));
    }
  }
  cur.isEnd=true;
  }
   void search(String a,trie root)
   {
     trie cur=root;
     for (int i=0; i<a.length();++i ) {
       char t=a.charAt(i);
       trie node=cur.child.get(t);
       if(node==null)
       {System.out.print("0");
     return;}

     cur=node;
     }
     print(cur,a);
   }
   void print(trie root,String prefix)
   {
       if(root.isEnd)
       {System.out.print(prefix+" ");
       }
     for(char i='a';i<='z';++i)
     {
       trie node=root.child.get(i);
       
       if(node!=null)
       print(node,prefix+i);
     }
   }
}
class phoneDict
 {
  static trie root;
  public static void fn(String a[],int n,String q)
  {
    for (String t :a ) {
      root.add(t,root);
    }
    for(int i=1;i<=q.length();++i)
    {root.search(q.substring(0,i),root);
      System.out.println();
    }
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    root=new trie();
    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());
    //System.out.println();
}
}
}

Read More

Lazy Pasha String Rotation

Lazy Pasha String Rotation

  July 12, 2018    

---

Problem:
Rotate Array k times left and print char at index j

One of the approach is to rotate and print output at index j
Time :O(n) Rotation * O(q) query

Another One:

If we got to know the index at which new rotated string will be started then it will only take O(q) time.
As per observation

if(index==-1)
        index=(n-desired);
        else
        index=((n-desired)-(n-index)+n)%n;


Implementation 

import java.util.*;
import java.lang.*;
import java.io.*;
class ArrayLeftRoatateN
 {
  public static void fn(char a[],int n,Scanner ab,int q)
  {
    int index=-1;
    while(q-->0)
    {
      int type=ab.nextInt();
      int desired=ab.nextInt()%n;
      if(type==1)
      {
        if(index==-1)
        index=(n-desired);
        else
        index=((n-desired)-(n-index)+n)%n;
      }
      else
      System.out.println(a[(index+desired)%n]);
    }
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int q=ab.nextInt();
      fn(ab.next().toCharArray(),n,ab,q);
    System.out.println();
}
}
}

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

Length of longest AP sequence

Length of longest AP sequence

  June 17, 2018    

---

We are given an sorted array , now we need to find longest subseqence forming A.P.
Idea is to look for every gap but it will take more time to perform that.

So we are going to fix middle element and find two element such that these 3 elements  form A.P.
This find can be done using sliding window concept
and if any sequence found then we can say that from start to fix subseqence AP=fix to k subsequence AP+1.

Base case:
if elements are >=2 then ap will be atleast of 2 size.

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class longestAP
 {
  public static int fn(int a[],int n)
  {
    if(n<=2) return n;
    int dp[][]=new int[n][n];
    int res=2;
    for (int i = 0; i < n; i++)
           dp[i][n - 1] = 2;
   //fixing jth pointer and looking both side for AP pair having a[i]+a[k]==2*a[j]
    for(int j=n-2;j>=1;--j)
    {
      int i=j-1,k=j+1;
      while(i>=0 && k<n)
      {
        if(a[i]+a[k]==2*a[j])
        {
          dp[i][j]=dp[j][k]+1;
          res=Math.max(res,dp[i][j]);
          --i;
          ++k;
        }
        else
        {
         dp[i][j]=Math.max(dp[i][j],2);
          if(a[i]+a[k]<2*a[j])
          ++k;
          else
          --i;
        }
      }
      while (i >= 0)
           {
               dp[i][j] = 2;
               i--;
           }
    }
    return res;
  }
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();
    System.out.println(fn(arr,n));
}
}
}

Time : O(n^2)

Read More

max of all min for every window size

max of all min for every window size

  May 25, 2018    

---

Problem:
for every window size you have to find maximum value 

idea is to find previous smaller and next smaller element 
this element is minimum for nextSmaller[i]-prevSmaller[i]-1 
Find all maximum


Code will comment:

import java.util.*;
import java.lang.*;
import java.io.*;
class maxofMinForEverywindow
 {
   public static void prevSmallerIndex(int a[],int j[],int n)
   {
     Stack<Integer> s=new Stack<Integer>();
     s.push(n-1);
     for(int i=n-2;i>=0;--i)
     {
       while(!s.isEmpty() && a[s.peek()]>a[i])
       {
         int k=s.pop();
         j[k]=i;
       }
          s.push(i);
     }
     while(!s.isEmpty())
     {
       int k=s.pop();
       j[k]=-1;
     }
   }
   public static void nextSmallerIndex(int a[],int j[],int n)
   {
     Stack<Integer> s=new Stack<Integer>();
     s.push(0);
     for(int i=1;i<n;i++)
     {
         while(!s.isEmpty() && a[s.peek()]>a[i])
         {
           int k=s.pop();
           j[k]=i;
         }
            s.push(i);
     }
     while(!s.isEmpty())
     {
       int k=s.pop();
       j[k]=n;
     }
   }
  public static void fn(int a[],int n)
  {
    int nextSmaller[]=new int[n];
    int prevSmaller[]=new int[n];
    nextSmallerIndex(a,nextSmaller,n);
    prevSmallerIndex(a,prevSmaller,n);
    /*
    for(int x:prevSmaller)
    System.out.print(x+" "); */
    //Now we know that a[i] is minimum in window from prevSmaller to nextSmaller
    //find max for the same size of window and store them in array
    int res[]=new int[n+1]; // it holds max of min value for window size n
    for(int i=0;i<n;++i)
    {
      int t=nextSmaller[i]-prevSmaller[i]-1;
     res[t]=Math.max(res[t],a[i]);
    }
    // now we will be having result but some values are missing
    //as per observation res[i] will be greater than or equal to res[i+1..n]
    //fill values
    for(int i=n-1;i>=1;--i)
    {
      res[i]=Math.max(res[i],res[i+1]);
    }
    for(int i=1;i<=n;++i)
    System.out.print(res[i]+" ");
  }
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();
      fn(arr,n);
    System.out.println();
}
}
}

Read More

Maximum Index Geeks Solution

Maximum Index Geeks Solution

  February 12, 2018    

---

Problem:
Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j]

Idea is to use stack and push in decresing order.
Pop index until stack element is less than current element


import java.util.*;
import java.lang.*;
import java.io.*;
class dmg
 {
public static int maxIndexDiff(int arr[],int n)
{
Stack<Integer> stk=new Stack<Integer>();
for(int i=0;i<n;++i)
{
if(stk.isEmpty() || arr[i]<arr[stk.peek()])
stk.push(i);
}
int res=-1;
for(int i=n-1;i>=0;--i)
{
while(!stk.isEmpty() && arr[i]>=arr[stk.peek()])
res=Math.max(res,i-stk.pop());
//remove all values which have processed i.e. index that has been used
while(!stk.isEmpty() && i<stk.peek())
stk.pop();
}
return res;
}
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();
    System.out.println(maxIndexDiff(arr,n));
}
}
}

Read More

Largest Rectangle with 1's with swapping column

Largest Rectangle with 1's with swapping column

  October 15, 2017    

---

Idea is to first find max continuous 1's 

Sort that stored matrix.

Now mattrix is sorted so area (Max) can be found by (col+1){as col started from 0} * value at that index


Code:


import java.util.*;
import java.lang.*;
import java.io.*;
class hackerranksolutionc
 {
public static int maxArea(int arr[][],int r,int c)
{
Integer dp[][]=new Integer[r+1][c+1];
for(int i=0;i<c;++i)
{
dp[0][i]=arr[0][i];
for(int j=1;j<r;++j)
{
dp[j][i]=(arr[j][i]==0)?0:dp[j-1][i]+1;
}
}
for (int i=0; i<r; i++)
    {
        int count[] = new int[r+1];

        // counting occurrence
        for (int j=0; j<c; j++)
            count[dp[i][j]]++;

        //  Traverse the count array from right side
        int col_no = 0;
        for (int j=r; j>=0; j--)
        {
            if (count[j] > 0)
            {
                for (int k=0; k<count[j]; k++)
                {
                    dp[i][col_no] = j;
                    col_no++;
                }
            }
        }
    }
int cur=0,max=0;
for(int i=0;i<r;++i)
{
for(int j=0;j<c;++j)
{
//as matrix is stored in form of consecutive 1's,after sorting we will get area by this frmula
cur=(j+1)*dp[i][j];
if(cur>max)
max=cur;
}
}
return max;
}
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int r=ab.nextInt();
    int c=ab.nextInt();
    int arr[][]=new int[r][c];
    for(int i=0;i<r;++i)
for(int j=0;j<c;++j)
{
arr[i][j]=ab.nextInt();
}
    System.out.println(maxArea(arr,r,c));
}
}
}

Read More

Count Palindrome Sub-Strings of a String

Count Palindrome Sub-Strings of a String

  October 15, 2017    

---

Idea is to use DP.

First mark all single length and length two substring of same char TRUE.

and start a loop for gap > 2 and find if chars are equal and in that gap and check if inner substring within this gap is also palindrome by checking value in DP , if so then increment count by 1 and both neighbor substring and exclude common substring.

Code:

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

Read More

Check Mirror in Array tree

Check Mirror in Array tree

  October 05, 2017    

---

Idea is to use Stack and Queue .
for 1 tree use stack and for another use queue .

When we compare with the node of both the tree they will be same as per the structure of q and stack.


Code:

public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    boolean flag=true;
    int e=ab.nextInt();
    Map<Integer,String> map=new HashMap<Integer,String>();
    Map<Integer,String> map1=new HashMap<Integer,String>();
    boolean visited[]=new boolean[n+1];
    for(int i=0;i<e;i++)
   {
       int val=ab.nextInt();
       if(map.containsKey(val))
       {
           String str=map.get(val);
           map.put(val,str+ab.nextInt());
       }
       else
       {
           String str=new String(String.valueOf(ab.nextInt()));
           map.put(val,str);}
       }
    for(int i=0;i<e;i++)
   {
       int val=ab.nextInt();
       if(map1.containsKey(val))
       {
           String str=map1.get(val);
           map1.put(val,String.valueOf(ab.nextInt())+str);
         //  System.out.println(String.valueOf(ab.nextInt())+" "+str);
       }
       else
       {
           String str=new String(String.valueOf(ab.nextInt()));
           // System.out.println(str);
           map1.put(val,str);}
       }
      /*  for(Map.Entry<Integer,String> m:map1.entrySet())
       {
          System.out.println(m.getKey()+" "+m.getValue());
       }*/
       for(Map.Entry<Integer,String> m:map.entrySet())
       {
           int key=m.getKey();
           visited[key]=true;
           String str=new String(m.getValue());
          // System.out.println(m.getKey()+" "+m.getValue());
           if(!map1.containsKey(key))
           {
             //  System.out.println("no key");
               flag=false;
               break;
           }
           if(!str.equals(map1.get(key)))
           {
              // System.out.println(str+" no match "+map1.get(key));
               flag=false;
               break;
           }
           
       }
       for(Map.Entry<Integer,String> m:map1.entrySet())
       {
           if(!visited[m.getKey()])
           {
               flag=false;
               break;
           }
       }
       System.out.println((flag)?"1":"0");
}
}

Read More

Tree from Post and Inorder

Tree from Post and Inorder

  October 05, 2017    

---

Idea is to break into subproblem :

as we know last node will be root so create that node and recur for left and right subtree by getting position of that element in Inorder array.



Code:

       int index;
int search(int arr[],int start,int end,int x)
{
    int i;
    for(i=start;i<=end;++i)
    {
        if(x==arr[i])
        break;
    }
    return i;
}
Node makeTree(int in[],int post[],int start,int end)
{
    if(start>end)
    return null;
    Node n=new Node(post[index]);
    --index;
          // if no subtree is there
    if(start==end)
    return n;
    int loc=search(in,start,end,n.data);
    n.right=makeTree(in,post,1+loc,end);
    n.left=makeTree(in,post,start,loc-1);
    return n;
}
        Node buildTree(int in[], int post[], int n)
{
           index=n-1;
          return  makeTree(in,post,0,n-1);
}

Read More

Longest Span with same Sum in two Binary arrays

Longest Span with same Sum in two Binary arrays

  September 24, 2017    

---

Explanation :

Here we are having difference from -n to n so there are 2n+1 possibility of diff.
We are having 2 cases :

1: if index 0 to n is maxLength 
2: any subarray having maxLength

For this we are maintaining a diff array and checking if sum in both array is equal then change maxLength

Ref:
http://practice.geeksforgeeks.org/problems/longest-span-with-same-sum-in-two-binary-arrays/0

Code:
     public static int longestSpan(int arr[],int n,int arr2[])
     {
         int diff[]=new int[2*n+1];
         int maxLen=0,pre1=0,pre2=0;
         Arrays.fill(diff,-1);
         for(int i=0;i<n;++i)
         {
             pre1+=arr[i];
             pre2+=arr2[i];
             int cdiff=pre1-pre2;
//index finded by adding n as max neg val is -n
             int diffindex=n+cdiff;
//from 0 to i
             if(cdiff==0)
             {
                 maxLen=i+1;
             }
             else if(diff[diffindex]==-1)
             {
              diff[diffindex]=i;   
             }
             else
             {
                 maxLen=Math.max(maxLen,i-diff[diffindex]);
             }
         }
         return maxLen;
     }

Read More

Check if Array Represents preorder of BST

Check if Array Represents preorder of BST

  September 14, 2017    

---

Explanation:

Here we will use stack.
Initialize root with min value.

Loop from 1 to arr.length
check if arr[i]<root it means it is voilating property
Pop all the elements from stack who are lesser than arr[i]
Finally push arr[i]


Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class hackerranksolutionc
 {
     public static boolean isBst(int arr[],int n)
     {
         Deque<Integer> q=new ArrayDeque<Integer>();
        // q.add(Integer.MIN_VALUE);
         int i=0;
         int root=Integer.MIN_VALUE;
         for(i=0;i<n;++i)
         {
            if(arr[i]<root)
            return false;
            while(!q.isEmpty() && q.peekFirst()<arr[i])
            {
                root=q.removeFirst();
            }
            q.addFirst(arr[i]);
            
         }
         return true;
     }
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();
   System.out.println(isBst(arr,n)?1:0);
}
}
}

Ref

http://www.geeksforgeeks.org/check-if-a-given-array-can-represent-preorder-traversal-of-binary-search-tree/

Read More

Morris Inorder Traversal

Morris Inorder Traversal

  September 12, 2017    

---

It will take O(1) extra space

Code with comments :

void morrisInorder(Node root)
{
if(root==null)
return;

Node curr=root;
while(curr!=null)
{
//tree has no left subtree so move to right
if(curr.left==null)
{
System.out.print(curr.data);
curr=curr.right;
}
else
{
//find preorder suceesor to link with its root
Node pre=curr.left;
while(pre.right!=null || pre.right==curr)
pre=pre.right;
//we have already traversed this tree so remove link and move to right subtree
if(pre.right==curr)
{
pre.right=null;
System.out.print(curr.data);
curr=curr.right;
}
else {
//link child's right
pre.right=curr;
curr=curr.left;
}
}
}
}

Read More

Coin Change DP

Coin Change DP

  August 09, 2017    

---

Explanation:

We can make 1 combination for 0 money
Start a loop from 0 to length of array 
Inner Loop from value at i to n
Add value of t[i]+t[i-c[k]] to t[i].


Here in code i have typecasted long to int as we can't give long value to [].

Code:

static long getWays(long n, long[] c){
        int len=(int)n+1;
        long j;
        long t[]=new long[len];
        Arrays.fill(t,0);
        t[0]=1;
        
        for(long i=0;i<c.length;i++)
        {
            for(j=c[(int)i];j<=n;j++)
                t[(int)j]+=t[(int)(j-c[(int)i])];
        }
        
      //  System.out.println("ds");
        return t[(int)n];
    }

Read More

Binary Tree to CDLL Geeks solution

Binary Tree to CDLL Geeks solution

  July 23, 2017    

---

First read this problem :
https://hackerranksolutionc.blogspot.com/2017/07/binary-tree-to-dll-geeks-solution.html

Problem :

Given a Binary Tree (BT), convert it to a Circular Doubly Linked List(DLL) In-Place

Idea:

Use concept of previous problem (link given above), loop to leftmost and rightmost node and connect them .

Code:

/*Complete the function below
Node is as follows:
struct Node
{
    struct Node *left, *right;
    int data;
};*/
Node *BtoDLL(Node *root)
    {
        //if tree is empty
 if(root==NULL)
 return root;
 if(root->left!=NULL)
 {
     Node *x=BtoDLL(root->left);
//go to last right node 
     for(;x->right;x=x->right);
     x->right=root;
     root->left=x;
 }
 if(root->right!=NULL)
 {
     Node *y=BtoDLL(root->right);
     for(;y->left;y=y->left);
     y->left=root;
     root->right=y;
 }
 return root;
    }
Node *bTreeToCList(Node *root)
{
if(root==NULL)
 return root;
 Node *head=BtoDLL(root);
 Node *temp=head;
 while(temp->right!=NULL)
 temp=temp->right;
 while(head->left!=NULL)
 head=head->left;
 temp->right=head;
 head->left=temp;
 return head;
}

Read More