CareerCup

public class Test {

public static int getNumber(int[] A) throws Exception {
int result = helper(A, 0, A.length - 1, 0);
if (result == 0)
throw new Exception("Number does not exist!");
return A[A.length - result];
}

// return the num of elements which is greater to equal to the pivot
public static int helper(int[] A, int start, int end, int tailSize) {
if (start > end)
return 0;

// choose the starting number of this range as pivot
int left = start, mid = start + 1, right = end;
while (mid <= right) {
if (A[mid] < A[left]) {
swap(A, left, mid);
mid++;
left++;
} else if (A[mid] == A[left])
mid++;
else {
swap(A, mid, right);
right--;
}
}

int greaterOrEqualToPivot = end - left + 1 + tailSize;
if (greaterOrEqualToPivot >= A[left]) {
int subResult = helper(A, right + 1, end, tailSize);
if (subResult != 0)
return subResult;
else
return greaterOrEqualToPivot;
} else
return helper(A, start, left - 1, greaterOrEqualToPivot);
}

public static void swap(int[] A, int left, int right) {
int temp = A[left];
A[left] = A[right];
A[right] = temp;
}

public static void main(String[] args) throws Exception {
System.out.println(getNumber(new int[] { 900, 2, 901, 3, 1000 }));
}

}

Find the all the guards first, populate all the surrounding empty rooms at distance 1, keep track of these rooms.
1.Find the G cells
2.Update the distance of surrounding cells found in step 1 to 1, use a list to keep track these cells been updated
3.Distance+1, repeat step 2, if the cell's distance is already there, that's definitely the shortest distance, skip this cell

public static int[][] nearestGuard(char[][] input) {
int[][] result = new int[input.length][input[0].length];
ArrayList<int[]> current = new ArrayList<int[]>();
for (int i = 0; i < input.length; i++) {
for (int j = 0; j < input[0].length; j++) {
if (input[i][j] == 'G')
current.add(new int[] { i, j });
}
}
int distance = 1;
while (!current.isEmpty()) {
ArrayList<int[]> next = new ArrayList<int[]>();
for (int[] c : current) {
guradHelper(input, c[0] + 1, c[1], distance, result, next);
guradHelper(input, c[0] - 1, c[1], distance, result, next);
guradHelper(input, c[0], c[1] + 1, distance, result, next);
guradHelper(input, c[0], c[1] - 1, distance, result, next);
}
current = next;
distance++;
}
return result;
}

public static void guradHelper(char[][] input, int i, int j, int distance,
int[][] result, ArrayList<int[]> next) {
if (i < 0 || j < 0 || i >= input.length || j >= input[0].length
|| input[i][j] == 'G' || input[i][j] == 'B'
|| result[i][j] != 0)
return;
result[i][j] = distance;
next.add(new int[] { i, j });
}

public static boolean isomorphic(String s1, String s2){
if(s1==null || s2==null || s1.length()!=s2.length())
return false;

int[] c1=new int[26];
int[] c2=new int[26];
Arrays.fill(c1,0);
Arrays.fill(c2,0);

for(int i=0;i<s1.length();i++){
int index1=s1.charAt(i)-97;
int index2=s2.charAt(i)-97;
if(c1[index1]==0 && c2[index2]==0)
{
c1[index1]=s2.charAt(i);
c2[index2]=s1.charAt(i);
}else if(c1[index1]!=0 && c2[index2]!=0){
if(c1[index1]!=s2.charAt(i) || c2[index2]!=s1.charAt(i))
return false;
}else
return false;
}

return true;
}

I don't think the first char with the counter 1 in the hash table is the first non-repeating char in the original string. You may forget the hashcode is generated.

The servlet container loads the servlet class and calls the init method of the servlet as soon as the servlet is called for the first time. Then the container makes an instance of javax.servlet.ServletRequest and javax.servlet.ServletResponse for each request. Then it passes the ServletRequest and ServletResponse objects by invoking the servlet's service method. Finally, it calls the destroy method and unload the servlet class when the servlet class is to be shut down.

HashMap is unsynchronized and permits nulls. Whereas Hashtable is unsynchronized. HashMap allows null values as key and values. Hashtable does not guarantee the order of the order of the map will remain constant over time.