@Dark prince : what is meant by Allones(i,0.k) what subsquare he is
considering here??
On 22 November 2011 23:57, DarkPrince darkprince...@gmail.com wrote:
It means that the Borders of the mavximum rectangle should hav all 1s
irrespective the elements inside the rectangles , it can be either 0
Exactly. But I think you can get O(n) by using the linear time K-
median selection algorithm (see for example
http://en.wikipedia.org/wiki/Selection_algorithm)
on the distances to the target point.
These kinds of questions where you process all n points every time are
seldom of practical
When i try to solve this
T(n) = 2T(n/2) + 2
recurrence relation i get order N. But
http://www.geeksforgeeks.org/archives/4583
claims that it is 3/2n-2. The order is still N only but how do we get
the constants ?
--
You received this message because you are subscribed to the Google Groups
It's a nice problem, and this solution is almost right.
Process the input in _reverse_ order, which means we'll also generate
output in reverse order.
The invariant is that the stack is a sorted list - highest value on
top - of the strictly descending subsequence of elements seen so far
in
Solution given by tech coder is fine and is working .. I coded it and its
working perfectly using stack
On Wed, Nov 23, 2011 at 2:50 PM, Gene gene.ress...@gmail.com wrote:
It's a nice problem, and this solution is almost right.
Process the input in _reverse_ order, which means we'll also
Here is my code with logic techcoder described ...
void PushSmallerElement(int a[],int n){
stackpairint,int s;
pairint,intp;
int top;
for(int i=0;in;i++){
if(s.empty())
s.push(pairint,int(a[i],i));
else{
p=s.top();
while( !s.empty() a[i]p.first ){
Solving recurrences is an art form. There are many techniques. One
of the simplest is to assume you know the form of the result with some
unknown coefficients. Then plug the form into the recurrence and try
to solve for the coefficients. If you succeed, you're done. If not,
look for another
Thanks. Maybe I'm not reading correctly, but tech coder's algorithm
doesn't mention anything about pairs, which are necessary to obtain
O(n). This is what I meant by almost.
In reverse order, you don't need the pairs. Its simpler.
In a subroutine like yours,
void find_smaller_to_right(int *a,
It's a variation of next greater element problem (
http://www.geeksforgeeks.org/archives/8405). Instead of next greater
element, this problem asks about next smaller element.
On Wed, Nov 23, 2011 at 5:29 PM, Gene gene.ress...@gmail.com wrote:
Thanks. Maybe I'm not reading correctly, but tech
Sorry I forgot to initialize p. It's fixed below.
On Nov 23, 6:59 am, Gene gene.ress...@gmail.com wrote:
Thanks. Maybe I'm not reading correctly, but tech coder's algorithm
doesn't mention anything about pairs, which are necessary to obtain
O(n). This is what I meant by almost.
In reverse
You are given a word and a dictionary. Now propose an algorithm edit
the word (insert / delete characters) minimally to get a word that
also exists in the dictionary. Cost of insertion and deletion is same.
Write pseudocode for it.
Seems like minimum edit distance problem but some modification is
@Gene
Your algo is also right...Just that I followed techcoders logic and coded
the same...pair I used to map the index of the element ..But urs working
fine too :)
On Wed, Nov 23, 2011 at 7:04 PM, Gene gene.ress...@gmail.com wrote:
Sorry I forgot to initialize p. It's fixed below.
On Nov
Thanx Gene. Is there any other method than master's thm ?
On Nov 23, 4:13 pm, Gene gene.ress...@gmail.com wrote:
Solving recurrences is an art form. There are many techniques. One
of the simplest is to assume you know the form of the result with some
unknown coefficients. Then plug the form
There is a binary tree (Not a BST) in which you are given three nodes
X,Y, and Z .Write a function which finds whether y lies in the path b/
w x and z.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
The Masters Thm covers only a certain family of recurrences. There
are many others.
Solving recurrences is comparable to finding analytical solutions to
differential equations except that recurrences aren't as important in
mathematical analysis, so aren't studied as much.
I am not an expert,
yes levenshtein distance and BK tree can be used to solve this.
where edge weight between nodes is equal to levenshtein distance.
On Wed, Nov 23, 2011 at 7:14 PM, abhishek kumar afs.abhis...@gmail.comwrote:
You are given a word and a dictionary. Now propose an algorithm edit
the word (insert
In the given array all the elements occur single time except one element
which occurs 2 times find it in O(n) time and O(1) space.
e.g. 2 3 4 9 3 7
output :3
If such a solution exist can we extend the logic to find All the repeated
elements in an array in O(n) time and O(1) space
--
Only possible best solution seems to be sorting the array using median
selection algorithm ( a varient of quicksort) and then comparing to
find the elements.
Cheers,
Ankit!!!
On Thu, Nov 24, 2011 at 11:32 AM, kumar raja rajkumar.cs...@gmail.com wrote:
In the given array all the elements occur
@ankit : I think ur solution does not work because
if the array is
4 2 8 9 5 1 9
sorting: 1 2 4 5 8 9 9
median is 5 ,but i want 9 as the answer
that to median finding algorithm is O( n logn).
On 23 November 2011 23:09, Ankit Sinha akki12...@gmail.com wrote:
Only possible best solution
On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote:
In the given array all the elements occur single time except one element
which occurs 2 times find it in O(n) time and O(1) space.
e.g. 2 3 4 9 3 7
output :3
If such a solution exist can we extend the logic to find All the
20 matches
Mail list logo
