Pages

Saturday, January 9, 2010

Find String

PROBLEM: Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N.

SOLUTION:
package google;

public class FindString {
    public String functionOrderNSquare(String a, String b) {
        String result = "";
        for (int i = 0; i < a.length(); i++) {
            char cha = a.charAt(i);
            for (int j = 0; j < b.length(); j++)
                if (cha == b.charAt(j) && result.indexOf(cha) < 0)
                    result += cha;
        }
        return result;
    }

    public String functionOrderN(String a, String b) {
        String result = "";
        for (int i = 0; i < a.length(); i++) {
            char cha = a.charAt(i);
            if (b.indexOf(cha) >= 0 && result.indexOf(cha) < 0)
                result += cha;
        }
        return result;
    }

    public String functionOrderN(String a, String b) {
        StringBuffer result = new StringBuffer();
        boolean[] set = new boolean[256]; // primitive boolean initialize as false

        for (int i = 0; i < a.toCharArray().length; i++)
            set[a.toCharArray()[i]] = true;

        for (int i = 0; i < b.toCharArray().length; i++)
            if (set[b.toCharArray()[i]]) {
                result.append(b.toCharArray()[i]);
                set[b.toCharArray()[i]] = false; // already printed
            }
        return result.toString();
    }
}


TEST:
package google.test;

import google.FindString;

import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.Random;
import java.util.TimeZone;

public class FindStringTest {
    static final String AB = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    static Random rnd = new Random();

    public static void main(String[] args) {
        FindString find = new FindString();
        final int ARRAY_SIZE = (int) Math.pow(2, 10);
        final int MAX_STRING_SIZE = (int) Math.pow(2, 12);
        final DateFormat df = new SimpleDateFormat("HH 'hours', mm 'mins,' ss 'seconds,' SSS 'milliseconds'");
        df.setTimeZone(TimeZone.getTimeZone("GMT+0"));

        String a[] = new String[ARRAY_SIZE];
        String b[] = new String[ARRAY_SIZE];
        for (int i = 0; i < ARRAY_SIZE; i++) {
            StringBuilder sb = new StringBuilder(MAX_STRING_SIZE);
            for (int j = 0; j < MAX_STRING_SIZE; j++)
                sb.append(AB.charAt(rnd.nextInt(AB.length())));
            a[i] = sb.toString();
            
            for (int j = 0; j < MAX_STRING_SIZE; j++)
                sb.append(AB.charAt(rnd.nextInt(AB.length())));
            b[i] = sb.toString();
        }

        long startTime = System.currentTimeMillis();
        for (int i = 0; i < ARRAY_SIZE; i++) {
            find.functionOrderNSquare(a[i], b[i]);
        }
        long endTime = System.currentTimeMillis();
        long elapsed = (endTime - startTime);
        System.out.println("Function O(n^2) -  Execution time: " + df.format(new Date(elapsed)));

        startTime = System.currentTimeMillis();
        for (int i = 0; i < a.length; i++) {
            find.functionOrderN(a[i], b[i]);
        }
        endTime = System.currentTimeMillis();
        elapsed = (endTime - startTime);
        System.out.println("Function O(n) -  Execution time: " + df.format(new Date(elapsed)));
    }
}


RESULT: 
Function O(n^2) -  Execution time: 00 hours, 55 mins, 01 seconds, 118 milliseconds
Function O(n) -  Execution time: 00 hours, 00 mins, 38 seconds, 002 milliseconds


*Updated on April 13th 2010

No comments :