Giorgi
BAN USERHey, I'd use hash table with key being user id and value an object like {int count, max_count} then on each new call I'd increase "count" for calling user and update max_count if count became more than it. On hangup I just decrease count. On 24 hour boundary hashtable is dumped and users are billed according to that data. O(n) runtime and O(n) memory I guess :)
- Giorgi March 29, 2011v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
// swap consecutive pairs
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
// swap nibbles ...
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
// swap bytes
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
// swap 2-byte long pairs
v = ( v >> 16 ) | ( v << 16);
Nice idea man, lot space for improvements thou. What we have is sorted arrays of positions we have to search. Now we have to find smallest range of integers in these arrays, so we do it in this manner: Iterate first array from last element to first, and for every index encountered, search element more than this one in next array using binary search. continue this process for all remaining arrays.
Using this search pattern we guarantee that first found solution is the smallest one, i.e. the one we're seeking.
Algorithm: Sort the list with ugly sort algo, bubblesort, it can be done inplace and acces pattern is usable with list. Then, use recurrence: select middle element of this sorted list as root of our bst( O(n) ), and call the same function recursively on left remaining side and right remaining side of lists and set current root's left and right to values returned by these recursive calls. Result is going to be balanced binary search tree.
As for complexity analysis, Memory is log(n) on stack for recursive calls, and performance is O(n^2) for bubblesort and O(n) + 2*(O(n/2)) + 4*(O(n/4))+... = nlogn for actual treefying of sorted list.
please correct me if i'm wrong, i'm actually not sure about treefying time analysis.
Heres the (untested) code
import java.util.concurrent.Semaphore;
class BlockingResourcePool<T>
{
Semaphore semaphore;
T resources[];
boolean acquired[];
public BlockingResourcePool(T resources[])
{
int len = resources.length;
this.resources = resources.clone();
acquired = new boolean[len];
//secnd parameter passed to constructor is fairness, i.e. queue behavior
semaphore = new Semaphore(len, true);
}
public T getResource() throws InterruptedException
{
semaphore.acquire();
T ret = null;
synchronized(this)
{
for(int i = 0; i < acquired.length; i++)
if(acquired[i] == false)
{
ret = resources[i];
acquired[i] = true;
}
}
return ret;
}
public void releaseResource(T resource)
{
if(resource == null)
throw new IllegalArgumentException("Invalid resource specified");
synchronized(this)
{
for(int i = 0; i < acquired.length; i++)
if(resource == resources[i])
{
if(acquired[i] == false)
throw new IllegalArgumentException("Resource was not acquired");
acquired[i] = false;
semaphore.release();
return;
}
}
throw new IllegalArgumentException("Invalid resource specified");
}
}
Well, in that case the algo would be O(N) no more, as in case of input of format you specified, You'd need nlogn time to sort call start time and end time along the timeline. For this case I think the format like
would be better. The satellite would have to log these actions into simple file, each new action would be simply appended to the end of file. Then processing would require traversal of this file from start to end i.e. linear time again :)
- Giorgi March 29, 2011