I've done this before with a deque although I don't remember the
implementation details off my head.
Since a deque allow insertion and removal at both ends what we need to do is
decide which end we starting consuming node and which end we add the queues
of the next level. For every level we
Whats with the intersection point? Intersection of what two things are we
talking about here? Row of 1s and column of 1s?
On Sat, Oct 10, 2009 at 3:47 AM, Manisha pgo...@gmail.com wrote:
There is a n x n grid of 1's and 0's. Find the i, where i is the row
containing all 1's, except the
On another thought, constant time complexity would not be possible with no
constraints on the size of the matrix or any limitation on what possible
data it would have.
It wouldn't be possible to do it in 25 comparisons for a 1 Million x 1
Million grid. If there is no restriction on the data as
The basic idea would be to do push / pop the minimum in stack along with the
push / pop elements. It is like maintaining a parallel stack of minimums. A
naive implementation would involve two stacks. All operations should be O(1)
time complexity.
On Tue, Oct 6, 2009 at 1:31 PM, Manisha
Use a bit-field of M bits to keep track of the presence of X..X+M-1. We can
do 2^32/M passes (if the elements are 32-bit size) to check for numbers in a
range. Depending on the memory footprint and speed the app would want we can
find a soft spot for X.
On Sun, Oct 4, 2009 at 9:39 PM, Amit
We could do in O(log n) space and O(nlog n) time complexity. Traverse once
to find the maximum depth d ~= log n keeping track of the trail upto root
(just as with any recursive traversal). Then traverse d times but visit
nodes at depth d, d-1 ... 1 in each traversal.
We could optimize the
Can we evaluate the logarithm any more efficiently that repeated division by
3?
On Tue, Sep 22, 2009 at 12:27 PM, Dave dave_and_da...@juno.com wrote:
You could compute the logarithm of the number to the base 3 and see if
the result is an integer.
Dave
On Sep 21, 12:22 pm, Anshya Aggarwal
I don't quite get the if possible clause.
But here is what we can do. Have an array C[i] with counts correspondint to
denominations in D[i] (ordered).
From the lowest denomination assign 1 of each until the total doesn't exceed
the required amount. Once that is done, from the highest denomination
Agreed finding the largest is O(n). Finding the largest k will be O(n log
k). Just coz we don't have loops it doesn't mean the op is O(1).
Product of largest 3 does not guarantee largest product! (Take for e.g. -10,
5, 0, -20, 8. The max product is 1600, not 0.
On Wed, Sep 16, 2009 at 2:48 AM,
I am not sure if constant space requirement is possible. But we can do it
with O(k) space complexity.
Maintain a max heap of k elements. For each of the n*m sums add it to the
heap (if it ain't full with k elements) or replace the root and heapify if
the sum is lesser than the root.
Finally the
(k * n).
On Mon, Sep 14, 2009 at 11:19 PM, Anil C R cr.a...@gmail.com wrote:
@dufus
if extracting the kth smallest element would tske O(kn) then extracing the
nth element would take O(n^2) right?
On 9/14/09, Ramaswamy R ramaswam...@gmail.com wrote:
I am not sure if constant space
elements).
Not writing a loop and maintaining k locals would entail the same complexity
if not more.
@Dufus: Does your approach find k largest / smallest elements in O(n) time
and O(1) space complexity?
On Mon, Sep 14, 2009 at 10:49 AM, Ramaswamy R ramaswam...@gmail.com wrote:
We probably missed
The order does not matter! When you keep feeding a max heap with N values
(replacing the root and heapifying if the value is smaller than root) in
this case the sums, you end up with the least k sums encountered. And the
root would be the kth sum in increasing order.
We feel all n*m values and
We probably missed just one case here. All numbers being negative, in which
case the ans would be the product of the greatest 3 negative numbers.
On Sun, Sep 13, 2009 at 10:10 AM, Dave dave_and_da...@juno.com wrote:
The following assumest that n = 5. Find the 3 largest positive
numbers and
Generate the random number 7 times. Sum them all and divide by 5.
Theoritically it should be evenly distributed over 1-7. But owing to random
number generators characteristics the sum of rand(5) called 7 times may not
be perfectly evenly distributed over 1-7.
A nice discussion on some neat options
If you have just two colors then this is possible in O(N). But since the
problem says K colors, this would effectively be sorting of K numbers.
If K is limited (N) then we could use counting sort and such algo's to do
it in near O(N) (with O(K) storage as well). If K can be unlimited and the
input
then this ques cannot be solved in log n
as
i made only 1 change in the whole array of sorted millions number
1,2,3,4,5,6,...,1,10010,1001,110001...
how will u do that ..
On Wed, Sep 2, 2009 at 11:50 PM, Ramaswamy R ramaswam...@gmail.comwrote:
On Tue, Sep 1
It is possible.
This will be a binary search as well. Only instead of matching the value
with the mid value you'd check the following
bool c1 = array[left] array[mid]
bool c2 = array[mid] array[right]
if both the conditions are true then, then the entire range is sorted
if c1 is true and c2 is
On Tue, Sep 1, 2009 at 5:58 AM, ankur aggarwal ankur.mast@gmail.comwrote:
it is a jus a try
i=1,j=2;
while (a[i]a[j])
{
j=i;
i=i*2;
}
now we have i and j and we know that in between these indexes we have a
point z (n as u say) where
Not necessarily. The problem only states
Brute force, pick all combinations and keep track of minimum difference.
Complexity: O(n^2) - (n-1)+(n-2)+(n-3) ... 1
A little better, use any of the O(nlog n) sorting algorithm. In O(n) compare
adjacent pairs and find the minimum difference. Complexity O(nlog n).
On Tue, Sep 1, 2009 at 6:05 AM,
To begin with I find the invariant doesn't hold in the system progressively.
Forget about islock and assume that we only do lock / unlock. Given that a
node cannot be locked if any of its descendants / ancestors is locked. It is
never possible for the tree to enter a state where any of the
is balanced? It wouldn't be O(n log n) if
the tree degenerates into a linked list, would it? So what is your
justification in assuming balance?
Dave
On Aug 30, 6:01 pm, Ramaswamy R ramaswam...@gmail.com wrote:
To begin with I find the invariant doesn't hold in the system
progressively
The following will generate an output like this - 0
0 1
0 1 2
0 1 2 3
0 1 3
0 2 3
0 3
1
1 2
1 2 3
1 3
2
2 3
3
using these indices you can generate from any given set.
class SetGenerator
{
public:
SetGenerator(size_t length)
: LENGTH(length)
{
You just gt generate this pattern of indices into the set -
0
0 1
0 1 2
0 1 2 3
0 1 3
0 2 3
0 3
1
1 2
1 2 3
1 3
2
2 3
3
just figure out the conditions to generate the above yourself ... and you'll
figure out what the code does
On Wed, Aug 26, 2009 at 10:01 PM, Abhijeet Kumar
Bisection and Newton raphson method are a couple of simple way to do it.You
can check up for these on any book on numerical methods.
On Mon, Feb 9, 2009 at 9:42 AM, rakesh sathu rakesh2...@gmail.com wrote:
Can anybody help me for writing code in 'c'-language to find the
square root of a
bottomline - bad code!
The pointer returned by modify() is not guranteed (although it may depending
on compiler implementation) to hold good as the local array goes out of
scope once the function returns!
The output of the 2nd printf is undefined.
On Mon, Jan 5, 2009 at 1:18 PM, tania hamid
Use Depth first search or Breath First Search. As long as it not a graph a
recursive algorithm in either should work easy. If not you'd have to
maintain visited nodes by some means.
If order is not of concern then DFS should be easier. BFS would require
maintaining nodes to be visited although it
Counting sort doesn't work that way. The algo inherently requires O(N)
storage for the counting array which effectively makes the algorithm running
time O(N). If the range of values were known before hand, then the counting
array would be of fixed size thus catering to what you need. But if the
I am not sure of a solution for this, but ain't this an NP-complete problem?
On 6/19/07, ihinayana [EMAIL PROTECTED] wrote:
Description:
Given a group of rectangles with different integer width and
height,such as 5*4, 2*3,1*7,etc. The total number of rectangles is
like 10 or more.The
On 6/14/07, Monu Rathour [EMAIL PROTECTED] wrote:
There are some rectangles and some pin-vertices's in a two dimensional
plane. I have to join pin-vertices's such that lines are rectilinear and
line should not cross over the rectangles.
How to write a mathematical formula for calculating
Write a function strrev(char *str) to reverse the contents of a string
in-place (in case you aint't supposed to use the library function).
//--
void strreverse(char* str)
{
char* end = str;
while( '\0' != *end )
31 matches
Mail list logo
