Cerberuz
BAN USERip = given string
parts = number of ip sections yet to be generated from remaining ip string ( start to end )
sub = saved valid ip formed till previous section
Each ip has 4 sections, each section can have at most 3 digits with maximum value of 255. If k sections are yet to be formed then length of remaining ip string ( start to end ) must be >= 3 and <= 3*k. When all 4 parts have been formed and no remaining characters are there in ip string ( start to end ) then print the valid ip formed ( stored in sub ).
Code : http://ideone.com/ht7al#ul_inouterr
void valid( char *ip, int start, int end, int parts, string sub )
{
if( !parts && start == end+1 ) {
sub.erase( --sub.end() ); //remove last '.'
cout << sub << endl;
return;
}
if( end-start+1 < parts || end-start+1 > 3*parts ) {
return;
}
sub +=ip[start];
valid( ip, start+1, end, parts-1, sub + '.' ); //ip address sub section can be 1 digit
sub += ip[start+1];
valid( ip, start+2, end, parts-1, sub + '.' ); //ip address sub section can be 2 digit
//3 digit ip section must be less than 256
if( (ip[start]-'0')*100 + (ip[start+1]-'0')*10 + (ip[start+2]-'0') < 256 ) {
sub += ip[start+2];
valid( ip, start+3, end, parts-1, sub + '.' ); //ip address sub section can be 3 digit
}
}
Linear time can be achieved by using counting sort ( range of elements should be low ) OR hashing with counting sort.
If you can find a solution of closest pair of point problem in 2D in linear time then you can obtain the solution to this problem ( closest pair in 1D ) also in linear time.
Sort the array.
Initialize l = 0, r = size-1.
In each iteration compare a[l]+a[r] with closest sum to 0 ( min_sum ) found so far and update the min_sum if required.
If a[l]+a[r] < 0 => l++
else => r--
void fsum( int *a, int n )
{
//n = size of array a
sort( a, a+n ); //STL sort
int l, r, al, ar, sum, min_sum;
min_sum = INT_MAX;
for( l = 0, r = n-1; l < r; sum < 0 ? l++ : ( r-- ) ) {
if( abs( sum = a[l]+a[r] ) < abs(min_sum) ) {
min_sum = sum;
al = l;
ar = r;
}
}
print( "%d %d\n", al, ar );
}
Run-way can be treated as a resource with single instance only. Now we can use the concept of mutex ( binary semaphore ).
Maintain a waiting queue of planes ready to take-off or land.
Pick a plane from waiting queue.
If mutex variable == true :
a plane is using run-way for take-off or landing => put the plane in waiting queue
else
set mutex = true
perform take off and landing
set mutex = false
Its a simple core idea, complete design can be built around it considering a multi-threaded environment.
- Cerberuz August 31, 2012While traversing the 2d matrix ( a[][] ) row wise.
If ( a[i][j] == first character of given word ) {
search for rest of the letters in 4 directions i.e. right, right diagonally down, down and left diagonally down.
} else if( a[i][j] == last character of the given word ) {
search for remaining characters in reverse order in 4 directions i.e. left, right diagonally up, up, left diagonally up.
}
As word to match is very small ( ERROR ), so using KMP wont give any significant performance improvement. I think it can be done easily using brute force ( match each character one by one until we find '\n' or word matches, then continue for next line in similar manner ).
- Cerberuz August 28, 2012^that was my comment ( forgot to sign in ) :P
Updated Approach :
Queue ( linked list ) + hash table ( each entry is a linked list ).
Implement queue as linked list. Always save its head and tail pointer.
For each element i inserted in queue add a new node in the hash[i] linked list. This node contains two values i.e. pointer to position of value in queue + pointer to previous element in the queue ( for deletion previous pointer is required ).
Enqueue : O(1) : add at hash[i] a new node with two pointers as explained above + enqueue value in queue ( linked list ) using tail pointer
Dequeue : O(1) : delete in queue using head pointer + remove first node of hash[i]
Search : O(1) : check if hash[i] is NULL or not
Delete any element O(1): first search then delete.
Sorting can solve it in O(nlogn).
If array elements are in definite range ( small enough ), we can store count of each element and traverse the count array to get its second minimum element whose index will be the answer. { O(range of elements) }
Else, we can use appropriate hash table( taking care of collisions ). { O(n) + collision avoidance overhead }
We need a deque with following O(1) operations :
- Cerberuz September 09, 2012push_front(), pop_front(), pop_back()
1) The last element of deque will always hold the minimum element in each step( each step will give minimum for ith subarray ).
2) Element will be inserted in front only.
Suppose you have some elements in deque such that last element is minimum for subarray a[i-k] to a[i-1]. You need to find the minimum for subarray a[i-k+1] to a[i]
a) Pop all elements from front which are greater than a[i]
b) Pop all elements from back which have index less than equals to i-k
c) Push a[i] to front
d) Store last element as minimum of subarray a[i-k+1] to a[i]
Repeat a,b,c,d for all i
As all elements are inserted and deleted once only => O(n)