we can use another stack to store the min/max number in stead of using
pointers in every item. At the time of push, we have to do normal push in
the first stack and in the extra stack, we can check the top value, if it's
greater than the current item, we should push the current item in the extra
st
@Nikhil: The number of valid parenthesizations of n pairs of
parentheses is given by the nth Catalan Number. See
http://en.wikipedia.org/wiki/Catalan_number to validate this
statement. It is the first bullet point in "Applications in
combinatorics." Just let X = "(" and Y = ")".
Furthermore, a sim
we can use recursion to do that. recursively call parent(left, right),
just make sure that left is always less or equal to right
On Sep 30, 2:56 pm, Nikhil Jindal wrote:
> Try this:
>
> Find the number of ways for generating n pairs of valid parenthesis.
> A set of parenthesis is said to be valid
The problem here is more about finding the most optimal solution and not just
solution.
Rgds
Adi
-Original Message-
From: Sathaiah Dontula
Sent: 29/09/2010, 09:25
To: algogeeks@googlegroups.com
Subject: Re: [algogeeks] Algorithm to determine the largest number of envelopes
that can be n
Try this:
Find the number of ways for generating n pairs of valid parenthesis.
A set of parenthesis is said to be valid if at any instant while scanning
from left to right, the number of opening parenthesis are never less than
the number of closing parenthesis.
For ex: for n=3, f(n) = 5
()()(),
Design a hash table to store phone #s. Your job is to write a hash
function that has a parameter username, and generate a key. Username
is unique, length 5 and can be A-Z, 0-9, space. Write a hash function
that generate keys without collisions and use minimum memory.
--
You received this message
@ Minotauraus
*
*
*but here we are not going to find maximum product subarray, we are finding
here the subarray whose product is k.
*
correct me if i am wrong
On Thu, Sep 30, 2010 at 9:35 PM, Minotauraus wrote:
> I guess you could use Kadane's algo replacing addition with
> multiplication.
> htt
Please some one provide link or source code for " Prim's algorithm
using min heap" Am having trouble with the implementation
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.
Saurabh Singh's method is fine. It's even simpler to use a regular
stack of ints, but re-implement push(x) and pop() to do 3 operations
each.
void mm_push(stack s, int x)
{
int min = mm_min(s);
int max = mm_max(s);
push(s, x);
push(s, x < min ? x : min);
push(s, x > max ? x : max);
}
i
Here is a code for solving the problem using DP.
http://codepad.org/AoPtCmwA
On Thu, Sep 30, 2010 at 3:01 AM, Modeling Expert <
cs.modelingexp...@gmail.com> wrote:
> recurssion...
>
> At any point X
>
> val_t getMax( position X){
>
>( ! End of Table )
>sum = GetApples[X] + MAX (
@ Modeling Expert,,thanx
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options,
Ya as minotauraus said it can be approached like a max_subarray problem
but a minor modification
a[i][j] is a SET
define a[i][j] as the possible product ending at i... j is used to indicate
if it was extended from previous window r starting at i...0- for ext 1-for
new start
for every i calcul
I guess you could use Kadane's algo replacing addition with
multiplication.
http://en.wikipedia.org/wiki/Maximum_subarray_problem
On Sep 30, 8:08 am, Abhishek Kumar Singh
wrote:
> How will you find the subarray whose product is k in an array of
> negative and positive numbers
>
> efficient algori
@Divesh,
Can you please check the method present in
Art_of_Programming_Contest_SE_for_uva.pdf for LIS nlogn (nlogk, k is the
size of longest
increasing sequence) page number 129 ?.
(1,2) (2,13) (5,10) (7,9)(9,1)
In this case, longest sequence is of length two and possible solutions are
below,
use array/vector of int to store value. E.g.
if you want to store value : 23451023456678, you can't in a normal int
or long
but You can have int array /vector , say "int A[SIZE] " or "
vector A(SIZE,0)
A[0] 78
A[1] 66
A[2] 45
..
..
I have coded this long back to calculate factorial of big n
recurssion...
At any point X
val_t getMax( position X){
( ! End of Table )
sum = GetApples[X] + MAX ( getMax(X_down) , getMax
( X_right) ) ;
returnn sum ;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to thi
This is the best way currently known-
http://www.cs.utexas.edu/users/moore/best-ideas/mjrty/index.html
On Sep 30, 1:03 am, Christi Massey wrote:
> Q.Assume you have an array A[1:n] of n elements.A majority element of a is
> any element occuring in more than n/2 positions(so if n=6 or n=7, any
> m
since this only allows you to go right or down, the easiest(easy to
understand) way is to draw a binary tree, then you will have a pretty
good view on what you have to do. basically recursion from top going
down(return the end node(bottom) and compare left and right
On Sep 30, 5:27 am, Christi Mas
How will you find the subarray whose product is k in an array of
negative and positive numbers
efficient algorithm is to be considered, it will be better if time
complexity is O(n)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to t
will you plz explain this problen in detail.if possible by designing its
algorithm
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
Top-Down DP = DP implemented recursively with storing and checking the states.
On Thu, Sep 30, 2010 at 2:27 AM, Christi Massey wrote:
> A table composed of N*M cells,each having a certain quantity of apples, is
> given. you start from the upper-left corner. At each step you can go down or
> right
Top-Down DP will work well.
On Thu, Sep 30, 2010 at 2:27 AM, Christi Massey wrote:
> A table composed of N*M cells,each having a certain quantity of apples, is
> given. you start from the upper-left corner. At each step you can go down or
> right one cell.Design an algorithm to find the maximum n
A table composed of N*M cells,each having a certain quantity of apples, is
given. you start from the upper-left corner. At each step you can go down or
right one cell.Design an algorithm to find the maximum number of apples you
can collect ,if you are moving from upper-left corner to bottom-right
c
Q.Can you give the optimal solution to the knapsack instances n=7,
m=15,(p1,p2..p7) = (10,5,15,7,6,18,3) and
(w1,w2.w7)=(2,3,5,7,1,4,1)?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@go
I really liked Rahul's formulation; is it possible to solve a similar
problem of finding Minimum number of envelopes (may be to save some
stamps) to send all the envelopes with the graph representation? Maybe
by using maximum flow to solve "Minimum path cover in directed acyclic
graph", or am I mis
One thing to note is that, this graph is a directed acyclic graph,
since by definition there can be no edge from a smaller or equal sized
envelope to a large one. In this setting it is possible to find the
longest path, by a topological sort and dynamic programming in linear
time O(V+E). Funny thou
Similar to majority voting problem...
Assume there exits a majority element
As only one such element is possible...
Algo:A[1..n]
int Major(A[1..n]){
Majority=a[1];
count=1;
for(i=2;i<=n;i++)
{ if(majority ==a[i])
count++;
else
{ if(count==0)
{ m
Q.an n-vertex graph is a scorpion if it has a vertex of degree one(the
sting)connected to a vertex of degree two(the tail) connected a vertex of
degree n-2(the body) connected to the other n-3 (the feet). some of the feet
may be connected to other feet. Design an algorithm that decides whether a
gi
Q.Assume you have an array A[1:n] of n elements.A majority element of a is
any element occuring in more than n/2 positions(so if n=6 or n=7, any
majority element will occur in at least 4 positions).assume that elements
cannot be ordered or sorted, but can be compared for equality.(you might
think o
@ashuthosh:
MAintaining min and max pointers would mean another way of saying
constant space right?
On Thu, Sep 30, 2010 at 12:17 AM, saurabh singh wrote:
> You will just need to see what is min and max available on the current top
> before push. in case of pop u dnt need to do anything...
>
30 matches
Mail list logo
