nothing special here
BAN USERI'm not really sure where you are going with this, but it appears to be a very brute force. While DP does not need to be recursive, you still appear to check every character for every slot in the NxN character matrix.
- nothing special here December 15, 2013The if/else block appears to be wrong. Ignores all punctuation for the word count.
- nothing special here December 15, 2013I don't understand your restrictions on directions. What's "forward"? Do you mean you can go to the right column? And which "diagonal" are you talking about? All four?
Anyways, I would imagine you could do a modified DFS.
Are you saying to preprocess all of the 2 base values? Seems unnecessary, but I could be misunderstanding.
I suspect your algorithm will be adding unnecessary space. When you pop 2^4, you don't need to add 3^4 until 3^3 has been popped. It's just wasted space. This becomes increasingly a problem when you pop something like 2^8 and having 3^4-3^8 in the heap, too.
I believe the only time you need to add (a+1)^b is when you pop a^2.
This is very similar to Jason's idea, but I didn't preprocess all of the 2^n values.
1) Use a minheap
2) Upon reset (or instantiation), make sure heap is cleared with 4 on the top with {2,2} for m^n as metadata.
3) When next is called, pop the min and add 8 {2,3} and 9 {3,2}
4) Repeat for {m,n+1} when you pop {m,n}. If a {m,2} is popped, then add {m+1,2}
5) For any existing values, push {m,n+2} instead
6) Rinse and repeat for each next().
You have a problem with negative sums, but this would be the O(n^3) solution as stated by Jason.
- nothing special here November 03, 2013Actually, I didn't realize that you could get O(n) until I read some paper on it. Yet another cool use of Suffix Trees.
- nothing special here November 03, 2013Disregarding the errors in your code, why do you have a double boolean array? I'm guessing you're trying to keep a table of the start/stop of your palindromes, but this is beyond scope of the question. Additionally, you don't even take advantage of it. Regardless of your intended use and even though it's a small amount of wasted space, it's still wasted space.
- nothing special here November 03, 2013What if the string has no spaces? This assumes that each word is the candidate rather than a substring of the given string.
- nothing special here November 03, 2013FYI, this is regression analysis using orthogonals. Seems to be a rather difficult question to be answered over the phone if you don't know the math behind it.
- nothing special here November 02, 2013I'm pretty sure this is an exhaustive search for a special case, or the poster misunderstood the original question.
- nothing special here November 02, 2013Appears this solution's running time is O(n^3) with no palindrome found.
- nothing special here November 02, 2013Use two index values to traverse over the string as "the middle values" and then use those index values to sprawl outwards from the middle to the end. You could also just get away with one index value. You just need to be aware of even/odd length palindromes.
For example,
a = {d,a,b,b,a,c}
Here you'll check [i,j] = {0,0} and [i,j] = {0,1}.
Now sprawl outwards from these two indexes. For i=0, you're limited to d since i will be less than 0 when you decrement it. For {0,0}, you'll get d and this will be your max palindrome until you get to {a,b,b,a}.
Progressing through the iterations, you'll eventually get something like [i,j] = {2,2} and {2,3}.
For {2,2}, you won't get a valid search. For {2,3}, you'll get {a,b,b,a}. Note, you'll also get {b,b} within your {2,3} search.
This should be O(N^2) time.
Using a suffix tree would be a poor choice for space.
- nothing special here November 02, 2013I'm assuming you're wanting to traverse the tree until you get to the value matching A[i] and then take its right child. However, once this BST starts to become imbalanced, you'll no longer have O(log n) for searching or inserting. This becomes apparent when the array is already in order.
I suspect you could make it keep balanced and do an in-order search for the next highest value.
This would probably work if peek before you pop. If the current elem is less than your read-in elem, pop the stack. Not sure if you meant to be inclusive in your 'pop until' or not.
- nothing special here November 01, 20131) There's no reason to use a Map. A set would be a better approach.
2) With this recursion algo, you're not saving any time because your map will always be empty until you get to the end of your string and start coming out of your recursion stack. Every word gets placed into the map and every existing word gets overwritten.
This will only work if a[j] is never a zero.
- nothing special here October 23, 2013This is the naive approach. It has O(n^2) time due to the inner for loop.
- nothing special here October 23, 2013You have a few problems with your code, but the biggest one is your associative array solution has a problem with repeated characters.
aab
abb
This would return true. You want to increment/decrement as needed.
This will only work if you make the hashCode method yourself.
- nothing special here October 22, 2013Correct, you could make this constant space if you get rid of the unnecessary array. The only problem would be the overflow, but no solution is really immune that problem.
- nothing special here October 22, 2013I don't see the potential of overlaps in equations made. Are you assuming that the recursion would require to go back to 0 for each product?
Of course, there is problems with this solution as I stated. I went ahead and implemented the recursion. It's been awhile, so let me know if you have concerns or what not.
public static void getIntegers(int[] a, int c, int idx) {
// push down a[i] down to avoid product
// for a[j], this pushes down Pi(j,j)
a[idx-1] = a[idx];
if (idx < ( a.length - 1)) {
getIntegers(a,c*a[idx],idx+1);
// push down Pi(i,j)
a[idx-1] = a[idx]*a[idx-1];
// assign Pi(0,i-1)*Pi(i+1,j)
a[idx] = c*a[idx];
} else {
// assign P(0,j-1)
a[idx] = c;
}
}
Disregarding the typos, you have a few issues
1) Using A[i] within your product increases overflow issues regardless if you use a long
2) Your space doubles (assuming you're given integers).
This is solvable by using recursion in place.
Given the array as below,
idx_1, idx_2....idx_i-1, idx_i, idx_i+1 ... idx_j
You'll need to find the products of Pi(idx_1,idx_i-1) and Pi(idx_i+1,idx_j) for any idx_i. Of course, you have the corner cases of Pi(idx_2,idx_j) and Pi(idx_1,idx_j-1). These are easily solvable with your recursion method input and your recursion method output.
That is, for every call onto the recursion method, you can enter Pi(idx_1,idx_i-1) and when you exit the stack, you can return Pi(idx_i+1,idx_j). Thus,you have both products available for you for idx_i.
This leaves you with O(n) time and O(1) space. However, if you have a huge array of numbers, it can be problematic because of the stack.
The 'easiest' approach would be any type of associative array with the count as the value. This would be O(n) assuming your associative array is long enough to support the keys required for the string. Some data structures give you O(1) for put / get with 'high probability.'
By "first repeating..." I'm assuming you mean the first time a character repeats in the array.
So, if you have {a,b,d,b,e,e,a}
Your answer would be b, which repeats at index 3, not a which appears first at index 0 and again at 6.
In your associative array, you'll have
[ a=6, b=3,d=-1,e=5 ]
If you have a minimal array, you could traverse over that array, but you'll probably not have one. In most cases, you should traverse over the string again and the character with the lowest number for the value would be the answer. In this example, I used -1 to note that the character did not repeat.
EulGam,
- nothing special here December 18, 2013That's generally the problem if you see with DFS if you don't guard against excessive runtime. Some type of memoization would be required or something similar to the marked/seen as with DFS/BFS algorithms.