gus
BAN USERIf we can restrict the arguments to positive integers (likely), this can be done very simply.
The trick is to use a logarithm:
public static int concat(int a, int b) {
return (int) (a * Math.pow(10, Math.ceil(Math.log10(b))) + b);
}
Not sure what the runtime is since I don't know a lot about how log10 and pow are implemented. I'd guess that it's logarithmic, or near-constant since we are just dealing with relatively small variations in the problem size.
- gus January 20, 2014The recursive version that many have posted is elegant but not efficient since it performs backtracking. We can match any regex in a single scan, although it may be tricky. In my case, it was just a lot of tricky edge cases.
Here's my shot at it:
public static Boolean match(String string, String pattern) {
int strIdx = 0;
int patIdx = 0;
int starIdx = -1;
while(true) {
if (strIdx == string.length()) {
if (patIdx == pattern.length()) return true;
else if (pattern.charAt(patIdx) == '*') {
if (patIdx == pattern.length()-1) return true;
else {
patIdx++;
continue;
}
}
else return false;
}
else if (patIdx == pattern.length()) {
return false;
}
else if (pattern.charAt(patIdx) == '*') {
if (patIdx == pattern.length()-1) return true;
starIdx = patIdx;
patIdx++;
}
else if (string.charAt(strIdx) != pattern.charAt(patIdx)) {
if (starIdx != -1) {
patIdx = starIdx+1;
strIdx++;
}
else return false;
}
else {
strIdx++;
patIdx++;
}
}
}
Yes it is assuming that we already have a way to map the ball color to the array index. I'm pretty sure you'll need that in order to complete the problem (somebody correct me if I'm wrong!). If you don't have it, then you'll need an aux variable or function to map the colors to indices (unless you want to move into polynomial time).
If we don't know which colors we have beforehand, I think we'll need an aux variable or function to do the mapping in order to do it in one scan. For example, here's a different solution, including the mapping, done in a single pass using an auxiliary dictionary to store the mappings:
i = 0
buckets = [] // solution list of size 500, will be a list of lists
index = {} // aux dict, stores the mappings
for ball in balls:
if ball.color not in index:
index[ball.color] = i
i += 1
buckets.append([color])
else:
buckets[index[ball.color]].append(ball.color)
If you just want counts, and not the actual balls:
i = 0
buckets = [0]*500 // solution list of size 500, a list of ints
index = {} // aux dict, stores the mappings
for ball in balls:
if ball.color not in index:
index[ball.color] = i
i += 1
buckets[index[ball.color]] += 1
You can do it in one pass, just use the auxiliary array as an array of linked lists, and append each ball to its respective linked list as you iterate through the 10,000 balls.
Pseudocode (assuming the aux array is already created as an array of linked lists):
for ball in balls:
aux_array[ball.color].append(ball)
Ah good point, and nice solution.
- gus January 21, 2014