Zythum42
BAN USERJAVA: The code is a bit clogged because I took care of the scenario where you need to take the average of both middle values if you get an even number of integers when merging both arrays. Any ways to make it a bit cleaner? (Aside from putting the code replicate in another function), something actually clever...
public int getMutualMedian(int[] A, int[] B){
boolean isEven = ((A.length + B.length) % 2 == 0)
int medianIndex = (A.length + B.length)/2;
int indexA = 0;
int indexB = 0;
int median = 0;
int median1 = 0;
int median2 = 0;
while(A[indexA] != null && B[indexB] != null && medianCount != 1){
if(A[indexA] < B[indexB]){
if (isEven){
median1 = median2
median2 = A[indexA++];
median = (median1+median2)/2;
} else
median = A[indexA++];
}
else {
if (isEven){
median1 = median2
median2 = B[indexB++];
median = (median1+median2)/2;
} else
median = B[indexB++];
}
}
while(A[indexA] != null && medianCount != 1){
if (isEven){
median1 = median2
median2 = A[indexA++];
median = (median1+median2)/2;
} else
median = A[indexA++];
}
while(B[indexB] != null && medianCount != 1){
if (isEven){
median1 = median2
median2 = B[indexB++];
median = (median1+median2)/2;
} else
median = B[indexB++];
}
return median;
}

Zythum42
March 01, 2013 Isn't the problem too trivial if the arrays are already sorted? It sounds like you only to apply a fraction of what is needed in the standard merge sort algorithm. Basically, you could retrieve the total number of element and divide that by 2, then you can do the simple loop where as long as you haven't reached the end of your left and right array you increment the pointer on the array on which the current element is the lowest, when you have counted to total size / 2, return that value. That is, if you are looking for the Median...
 Zythum42 March 01, 2013@Barry
Add, Remove and Contains provide Constant O(1) time complexity on HashSet and HashMap. However, since there are no ordering in HashMap/Set, and say we are trying to find the top Key or something like that, this is where the complexity O(N) kicks in and this is where you will favor the usage of Trees. However, there's no such logic required in the above code, unless I am missing something.
@barry
The question specifies that an intersection between 2 circles, in this case, occurs if any point of the inner disk (not just the edge) is share with any other disk.
@Kosuru
This is the best solution around so far, a HashSet will do the map too, you are not really using that boolean value in the map.
Java:
=====================
public String sortByD(String s, List<Char> dict){
String output = "";
HashMap<Char, String> map = new HashMap<Char, String>();
for (Char c : dict)
m.put(c,"");
for (int i = 0; i < s.length(); ++i)
m.put(s.charAt(i),m.get(s.charAt(i))+s.charAt(i));
for (Char c : dict)
output += m.get(c);
return output;
}

Zythum42
February 28, 2013
I see, let's try something that yields log N complexity rather.
 Zythum42 March 01, 2013