z.d.donnell
BAN USERwhat about making one linear pass to set up hashmaps of chars for each word that map char > number of occurrences in that word. Then compare all elements in each hashmap to every other hash map. Should be O(n + n * n) or just O(n^2) should be a bit faster than the O(n^2 logn) no?
- z.d.donnell July 29, 2013This should work as a simple solution, does anyone have a more effecient one? (call it with -1 for the parent value to start it)
private static int calcDepth(int parent, int[] tree) {
int maxDepth = 0;
for (int i = 0; i < tree.length; i++) {
if (tree[i] == parent) {
int depth = 1 + calcDepth(i, tree);
if (depth > maxDepth) maxDepth = depth;
}
}
return maxDepth;
}
The answer has already been posted, but for anyone that wants some working code, this should do the trick:
private static int[] closestNumbers(int[] a1, int[] a2) {
int i = 0, j = 0;
int x = 0, y = Integer.MAX_VALUE;
while (true) {
if (Math.abs(a1[i] - a2[j]) < Math.abs(x - y)) {
x = a1[i];
y = a2[j];
}
if (i < a1.length - 1 && a1[i] < a2[j]) i++;
else if (j < a2.length - 1) j++;
else break;
}
return new int[] { x, y };
}
Someone please correct me if you see anything wrong.
- z.d.donnell July 22, 2013I don't have the specifics right off the top of my head, but you'll want to do a modified binary search again once you are in the range. Searching linearly in each direction as you state should, if I am not mistaken, result in O(n) overall runtime, not the Sub O(n) the answer sought.
- z.d.donnell July 11, 2013
This should do the trick in Java
- z.d.donnell July 31, 2013