SRM524:

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3
Div 2	Level 1	Level 2	Level 3

This contest is probably the best score I ever had.
Keep trying, and keep being part of what you like to do.

Tutorials:

---

Division One - Level Three:

Solution

Source Code:

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

Solution

The same with Div2-Level2

Source Code:

---

Sivision Two - Level Three:

Solution

1st, filter out all the available digits left.
2nd, using BFS to compose every possible number, then check if it's the multiple of the given N.
PS: Redefine the comparator for String is another key for this solution. The default comparator compares the two strings character by character, which take the alphabetical order as higher priority, while the length of the string is set as second.

Source Code:

/**
 * 1st, filter out all the available digits.
 *
 * 2nd, using BFS to compose every possible digits,
 * check the number when it's the multiple of the given N;
 */

/**
 * @author antonio081014
 * @since Nov 17, 2011, 8:16:26 AM
 */
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class MultiplesWithLimit {
    public List<String> nonForbidden;
    public boolean[] visited;

    public String minMultiples(int N, int[] forbiddenDigits) {
        nonForbidden = new ArrayList<String>();
        for (int i = 0; i <= 9; i++) {
            boolean flag = true;
            for (int j = 0; j < forbiddenDigits.length && flag; j++) {
                if (i == forbiddenDigits[j])
                    flag = false;
            }
            if (flag)
                nonForbidden.add(Integer.toString(i));
        }

        visited = new boolean[10002];
        Queue<String> queue = new PriorityQueue<String>(10,
                new Comparator<String>() {
                    // overriding the compare method
                    public int compare(String i, String j) {
                        if (i.compareTo(j) == 0)
                            return 0;
                        if (i.length() < j.length())
                            return -1;
                        if (i.length() == j.length() && i.compareTo(j) < 0)
                            return -1;
                        return 1;
                    }
                });
        queue.add("");
        while (queue.isEmpty() == false) {
            String top = queue.poll();
            String tmp;
            for (int i = 0; i < nonForbidden.size(); i++) {
                tmp = top + nonForbidden.get(i);
                if (tmp.startsWith("0"))
                    continue;
                int number = compose(tmp, N);
                if (visited[number])
                    continue;
                if (number == 0) {
                    return getReturn(tmp);
                }
                queue.add(tmp);
                visited[number] = true;
            }
        }
        return "IMPOSSIBLE";
    }

    public String getReturn(String s) {
        if (s.length() < 9)
            return s;
        else
            return s.substring(0, 3) + "..." + s.substring(s.length() - 3)
                    + "(" + s.length() + " digits)";
    }

    public int compose(String s, int N) {
        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            sum = sum * 10 + s.charAt(i) - '0';
            sum %= N;
        }
        return sum;
    }

    // <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!

---

Division Two - Level Two:

Solution

Take the closest non-prime number, which is smaller than n. Greedy Algorithm.

Source Code:

/**
 * 
 */

/**
 * @author antonio081014
 * @since Nov 17, 2011, 8:08:21 AM
 */

public class MagicDiamonds {
    public long minimalTransfer(long n) {
        long count = 0;
        while (n > 0) {
            count++;
            n -= closestNonePrime(n);
        }
        return count;
    }

    public long closestNonePrime(long n) {
        for (long x = n; x >= 1; x--) {
            if (isPrime(x) == false)
                return x;
        }
        return -1;
    }

    public boolean isPrime(long n) {
        if (n == 2)
            return true;
        if (n <= 1)
            return false;
        if (n % 2 == 0)
            return false;
        for (long i = 3; i * i <= n; i += 2) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    // <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!

---

Division Two - Level One:

Solution

Iterate every possible combination of a, b, c. Then check if is smaller than what I have already.

Source Code:

/**
 * 
 */

/**
 * @author antonio081014
 * @since Nov 17, 2011, 8:03:13 AM
 */
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class ShippingCubes {
    public int minimalCost(int N) {
        int mmin = Integer.MAX_VALUE;
        for (int a = 1; a <= N; a++) {
            for (int b = 1; b <= N; b++) {
                for (int c = 1; c <= N; c++) {
                    if (a * b * c == N) {
                        mmin = Math.min(mmin, a + b + c);
                    }
                }
            }
        }
        return mmin;
    }

    // <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!

Interview Problem: if string s2 is a rotation of string s1

Problem:

Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i.e., “waterbottle” is a rotation of “erbottlewat”)

Solution:

1st , check it they share the same length.
2nd, concatenate s1 with itself, check if s2 is the substring of s1.

Interview Problem: Rotate Matrix.

Problem

Rotate the Matrix by 90 degree.

Solution:

/**
 * Given an image represented by an NxN matrix,
 * where each pixel in the image is 4 bytes,
 * write a method to rotate the image by 90 degrees.
 */
/**
 * @author antonio081014
 * @since Nov 6, 2011, 4:57:14 PM
 */
public class MatrixRotation {

    public static void rotate(int[][] matrix, int n) {
        for (int i = 0; i < n / 2; i++) {
            int left = i;
            int right = n - 1 - i;
            for (int j = left; j < right; j++) {
                int offset = j - left;
                // save the top element;
                int tmp = matrix[left][left + offset];
                // right -> top;
                matrix[left][left + offset] = matrix[left + offset][right];
                // bottom -> right;
                matrix[left + offset][right] = matrix[right][right - offset];
                // left -> bottom;
                matrix[right][right - offset] = matrix[right - offset][left];
                // top -> left;
                matrix[right - offset][left] = tmp;
            }
        }
    }
}

Interview Problem: String Replacement.

Problem:

Replace all spaces in a string with '%20'.

Solution:

Go through every characters in the string, then replace it with %20 once the character is space.
Time complexity: O(n).
Space complexity: O(n).

/**
 * replace all spaces in a string with '%20'
 */

/**
 * @author antonio081014
 * @since Nov 5, 2011, 9:20:12 PM
 */
public class StringReplace {

    public String replaceSpace(String s) {
        String tmp = "";
        for (int i = 0; i < s.length(); i++)
            if (s.charAt(i) == ' ')
                tmp += "%20";
            else
                tmp += s.charAt(i);
        return tmp;
    }
}

Testing:

1st, using string having space.
2nd, using string without space.

PS: The following solution is wrong, though the idea is quite right, which could save much memory while spending the similar amount of time. The reason for its failure is it would rise IndexOutOfBoundsException exception caused by line: str[newLength] = '\0';The newLength will be equal to or bigger than the original length, the memeory could not be accessed until it's allocated before. Here if newLength is larger than the original one, the program will try to access the memory which is not allocated or we could say that the memory is not assigned to the program by the virtual system.
/**
 * replace all spaces in a string with '%20'
 */
/**
 * @author antonio081014
 * @since Nov 5, 2011, 9:20:12 PM
 */
public class StringReplace {

    public static void ReplaceFun(char[] str, int length) {
        int spaceCount = 0, newLength, i = 0;
        for (i = 0; i < length; i++) {
            if (str[i] == ' ') {
                spaceCount++;
            }
        }
        newLength = length + spaceCount * 2;
        str[newLength] = '\0';
        for (i = length - 1; i >= 0; i--) {
            if (str[i] == ' ') {
                str[newLength - 1] = '0';
                str[newLength - 2] = '2';
                str[newLength - 3] = '%';
                newLength = newLength - 3;
            } else {
                str[newLength - 1] = str[i];
                newLength = newLength - 1;
            }
        }
    }
}

Interview Problem: Anagram Strings.

Problem:

Decide if two strings are anagrams or not.

Solution:
Here, first sort two strings in order, then compare one with another character by character.
Time complexity: O(nlgn); The main consuming is the sort function used for sorting.
Space complexity: O(c); constant possibly.
/**
 * Decide if two strings are anagrams or not.
 */

/**
 * @author antonio081014
 * @since Nov 5, 2011, 3:30:10 PM
 */
public class Anagrams {

    /*
     * Using sort function to check if they have the arrays after they are both
     * sorted.
     */
    public boolean isAnagramsSorted(String a, String b) {
        char[] aArray = a.toCharArray();
        char[] bArray = b.toCharArray();
        Arrays.sort(aArray);
        Arrays.sort(bArray);
        // if (aArray.length != bArray.length)
        // return false;
        // for (int i = 0; i < aArray.length; i++)
        // if (aArray[i] != bArray[i])
        // return false;
        // return true;
        return Arrays.equals(aArray, bArray);
    }
}

Alternate Solution:

Here, using a hash table to keep the record of each existing character in string a, and then check the occurrence of each characters in string b.
1st, If they share the same length.
2nd, Needs to check if the ith character exists in string b.
3rd, subtract the number from hash table for each existing character in string b, until it's zero already. Then return false for that value.
Time complexity: O(n); n is the length of strings.
Space complexity: O(n); n is the number of unique characters in the strings, it should be smaller than the length of string.

It just takes more time to program.

import java.util.Arrays;
import java.util.Hashtable;

/**
 * Decide if two strings are anagrams or not.
 */

/**
 * @author antonio081014
 * @since Nov 5, 2011, 3:30:10 PM
 */
public class Anagrams {

    /*
     * Check if they share the same characters with the same counts.
     */
    public boolean isAnagramsUnsorted(String a, String b) {
        if (a == null || b == null)
            return false;
        if (a.length() != b.length())
            return false;
        Hashtable<String, Integer> set = new Hashtable<String, Integer>();
        for (int i = 0; i < a.length(); i++) {
            Integer tmp = set.get("" + a.charAt(i));
            if (tmp == null) {
                set.put("" + a.charAt(i), 1);
            } else {
                set.put("" + a.charAt(i), tmp + 1);
            }
        }
        for (int i = 0; i < b.length(); i++) {
            Integer tmp = set.get("" + b.charAt(i));
            if (tmp == null)
                return false;
            if (tmp.intValue() == 0)
                return false;
            set.put("" + b.charAt(i), tmp - 1);
        }
        return true;
    }
}

Conclusion:

The second algorithm apparently takes fewer time than the first one, it could be a good choice if memory limit is not such critical, especially good for large data sets. Even if the characters in two large files needs to be compared, it could be a good choice, since generally the number unique characters must be much less than the number of characters in the file.