[algogeeks] Re: DP problem

2010-10-22 Thread Anand 
Corrected version: http://codepad.org/wlvIr0Km

On Fri, Oct 22, 2010 at 9:47 PM, Anand  wrote:

> Counting Boolean 
> Parenthesizations.
> You are given a boolean expression consisting of a string of the symbols
> 'true', 'false', 'and', 'or', and 'xor'. Count the number of ways to
> parenthesize the expression such that it will evaluate to true. For example,
> there is only 1 way to parenthesize 'true and false xor true' such that it
> evaluates to true.
>
> http://codepad.org/gCSRe9m8.
>
>
> Is the above logic correct?

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] DP problem

2010-10-22 Thread Anand 
Counting Boolean
Parenthesizations.
You are given a boolean expression consisting of a string of the symbols
'true', 'false', 'and', 'or', and 'xor'. Count the number of ways to
parenthesize the expression such that it will evaluate to true. For example,
there is only 1 way to parenthesize 'true and false xor true' such that it
evaluates to true.

http://codepad.org/gCSRe9m8.


Is the above logic correct?

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: 10 most repeating words

2010-10-22 Thread Dave 
@Ligerdave: Hey, the King James version of the Bible is only about
600,000 words. I use the Bible as an example only because it is a
fairly large book. Maybe we are talking 10 megabytes to store the
whole thing, seeing that there are some long words such as "Maher-
shalal-hash-baz," a name that occurs in Isaiah 8:3. Ten megabytes
hardly seems "large," when compared to the 4 or 8 gigabytes or more of
RAM on many computers. Besides, you don't have to keep all of the text
in memory, but only the distinct words and an integer count of the
number of occurrences. For the King James bible, this is less than
5,000 words, so we're talking a pretty minimal amount of memory. A
hash table might work fine for this, or build a balanced binary tree
of the words. After you have scanned all of the input text and
determined the number of occurrences of each word, it is fairly easy
to scan the word counts and pick out the ten largest.

Dave

On Oct 22, 9:24 am, ligerdave  wrote:
> for a large file, you probably would want to use external sort. kinda
> like a map-reduce concept. it's actually how sort&uniq kinda stuff
> work in unix/linux when you try to find some "TOP X"
>
> again, we are talking about the memory might not hold the entire file
>
> On Oct 21, 9:35 am, "Vinay..."  wrote:
>
>
>
> > how do u find 10 most repeating words on a large file containing words
> > in most efficient way...if it can also be done using heapsort plz post
> > ur answers..- Hide quoted text -
>
> - Show quoted text -

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: how would you find the integer pairs which sum to m in o(n) time complexity

2010-10-22 Thread juver++ 
Iterate over an array and add number to the set (simply set up an
appropriate bit there).
Every time check if there exists in the set number A = m -
currentNumber (check corresponding bit in the bitset).
So the complexity is O(N).
Additional care should be taken for working with negative numbers.
One of the ways to do this is using some Offset, so the number A will
be A + Offset.

On 22 окт, 20:49, Mridul Malpani  wrote:
> if array is not sorted, then how u are solving it in O(n) using
> bitset.
> will u plz explain??
>
> On Oct 22, 9:15špm, "juver++"  wrote:
>
>
>
>
>
>
>
> > You may use C++ bitset. It requires O(Max / 8) bytes for space.
> > If the array is sorted, there is O(n) solution with O(1) space
> > complexity:
> > keep two pointers, left = 0 and right = n - 1;
> > while (l < r) {
> > š int diff = A[l] + A[r] - m;
> > š if (diff > 0) --r;
> > š else if (A[l] + A[r] < 0) ++l;
> > š else break; // found solution
>
> > }
>
> > // check pointers
> > if (l != r) then you found solution, so A[l] + A[r] == m
>
> > On 22 ÏËÔ, 15:32, RIDER  wrote:
>
> > > you have an array of n integers, how would you find the integer pairs
> > > which sum to m? complexity?
>
> > > if we use hash table then should we implement efficient hash table in c
> > > ++?

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Duplicate in an array

2010-10-22 Thread Mridul Malpani 
@ mahesh

i didnt get ur algo. why it will work??
plz expalin..

On Oct 20, 3:49 pm, Mahesh_JNU  wrote:
> Just add the number of the array and let the sum is S. Its complexity is
> O(n).
> Now XOR all elements of the array and say the result is X_SUM.Its complexity
> is  O(n).
> Now the duplicate element is = (S - X_SUM)/2
>
> On Wed, Oct 20, 2010 at 4:14 PM, Asquare  wrote:
> > @Anirvana - In context to the XOR method u suggested, could u plz
> > explain why does it so happen.. ??
>
> > --
> > 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 > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
>    Mahesh Giri

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: how would you find the integer pairs which sum to m in o(n) time complexity

2010-10-22 Thread Mridul Malpani 
if array is not sorted, then how u are solving it in O(n) using
bitset.
will u plz explain??

On Oct 22, 9:15 pm, "juver++"  wrote:
> You may use C++ bitset. It requires O(Max / 8) bytes for space.
> If the array is sorted, there is O(n) solution with O(1) space
> complexity:
> keep two pointers, left = 0 and right = n - 1;
> while (l < r) {
>   int diff = A[l] + A[r] - m;
>   if (diff > 0) --r;
>   else if (A[l] + A[r] < 0) ++l;
>   else break; // found solution
>
> }
>
> // check pointers
> if (l != r) then you found solution, so A[l] + A[r] == m
>
> On 22 окт, 15:32, RIDER  wrote:
>
>
>
> > you have an array of n integers, how would you find the integer pairs
> > which sum to m? complexity?
>
> > if we use hash table then should we implement efficient hash table in c
> > ++?

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: how would you find the integer pairs which sum to m in o(n) time complexity

2010-10-22 Thread juver++ 
You may use C++ bitset. It requires O(Max / 8) bytes for space.
If the array is sorted, there is O(n) solution with O(1) space
complexity:
keep two pointers, left = 0 and right = n - 1;
while (l < r) {
  int diff = A[l] + A[r] - m;
  if (diff > 0) --r;
  else if (A[l] + A[r] < 0) ++l;
  else break; // found solution
}

// check pointers
if (l != r) then you found solution, so A[l] + A[r] == m

On 22 окт, 15:32, RIDER  wrote:
> you have an array of n integers, how would you find the integer pairs
> which sum to m? complexity?
>
> if we use hash table then should we implement efficient hash table in c
> ++?

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Adobe question

2010-10-22 Thread Saurabh Koar 
@Mohit: Rajan clearly sais that array 2 contains all the elements of array1
+ 1 extra element..Your example doesn't do so...By the way the method
suhhested by Rajan is not universal.It is not necessary that array 2 will
contain the same elements as array 1...XOR method will be the best...

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Adobe question

2010-10-22 Thread MOHIT .... 
@rajan

array 1  -> {2,2}
array 2   -> { 4,4,1}

according 2 you .. unique is {(4+4+1)-(2+2)}=5 ? but it is not...

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] how would you find the integer pairs which sum to m in o(n) time complexity

2010-10-22 Thread RIDER 
you have an array of n integers, how would you find the integer pairs
which sum to m? complexity?

if we use hash table then should we implement efficient hash table in c
++?

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Duplicate in an array

2010-10-22 Thread MOHIT .... 
@ dev : i said eariler it work only if max number is less than no of values
in array ...

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Frequent values spoj

2010-10-22 Thread Terence 

http://www.informatik.uni-ulm.de/acm/Locals/2007/output/

On 2010-10-21 18:59, ANUJ KUMAR wrote:

please give me its output file also so that i can check mine

On 10/21/10, ANUJ KUMAR  wrote:

thanks

On 10/21/10, juver++  wrote:

Please have a look at this page:
http://www.informatik.uni-ulm.de/acm/Locals/2007/input/.
It contains input data for the problem.

On 21 окт, 00:39, ANUJ KUMAR  wrote:

i am getting wa forhttps://www.spoj.pl/problems/FREQUENT/
here is my code i have used segment trees it would be great if someone
could give me a test case for which my code gives wa.
Thanks in advance.

 #include
 #include
 #include
 #include
 #include
 #include
 using namespace std;
 int max(int a,int b)
 {
 if(a>b)return a;
 return b;
 }
 int min(int a,int b)
 {
 if(a
 class SegmentTree
 {
  int **A,size;
  public:
  SegmentTree(int N)
  {
   int x = (int)(ceil(log(N)/log(2)));
   size = 2*(int)pow(2,x);
   A = new int*[size];
   for(int x=0;xv1,vectorv2,vectorv3)
  {

   if (start==end)
  {A[node][0] =
v1[start];A[node][2]=v2[start];A[node][3]=v3[start];A[node][1]=-1;}
   else
   {
   int mid = (start+end)/2;
   initialize(2*node,start,mid,v1,v2,v3);
   initialize(2*node+1,mid+1,end,v1,v2,v3);
   if (A[2*node][3]>=
  A[2*node+1][3])
  {A[node][0] = A[2 * node][0];A[node][1] = A[2 *
node][2];A[node][2] = A[2 * node+1][2];A[node][3]=A[2*node][3];}
   else
{A[node][0] = A[2 * node][0];A[node][1] = A[2 *
node][2];A[node][2] = A[2 * node+1][2];A[node][3]=A[2*node+1][3];}
   }
  }
 // void pr()
 // {
 // for(int x=1;xA[node][2] || j=A[node][0])
{int
ss=max(i,A[node][0])-A[node][0];ss=ss+A[node][2]-min(j,A[node][2]);return
(A[node][3]-ss);}
else
{ int id1=-1,id2=-1;
if(i<=A[node][1])
  id1 = query(2*node,i,min(j,A[node][1]));
  if(A[node][1]=id2)
 return id1;
  else
  return id2;
}

  }
 };
 int main()
 {
   int i,j,N;
 int A[16];
 scanf("%d",&N);
 int M;
 scanf("%d",&M);
 for (i=0;iv1;
vectorv2;
vectorv3;
int ini=A[0],now,count=1,ip=0;
for(int x=1;x  s(sz);
 s.initialize(1,0,sz-1,v1,v2,v3);

 for(int x=0;x>tmp;
 return(0);
 }

--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.




--
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Yahoo coding round question

2010-10-22 Thread Kishen Das 
Ok, if you look at the inner loop, it is -

 for ( j = i to j = 0 ) {
 sum[j] +=  A[ i]
 product[j] *= A [ i]
}

This is as good as executing -
sum[i] =   sum [ i ] + A[ i ] ---> ( 1 )
sum[i-1]= sum[i-1]+ A[i]  > ( 2 )
--
---
---
sum[0]  = sum[ 0]+A[i]   --> ( i )

Each of these assignments doesn't have any dependency with other
computations i.e.,
( 1 ) is independent of ( 2 ) to ( i ) and so does ( 2 ) , ( 3 ) ,  ( i
)
and hence each of this can be assigned to a different processor.
So, each of these statements( iterations) of the inner-loop j can be run in
different processors, making it O(1).

I am sorry, if people are still not getting my point !!!
This is the best I can do !!!

Kishen

On Thu, Oct 21, 2010 at 9:08 AM, ligerdave  wrote:

> @Kishen
>
> I don't have much knowledge on parallel computation in OpenCL or CUDA.
> Do you mean parallelised="not have to do the computation at all"?
> did you mean without knowing the boundary of the inner loop which is
> depended on the outer loop, the inner loop would be smart enough to
> figure out the i and j?
>
> On Oct 20, 7:33 pm, Kishen Das  wrote:
> > Well, looks like people are not understanding when I say "run a loop in
> > parallel "!!!
> >
> > Please look at some of the examples on Nvidia website on how computations
> > can be parallelised in OpenCL or CUDA.
> > And also some of the high level programming languages like Scala which is
> > also providing these parallel constructs.
> >
> > If you don't understand GPUs or not familiar with parallel constructs in
> > Java, then my algorithm will definitely look like O ( n ^ 2 ).
> >
> > Kishen
> >
> >
> >
> > On Wed, Oct 20, 2010 at 4:25 PM, ligerdave  wrote:
> > > @Kishen
> > > as long as you have one for loop in another, you wont have O(n). it
> > > will most likely run O(n^2)
> >
> > > On Oct 19, 7:41 pm, Kishen Das  wrote:
> > > > In the below code the jth and kth inner for loops can be run in
> parallel
> > > > making them O(1) and the entire thing O(n).
> >
> > > > for ( i=0 to i=N-1 )
> > > > {
> >
> > > > for ( j = i to j = 0 ) {
> > > > sum[j] +=  A[ i]
> > > > product[j] *= A [ i]
> >
> > > > }
> >
> > > > for( k=0 to k= i )
> > > > if ( sum[k] == S and product[k] == P ) {
> > > > Answer is the sub array A[k to i ]
> > > > break
> >
> > > > }
> > > > }
> >
> > > > Kishen
> >
> > > > On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh <
> iiita2007...@gmail.com
> > > >wrote:
> >
> > > > > @ Rahul patil  ofcourse array may have negative or positive
> integers
> >
> > > > > @ Kishen   both O(n) and O(n logn) solutions was asked in this
> yahoo
> > > coding
> > > > > round question
> >
> > > > > On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh <
> > > > > iiita2007...@gmail.com> wrote:
> >
> > > > >> Given an array of length N. How will you find the minimum length
> > > > >> contiguous sub - array of whose sum is S and whose product is P .
> Here
> > > > >> S and P will be given to you.
> >
> > > > >> --
> > > > >> 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, visit this group at
> > > > >>http://groups.google.com/group/algogeeks?hl=en.
> >
> > > > > --
> > > > > ABHISHEK KUMAR SINGH
> > > > > BTECH (INFORMATION TECHNOLOGY)
> > > > > IIIT ALLAHABAD
> > > > > 9956640538
> >
> > > > > --
> > > > > 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, visit this group at
> > > > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > > --
> > > 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, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> 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, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
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

[algogeeks] Re: 10 most repeating words

2010-10-22 Thread ligerdave 
for a large file, you probably would want to use external sort. kinda
like a map-reduce concept. it's actually how sort&uniq kinda stuff
work in unix/linux when you try to find some "TOP X"

again, we are talking about the memory might not hold the entire file

On Oct 21, 9:35 am, "Vinay..."  wrote:
> how do u find 10 most repeating words on a large file containing words
> in most efficient way...if it can also be done using heapsort plz post
> ur answers..

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: 10 most repeating words

2010-10-22 Thread Vinay... 
can u plz elaborate how min heap helps to find most repeating words

On Oct 21, 6:40 am, ashish agarwal 
wrote:
> use a array of 10 and apply min heap
>
>
>
> On Thu, Oct 21, 2010 at 7:05 PM, Vinay...  wrote:
> > how do u find 10 most repeating words on a large file containing words
> > in most efficient way...if it can also be done using heapsort plz post
> > ur answers..
>
> > --
> > 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 > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.