Pages

Showing posts with label Coding Interview. Show all posts
Showing posts with label Coding Interview. Show all posts

Wednesday, 3 February 2016

Write a method to replace all spaces in a string with ‘%20’.


Algorithm:
1. Count the number of spaces during the first scan of the string.
2. Scan the string from start to end for each character:
If a space is encountered, store “%20”.
Else, store the character as it is in the newly shifted location.

packagecrack.coding.interview;

/**
 * This class is used to replace all the spaces by "%20" in a string.
 * @author rajesh.dixit
 */
public classReplaceSpacesInString {
    
    
     /**
      * Replace spaces from String from "%20"
      * @param str
      * @return
      */
     private staticString replaceSpaces(String str) {
           if(str==null) {
                return null;
           }
          
           int len = str.length();
           int count = 0;
          
           /* Count all the spaces in the String. */
           for(inti=0;i<len;i++) {
                if(str.charAt(i) == ' ') {
                     count ++;
                }
           }
          
           /* Calculate the length of new String and define the new Char array. */
           int newLen = len + 2 * count;
           char[] newCharArray = new char[newLen];
           int j = 0;
          
           for(inti=0;i<len;i++) {
                char ch = str.charAt(i);
                if(' ' == ch) {
                     newCharArray[j++] = '%';
                     newCharArray[j++] = '2';
                     newCharArray[j++] = '0';
                } else {
                     newCharArray[j++] = ch;
                }
           }
           return newString(newCharArray);
     }
    
     /**
      * Driver Method
      * @param args
      */
     public static voidmain(String[] args) {
           String str = "replace space from string";
           String newStr = replaceSpaces(str);
           System.out.println(newStr);
     }
}



Posted by at No comments:
Labels:

Tuesday, 2 February 2016

Remove Duplicate from String in Java

Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer.

To solve this problem, we can apply the same approach as we used to check the unique character in the string. Please check for the unique character in the string for better understanding of below given solution. 

Using one Boolean array:
packagecrack.coding.interview;
public classRemoveDuplicate {

     /**
      * Remove Duplicate using extra memory space.
      * @param str
      */
     public static voidremoveDuplicatesEff(char[] str) {
           int len = 0;
           if (str == null || (len = str.length)<2) {
                return;
           }
          
           boolean[] map = new boolean[256];

           for (int i = 1; i < len; ++i) {
                if (!map[str[i]]) {
                     map[str[i]] = true;
                } else {
                     str[i] = '0';
                }
           }
     }

     /**
      * Driver method top remove duplicate.
      * @param args
      */
     public static voidmain(String[] args) {
           String str = "removeduplicate";
           char[] array = str.toCharArray();
           removeDuplicatesEff(array);

           System.out.println(newString(array));
     }
}

Using only one extra variable:
packagecrack.coding.interview;
public classRemoveDuplicate {
     private static voidremoveDuplicate(char[] array) {
           int map = 0;
           for (int i = 0; i < array.length; i++) {
                int val = array[i] - 'a';

                /* Shift for Map bit position.
                 * Exp: For b val= 1 and the bit position after shifting 10,
                 * For c val= 2 and the bit position after shifting 100 */
                int bitPos = 1 << val;

                /* Check whether bit position already 1.
                 * If true: Set duplicate bit to zero. */
                if((map & bitPos)>0) {
                     array[i] = '0';
                }

                /* Modify the bit position in the array. */
                map = map | bitPos;
           }

     }

     /**
      * Driver method top remove duplicate.
      * @param args
      */
     public static voidmain(String[] args) {
           String str = "removeduplicate";
           char[] array = str.toCharArray();
           removeDuplicate(array);

           System.out.println(newString(array));
     }
}




Posted by at No comments:
Labels:

Write a function to check whether two strings are anagram of each other.


Input:str1 – “geeksforgeeks”, str2 – “geeksforgeeks”
Output = Strings are Angram

Input:str1 – “geeksforgeeksk”, str2 – “lgeeksforgeeks”
Output = Strings are not Angram

Approach#1:
Sort both the strings and then compare the strings.
Time Complexity: O(nlogn).
packagecrack.coding.interview;
importjava.util.Arrays;
public class AngramSrtings {
     /**
      * Check that the Strings are anagram.
      * @param str1
      * @param str2
      * @return
      */
     private static boolean isStringsAngrmUsingSorting(String str1, String str2) {
           if(str1.length()!= str2.length()) {
                return false;
           }

           char[] array1 = str1.toCharArray();
           char[] array2 = str2.toCharArray();
           Arrays.sort(array1);
           Arrays.sort(array2);
           int len = array1.length;
           for (int i = 0; i < len; i++) {
                if(array1[i]!=array2[i]) {
                     return false;
                }
           }
           return true;
     }

     /**
      * Driver method.
      * @param args
      */
     public static voidmain(String[] args) {
           String str1 = "geeksforgeeks";
          
           String str2 = "geeksfoeekrgs";
           booleanresult = isStringsAngrmUsingSorting(str1,str2);
           String angram = "Not Angram";
           if(result) {
                angram = "Angram";
           }
           System.out.println("Strings are "+angram);
     }
}

Approach#2:
Check if the two strings have same count for each character. It can be achieved using temporary array or HashMap.

1. Create an array of size 256(=all possible character ASCIIs) initialized with 0′s.
2. For first string increment count of character in count array.
3. For second string decrement the count of character from count array.
4. Repeat steps 2 and 3 till we reach end of any string.
5. Check if array contains only zero then strings are anagram otherwise not.

packagecrack.coding.interview;
importjava.util.Arrays;
public class AngramSrtings {

     /**
      * Check that the Strings are anagram using Temporary storage array.
      * @param str1
      * @param str2
      * @return true/false.
      */
     private static booleanisAngrams(String str1, String str2) {
           int len = 0;
           if((len = str1.length())!= str2.length()) {
                return false;
           }
          
           int[] counts = new int[256];
           for (int i = 0; i < len; i++) {
                int ch1 = str1.charAt(i);
                int ch2 = str2.charAt(i);
               
                /**For first string increment count of character in count array. */
                counts[ch1] = counts[ch1] + 1;
                /**For second string decrement the count of character from count array. */
                counts[ch2] = counts[ch2] - 1;
           }

           /** Check if array contains only zero then strings are anagram otherwise not.*/
           for (int i = 0; i < len; i++) {
                if(counts[i]!=0) {
                     return false;
                }
           }
           return true;
     }
    
     /**
      * Driver method.
      * @param args
      */
     public static voidmain(String[] args) {
           String str1 = "geeksforgeeks";
           String str2 = "geeksfoeekrgs";
          
           booleanresult = isAngrams(str1,str2);
           String angram = "Not Angram";
           if(result) {
                angram = "Angram";
           }
           System.out.println("Strings are "+angram);
     }
}

Time Complexity: O(n) and extra space required for temporary array.


Posted by at No comments:
Labels:
Subscribe to: Posts (Atom)