String Reverse using XOR

Better implementation of string reverse is by using XOR operation. This eliminates swap operation. See how it works:

    

  public static final String reverseWithXOR(String string) {

        char[] array = string.toCharArray();

        int length = array.length;

        int half = (int) Math.floor(array.length / 2);

        for (int i = 0; i < half; i++) {

            array[i] ^= array[length - i - 1];

            array[length - i - 1] ^= array[i];

            array[i] ^= array[length - i - 1];

        }

        return String.valueOf(array);

    }

The performance of this method is very similar as the one implemented in the Java Library:

public static final String reverseWithStringBuilderBuiltinMethod(String string) {
        StringBuilder builder = new StringBuilder(string);
        return builder.reverse().toString();
    }

Reversing a string with StringBuilder built-in reverse method.

before=ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz after=zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA

Computed in 26000 ns

Reversing a string with swaps.

before=ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz after=zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA

Computed in 75000 ns

Reversing a string with XOR.

before=ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz after=zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA

Computed in 20000 ns

The source code for this article is part of the library: Java Algorithms - Implementation.

Continue reading →

Binary Search algorithm

This implementation of Binary Search algorithm is aim to be one of the most simplest. The elements are in sorted array.

If the search element (item) value is less than the middle value - > take the left part and apply the algorithm on it.

If the search element (item) value is bigger than the middle value - > take the right part and apply the algorithm on it.
If the search element is the middle element - the recursion stoops - > returns the element.
The recursion also stops if there is no such element in the array - the checks are done till start index is lest than the end index. Another interesting point is that the calculation of the middle index is done by accumulating the start index (in the beginning =0) : int index = start + (end-start)/2;
When we are somewhere in the array - the start will not be always equals to 0 as it is in the beining but will really depends on the search element and the elements in the array.

// Binary search in sorted array

public class BinarySearch

{

public static void main(String[] args)

{

int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 

22, 34, 56, 78, 90, 112, 113, 224};

int result = find(arr, Integer.parseInt(args[0]));

System.out.println(result);

}

public static int find(int[] arr, int item)

{

return find(arr, 0, arr.length, item);

}

public static int find(int[] arr, int start, int end, int item)

{

if(arr==null)

return -1;

if(arr.length==0)

return -1;

if(start

{

int index = start + (end-start)/2;

int middle = arr[index];

if(item < middle)

return find(arr, start, index, item);

else if(item>middle)

return find(arr, index+1, end, item);

else

return index;

}

return -1;

}

}

Continue reading →

Implementation of string replace method in JAVA

The idea is to create a custom implementation of the well known method in java, which replaces substring of a string with other string.
Example:

String str1 = "Lyubomir";

System.out.println(str1.replace("Ly", "fiko"));

Result: fikoubomir

The method will be implemented using arrays or characters, although Strings can be used as well. This will be much simple, but the idea here is to get more details in how the algorithm works.

On the first pass we have to calculate how many times the string which will be replaced occurs in the input string.

private static int countNumFimesOneStrInOther(char[] str1Arr,char[] str2Arr )

{

      //count how many times the second string is in the first one

      int counter=0;

      for(int i=0; ilength

; i++){

 int j=i;

     int k=0;

     while(jlength

&& klength && str1Arr[j]==str2Arr[k])

     {         

          j++;

          k++;

     }

       //the whole string 2 is in string one

    if(k==str2Arr.length)

    {

       counter++;

    }

       }

    return counter;

}

Here for every character in the truing we check the characters in the second string, if they are the same as the ones in the first characters increment the counter. Then if the counter is equal to the size of the array - then this is occurrence.

This will give the size of the resulting character array - the size of the string - number of times the second string occurs*it's length  + number of times the second string occurs * it's length: 

char[] strResult = new char[str1Arr.length + Math.abs(numTimes*(str3Arr.length-str2Arr.length))];

Again when the whole string 2 is found in string one - iterate through the third string and put it's character by character in the result string.

Here is the full source code of the program:

import java.util.Hashtable;
import java.io.Console;
import java.util.*;
import java.io.*;
import java.lang.*;

//replace all the strings with string

public class StringReplace {
    public static void main(String[] args)
    {  
        String str1 = args[0];
        String str2 = args[1];
        String str3 = args[2];

        System.out.println(replace(str1, str2, str3));
   }

   private static int countNumFimesOneStrInOther(char[] str1Arr,char[] str2Arr )
   {

        //count how many times the second string is in the first one

        int counter=0;
        for(int i=0; ilength
; i++)         {
            int j=i;
            int k=0;
            while(jlength
&& klength && str1Arr[j]==str2Arr[k])             {
                j++;
                k++;
            }

            //the whole string 2 is in string one

            if(k==str2Arr.length)
            {
                counter++;
            }
        }
        return counter;
   }

    private static String replace(String str1, String str2, String str3)
    {
        if(str1==null || str2==null)
            return "";

      

        char[] str1Arr = str1.toCharArray();
        char[] str2Arr = str2.toCharArray();
        char[] str3Arr = str3.toCharArray();

        int numTimes = countNumFimesOneStrInOther(str1Arr, str2Arr);

        //the result string will be with length x times the number of times the string which replaces the first one occurs

        char[] strResult = new char[str1Arr.length + Math.abs(numTimes*(str3Arr.length-str2Arr.length))];

        int resIndex=0;
        for(int i=0; ilength
; i++)         {
            int j=i;
            int k=0;

            

            while(jlength
&& klength && str1Arr[j]==str2Arr[k])             {
                j++;
                k++;
            }

            //the whole string 2 is in string one

            if(k==str2Arr.length)
            {
                k=0;
                while(klength
)                 {
                    strResult[resIndex] = str3Arr[k];
                    resIndex++;
                    k++;
                    i++;
                }
            }

            

            strResult[resIndex] = str1Arr[i];
            resIndex++;

            

        }

            

        return new String(strResult);
    }
}

The complexity of the method is O(n^2) and the space needed is O(m - k.n + k.p), where n-the size of the replaced string, p-the size of the string replacement.

Better solution will be to use suffix tree or suffix array data structure - which gives the index on the substring in linear time and uses no extra space.

Continue reading →

Majority Vote Algorithm

Question: How we can determine which element in an array is majority element? (A majority element is the one which occurs most of the time compared with the other elements)

For example in the string: ABCAGRADART - A is the majority element.

A naive solution of this problem will be to traverse the string (the array) and count the number of occurrences of every character. - In that case we will store a of of unnecessary information.

Another approach is to put every element in a hash-map and then after all the elements are in the map to traverse the elements in the map and see which has the biggest value in its key/value pair.

Both of the above solutions can be used for solving the problem but there is more effective way of doing that.

If we store a pair of the current candidate for majority element and the number of occurences. When we move through the array we compare the next element with the current one...

public class MajorityVotingAlgorithm {

public static void main(String[] args) {

char[] votes = { 'A', 'A', 'A', 'C', 'C', 'C', 'B', 'B', 'C', 'C', 'C',

'B', 'C', 'C' };

int counter = 0;

char candidate = ' ';

for (char v : votes) {

if (counter == 0) {

candidate = v;

counter++;

} else {

if (candidate == v)

counter++;

else

counter--;

}

}

System.out.println("Majority Element is: " + candidate + " (counter = "

+ counter + ")");

}

}

Continue reading →