On Sat, May 14, 2011 at 12:55 PM, pacific :-) pacific4...@gmail.com wrote:
Will not a balanced binary tree do the job ? if we will pick the root each
time for the median.
You cannot do it with a vanilla balanced binary tree.
But you can, if you use an augmented tree in the following sense -
capacity to hold and pick the root each time. If the root cannot accomodate
then no other node will be able to accomodate.
On Sat, May 14, 2011 at 1:26 AM, MK stardust...@gmail.com wrote:
Consider the first fit strategy for online bin packing.
So if you have N bins numbered 1, 2, 3..N and you
Consider the first fit strategy for online bin packing.
So if you have N bins numbered 1, 2, 3..N and you are given value V,
you scan them from left to right and insert V into the first bin that
currently has enough capacity.
In the naieve case, N insertions will take O(N^2) time.
How can this
Let there be n elements v1, v2, v3 .. vn
Let S(i,k) mean - Sum k exists in a subset of {v1, v2, v3, ... vi}
At any given time, if solution has not yet been found then :
S(i,k) = S(i-1,k-vi) + vi or no solution exists
We need to find S(n,k)
So in a systematic fashion, solve S(1,1), S(1,2),
2) Design a DS that would do Push(),Pop(), and GetMax() elements at
complexity O(1)
Are you sure you remember this correctly? This would give you a way of
sorting in O(1).
Thanks..
On Thu, Mar 24, 2011 at 12:09 AM, balaji a peshwa.bal...@gmail.com wrote:
The main thing they are testing is
Why is unlock O(log(n)) - Shouldn't it be just O(1) ?
templateint N
struct Node
{
bool isLocked_;
Node *parent_;
Node *children_[N];
};
bool isLocked(NodeN *node)
{
return
Actually, you probably mean that GetMax() does not remove it from the DS?
Sorry for the hasty conclusion.
On Thu, Mar 24, 2011 at 12:11 AM, MK stardust...@gmail.com wrote:
2) Design a DS that would do Push(),Pop(), and GetMax() elements at
complexity O(1)
Are you sure you remember
