CT
BAN USER//return: index age, value count of this age
public static int[] count ( int[] input ) {
int[] count = new int[input[input.length-1]+1];
count ( input, 0, input.length-1, count);
return count;
}
private static void count ( int[] input, int begin, int end, int[] count ) {
if ( input[begin] == input[end] ) {
count[input[begin]] += end-begin+1;
}
else {
count( input, begin, (begin+end)/2, count);
count( input, (begin+end)/2 + 1, end, count);
}
}
Two stocks:
1) Enqueue by pushing into stack 1
2) Dequeue by popping from stack 2
3) ONLY when you dequeue and there is nothing in stack 2, lock both stacks and transfer all from stack 1 to stack 2 by popping-pushing. This is the worst case scenario for dequeue which is O(n) and the worst case scenario for enqueue if it has to wait for such lock. However, amortized time is constant O(1) for both, enqueue and dequeue
Believe it or not, this is useful. For instance, when there is an operation that exists for stock but not for queue. Such as, getting max in constant time.
The thing is, the time complexity gets reduced by simply finding palindrome that start from first character. If we reduce the suffix tree implementation:
1. Create suffix tree from the reverse string (Ukkonen proved this is O(n))
2. Walk this tree from the beginning with the original string until there is path.
This is largest palindrome that starts with beginning. So you need to add [original string length] - [found polyndrome] characters in the front
Excellent solution. It is also important to clarify whether we deal with primitive integer types or the input can be unbound integer. Because if unbound, it will not fit into one CPU operation and squaring itself will not be constant, possible O(i) where i is number to square. Why is this important. Let's say when we talk about complexity of prime factorization problem, we assume unbound numbers that cannot be divided or multiplied in one CPU operation.
- CT November 20, 2014HashMap<String,Histogram> contact2contacts.
Histograms interface:
void countContact(String contact);
List<String> getContacts() // in the order from higher count
On every send and receive email, for each pair of contacts in the same email, get Histogram form HashMap for first and count the second and vice versa.
1. How are you certain you did not pass by optimal solution? Just asking, it is not immediately obvious to me.
2. Knowing Google, they would probably ask something like what if some arrays are much larger than the others. Potentially, smallest can be walked and larger can be binary-search-jumped.
I did not say distinct, sequential, in order. On arbitrary input, amortized time complexity can be assumed. Due to the probability of the resulting subset to consist from one integer in problem 1 and from two integers in problem 2, I suggest that amortized time is O(n) in problem 1 and O(n^2) in problem 2.
If we had random integers and did int mod N, we would have distribution of 1 to N numbers whith N elements. For the 2nd problem it would be distribution of 1 to 2N numbers within N elements. Those are the numbers that you can sum up instead of originals.
1) If you make a simple recursive search, it shoul be O (N) because it is likely that amoung N numbers there will be one that is mod N 0, and if not, it is even more likely to have one with remainder N - x mod N where x any of the other number (so they compliment each other) and so on. So the search must stop in O(N) amortized time.
1.5) Is not asked, but lets say the question about devisability on number much larger than N. Than such search is simply exponential.
2) This one is tough. Each of 2N reminder can be as likely as present as not present. Having subset of one number is 50% likely. Complimenting pair is probably very likely. because if you don't find compliment for one number you are likely to find for another. That's seems like O(n^2).
EDIT: See my comment below, 2nd problem is really O (n log n)
Thank for bringing up movie scheduling problem. The way I see the difference, the movie that starts after other movie starts but finishes before is not conflicting. Therefore I say that we recurse into 3 time intervals: before start, during movie, after movie. With the exception of first step that breaks circle into two. And instead of removing I am interested in the set of segments that begin and end within current sector. You can take a look at my solution. I like yours a lot, just don't understand the need for rotation.
- CT November 09, 2014Recursive procedure:
For each segment s do:
[segment s had broken circle into two sectors, s1 and s2]
run recursive procedure on segment set that fully fit in s1 and similarly with s2, sum them up and plus one for selected one.
Select max sum from for loop and return
Note. in the second recursion and on, selected segment will be breaking current sector into 3 sectors, so sum up from 3 recurcsive procedures.
Time analizes:
T(n) = n * 3T(n/3)
T(1) = 1
n^log n. Which is better than exponentional needed for straight forward solution to coloring problem.
Now, we can enhaunce solution to each sector with caching. There should be O(n^2) of such sectors, so the time complexity should be O(n^2) because all the time solving this we are filling each cache entry and once done, the rest will complete.
divide array into two.
lets say k is end of first half and k+1 is begining of second
find kth largest element and k+1th largest element via quickselect - O(n)
count number of elements bigger than kth in first half and smaller than k+1th in the second - O(n)
multiply them.
Do same thing for each half recursively and add up those products along the way.
Total complexit O(n log n )
For each x and y, fill two matrices. We only want one triangle so it can be optimized into one.
size of matrix side is the amount of points. Enter only what is given. If p1 and p2 p1.x > p2.x enter 1 at position 1,2. less, enter -1. equal 0.
For every filled point, see that if all filled elements on the same row and column >= 1 and current is -1: impossible. Similarly, all are <= 1 and current one 1: impossible
Victor, I disagree. How many births there were on this island in these 20 years? Let's say you answer is 12345. Out of these 12345 births, each had equal 50/50 chance.
When I thought about this problem, I though is there any cooperative strategy to change 50/50. I thought about community that wants to have more boys than girls and decided to give birth untill there is one more boy than a girl - and stop in order not to equalize it. Even this will not help.
I asked this modified problem to not so well educated locksmith who is known to be puzzle lover. He was very uncomfortable with the statement "What is the boy to girl ratio in 20 years" - he said we cannot know because this is just probabilistic. I thought that he is correct, and the more proper question is "What is the most likely boy to girl ratio in 20 years"? He reacted that "most likely boy to girl ratio" is equivalent to "a chance of giving birth to boy vs girl"
Yes, I meant the the same. I don't think it can be that simple because n/2 highest can be all consecutive and this sequence would have to be broken by second after at most in the half of the game. However, perhaps there exist O(n) solution, or less than n^2 for this version of problem interpretation, I would myself be interested to research.
- CT October 29, 2014An idea surfaced that the problem implies that max may mean that first plays to maximize gold but the second, perhaps due to inexperience in the game, inadvertently plays to minimize his/her gold, thus helping the first to achieve his absolute max gold possible by the game rules. If that was the correct interpretation, my solution can be easily modified for this:
public static int maxGold( int[] input ) {
int[] sum = new int[input.length+1];
sum[0] = 0;
for ( int i = 0; i < input.length; i ++) sum[i+1] += sum[i] + input[i];
int[][] takenOnSides2Gold = new int[input.length+1][input.length+1];
for ( int taken = input.length - 1; taken >= 0; taken --) {
for ( int takenFront = 0; takenFront <= taken; takenFront ++) {
int takenEnd = taken - takenFront;
takenOnSides2Gold[takenFront][takenEnd] =
sum[input.length-takenEnd] - sum[takenFront] - //total gold left
( (taken % 2 ==0) ?
Math.min(
takenOnSides2Gold[takenFront+1][takenEnd],
takenOnSides2Gold[takenFront][takenEnd+1]) :
Math.max(
takenOnSides2Gold[takenFront+1][takenEnd],
takenOnSides2Gold[takenFront][takenEnd+1] ) );
}
}
return takenOnSides2Gold[0][0];
}
DP with no recursion:
(If you wonder how comes it does not look like minimax but rather min-min: switch of turn is implied by even or odd number of taken jars or by moving one cell horizontally or vertically)
public static int maxGold( int[] input ) {
int[] sum = new int[input.length+1];
sum[0] = 0;
for ( int i = 0; i < input.length; i ++) sum[i+1] += sum[i] + input[i];
int[][] takenOnSides2Gold = new int[input.length+1][input.length+1];
for ( int taken = input.length - 1; taken >= 0; taken --) {
for ( int takenFront = 0; takenFront <= taken; takenFront ++) {
int takenEnd = taken - takenFront;
takenOnSides2Gold[takenFront][takenEnd] =
sum[input.length-takenEnd] - sum[takenFront] - //total gold left
Math.min( //next move minimizes how much is taken by opponent
takenOnSides2Gold[takenFront+1][takenEnd],
takenOnSides2Gold[takenFront][takenEnd+1]);
}
}
return takenOnSides2Gold[0][0];
}
Full solution:
- CT November 28, 2014