Cerberuz
BAN USERThere can be atmost 2 elements that appear more than n/3 times.
Suppose given array is A. Use a 2d array of size 2 ( or u can use 4 variables ) -> RES[2][2] which stores the two possible values in R[0][0] and R[1][0]
RES[0][1] -> count of RES[0][0] in array
RES[1][1] -> count of RES[1][0] in array
The trick is if we keep cancelling 3 distinct elements then the remaining one/two final values will be the possible answer ( like for majority element, we keep cancelling two distinct elements )
for each A[i] in A:
if RES[0][1] == 0:
RES[0][0] = A[i]
RES[0][1] = 1
else if RES[0][0] == A[i]:
RES[0][1]++
else if RES[1][1] == 0:
RES[1][0] = A[i]
RES[1][1] = 1
else if RES[1][0] == A[i]:
RES[1][1]++
else
RES[0][1]--
RES[1][1]--
count1 = count2 = 0
for each A[i] in A:
if A[i] == RES[0][0]:
count1++
else if A[i] == RES[1][0]:
count2++
if count1 > size(A)/3:
RES[0][0] is first desired no.
if count2 > size(A)/3:
RES[1][0] is second desired no.
Complexity : O(n)
- Cerberuz December 09, 2012Use an auxiliary stack S. Suppose given preorder traversal array is A[ 1..N ]
Push A[1] in S. Make A[1] as root of BST
For each A[i] :
If A[i] <= S.top():
make A[i] left child of element at the top of stack
else
while S is not empty and A[i] > S.top:
last_top = S.pop()
make A[i] right child of last_top ( last popped element )
push A[i] in S
As each array element is pushed and popped once only => O(N)
- Cerberuz November 29, 2012Your algorithm is O(N^2*lgN) { insertion in map is lgN }
Another approach:
ans = 0
For each point A:
store all possible slopes with the remaining points in an array slopes[]
sort the array slopes[] and now you can easily find the slope with max. occurence in this array i.e ans = MAX( ans, current_max occurence of slope )
ans gives you the final result
This method has same time complexity O(N^2lgN) but will be relatively faster due to much smaller constact factor. You may also try to hash the slopes and then find the max but hashing floating point values will be extra overhead.
- Cerberuz November 29, 20121) Search in four directions from position (i,j) :
right, right-diagonal downwards, down, left-diagonal downwards.
2) Keep track of longest trail of 1's found so far. Also change 1 to 0 as you traverse a cell in matrix so that you dont need to check for that position again.
=> O(n^3)
OR
You can save at position (i,j) four values a,b,c,d:
Longest trail of 1's ending at (i,j) from four directions i.e left, right-diagnoal up, up and left-diagonal up.
temp[i][j].a = mat[i][j] == 1 ? mat[i][j-1]+1 : 0;
temp[i][j].b = mat[i][j] == 1 ? mat[i-1][j-1] + 1 : 0;
temp[i][j].c = mat[i][j] == 1 ? mat[i][j-1] + 1 : 0;
temp[i][j].d = mat[i][j] == 1 ? mat[i-1][j+1] + 1 : 0;
Answer is max( temp[i][j].a, temp[i][j].b, temp[i][j].c, temp[i][j].d ) for all cells (i,j).
=> O(n^2)
Simple O(n) solution with traversal of string.
Keep track of number of characters found so far, if it exceeds or equals k then print the corresponding previously saved character.
char func_kth_char( string s, int k )
{
int i, l, fc, j, n;
l = s.length();
fc = j = 0;
for( i = 1; i < l; j = i++ ) {
n = 0;
while( i < l && s[i] >= '0' && s[i] <= '9' ) {
n = n*10 + (s[i++]-'0');
}
fc += n;
if( fc >= k ) {
return s[j];
}
}
}
Firstly, i am not using array B for storing result ( result is stored inplace in the given array ).
e.g 5,1,3,4,2,7
Initialization : a[0] = minimum of ( a[0] to a[k-1] ) = 1
deque = 3->1 ( insert elements from min element till a[k-1] )
Now proceed from a[3] and fill values from a[1]
deque = 4->3->1 : a[1] = 1
deque = 2 : a[2] = 2
deque = 7->2 : a[3] = 2
I think this can be extended to any number of colors but those nested if conditions ( like that in first if() ) will become very complex and it will be difficult to write accurate solution for large number of colors in single pass of array.
Moreover the constant factor involved in such complex linear time solution will be so large that normal (NlogN)sorting or bucket sort will outperform it.
It is similar, consider 5 ranges :
0 to r0-1 => contains 0
r0 to r1-1=> contains 1
r1 to r2-1 => contains 2
r2 to r3 => values to process
r3+1 to len-1 => contains 3
You just have to make sure these conditions are satisfied after each iteration.
r0 = r1 = r2 = 0;
r3 = size-1;
while( r2 <= r3 ) {
if( a[r2] == 0 ) {
swap( a[r0], a[r2] );
if( r1 <= r0 ) {
r1++;
r2++;
}
r0++;
} else if( a[r2] == 1 ) {
swap( a[r1++], a[r2++] );
} else if( a[r2] == 2 ) {
r2++;
} else {
swap( a[r2], a[r3--] );
}
}
Consider three ranges in the array at any instant :
0 to low-1 => contains 0
low to mid-1 => contains 1
mid to high => values to process
high+1 to len-1 => contains 2
for( low = mid = 0, high = len-1; mid <= high; ) {
a[mid] == 0 ? swap(a[low++], a[mid++]) : a[mid] == 1 ? mid++ : ( swap(a[mid],a[high--]) );
}
- Cerberuz September 14, 2012Little more info from google URL shortener :
The Google URL Shortener provides different functionality based on whether or not you are signed in:
: If you are signed in to goo.gl using a Google Account, a unique short URL is generated each time a long URL is shortened.
: If you are not signed in to goo.gl, the same short URL is reused each time a long URL is shortened, across multiple users
DDOS attack is a different thing, i think the service provider takes care of such things when considering multiple ids for same url ( complete consumption of id space is a rare case, DDOS attack will have to be of huge order and extremely fast to do that ). Moreover i already specified that some sites don't add multiple id's for same url e.g tinyurl while some sites do e.g google url shortener.
- Cerberuz September 13, 2012Everytime when a url is to be shortened, url_id field is incremented, url_id is converted to base-36 ( 26 alphabets + 10 digits ) OR base-62 ( 26 small alphabets + 26 capital alphabets + 10 digits ) which serves as primary key for each tuple. A string i.e. the actual url is added corresponding to this key in database. The primary key is appended to service providers domain name after '/' and returned to the user.
Usually its better to add a new url_id rather than searching for existence of a url in database. So same url can be shortened to multiple short url's.
But some sites do take care of not adding multiple short url's in database if same user try to reproduce it. They consider user location for this purpose.
For each subarray of type a[i-k+1] to a[i] you have to maintain deque such that it contains elements less than equals to a[i] in non increasing order from front.
So in each step you throw out all elements from front which are greater than a[i] and elements from back which are not in current window.
As deque is sorted in non increasing order, minimum element of sub array will always be at its end.
Oh, its more complicated then i thought. So here's improved version:
a) For each white piece check if black king is under attack.
b) If black king is under attack by any white piece x then find
1) if we can kill x using any black piece OR
2) can we block its attacking path( Path blocking will be possible if x is queen, rook or bishop ) OR
3) can we move black king to safe place.
If any of 1,2,3 is possible then there is no checkmate for black.
Perform same steps for white king checkmate.
@eugene.yarovoi, using R-B Tree we can store count of each string directly. This will give O(n*log(n)*log(n)) implementation. If we use hashing for counting, it will give O(n*log(n)) solution. { obviously i am ignoring string lengths in time complexity + overhead of collision avoidance }. So, it won't be better than radix sort but will outperform selection sort.
- Cerberuz September 10, 2012The recursive solution is O(n^3).
The double loop will be called for all x,y <= n => O(n^2) + Inside y loop bfs will be called at least once => O(n)
=> O(n^3)
The way of implementation can be improved to reduce complexity to O(n^2) by avoiding complete double loop run and stopping when whole graph/matrix has been traversed.
"Maximum area rectangle in a histogram" : Standard problem : Linear time solution using stack exists.
- Cerberuz December 11, 2012