Twenty Percent Knowledge

Saturday, June 25, 2016

Hackerrank common sample code snipets

1. reading input

Scanner in = new Scanner(System.in);
int n = in.nextInt();
in.nextLine();//read rest of line. finish current line's reading
String[] ss = new String[n];
for(int i=0;i
s[i] = in.next();

Thursday, June 23, 2016

Distance to anagram:

Sid is obsessed with reading short stories. Being a CS student, he is doing some interesting frequency analysis with the books. He chooses strings

and

in such a way that

.
Your task is to help him find the minimum number of characters of the first string he needs to change to enable him to make it an anagram of the second string.
Note: A word x is an anagram of another word y if we can produce y by rearranging the letters of x.
Input Format
The first line will contain an integer,

, representing the number of test cases. Each test case will contain a string having length

, which will be concatenation of both the strings described above in the problem.The given string will contain only characters from

.
Output Format
An integer corresponding to each test case is printed in a different line, i.e. the number of changes required for each test case. Print

if it is not possible.
Constraints

Sample Input

6
aaabbb
ab
abc
mnop
xyyx
xaxbbbxx

Sample Output

Explanation
Test Case #01: We have to replace all three characters from the first string to make both of strings anagram. Here,

= "aaa" and

= "bbb". So the solution is to replace all character 'a' in string a with character 'b'.

Test Case #02: You have to replace 'a' with 'b', which will generate "bb".

Test Case #03: It is not possible for two strings of unequal length to be anagram for each other.

Test Case #04: We have to replace both the characters of first string ("mn") to make it anagram of other one.

Test Case #05:

and

are already anagram to each other.

Test Case #06: Here S1 = "xaxb" and S2 = "bbxx". He had to replace 'a' from S1 with 'b' so that S1 = "xbxb" and we can rearrange its letter to "bbxx" in order to get S2.

Solution:
counting the presence of characters in first string, then reduce its counting by examining the second string. the sum of remaining numbers are the edit distance to make another anagram.

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. */
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for(int i=0;i<n;i++){
            System.out.println(solve(in.next()));
        }
                              
    }
    private static int solve(String s){
        if(s==null||s.length()%2==1)return -1;
        int[] cStatus = new int[26];
        for(int i=0;i<s.length()/2;i++){
            cStatus[s.charAt(i)-'a']++;
        }
        for(int i=s.length()/2;i<s.length();i++){
            if(cStatus[s.charAt(i)-'a']>0)
                cStatus[s.charAt(i)-'a']--;
        }
        int sum = 0;
        for(int i:cStatus)
            sum+=i;
        return sum;
    }
}

Alternating Characters -- Number of Deletions

Caution: scanner.next() is the function to read each line in hackerrank.use nextLine()if next() is not working. Hackerrank's input/output methods sucks. very often a right solution is reported as wrong solution.

Number of Deletions

Shashank likes strings in which consecutive characters are different. For example, he likes ABABA, while he doesn't like ABAA. Given a string containing characters

and

only, he wants to change it into a string he likes. To do this, he is allowed to delete the characters in the string.
Your task is to find the minimum number of required deletions.

Input Format

The first line contains an integer

, i.e. the number of test cases.
The next

lines contain a string each.

Output Format

For each test case, print the minimum number of deletions required.
Constraints

length of string

Sample Input

5
AAAA
BBBBB
ABABABAB
BABABA
AAABBB

Sample Output

Explanation

AAAA

A, 3 deletions
BBBBB

B, 4 deletions
ABABABAB

ABABABAB, 0 deletions
BABABA

BABABA, 0 deletions
AAABBB

AB, 4 deletions because to convert it to AB we need to delete 2 A's and 2 B's

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. */
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        
        for(int i=0;i<n;i++){
            numDeletion(in.next());
        }
    }
    private static void numDeletion(String s){
        if(s==null)
            System.out.println(0);
        if(s.length()==1)System.out.println(0);
        int totalDeletion = 0;
        int i=0,j=1;
        while(j<s.length()){
            while(j<s.length()&&s.charAt(j)==s.charAt(i))
                j++;
            totalDeletion+=j-i-1;
            i=j;
        }
        System.out.println(totalDeletion);
    }
}

Pangrams: Check existence of character in string

If it tells you that the problem is case insensitive alphabets, to check a letters existence, you can use an integer to set corresponding bit value to represent existence of a letter since there are totally 26 letters and integer has 32 bits.

Problem:

Given a sentence

, tell Roy if it is a pangram or not.

Input Format

Input consists of a string

.
Constraints
Length of

can be at most

and it may contain spaces, lower case and upper case letters. Lower-case and upper-case instances of a letter are considered the same.

Output Format

Output a line containing pangram if

is a pangram, otherwise output not pangram.

Sample Input

Input #1

We promptly judged antique ivory buckles for the next prize

Input #2

We promptly judged antique ivory buckles for the prize

Sample Output

Output #1

pangram

Output #2

not pangram

Explanation

In the first test case, the answer is pangram because the sentence contains all the letters of the English alphabet.

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) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        int bitCheck=0;
        Scanner in = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        while(in.hasNext()){
            sb.append(in.next());
        }
        
        for(int i=0;i<sb.length();i++){
            if(Character.isLetter(sb.charAt(i) )){
                int n = Character.toLowerCase(sb.charAt(i))-'a';
                bitCheck|=1<<n;}
        
        }
        if(bitCheck==0b00000011111111111111111111111111)
            System.out.println("pangram");
        else
            System.out.println("not pangram");
    }
}

Monday, June 20, 2016

Find kth Smallest Element in Two Sorted Arrays

O(m+n) Solution:
merge the two arrays using O(m+n) time and space, and then pick kth element from merged array.

O(k) Solution:
using two pointers and a counter, move forward the smaller value one until they are equal or hit k, when they are equal, move both of them forward and count it as 2. This is a solution always came up to me.

O(lgn+lgm) Solution:
I could not figure it out, I could understand many of the explainations but still could not easily to understand the code developed for it. Until I found explain from here:

This is the one finally makes me easily understand how it works.

When you calculate out the position of median, this is also a function to help find the median efficiently form two sorted arrays.

Ideas:
1. try to find half of k from both arrays.
2. compare the k/2th elements, discard the part that is higher than the bigger element in corresponding array, discard the part that is lower than the smaller element in the corresponding array.
3. after step 2, we know the elements smaller than smaller elements are part of the i or j elements within the k smallest elements
4. recursively check the rest of elements for k-i or k-j th smallest element.

First version:

    int findKthSmallestElement(int a[], int b[], int k) {
  if (a.length > b.length)
   return findKthSmallestElement(b, a, k);// this is for next condition
             // check.
  /*
   * Now case when size of smaller array is 0 i.e there is no element in
   * one array
   */
  if (a.length == 0 && b.length > 0)
   return b[k - 1]; // due to zero based index

  /* case where K ==1 that means we have hit limit */
  if (k == 1)
   return Math.min(a[0], b[0]);

  /* Now the divide and conquer part */
  //i and j means length and not index
  int i = Math.min(k / 2,a.length);// Math.min(sizeA, k/2) ; 
  int j = Math.min(k -i,b.length);// Math.min(sizeB, k/2) ;
  
  int[] aTmp, bTmp;
  
  if (a[i - 1] > b[j - 1]) {
   // let's use non-smart way the first
   aTmp = new int[i];
   System.arraycopy(a, 0, aTmp, 0, i);
   bTmp = new int[b.length - j];
   System.arraycopy(b, j, bTmp, 0, b.length - j);
   // Now we need to find only K-j th element since we have found out
   // the lowest j
   return findKthSmallestElement(aTmp, bTmp, k - j);
  } else {
   aTmp = new int[a.length - i];
   System.arraycopy(a, i, aTmp, 0, a.length - i);
   bTmp = new int[j];
   System.arraycopy(b, 0, bTmp, 0, j);
   // Now we need to find only K-i th element since we have found out
   // the lowest i
   return findKthSmallestElement(aTmp, bTmp, k - i);
  }

 }

Easy to understand, but not space wise.

Second Version:
In-place algorithm based on first version

static int findKthSmallestElementInPlace(int a[], int b[], int aStart,int aEnd,int bStart, int bEnd,int k) {
  /*
   * to maintain uniformity, we will assume that size_a is smaller than
   * size_b else we will swap array in call :)
   */
  int aLength =aEnd-aStart+1;
  int bLength = bEnd-bStart+1;
  if ( aLength > bLength)
   return findKthSmallestElementInPlace(b, a, bStart,bEnd,aStart,aEnd, k);// this is for next condition
             // check.
  /*
   * Now case when size of smaller array is 0 i.e there is no element in
   * one array
   */
  if ((aLength == 0 )&& bLength > 0)
   return b[bStart+k - 1]; // due to zero based index

  /* case where K ==1 that means we have hit limit */
  if (k == 1)
   return Math.min(a[aStart], b[bStart]);

  /* Now the divide and conquer part */
  int i = Math.min(k/2,a.length);// represents how many steps to advance based on start
  int j = k -i;// Math.min(sizeB, k/2) ;

  if (a[aStart+i-1 ] > b[bStart+j-1 ]) {
   // Now we need to find only K-j th element since we have found out
   // the lowest j
   int aS = aStart,aE = aStart+i-1;// including the bigger element
   int bS = bStart+j,bE = bEnd;//not including smaller element
   return findKthSmallestElementInPlace(a, b, aS, aE, bS, bE, k-j);
  } else {
   // Now we need to find only K-i th element since we have found out
   // the lowest i
   int aS = aStart+i,aE = aEnd;
   int bS = bStart,bE = bStart+j-1;
   return findKthSmallestElementInPlace(a, b, aS, aE, bS, bE, k-i);
  }

 }

Related use:
Find median from two sorted arrays.

static double findMedian(int a[],int b[]){
  int len = a.length+b.length;
  if(len%2==0){
   return  (double) ((findKthSmallestElement(a, b, len/2)+findKthSmallestElement(a, b, len/2+1))/2.0);
  }
  else
   return (double) findKthSmallestElement(a, b, len/2+1);
 }