[algogeeks] Re: Google Interview Question: In how many intervals does a number exists

[Monish Gupta]

Adding to the question. See inline.

On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote:
>
> There are n Intervals. *1 <= n <= 1,000,000.* *Limits of interval are 
> within 64 bit signed int.* Given a set of m numbers, tell in how many 
> intervals does each number exists.
> Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers 2,4,11
> For 2 -> 2 as 2 lies in *2* intervals. viz. [2,3], [1,4]
> For 4 -> 3 as 4 lies in 3 intervals
> For 11 -> 0 as 11 lies in none of the given 4 intervals.
>
> It can be easily done in O(m*n) by traversing n intervals for each number 
> in the given set of m numbers. How would improve this?
>
> Note: I could not fully recall, but I have seen very similar question in 
> codechef but could not find the same.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] Re: Google Interview Question: In how many intervals does a number exists

[Avi Dullu]

Can you tell the 'size' of your array 'f' if the intervals are [0, 10],
[10, 9223372036854775808] ?

Programmers should realize their critical importance and responsibility in
a world gone digital. They are in many ways similar to the priests and
monks of Europe's Dark Ages; they are the only ones with the training and
insight to read and interpret the "scripture" of this age.


On Mon, Jun 10, 2013 at 10:12 PM, sunny  wrote:

> yeah interval tree and binary indexed tree is a one solution which will
> give you answer in log(n) time for each query ,but if i got all the
> interval at the beigning of time i can get solution in O(1) time by O(n
> ) preprocessing take array f initialize with zero,now for each
> interval(l,r) do f[l]++ and f[r+1]--  once you are done wi all queries take
> prefix sum value of each index will tell you in how many interval it was
>
>
> On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote:
>>
>> There are n Intervals. Given a set of m numbers, tell in how many
>> intervals does each number exists.
>> Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11}
>> For 2 -> 1 as 2 lies only in 1 interval [2,3]
>> For 4 -> 3 as 4 lies in 3 intervals
>> For 11 -> 0 as 11 lies in none of the given 4 intervals.
>>
>> It can be easily done in O(m*n) by traversing n intervals for each number
>> in the given set of m numbers. How would improve this?
>>
>> Note: I could not fully recall, but I have seen very similar question in
>> codechef but could not find the same.
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Google Interview Question: In how many intervals does a number exists

[igor.b...@gmail.com]

Monish,  please take a look at a similar problem about poor elephants in 
the neighboring topic started today.  I believe the problem has a similar 
solution.  Each start point increases the no. of active intervals by one; 
each end point decreases it.  So, we do the following:

1. Convert the input array of pairs (BTW, the points don't have to be of an 
integral type!) into the following vector:
{ {2,+1}, {3,-1}, {3, +1}, {4, -1}...}  This takes O(N) time and O(N) 
additional memory

2. Sort the vector by: a) ascending .first; b) descending .second  -- this 
makes sure we count the intervals properly in case multiple intervals start 
and end at the same point.   Complexity is O(N*logN).

3. Convert "relative" counters to "absolute"; complexity is O(N).

int count = 0;
for (int i = 0; i < v.size(); ++i) {
  count += v.second;  
  assert (count >=0);  
  v.second = count;
}
assert (count == 0);

4. After this preparation work ( O(N*logN) time, O(N) memory), answering 
the question about the number of intervals for any numbers takes O(logN) -- 
use lower_bound() to binary search in the sorted vector.


On Sunday, June 9, 2013 3:20:46 AM UTC-4, Monish Gupta wrote:
>
> There are n Intervals. Given a set of m numbers, tell in how many 
> intervals does each number exists.
> Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11}
> For 2 -> 1 as 2 lies only in 1 interval [2,3]
> For 4 -> 3 as 4 lies in 3 intervals
> For 11 -> 0 as 11 lies in none of the given 4 intervals.
>
> It can be easily done in O(m*n) by traversing n intervals for each number 
> in the given set of m numbers. How would improve this?
>
> Note: I could not fully recall, but I have seen very similar question in 
> codechef but could not find the same.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Google Interview Question: In how many intervals does a number exists

[sunny]

typo mistake "take prefix sum of f and see each index value..."continue

On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote:
>
> There are n Intervals. Given a set of m numbers, tell in how many 
> intervals does each number exists.
> Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11}
> For 2 -> 1 as 2 lies only in 1 interval [2,3]
> For 4 -> 3 as 4 lies in 3 intervals
> For 11 -> 0 as 11 lies in none of the given 4 intervals.
>
> It can be easily done in O(m*n) by traversing n intervals for each number 
> in the given set of m numbers. How would improve this?
>
> Note: I could not fully recall, but I have seen very similar question in 
> codechef but could not find the same.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Google Interview Question: In how many intervals does a number exists

[sunny]

yeah interval tree and binary indexed tree is a one solution which will 
give you answer in log(n) time for each query ,but if i got all the 
interval at the beigning of time i can get solution in O(1) time by O(n 
) preprocessing take array f initialize with zero,now for each 
interval(l,r) do f[l]++ and f[r+1]--  once you are done wi all queries take 
prefix sum value of each index will tell you in how many interval it was

On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote:
>
> There are n Intervals. Given a set of m numbers, tell in how many 
> intervals does each number exists.
> Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11}
> For 2 -> 1 as 2 lies only in 1 interval [2,3]
> For 4 -> 3 as 4 lies in 3 intervals
> For 11 -> 0 as 11 lies in none of the given 4 intervals.
>
> It can be easily done in O(m*n) by traversing n intervals for each number 
> in the given set of m numbers. How would improve this?
>
> Note: I could not fully recall, but I have seen very similar question in 
> codechef but could not find the same.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Google Interview Question

[Navneet]

How was your interview? Can you please share the questions for benefit
of others?

On Oct 1, 3:37 pm, Siddhartha Banerjee 
wrote:
> lol!!!

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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: Google Interview Question

[Gene]

This is a well-known problem called "Perfect Shuffle" which has been
discussed here before.  You should be able to find it with a search.

Gene

On Aug 1, 4:15 am, Abhishek Gupta  wrote:
> A is an array of size 2n such that first n elements are integers in any
> order and last n elements are characters.
> i.e. A={i1 i2 i3 in c1 c2 c3... cn}
> then we have to rearrange the elements such that final array is
> A ={ i1 c1 i2 c2 .. in cn}
>
> Example :
> input : A ={ 5,1,4,d,r,a};
> output : A= {5,d,1,r,4,a};
>
> --
> Abhishek Gupta
> MCA
> NIT Calicut
> Kerela

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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: Google Interview Question

[Samba Ganapavarapu]

@Diniz  I guess they asked to do in inplace ( with no extra array )


On Mon, Aug 1, 2011 at 2:41 PM, Douglas Diniz  wrote:

> This is a simple merge, so what is the trick? Did you forget something?
>
> On Mon, Aug 1, 2011 at 3:19 PM, Gary Drocella  wrote:
> > Here is O(n) alg...
> > Does Waste Memory Though :) just don't have an array over 4G, and you
> > should be good.
> >
> > proc Merge_Partition(A)
> >
> > B = {};
> > index = 0;
> > count0 = 0;
> > count1 = (n/2);
> >
> > while index to A.length
> >   B[index++] = A[count0++];
> >   B[index++] = A[count1++];
> > end while
> >
> > return B
> >
> > end proc
> >
> > On Aug 1, 1:30 pm, Manmeet Singh  wrote:
> >> Your code does not works proper;y for all cases
> >>
> >>
> >>
> >>
> >>
> >>
> >>
> >> On Mon, Aug 1, 2011 at 10:42 PM, Rohit jalan 
> wrote:
> >> > Here is the recursive algo:
> >>
> >> > Rearrange(A,p,q)
> >> > 1. if p is not equal to q do the following
> >> > 2. r ← (p+q)/2
> >> > 3. Exchange A[(p+r)/2..r] ←→ A[(p+q)/2 +1 ..(r+q)/2].
> >> > 4. Rearrange(A,p,r)
> >> > 5. Rearrange(A,r+1,q)
> >> > 6. return
> >>
> >> > On Mon, Aug 1, 2011 at 1:45 PM, Abhishek Gupta <
> gupta.abh...@gmail.com>wrote:
> >>
> >> >> A is an array of size 2n such that first n elements are integers in
> any
> >> >> order and last n elements are characters.
> >> >> i.e. A={i1 i2 i3 in c1 c2 c3... cn}
> >> >> then we have to rearrange the elements such that final array is
> >> >> A ={ i1 c1 i2 c2 .. in cn}
> >>
> >> >> Example :
> >> >> input : A ={ 5,1,4,d,r,a};
> >> >> output : A= {5,d,1,r,4,a};
> >>
> >> >> --
> >> >> Abhishek Gupta
> >> >> MCA
> >> >> NIT Calicut
> >> >> Kerela
> >>
> >> >>  --
> >> >> You received this message because you are subscribed to the Google
> Groups
> >> >> "Algorithm Geeks" group.
> >> >> To post to this group, send email to algogeeks@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.
> >>
> >> > --
> >> > Regards :
> >> > ROHIT JALAN
> >> > B.E. Graduate,
> >> > Computer Science Department,
> >> > RVCE, Bangalore
> >>
> >> >  --
> >> > You received this message because you are subscribed to the Google
> Groups
> >> > "Algorithm Geeks" group.
> >> > To post to this group, send email to algogeeks@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 algogeeks@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.
> >
> >
>
>
>
> --
> ---
> Douglas Gameiro Diniz
> Engenheiro de Computação - 2003 - UNICAMP
>
> Mobile: (19) 92158777
> Gtalk: dgdiniz
> Msn: thedougdi...@hotmail.com
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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 algogeeks@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: Google Interview Question

[Douglas Diniz]

This is a simple merge, so what is the trick? Did you forget something?

On Mon, Aug 1, 2011 at 3:19 PM, Gary Drocella  wrote:
> Here is O(n) alg...
> Does Waste Memory Though :) just don't have an array over 4G, and you
> should be good.
>
> proc Merge_Partition(A)
>
> B = {};
> index = 0;
> count0 = 0;
> count1 = (n/2);
>
> while index to A.length
>   B[index++] = A[count0++];
>   B[index++] = A[count1++];
> end while
>
> return B
>
> end proc
>
> On Aug 1, 1:30 pm, Manmeet Singh  wrote:
>> Your code does not works proper;y for all cases
>>
>>
>>
>>
>>
>>
>>
>> On Mon, Aug 1, 2011 at 10:42 PM, Rohit jalan  wrote:
>> > Here is the recursive algo:
>>
>> > Rearrange(A,p,q)
>> > 1. if p is not equal to q do the following
>> > 2. r ← (p+q)/2
>> > 3. Exchange A[(p+r)/2..r] ←→ A[(p+q)/2 +1 ..(r+q)/2].
>> > 4. Rearrange(A,p,r)
>> > 5. Rearrange(A,r+1,q)
>> > 6. return
>>
>> > On Mon, Aug 1, 2011 at 1:45 PM, Abhishek Gupta 
>> > wrote:
>>
>> >> A is an array of size 2n such that first n elements are integers in any
>> >> order and last n elements are characters.
>> >> i.e. A={i1 i2 i3 in c1 c2 c3... cn}
>> >> then we have to rearrange the elements such that final array is
>> >> A ={ i1 c1 i2 c2 .. in cn}
>>
>> >> Example :
>> >> input : A ={ 5,1,4,d,r,a};
>> >> output : A= {5,d,1,r,4,a};
>>
>> >> --
>> >> Abhishek Gupta
>> >> MCA
>> >> NIT Calicut
>> >> Kerela
>>
>> >>  --
>> >> You received this message because you are subscribed to the Google Groups
>> >> "Algorithm Geeks" group.
>> >> To post to this group, send email to algogeeks@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.
>>
>> > --
>> > Regards :
>> > ROHIT JALAN
>> > B.E. Graduate,
>> > Computer Science Department,
>> > RVCE, Bangalore
>>
>> >  --
>> > You received this message because you are subscribed to the Google Groups
>> > "Algorithm Geeks" group.
>> > To post to this group, send email to algogeeks@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 algogeeks@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.
>
>



-- 
---
Douglas Gameiro Diniz
Engenheiro de Computação - 2003 - UNICAMP

Mobile: (19) 92158777
Gtalk: dgdiniz
Msn: thedougdi...@hotmail.com

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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: Google Interview Question

[Gary Drocella]

Here is O(n) alg...
Does Waste Memory Though :) just don't have an array over 4G, and you
should be good.

proc Merge_Partition(A)

B = {};
index = 0;
count0 = 0;
count1 = (n/2);

while index to A.length
   B[index++] = A[count0++];
   B[index++] = A[count1++];
end while

return B

end proc

On Aug 1, 1:30 pm, Manmeet Singh  wrote:
> Your code does not works proper;y for all cases
>
>
>
>
>
>
>
> On Mon, Aug 1, 2011 at 10:42 PM, Rohit jalan  wrote:
> > Here is the recursive algo:
>
> > Rearrange(A,p,q)
> > 1. if p is not equal to q do the following
> > 2. r ← (p+q)/2
> > 3. Exchange A[(p+r)/2..r] ←→ A[(p+q)/2 +1 ..(r+q)/2].
> > 4. Rearrange(A,p,r)
> > 5. Rearrange(A,r+1,q)
> > 6. return
>
> > On Mon, Aug 1, 2011 at 1:45 PM, Abhishek Gupta 
> > wrote:
>
> >> A is an array of size 2n such that first n elements are integers in any
> >> order and last n elements are characters.
> >> i.e. A={i1 i2 i3 in c1 c2 c3... cn}
> >> then we have to rearrange the elements such that final array is
> >> A ={ i1 c1 i2 c2 .. in cn}
>
> >> Example :
> >> input : A ={ 5,1,4,d,r,a};
> >> output : A= {5,d,1,r,4,a};
>
> >> --
> >> Abhishek Gupta
> >> MCA
> >> NIT Calicut
> >> Kerela
>
> >>  --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@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.
>
> > --
> > Regards :
> > ROHIT JALAN
> > B.E. Graduate,
> > Computer Science Department,
> > RVCE, Bangalore
>
> >  --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@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 algogeeks@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: Google interview question

[surender sanke]

@Dave awesome..!

On Sat, Jul 16, 2011 at 7:15 PM, Dave  wrote:

> @Anand: Assuming that the file contains unsigned 32-bit integers. Set
> an integer array a[65536] to zero, read through the file and tally the
> numbers based on their low-order 16 bits: a[j&0x]++. Since 4.3
> billion exceeds 2^32, by the pigeonhole principle, there will be at
> least one tally, say a[k], that has a value greater than 65536. Set
> the array to zero again. Read through the file again. Ignore all of
> the numbers whose low-order 16 bits are not k, and tally numbers based
> on their upper 16 bits: a[(j>>16)&0x]++. Again by the pigeonhole
> principle, there will be at least one number that exceeds 1. Now you
> know the high-order 16 bits and the low-order 16 bits of a number that
> occurs at least twice. You can quit the second pass as soon as you
> have your first tally equalling 2.
>
> Dave
>
> On Jul 15, 8:28 pm, Anand Shastri  wrote:
> > Given a file containing 4,300,000,000  integers, how
> > can you *find **one* that *appears* at *least **twice*
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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 algogeeks@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: Google interview question

[Dave]

@Anand: Assuming that the file contains unsigned 32-bit integers. Set
an integer array a[65536] to zero, read through the file and tally the
numbers based on their low-order 16 bits: a[j&0x]++. Since 4.3
billion exceeds 2^32, by the pigeonhole principle, there will be at
least one tally, say a[k], that has a value greater than 65536. Set
the array to zero again. Read through the file again. Ignore all of
the numbers whose low-order 16 bits are not k, and tally numbers based
on their upper 16 bits: a[(j>>16)&0x]++. Again by the pigeonhole
principle, there will be at least one number that exceeds 1. Now you
know the high-order 16 bits and the low-order 16 bits of a number that
occurs at least twice. You can quit the second pass as soon as you
have your first tally equalling 2.

Dave

On Jul 15, 8:28 pm, Anand Shastri  wrote:
> Given a file containing 4,300,000,000  integers, how
> can you *find **one* that *appears* at *least **twice*

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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: Google interview question

[XYZ]

If the there are problems with hashing method,
What about simply sorting the numbers & then comparing the adjacent numbers 
!

Time complexity O(nlogn)+O(n)=O(nlogn)

Cheers!

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/b2Z_3lJHz9wJ.
To post to this group, send email to algogeeks@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: Google interview question

[Dumanshu]

how about using voters algorithm? TC O(n) and SC O(1)

On Jul 16, 6:28 am, Anand Shastri  wrote:
> Given a file containing 4,300,000,000  integers, how
> can you *find **one* that *appears* at *least **twice*

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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: Google Interview Question

[Wladimir Tavares]

A & B are the concatenation of A and B. Set the following order relation
between the numeric strings
A <= B iff A & B <= B & A

Wladimir Araujo Tavares
*Federal University of Ceará

*




On Sat, May 28, 2011 at 1:54 PM, sunny agrawal wrote:

> @Logic King
> No, My algo will take only O(nlgn) where n is no of elements.
>
> what i mean by editing the comparision function cmp function of sort of
> 
>
> sort(a,a+n, cmp);
>
> where cmp is the comparision function defined in my prev. post
> it will take equal no. of comparision as in sorting. just now overhead of
> comparision is increased.
> instead of just > or <  here it is order of no of digits in a no, which is
> atmost 10 for int or 20 for long ints.
> so O(20*n*lgn)
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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 algogeeks@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: Google Interview Question

[Maksym Melnychok]

so here's oneliner code in ruby:

a.map{|x| x=x*10+1; -x/10.0**Math.log10(x).ceil}.sort.map{|x| 
(-x).to_s[2..-2]}.join

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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: Google Interview Question

[Maksym Melnychok]

here's efficient oneliner without any string manipulation

divide every number by 10^(log10(x).ceil)
sort
convert back to original numbers
join array into string

there are edge-cases where this doesn't work but they can be dealt with 
easily - have to go back to work :)

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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: Google Interview Question

[sunny agrawal]

@sravanreddy001
i don't find any cases for which my algo fails and its O(nlgn)
i may be missing something
can you tell any case where it fails



On Sun, May 29, 2011 at 10:15 PM, sravanreddy001
wrote:

> @vishal,Sanjeev..
> for the inputs 18,187.. apply ur method..
> 18 -- 188
> 187-- 187
>
> 18187 -> ur method
>
> 18718 -> actual
>
> @Sunny...
> i agree that your algorithm takes the *O(N logN)* time.. but again..
> the problem is it* doesn't get* the exact solution.
>
> Do we really have a polynomial solution for this one?
> I think this falls under the NP category.
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>



-- 
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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: Google Interview Question

[sravanreddy001]

@vishal,Sanjeev..
for the inputs 18,187.. apply ur method..
18 -- 188
187-- 187

18187 -> ur method

18718 -> actual

@Sunny...
i agree that your algorithm takes the *O(N logN)* time.. but again..
the problem is it* doesn't get* the exact solution.

Do we really have a polynomial solution for this one?
I think this falls under the NP category.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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: Google Interview Question

[srinivas reddy]

for eg 10, 9
most signifacnt digit of 10 is 1 and 9 is 9
so after sorting based on most significant digit is
10,9
output 910

2nd ex 2,3,5,78
most significant digit is 2,3,5,7
so out put is 78532

On May 29, 12:59 am, Vishal Jain  wrote:
> Can this work...
>
> Lets say I have following numbers
> 8 9 7 4 2 121 23 21 24 27 35 79 2334 6785
>
> Now repeat the last number to make all the number of equal length...
>      1211 2333 2111 2444 2777 3555 7999 2334 6785
>
> Sort the following numbers in descending order.
>   7999  6785 ...
>
> Now merge the numbers based on their actual value.
> 987976785..
>
> I have not testing this entirely, but after seeing solution(Multiplying by
> 10) at top, I though this might work better.
>
> Thanks & Regards
> Vishal Jain
> MNo: +91-9540611889
> Tweet @jainvis
> Blog @ jainvish.blogspot.com
> Success taste better when target achieved is bigger.
>
> P *We have a responsibility to the environment.*
>
> *Before printing this e-mail or any other document, let's ask
> ourselves whether we need a hard copy.*
>
>
>
>
>
>
>
> On Sun, May 29, 2011 at 12:58 PM, Ashish Goel  wrote:
> > Radix/bucket sort..
>
> > won't that help?
>
> > Best Regards
> > Ashish Goel
> > "Think positive and find fuel in failure"
> > +919985813081
> > +919966006652
>
> > On Fri, May 27, 2011 at 7:15 PM,  wrote:
>
> >> how about this case:
>
> >>  9, 100 -> 9100
> >> 100 9
> >> 9100
>
> >>  2, 3, 9, 78 -->
> >>  78 9 3 2
> >> 9 78 3 2
>
> >> I guess solution should be:-
> >> sort the array of numbers in an ascending order and then check for the
> >> first element in the array, if there is any other element greater than it,
> >> shift all the elements one right and place that element in the left most
> >> space.
>
> >> On Fri, May 27, 2011 at 9:37 AM, wujin chen wrote:
>
> >>> @Piyush， how to deal with this case :100 , 10
>
> >>> 2011/5/27 Piyush Sinha 
>
>  we can work out if we sort according to the leftmost integer
>
>  On 5/27/11, adityasir...@gmail.com  wrote:
>  > are you kidding me. Just simple sort wont work.
>
>  > On Fri, May 27, 2011 at 9:31 AM, radha krishnan <
>  > radhakrishnance...@gmail.com> wrote:
>
>  >> sort :)
>
>  >> On Fri, May 27, 2011 at 6:57 PM, ross 
>  wrote:
>
>  >>> Hi all,
>
>  >>> Given an array of elements find the largest possible number that can
>  >>> be formed by using the elements of the array.
>
>  >>> eg: 10 9
>  >>> ans: 910
>
>  >>> 2 3 5 78
>
>  >>> ans: 78532
>
>  >>> 100 9
>
>  >>> ans: 9100
>
>  >>> --
>  >>> You received this message because you are subscribed to the Google
>  Groups
>  >>> "Algorithm Geeks" group.
>  >>> To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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.
>
>  --
>  *Piyush Sinha*
>  *IIIT, Allahabad*
>  *+91-8792136657*
>  *+91-7483122727*
>  *https://www.facebook.com/profile.php?id=10655377926*
>
>  --
>  You received this message because you are subscribed to the Google
>  Groups "Algorithm Geeks" group.
>  To post to this group, send email to algogeeks@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 algogeeks@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 ema

Re: [algogeeks] Re: Google Interview Question

[sunny agrawal]

@Logic King
No, My algo will take only O(nlgn) where n is no of elements.

what i mean by editing the comparision function cmp function of sort of


sort(a,a+n, cmp);

where cmp is the comparision function defined in my prev. post
it will take equal no. of comparision as in sorting. just now overhead of
comparision is increased.
instead of just > or <  here it is order of no of digits in a no, which is
atmost 10 for int or 20 for long ints.
so O(20*n*lgn)
-- 
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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: Google Interview Question

[sanjeev chakravarty]

Here is a Java impl...

public class LargestPossibleNumber {

static class LPNComparator implements Comparator {

@Override
public int compare(String s1, String s2) {

int l1 = s1.length(); // new element
int l2 = s2.length(); // existing element

if (l1 == l2) {
for (int i1 = 0, i2 = 0; i1 < l1 && i2 < l2; i1++, i2++) {
char c1 = s1.charAt(i1);
char c2 = s2.charAt(i2);
if (c1 != c2) {
return c1 - c2;
}
}
return 0;
} else if (l1 < l2) { // padding
StringBuilder s = new StringBuilder(s1);
for (int i = 0; i < l2 - l1; i++) {
s.append(s1.charAt(l1 - 1));
}
s1 = s.toString();
for (int i1 = 0, i2 = 0; i2 < l2; i1++, i2++) {
char c1 = s1.charAt(i1);
char c2 = s2.charAt(i2);
if (c1 != c2) {
return c1 - c2;
}
}
return 1;
} else { // l1 > l2  // padding
StringBuilder s = new StringBuilder(s2);
for (int i = 0; i < l1 - l2; i++) {
s.append(s2.charAt(l2 - 1));
}
s2 = s.toString();
for (int i1 = 0, i2 = 0; i2 < l1; i1++, i2++) {
char c1 = s1.charAt(i1);
char c2 = s2.charAt(i2);
if (c1 != c2) {
return c1 - c2;
}
}
return -1;
}
}
}

public static String getLNP(TreeSet set) {

Iterator iter = set.iterator();
StringBuilder sBuilder = new StringBuilder();
while (iter.hasNext()) {
String element = iter.next();
sBuilder.insert(0, element);
}
return sBuilder.toString();
}

public static void main(String args[]) {

TreeSet set = new TreeSet(new LPNComparator());
 set.add("9"); set.add("10");
 System.out.println(getLNP(set)); //910
 set.clear();set.add("2");set.add("3");set.add("5");set.add("78");
 System.out.println(getLNP(set)); //78532
 set.clear();set.add("10");set.add("100");
 System.out.println(getLNP(set)); //10100 *
 set.clear();set.add("9");set.add("100");
 System.out.println(getLNP(set)); //9100
 set.clear();set.add("2");set.add("3");set.add("9");set.add("78");
 System.out.println(getLNP(set)); //97832
 set.clear();set.add("101");set.add("10");
 System.out.println(getLNP(set)); //10110
 set.clear();set.add("97");set.add("8");set.add("9");
 System.out.println(getLNP(set)); //9978 *

set.clear();set.add("8");set.add("87");set.add("89");
System.out.println(getLNP(set)); // 89887 *
}
}

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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: Google Interview Question

[Dumanshu]

I think he means to edit the comparison function to get the order. so
at a time only 2 elements are compared.

On May 28, 7:51 am, Logic King  wrote:
> @sunny it will work fine if you have 2 numbers only...but what about the
> list...3..4 or 5..or morethen the possible number of combinations will
> be  'N!'...where n is the number of digits...the code will work quite
> slowly for larger 'n'.
>
>
>
>
>
>
>
> On Fri, May 27, 2011 at 3:33 PM, Dave  wrote:
> > @Shubham: Try 8, 89, 7. Your algorithm gives 8897, but the right
> > answer is 8987.
>
> > Dave
>
> > On May 27, 1:11 pm, shubham  wrote:
> > > check whether these steps work:
>
> > > step 1:
> > >         sort the given numbers in the decreasing order based on their
> > first
> > > digit.
> > > step 2:
> > >         if two numbers come out to be equal in the above case & both of
> > > their next digit exist then sort on the basis of their next digit,
> > otherwise
> > > the number
> > >         whose next digit doesnot exist should be placed before the other
> > > number.
> > > step 3:
> > >        concatenate these numbers.
>
> > > e.g.
>
> > > (0,1,10,100) sorting it gives: 1,10,100,0 => 1101000
> > > (97,8,9) sorting gives: 9,97,8 => 9978
>
> > > correct me if i'm wrong.
>
> > > Shubham
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@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 algogeeks@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: Google Interview Question

[Logic King]

@sunny it will work fine if you have 2 numbers only...but what about the
list...3..4 or 5..or morethen the possible number of combinations will
be  'N!'...where n is the number of digits...the code will work quite
slowly for larger 'n'.

On Fri, May 27, 2011 at 3:33 PM, Dave  wrote:

> @Shubham: Try 8, 89, 7. Your algorithm gives 8897, but the right
> answer is 8987.
>
> Dave
>
> On May 27, 1:11 pm, shubham  wrote:
> > check whether these steps work:
> >
> > step 1:
> > sort the given numbers in the decreasing order based on their
> first
> > digit.
> > step 2:
> > if two numbers come out to be equal in the above case & both of
> > their next digit exist then sort on the basis of their next digit,
> otherwise
> > the number
> > whose next digit doesnot exist should be placed before the other
> > number.
> > step 3:
> >concatenate these numbers.
> >
> > e.g.
> >
> > (0,1,10,100) sorting it gives: 1,10,100,0 => 1101000
> > (97,8,9) sorting gives: 9,97,8 => 9978
> >
> > correct me if i'm wrong.
> >
> > Shubham
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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 algogeeks@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: Google Interview Question

[Dave]

@Shubham: Try 8, 89, 7. Your algorithm gives 8897, but the right
answer is 8987.

Dave

On May 27, 1:11 pm, shubham  wrote:
> check whether these steps work:
>
> step 1:
>         sort the given numbers in the decreasing order based on their first
> digit.
> step 2:
>         if two numbers come out to be equal in the above case & both of
> their next digit exist then sort on the basis of their next digit, otherwise
> the number
>         whose next digit doesnot exist should be placed before the other
> number.
> step 3:
>        concatenate these numbers.
>
> e.g.
>
> (0,1,10,100) sorting it gives: 1,10,100,0 => 1101000
> (97,8,9) sorting gives: 9,97,8 => 9978
>
> correct me if i'm wrong.
>
> Shubham

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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: Google Interview Question

[xeron!x]

No, Kadane's algorithm considers subarray sum, we are considering
concatenation ( for whole array ).
The solution with custom string comparator : http://ideone.com/doASH.

On May 27, 9:15 pm, Supraja Jayakumar 
wrote:
> Hi
>
> Isnt this the Kadane's (largest subarray) problem ?
>
> Rgds
> Supraja J
>
> On Fri, May 27, 2011 at 9:41 AM, anshu mishra 
> wrote:
>
>
>
>
>
>
>
>
>
> > @all go through this code
>
> > #include
> > #include
>
> > using namespace std;
> > bool compare(int a, int b)
> > {
> >         string u, v;
> >         u = v = "";
> >         while (a)
> >         {
> >                 u += (a % 10 + '0');
> >                 a/=10;
> >         }
> >         while (b)
> >         {
> >                 v += (b % 10 + '0');
> >                 b/=10;
> >         }
> >         int i = 0, j = 0;
> >         reverse(u.begin(), u.end());
> >         reverse(v.begin(), v.end());
> >         while (i < u.size() || j < v.size())
> >         {
> >                 if (i == u.size()) i = 0;
> >                 if (j == v.size()) j = 0;
> >                 for (; i < u.size() && j < v.size(); i++, j++)
> >                 {
> >                         if (u[i] == v[j]) continue;
> >                         return (u[i] > v[j]);
> >                 }
> >         }
> >         if (u.size() == v.size()) return true;
> > }
> > int main()
> > {
> >         int n;
> >         cin >> n;
> >         int ar[n];
> >         int i;
> >         for (i = 0; i < n; i++)
> >         {
> >                 cin >> ar[i];
> >         }
> >         sort (ar, ar +n, compare);
> >         for (i = 0; i < n; i++) cout << ar[i];
> >         cout << endl;
> >         return 0;
> > }
>
> >  --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.> To post to this group, send email 
> > toalgoge...@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.
>
> --
> U

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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: GOOGLE INTERVIEW QUESTION

[bittu]

@all geeks ..check out the algo & solution with detailed explanation
here

http://shashank7s.blogspot.com/2011/03/wap-to-find-all-possible-palindromes-in.html

let me know if it will fail for any test  cases

Thanks & Regards
Shashank Mani >> " The Best Way To Escape From The problem is Solve
It"
Computer Science & Engg.
BIT Mesra

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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: GOOGLE INTERVIEW QUESTION

[Anders Ma]

take “aabab” for example,  the result is "aba, b,a"; however, the
right result is "aa,bab"

On Wed, May 11, 2011 at 10:57 AM, shubham  wrote:
> check this one out:
>
> #include
> #include
> #include
> #include
> using namespace std;
> int check_palin(string str,int *start)
> {
>    int pos=-1,ret,size=str.size()-1;
>    char last_char=str[size];
>    while(pos    {
>        ret=0;int i;
>        pos=str.find(last_char,pos+1);
>        for(i=0;i<=(size-pos);i++)
>          if(str[i+pos]!=str[size-i]) break;
>        if(i==size-pos+1){(*start)=pos;return (size-pos+1);}
>    }
> }
> int main()
> {
>    string arr;
>    vector palin,str;
>    cin>>arr;str.push_back(arr);
>    while(arr!="")
>    {
>        int s=0,e=0,max=0,start=0,end=0,len;
>        string tmp="";
>        for(int i=0;i        {
>            tmp+=arr[i];
>            len=check_palin(tmp,&s);
>            if(len>max){max=len;start=s;}
>        }
>        tmp=arr.substr(start,max);
>        palin.push_back(tmp);str.pop_back();
>        tmp=arr.substr(0,start);if(tmp!="") str.push_back(tmp);
>        tmp=arr.substr(start+max);if(tmp!="") str.push_back(tmp);
>        if(str.size())arr=str[str.size()-1];else arr="";
>    }
>    for(int i=0;i    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 algogeeks@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.
>
>



-- 
Regards
Anders

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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: GOOGLE INTERVIEW QUESTION

[shubham]

check this one out:

#include
#include
#include
#include
using namespace std;
int check_palin(string str,int *start)
{
int pos=-1,ret,size=str.size()-1;
char last_char=str[size];
while(pos palin,str;
cin>>arr;str.push_back(arr);
while(arr!="")
{
int s=0,e=0,max=0,start=0,end=0,len;
string tmp="";
for(int i=0;imax){max=len;start=s;}
}
tmp=arr.substr(start,max);
palin.push_back(tmp);str.pop_back();
tmp=arr.substr(0,start);if(tmp!="") str.push_back(tmp);
tmp=arr.substr(start+max);if(tmp!="") str.push_back(tmp);
if(str.size())arr=str[str.size()-1];else arr="";
}
for(int i=0;ihttp://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Google Interview Question

[bittu]

@lalit

hi its because whenever we talk about multi-threading we
need to take care of synchronization as the problem clearly says
"application made only single threaded " means not synchronized
otherwise as a programmer its his job to make a app..for multithreaded
environment so that such problem can avoided   simultaneous access of
any segment/part  of this application   causes curruption od
data...let us take a example

Let us assume that two threads T1 and T2 each want to increment the
value of a global integer by one. Ideally, the following sequence of
operations would take place:



   1. Integer i = 0; (memory)
   2. T1 reads the value of i from memory into register1: 0
   3. T1 increments the value of i in register1: (register1 contents)
+ 1 = 1
   4. T1 stores the value of register1 in memory: 1
   5. T2 reads the value of i from memory into register2: 1
   6. T2 increments the value of i in register2: (register2 contents)
+ 1 = 2
   7. T2 stores the value of register2 in memory: 2
   8. Integer i = 2; (memory)

In the case shown above, the final value of i is 2, as expected.
However, if the two threads run simultaneously without locking or
synchronization, the outcome of the operation could be wrong. The
alternative sequence of operations below demonstrates this scenario:

   1. Integer i = 0; (memory)
   2. T1 reads the value of i from memory into register1: 0
   3. T2 reads the value of i from memory into register2: 0
   4. T1 increments the value of i in register1: (register1 contents)
+ 1 = 1
   5. T2 increments the value of i in register2: (register2 contents)
+ 1 = 1
   6. T1 stores the value of register1 in memory: 1
   7. T2 stores the value of register2 in memory: 1
   8. Integer i = 1; (memory)

The final value of i is 1 instead of the expected result of 2.  its
the problem of synchronization..future solution of this problem is  it
is  mutual exclusion..its not ended world computer science..


Hope It Will help You


Thanks & Regards
Shashank Mani Narayan  "Don't Be Evil U Can Earn While U Learn"
Cell No +91-9740852296


-- 
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: Google Interview Question

[LALIT SHARMA]

@bittu

I would like to discuss one thing regarding your approach ,

How you managed to put forward your 1st statement that is of Synchronization
.

On Fri, Jan 7, 2011 at 1:18 PM, Pedro Rezende  wrote:

> Hi all!
> And what could be the best way to test / debug issues like these?
>
> 2011/1/7 vaibhav agrawal 
>
> @Douglas, nicely put!!!
>>
>>
>> On Fri, Jan 7, 2011 at 8:37 PM, Douglas Diniz  wrote:
>>
>>> Some examples, supposing you do always the same thing:
>>>
>>> 1-) You have a program that use some random number, and based on the
>>> number the program do different things, and this different things
>>> crash the program at different places.
>>>
>>> 2-) you have a program that connect with a external server. Depending
>>> on the links status you could crash in different places.
>>>
>>> 3-) You have a program that talk with another program (or external
>>> server) through a protocol, and the protocol could do different things
>>> even if you do the same thing several times.
>>>
>>> 4-) Your program has timeouts that could expire based on the system
>>> usage, crashing the program in different places.
>>>
>>> 5-) Your program read some system variable and do different things.
>>>
>>> 6-) etc
>>>
>>> On Fri, Jan 7, 2011 at 12:09 PM, juver++  wrote:
>>> > The application is single threaded :)
>>> >
>>> > --
>>> > 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 email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Lalit Kishore Sharma

IIIT Allahabad (Amethi Capmus)
6th Sem

-- 
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: Google Interview Question

[Pedro Rezende]

Hi all!
And what could be the best way to test / debug issues like these?

2011/1/7 vaibhav agrawal 

> @Douglas, nicely put!!!
>
>
> On Fri, Jan 7, 2011 at 8:37 PM, Douglas Diniz  wrote:
>
>> Some examples, supposing you do always the same thing:
>>
>> 1-) You have a program that use some random number, and based on the
>> number the program do different things, and this different things
>> crash the program at different places.
>>
>> 2-) you have a program that connect with a external server. Depending
>> on the links status you could crash in different places.
>>
>> 3-) You have a program that talk with another program (or external
>> server) through a protocol, and the protocol could do different things
>> even if you do the same thing several times.
>>
>> 4-) Your program has timeouts that could expire based on the system
>> usage, crashing the program in different places.
>>
>> 5-) Your program read some system variable and do different things.
>>
>> 6-) etc
>>
>> On Fri, Jan 7, 2011 at 12:09 PM, juver++  wrote:
>> > The application is single threaded :)
>> >
>> > --
>> > 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 email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Google Interview Question

[vaibhav agrawal]

@Douglas, nicely put!!!

On Fri, Jan 7, 2011 at 8:37 PM, Douglas Diniz  wrote:

> Some examples, supposing you do always the same thing:
>
> 1-) You have a program that use some random number, and based on the
> number the program do different things, and this different things
> crash the program at different places.
>
> 2-) you have a program that connect with a external server. Depending
> on the links status you could crash in different places.
>
> 3-) You have a program that talk with another program (or external
> server) through a protocol, and the protocol could do different things
> even if you do the same thing several times.
>
> 4-) Your program has timeouts that could expire based on the system
> usage, crashing the program in different places.
>
> 5-) Your program read some system variable and do different things.
>
> 6-) etc
>
> On Fri, Jan 7, 2011 at 12:09 PM, juver++  wrote:
> > The application is single threaded :)
> >
> > --
> > 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.

Re: [algogeeks] Re: Google Interview Question

[Douglas Diniz]

Some examples, supposing you do always the same thing:

1-) You have a program that use some random number, and based on the
number the program do different things, and this different things
crash the program at different places.

2-) you have a program that connect with a external server. Depending
on the links status you could crash in different places.

3-) You have a program that talk with another program (or external
server) through a protocol, and the protocol could do different things
even if you do the same thing several times.

4-) Your program has timeouts that could expire based on the system
usage, crashing the program in different places.

5-) Your program read some system variable and do different things.

6-) etc

On Fri, Jan 7, 2011 at 12:09 PM, juver++  wrote:
> The application is single threaded :)
>
> --
> 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.

[algogeeks] Re: Google Interview Question

[juver++]

The application is single threaded :)

-- 
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: Google Interview Question

[bittu]

After Spending Some Time To Analyze This Problem..I Got Its Non-
Synchronization,Multi Threading Problem..Let Me Describe..-

As The Source Program Build To Single Threaded Environment so When
Multiple User Trying To Access The Same Part of Program at the same
time ,its surely crashes..as Its Not Made Synchronized e.g.
synchronized block or synchronized method which multiple thread trying
to accesscauses crashing of program so of Application.

2 reason .Might The Program/Application Goes Out Of Memory so Stack
Overflow Occurs..

3.Segmentation Fault ...hope every one know it..

4. Possible reasons for memory corruption
|
|-A. stack corruption due to  overflow
|-B. heap corruption  due to  invalid free pointer

I think Its Sufficient for To Think The Interviewer

Correct Me If I am Wrong..


Thanks & Regards
Shashank Mani Narayan  "Don't Be Evil U Can Earn While U Learn"
Cell No +91-9740852296

-- 
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: Google Interview Question

[SM]

Corrupted heap may be the case.

On Jan 6, 8:38 pm, soundar  wrote:
> Maybe the code has lot of dynamic updations..So for each kind of i/
> p there can be different places where the updated value is used.

-- 
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: Google Interview Question

[soundar]

Maybe the code has lot of dynamic updations..So for each kind of i/
p there can be different places where the updated value is used.

-- 
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: Google Interview Question

[suhash]

Sorry my mistake! But the general problem with more than 2 children
possible is more interesting! :)

On Dec 28, 10:58 am, Terence  wrote:
> The description on internal nodes indicates this:
>
> > The value of an "AND" gate node is given by the logical AND of its TWO 
> > children's values.
> > The value of an "OR" gate likewise is given by the logical OR of its TWO 
> > children's values.
>
> On 2010-12-28 13:35, suhash wrote:
>
>
>
>
>
>
>
> > Your approach is for a binary tree, but the problem statement does not
> > say anything about it.
>
> > On Dec 28, 10:27 am, pacific pacific  wrote:
> >> here is my approach :
>
> >> Starting from the root node ,
> >> if root node need to have a 1 ...
> >> if root is an and gate :
> >>       flips  = minflips for left child to have value 1 + minflips for the
> >> right child to have value 1
> >> else
> >>       flips = minimum of ( minflips for left child to have value 1 , 
> >> minflips
> >> for right child to have value 1)
>
> >> For  a leaf node , return 0 if the leaf has the value needed else return
> >> INFINITY.Also if at any internal node if it is not possible return 
> >> INFINITY.
>
> >> On Tue, Dec 28, 2010 at 10:06 AM, Anand  wrote:
> >>> @Terence.
> >>> Could please elaborate your answer. Bottom up level order traversal helps
> >>> to get the final root value but how to use it to find minimum flips needed
> >>> to Obtain the desired root value.
> >>> On Fri, Dec 24, 2010 at 1:56 AM, Terence  wrote:
>  Using the same level order traversal (bottom up), calculating the minimum
>  flips to turn each internal node to given value (0/1).
>  On 2010-12-24 17:19, bittu wrote:
> > Boolean tree problem:
> > Each leaf node has a boolean value associated with it, 1 or 0. In
> > addition, each interior node has either an "AND" or an "OR" gate
> > associated with it. The value of an "AND" gate node is given by the
> > logical AND of its two children's values. The value of an "OR" gate
> > likewise is given by the logical OR of its two children's values. The
> > value of all of the leaf nodes will be given as input so that the
> > value of all nodes can be calculated up the tree.
> > It's easy to find the actual value at the root using level order
> > traversal and a stack(internal if used recursion).
> > Given V as the desired result i.e we want the value calculated at the
> > root to be V(0 or 1) what is the minimum number of gates flip i.e. AND
> > to OR or OR to AND be required at internal nodes to achieve that?
> > Also for each internal node you have boolean associated which tells
> > whether the node can be flipped or not. You are not supposed to flip a
> > non flippable internal node.
> > Regards
> > Shashank Mani Narayan
> > BIT Mesra
>  --
>  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 >>>  .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.

[algogeeks] Re: Google Interview Question

[suhash]

@Terence: I like your explanation. Very short and crisp! :)

On Dec 28, 12:10 pm, Terence  wrote:
> Let cst[i][j] store the cost to flip node i to given gate j (0-'AND',
> 1-'OR').
> Then: cst[i][j] = 0,        if j==gate[i];
>        cst[i][j] = 1,        if j!=gate[i] and ok[i];
>        cst[i][j] = INFINITY, if j!=gate[i] and !ok[i];
>
> 1. To get value 1:
> 1.1 flip current gate to AND, and change all children to 1
> 1.2 flip current gate to OR, and change any child to 1.
> 2. To get value 0:
> 1.1 flip current gate to AND, and change any child to 0
> 1.2 flip current gate to OR, and change all children to 0.
>
> So for internal node i:
>       dp[i][0] = min(cst[i][0]+sum{dp[x][1] for each child x of i},
>                    cst[i][1]+max{dp[x][1] for each child x of i});
>       dp[i][1] = min(cst[i][0]+max{dp[x][0] for each child x of i},
>                    cst[i][1]+sum{dp[x][0] for each child x of i});
>     for leaf i:
>       dp[i][j] = (value[i]==j ? 0 : INFINITY)
>
> On 2010-12-28 13:32, suhash wrote:
>
>
>
>
>
>
>
> > This problem can be solved using dp in O(n), where 'n' is the number
> > of nodes in the tree.
> > Definitions:
> > Let gate[i] be a boolean denoting whether the gate at node 'i' is
> > 'AND' or 'OR'. (0-'AND' 1-'OR')
> > Let dp[i][j] store the minimum no. of swaps required to get a value of
> > 'j' (0 or 1), for the subtree rooted at 'i'.
> > Let ok[i] be a boolean which denotes whether a flip operation can be
> > performed at the i'th node or not.
> > Let i1,i2,i3.ik be the children of node 'i'
>
> > Now we have 2 cases:
> > case 1: ok[i] = 0 (means no flipping possible at node 'i')
> >              In this, we have many cases:
> >              case 1.1: gate[i]=0 (there is an AND gate at node 'i'),
> > and j=1
> >                             this means all children should have a value
> > 1.
> >                             hence dp[i][j]=dp[i1][j]+dp[i2][j]
> > +.dp[ik][j]
> >              case 1.2: gate[i]=0 (there is an AND gate at node 'i'),
> > and j=0
> >                             i will discuss this case in the end.
> >              case 1.3: gate[i]=1 (there is an OR gate at node 'i'), and
> > j=1
> >                             this one too, for the end
> >              case 1.4: gate[i]=1 (there is an OR gate at node 'i'), and
> > j=0
> >                             this means all children should have a value
> > 0.
> >                             hence dp[i][j]=dp[i1][j]+dp[i2][j]
> > +.dp[ik][j]
>
> > case 2: ok[i] = 1 (means flipping is possible at node 'i')
> >              We have 2 cases in this:
> >              case 2.1: we choose not to flip gate at node 'i'. This
> > reduces to the 4 cases above(case 1.1, 1.2, 1.3, 1.4)
> >              case 2.2: we choose to flip gate 'i'. Again it is similar
> > to cases discussed above, except replacing 'AND' by 'OR' and vice
> > versa
> >                             and dp[i][j]=1 + dp[i1][j]+dp[i2][j]
> > +.dp[ik][j]
>
> > Note: 1)Boundary cases for leaf nodes.
> >           2)Top down is easier.
> >           3)If it is impossible to get a value 'j' for subtree rooted
> > at 'i', then dp[i][j]=INF(some large value)
> >           4)Answer is dp[root][required_value(o or 1)]. If this
> > quantity is INF, then it is impossible to achieve this.
>
> > Now, lets discuss case 1.2:
> > We have an 'AND' gate and we want a result of 0.
> > So, atleast one of the children of node 'i' should be 0.
> > Now create 2 arrays x,y each of size 'k'
> > x[1]=dp[i1][0], y[1]=dp[i1][1]
> > x[2]=dp[i2][0], y[2]=dp[i2][1]
> > .
> > .
> > .
> > x[k]=dp[ik][0], y[k]=dp[ik][1]
>
> > Now, let v=min(x[1],x[2],x[3],.x[k]), and 'h' be the index of the
> > minimum element(x[h] is minimum)
> > Then, dp[i][j]=v+sigma(f!=h)[min(x[f],y[f])]
>
> > The other cases are similar to this!
> > I can write a code and send if you have doubts.
>
> > On Dec 28, 9:36 am, Anand  wrote:
> >> @Terence.
>
> >> Could please elaborate your answer. Bottom up level order traversal helps 
> >> to
> >> get the final root value but how to use it to find minimum flips needed to
> >> Obtain the desired root value.
>
> >> On Fri, Dec 24, 2010 at 1:56 AM, Terence  wrote:
> >>> Using the same level order traversal (bottom up), calculating the minimum
> >>> flips to turn each internal node to given value (0/1).
> >>> On 2010-12-24 17:19, bittu wrote:
>  Boolean tree problem:
>  Each leaf node has a boolean value associated with it, 1 or 0. In
>  addition, each interior node has either an "AND" or an "OR" gate
>  associated with it. The value of an "AND" gate node is given by the
>  logical AND of its two children's values. The value of an "OR" gate
>  likewise is given by the logical OR of its two children's values. The
>  value of all of the leaf nodes will be given as input so that the
>  value of all nodes can be calculated up the tree.
>  It's easy to find the actual value at the root using level order
>  traversal

Re: [algogeeks] Re: Google Interview Question

[Terence]

Let cst[i][j] store the cost to flip node i to given gate j (0-'AND', 
1-'OR').

Then: cst[i][j] = 0,if j==gate[i];
  cst[i][j] = 1,if j!=gate[i] and ok[i];
  cst[i][j] = INFINITY, if j!=gate[i] and !ok[i];

1. To get value 1:
1.1 flip current gate to AND, and change all children to 1
1.2 flip current gate to OR, and change any child to 1.
2. To get value 0:
1.1 flip current gate to AND, and change any child to 0
1.2 flip current gate to OR, and change all children to 0.

So for internal node i:
 dp[i][0] = min(cst[i][0]+sum{dp[x][1] for each child x of i},
  cst[i][1]+max{dp[x][1] for each child x of i});
 dp[i][1] = min(cst[i][0]+max{dp[x][0] for each child x of i},
  cst[i][1]+sum{dp[x][0] for each child x of i});
   for leaf i:
 dp[i][j] = (value[i]==j ? 0 : INFINITY)


On 2010-12-28 13:32, suhash wrote:

This problem can be solved using dp in O(n), where 'n' is the number
of nodes in the tree.
Definitions:
Let gate[i] be a boolean denoting whether the gate at node 'i' is
'AND' or 'OR'. (0-'AND' 1-'OR')
Let dp[i][j] store the minimum no. of swaps required to get a value of
'j' (0 or 1), for the subtree rooted at 'i'.
Let ok[i] be a boolean which denotes whether a flip operation can be
performed at the i'th node or not.
Let i1,i2,i3.ik be the children of node 'i'

Now we have 2 cases:
case 1: ok[i] = 0 (means no flipping possible at node 'i')
 In this, we have many cases:
 case 1.1: gate[i]=0 (there is an AND gate at node 'i'),
and j=1
this means all children should have a value
1.
hence dp[i][j]=dp[i1][j]+dp[i2][j]
+.dp[ik][j]
 case 1.2: gate[i]=0 (there is an AND gate at node 'i'),
and j=0
i will discuss this case in the end.
 case 1.3: gate[i]=1 (there is an OR gate at node 'i'), and
j=1
this one too, for the end
 case 1.4: gate[i]=1 (there is an OR gate at node 'i'), and
j=0
this means all children should have a value
0.
hence dp[i][j]=dp[i1][j]+dp[i2][j]
+.dp[ik][j]

case 2: ok[i] = 1 (means flipping is possible at node 'i')
 We have 2 cases in this:
 case 2.1: we choose not to flip gate at node 'i'. This
reduces to the 4 cases above(case 1.1, 1.2, 1.3, 1.4)
 case 2.2: we choose to flip gate 'i'. Again it is similar
to cases discussed above, except replacing 'AND' by 'OR' and vice
versa
and dp[i][j]=1 + dp[i1][j]+dp[i2][j]
+.dp[ik][j]

Note: 1)Boundary cases for leaf nodes.
  2)Top down is easier.
  3)If it is impossible to get a value 'j' for subtree rooted
at 'i', then dp[i][j]=INF(some large value)
  4)Answer is dp[root][required_value(o or 1)]. If this
quantity is INF, then it is impossible to achieve this.

Now, lets discuss case 1.2:
We have an 'AND' gate and we want a result of 0.
So, atleast one of the children of node 'i' should be 0.
Now create 2 arrays x,y each of size 'k'
x[1]=dp[i1][0], y[1]=dp[i1][1]
x[2]=dp[i2][0], y[2]=dp[i2][1]
.
.
.
x[k]=dp[ik][0], y[k]=dp[ik][1]

Now, let v=min(x[1],x[2],x[3],.x[k]), and 'h' be the index of the
minimum element(x[h] is minimum)
Then, dp[i][j]=v+sigma(f!=h)[min(x[f],y[f])]

The other cases are similar to this!
I can write a code and send if you have doubts.

On Dec 28, 9:36 am, Anand  wrote:

@Terence.

Could please elaborate your answer. Bottom up level order traversal helps to
get the final root value but how to use it to find minimum flips needed to
Obtain the desired root value.

On Fri, Dec 24, 2010 at 1:56 AM, Terence  wrote:

Using the same level order traversal (bottom up), calculating the minimum
flips to turn each internal node to given value (0/1).
On 2010-12-24 17:19, bittu wrote:

Boolean tree problem:
Each leaf node has a boolean value associated with it, 1 or 0. In
addition, each interior node has either an "AND" or an "OR" gate
associated with it. The value of an "AND" gate node is given by the
logical AND of its two children's values. The value of an "OR" gate
likewise is given by the logical OR of its two children's values. The
value of all of the leaf nodes will be given as input so that the
value of all nodes can be calculated up the tree.
It's easy to find the actual value at the root using level order
traversal and a stack(internal if used recursion).
Given V as the desired result i.e we want the value calculated at the
root to be V(0 or 1) what is the minimum number of gates flip i.e. AND
to OR or OR to AND be required at internal nodes to achieve that?
Also for each internal node you have boolean associated which tells
whether the node can be flipped or not. You are not supposed to flip a
non flippable internal node.
Regards
Shashank Mani Narayan
BIT Mesra

--
You received this message because you are subscribed to the Google Gr

Re: [algogeeks] Re: Google Interview Question

[Terence]

The description on internal nodes indicates this:

The value of an "AND" gate node is given by the logical AND of its TWO 
children's values.
The value of an "OR" gate likewise is given by the logical OR of its TWO 
children's values.


On 2010-12-28 13:35, suhash wrote:

Your approach is for a binary tree, but the problem statement does not
say anything about it.

On Dec 28, 10:27 am, pacific pacific  wrote:

here is my approach :

Starting from the root node ,
if root node need to have a 1 ...
if root is an and gate :
  flips  = minflips for left child to have value 1 + minflips for the
right child to have value 1
else
  flips = minimum of ( minflips for left child to have value 1 , minflips
for right child to have value 1)

For  a leaf node , return 0 if the leaf has the value needed else return
INFINITY.Also if at any internal node if it is not possible return INFINITY.

On Tue, Dec 28, 2010 at 10:06 AM, Anand  wrote:

@Terence.
Could please elaborate your answer. Bottom up level order traversal helps
to get the final root value but how to use it to find minimum flips needed
to Obtain the desired root value.
On Fri, Dec 24, 2010 at 1:56 AM, Terence  wrote:

Using the same level order traversal (bottom up), calculating the minimum
flips to turn each internal node to given value (0/1).
On 2010-12-24 17:19, bittu wrote:

Boolean tree problem:
Each leaf node has a boolean value associated with it, 1 or 0. In
addition, each interior node has either an "AND" or an "OR" gate
associated with it. The value of an "AND" gate node is given by the
logical AND of its two children's values. The value of an "OR" gate
likewise is given by the logical OR of its two children's values. The
value of all of the leaf nodes will be given as input so that the
value of all nodes can be calculated up the tree.
It's easy to find the actual value at the root using level order
traversal and a stack(internal if used recursion).
Given V as the desired result i.e we want the value calculated at the
root to be V(0 or 1) what is the minimum number of gates flip i.e. AND
to OR or OR to AND be required at internal nodes to achieve that?
Also for each internal node you have boolean associated which tells
whether the node can be flipped or not. You are not supposed to flip a
non flippable internal node.
Regards
Shashank Mani Narayan
BIT Mesra

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

[algogeeks] Re: Google Interview Question

[suhash]

Btw...another observation in case 1.2:

I wrote:
Now, let v=min(x[1],x[2],x[3],.x[k]), and 'h' be the index of the
minimum element(x[h] is minimum)
Then, dp[i][j]=v+sigma(f!=h)[min(x[f],y[f])]

Here, just setting dp[i][j]=v will do (athough the complexity is same
in both the cases)
because for all (f!=h), atleast one of x[f], y[f] will be 0. (by not
performing any swaps, and just evaluating the value at the node)

hence dp[i][j]=min(x[1],x[2],x[3],.x[k])

On Dec 28, 10:32 am, suhash  wrote:
> This problem can be solved using dp in O(n), where 'n' is the number
> of nodes in the tree.
> Definitions:
> Let gate[i] be a boolean denoting whether the gate at node 'i' is
> 'AND' or 'OR'. (0-'AND' 1-'OR')
> Let dp[i][j] store the minimum no. of swaps required to get a value of
> 'j' (0 or 1), for the subtree rooted at 'i'.
> Let ok[i] be a boolean which denotes whether a flip operation can be
> performed at the i'th node or not.
> Let i1,i2,i3.ik be the children of node 'i'
>
> Now we have 2 cases:
> case 1: ok[i] = 0 (means no flipping possible at node 'i')
>             In this, we have many cases:
>             case 1.1: gate[i]=0 (there is an AND gate at node 'i'),
> and j=1
>                            this means all children should have a value
> 1.
>                            hence dp[i][j]=dp[i1][j]+dp[i2][j]
> +.dp[ik][j]
>             case 1.2: gate[i]=0 (there is an AND gate at node 'i'),
> and j=0
>                            i will discuss this case in the end.
>             case 1.3: gate[i]=1 (there is an OR gate at node 'i'), and
> j=1
>                            this one too, for the end
>             case 1.4: gate[i]=1 (there is an OR gate at node 'i'), and
> j=0
>                            this means all children should have a value
> 0.
>                            hence dp[i][j]=dp[i1][j]+dp[i2][j]
> +.dp[ik][j]
>
> case 2: ok[i] = 1 (means flipping is possible at node 'i')
>             We have 2 cases in this:
>             case 2.1: we choose not to flip gate at node 'i'. This
> reduces to the 4 cases above(case 1.1, 1.2, 1.3, 1.4)
>             case 2.2: we choose to flip gate 'i'. Again it is similar
> to cases discussed above, except replacing 'AND' by 'OR' and vice
> versa
>                            and dp[i][j]=1 + dp[i1][j]+dp[i2][j]
> +.dp[ik][j]
>
> Note: 1)Boundary cases for leaf nodes.
>          2)Top down is easier.
>          3)If it is impossible to get a value 'j' for subtree rooted
> at 'i', then dp[i][j]=INF(some large value)
>          4)Answer is dp[root][required_value(o or 1)]. If this
> quantity is INF, then it is impossible to achieve this.
>
> Now, lets discuss case 1.2:
> We have an 'AND' gate and we want a result of 0.
> So, atleast one of the children of node 'i' should be 0.
> Now create 2 arrays x,y each of size 'k'
> x[1]=dp[i1][0], y[1]=dp[i1][1]
> x[2]=dp[i2][0], y[2]=dp[i2][1]
> .
> .
> .
> x[k]=dp[ik][0], y[k]=dp[ik][1]
>
> Now, let v=min(x[1],x[2],x[3],.x[k]), and 'h' be the index of the
> minimum element(x[h] is minimum)
> Then, dp[i][j]=v+sigma(f!=h)[min(x[f],y[f])]
>
> The other cases are similar to this!
> I can write a code and send if you have doubts.
>
> On Dec 28, 9:36 am, Anand  wrote:
>
> > @Terence.
>
> > Could please elaborate your answer. Bottom up level order traversal helps to
> > get the final root value but how to use it to find minimum flips needed to
> > Obtain the desired root value.
>
> > On Fri, Dec 24, 2010 at 1:56 AM, Terence  wrote:
> > > Using the same level order traversal (bottom up), calculating the minimum
> > > flips to turn each internal node to given value (0/1).
>
> > > On 2010-12-24 17:19, bittu wrote:
>
> > >> Boolean tree problem:
>
> > >> Each leaf node has a boolean value associated with it, 1 or 0. In
> > >> addition, each interior node has either an "AND" or an "OR" gate
> > >> associated with it. The value of an "AND" gate node is given by the
> > >> logical AND of its two children's values. The value of an "OR" gate
> > >> likewise is given by the logical OR of its two children's values. The
> > >> value of all of the leaf nodes will be given as input so that the
> > >> value of all nodes can be calculated up the tree.
> > >> It's easy to find the actual value at the root using level order
> > >> traversal and a stack(internal if used recursion).
>
> > >> Given V as the desired result i.e we want the value calculated at the
> > >> root to be V(0 or 1) what is the minimum number of gates flip i.e. AND
> > >> to OR or OR to AND be required at internal nodes to achieve that?
>
> > >> Also for each internal node you have boolean associated which tells
> > >> whether the node can be flipped or not. You are not supposed to flip a
> > >> non flippable internal node.
>
> > >> Regards
> > >> Shashank Mani Narayan
> > >> BIT Mesra
>
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email

[algogeeks] Re: Google Interview Question

[suhash]

Your approach is for a binary tree, but the problem statement does not
say anything about it.

On Dec 28, 10:27 am, pacific pacific  wrote:
> here is my approach :
>
> Starting from the root node ,
> if root node need to have a 1 ...
> if root is an and gate :
>      flips  = minflips for left child to have value 1 + minflips for the
> right child to have value 1
> else
>      flips = minimum of ( minflips for left child to have value 1 , minflips
> for right child to have value 1)
>
> For  a leaf node , return 0 if the leaf has the value needed else return
> INFINITY.Also if at any internal node if it is not possible return INFINITY.
>
> On Tue, Dec 28, 2010 at 10:06 AM, Anand  wrote:
> > @Terence.
>
> > Could please elaborate your answer. Bottom up level order traversal helps
> > to get the final root value but how to use it to find minimum flips needed
> > to Obtain the desired root value.
>
> > On Fri, Dec 24, 2010 at 1:56 AM, Terence  wrote:
>
> >> Using the same level order traversal (bottom up), calculating the minimum
> >> flips to turn each internal node to given value (0/1).
>
> >> On 2010-12-24 17:19, bittu wrote:
>
> >>> Boolean tree problem:
>
> >>> Each leaf node has a boolean value associated with it, 1 or 0. In
> >>> addition, each interior node has either an "AND" or an "OR" gate
> >>> associated with it. The value of an "AND" gate node is given by the
> >>> logical AND of its two children's values. The value of an "OR" gate
> >>> likewise is given by the logical OR of its two children's values. The
> >>> value of all of the leaf nodes will be given as input so that the
> >>> value of all nodes can be calculated up the tree.
> >>> It's easy to find the actual value at the root using level order
> >>> traversal and a stack(internal if used recursion).
>
> >>> Given V as the desired result i.e we want the value calculated at the
> >>> root to be V(0 or 1) what is the minimum number of gates flip i.e. AND
> >>> to OR or OR to AND be required at internal nodes to achieve that?
>
> >>> Also for each internal node you have boolean associated which tells
> >>> whether the node can be flipped or not. You are not supposed to flip a
> >>> non flippable internal node.
>
> >>> Regards
> >>> Shashank Mani Narayan
> >>> BIT Mesra
>
> >> --
> >> 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.

[algogeeks] Re: Google Interview Question

[suhash]

This problem can be solved using dp in O(n), where 'n' is the number
of nodes in the tree.
Definitions:
Let gate[i] be a boolean denoting whether the gate at node 'i' is
'AND' or 'OR'. (0-'AND' 1-'OR')
Let dp[i][j] store the minimum no. of swaps required to get a value of
'j' (0 or 1), for the subtree rooted at 'i'.
Let ok[i] be a boolean which denotes whether a flip operation can be
performed at the i'th node or not.
Let i1,i2,i3.ik be the children of node 'i'

Now we have 2 cases:
case 1: ok[i] = 0 (means no flipping possible at node 'i')
In this, we have many cases:
case 1.1: gate[i]=0 (there is an AND gate at node 'i'),
and j=1
   this means all children should have a value
1.
   hence dp[i][j]=dp[i1][j]+dp[i2][j]
+.dp[ik][j]
case 1.2: gate[i]=0 (there is an AND gate at node 'i'),
and j=0
   i will discuss this case in the end.
case 1.3: gate[i]=1 (there is an OR gate at node 'i'), and
j=1
   this one too, for the end
case 1.4: gate[i]=1 (there is an OR gate at node 'i'), and
j=0
   this means all children should have a value
0.
   hence dp[i][j]=dp[i1][j]+dp[i2][j]
+.dp[ik][j]

case 2: ok[i] = 1 (means flipping is possible at node 'i')
We have 2 cases in this:
case 2.1: we choose not to flip gate at node 'i'. This
reduces to the 4 cases above(case 1.1, 1.2, 1.3, 1.4)
case 2.2: we choose to flip gate 'i'. Again it is similar
to cases discussed above, except replacing 'AND' by 'OR' and vice
versa
   and dp[i][j]=1 + dp[i1][j]+dp[i2][j]
+.dp[ik][j]

Note: 1)Boundary cases for leaf nodes.
 2)Top down is easier.
 3)If it is impossible to get a value 'j' for subtree rooted
at 'i', then dp[i][j]=INF(some large value)
 4)Answer is dp[root][required_value(o or 1)]. If this
quantity is INF, then it is impossible to achieve this.

Now, lets discuss case 1.2:
We have an 'AND' gate and we want a result of 0.
So, atleast one of the children of node 'i' should be 0.
Now create 2 arrays x,y each of size 'k'
x[1]=dp[i1][0], y[1]=dp[i1][1]
x[2]=dp[i2][0], y[2]=dp[i2][1]
.
.
.
x[k]=dp[ik][0], y[k]=dp[ik][1]

Now, let v=min(x[1],x[2],x[3],.x[k]), and 'h' be the index of the
minimum element(x[h] is minimum)
Then, dp[i][j]=v+sigma(f!=h)[min(x[f],y[f])]

The other cases are similar to this!
I can write a code and send if you have doubts.

On Dec 28, 9:36 am, Anand  wrote:
> @Terence.
>
> Could please elaborate your answer. Bottom up level order traversal helps to
> get the final root value but how to use it to find minimum flips needed to
> Obtain the desired root value.
>
> On Fri, Dec 24, 2010 at 1:56 AM, Terence  wrote:
> > Using the same level order traversal (bottom up), calculating the minimum
> > flips to turn each internal node to given value (0/1).
>
> > On 2010-12-24 17:19, bittu wrote:
>
> >> Boolean tree problem:
>
> >> Each leaf node has a boolean value associated with it, 1 or 0. In
> >> addition, each interior node has either an "AND" or an "OR" gate
> >> associated with it. The value of an "AND" gate node is given by the
> >> logical AND of its two children's values. The value of an "OR" gate
> >> likewise is given by the logical OR of its two children's values. The
> >> value of all of the leaf nodes will be given as input so that the
> >> value of all nodes can be calculated up the tree.
> >> It's easy to find the actual value at the root using level order
> >> traversal and a stack(internal if used recursion).
>
> >> Given V as the desired result i.e we want the value calculated at the
> >> root to be V(0 or 1) what is the minimum number of gates flip i.e. AND
> >> to OR or OR to AND be required at internal nodes to achieve that?
>
> >> Also for each internal node you have boolean associated which tells
> >> whether the node can be flipped or not. You are not supposed to flip a
> >> non flippable internal node.
>
> >> Regards
> >> Shashank Mani Narayan
> >> BIT Mesra
>
> > --
> > 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.

[algogeeks] Re: Google interview question

[Arif Ali Saiyed]

Read each file word by word and insert into a Suffix Tree...
Terminal node of each word contains the FileNo/FileName...

Quite simple

On Dec 14, 5:42 pm, Tuaa  wrote:
> According to me, the problem is regarding fastest search of
> substrings..
> Hashing is one of the solutions.
> Use Rabin-Karp Search..
> Use wiki 
> at:http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorit...
>
> On Dec 14, 4:01 pm, sourabh jakhar  wrote:
>
> > i have a one idea in my mind is to implement a hash table structure based on
> > 26 alphabets
> > and a data structure of words.
> > struct word
> > {
> > int info;
> > char a[n];};
>
> > structure  contains the info about the word and an array in  which document
> > it is present or not out of n
> > ex if it is word is mnnit and it is in document 1 ,4,6,9
> > the info of the structure would be char[1,4,6,9]=1
> > and the rest are zero.
> > insertion of word would take o(1) time but searching would take o(n) time if
> > list is implemented as an array list
> > and if implemented as an binary search tree would take it log(n) but than
> > insertion would also take log(n) time
>
> > On Mon, Dec 13, 2010 at 9:55 PM, GOBIND KUMAR  wrote:
> > > One of my friends attended google interview.This was one the question
> > > asked.
>
> > >      "you are given N documents(possibly in millions) with words in them.
> > > design datastructures such that the following scenarios take optimal time:
>
> > >         a. print all the the docs having a given word
>
> > >         b. print the docs having both of 2 given words"
>
> > > Help me in solving this problem.
>
> > >  --
> > > 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.
>
> > --
> > SOURABH JAKHAR,(CSE)(3 year)
> > ROOM NO 167 ,
> > TILAK,HOSTEL
> > 'MNNIT ALLAHABAD- 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: Google interview question

[Tuaa]

According to me, the problem is regarding fastest search of
substrings..
Hashing is one of the solutions.
Use Rabin-Karp Search..
Use wiki at:
http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm#Rabin.E2.80.93Karp_and_multiple_pattern_search

On Dec 14, 4:01 pm, sourabh jakhar  wrote:
> i have a one idea in my mind is to implement a hash table structure based on
> 26 alphabets
> and a data structure of words.
> struct word
> {
> int info;
> char a[n];};
>
> structure  contains the info about the word and an array in  which document
> it is present or not out of n
> ex if it is word is mnnit and it is in document 1 ,4,6,9
> the info of the structure would be char[1,4,6,9]=1
> and the rest are zero.
> insertion of word would take o(1) time but searching would take o(n) time if
> list is implemented as an array list
> and if implemented as an binary search tree would take it log(n) but than
> insertion would also take log(n) time
>
>
>
>
>
> On Mon, Dec 13, 2010 at 9:55 PM, GOBIND KUMAR  wrote:
> > One of my friends attended google interview.This was one the question
> > asked.
>
> >      "you are given N documents(possibly in millions) with words in them.
> > design datastructures such that the following scenarios take optimal time:
>
> >         a. print all the the docs having a given word
>
> >         b. print the docs having both of 2 given words"
>
> > Help me in solving this problem.
>
> >  --
> > 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.
>
> --
> SOURABH JAKHAR,(CSE)(3 year)
> ROOM NO 167 ,
> TILAK,HOSTEL
> 'MNNIT ALLAHABAD- 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.

Re: [algogeeks] Re: Google Interview question

[LALIT SHARMA]

ya.i was absolutely wrong ..regarding the solution ..dere is much more
for me ..to learn

On Tue, Nov 30, 2010 at 10:47 PM, Prims  wrote:

> Thanks Davenice solution
>
> On Nov 30, 9:56 pm, Dave  wrote:
> > @Prims: I gave an O(n^2 log n) algorithm to find the maximal number of
> > collinear points inhttp://
> groups.google.com/group/algogeeks/msg/d329dda12b332dd1.
> >
> > Dave
> >
> > On Nov 30, 10:18 am, Prims  wrote:
> >
> >
> >
> > > Given n points of structure
> > > struct point
> > > {
> > >  double x;
> > > double y;};
> >
> > > Your function should return two points which are present on a line
> > > passing through maximum number of these n points.- 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.
>
>


-- 
Lalit Kishore Sharma

IIIT Allahabad (Amethi Capmus)
5th Sem

-- 
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: Google Interview question

[Prims]

Thanks Davenice solution

On Nov 30, 9:56 pm, Dave  wrote:
> @Prims: I gave an O(n^2 log n) algorithm to find the maximal number of
> collinear points 
> inhttp://groups.google.com/group/algogeeks/msg/d329dda12b332dd1.
>
> Dave
>
> On Nov 30, 10:18 am, Prims  wrote:
>
>
>
> > Given n points of structure
> > struct point
> > {
> >  double x;
> > double y;};
>
> > Your function should return two points which are present on a line
> > passing through maximum number of these n points.- 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: Google Interview question

[Dave]

@Prims: I gave an O(n^2 log n) algorithm to find the maximal number of
collinear points in 
http://groups.google.com/group/algogeeks/msg/d329dda12b332dd1.

Dave

On Nov 30, 10:18 am, Prims  wrote:
> Given n points of structure
> struct point
> {
>  double x;
> double y;};
>
> Your function should return two points which are present on a line
> passing through maximum number of these n points.

-- 
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: Google Interview question

[Prims]

Could u please elaborate ?
I need an algo with O(N log N) time complexity and O(N) Space
Complexity


On Nov 30, 9:24 pm, LALIT SHARMA  wrote:
> according to my understanding...
>
> Least sqaure regression line concept can be used..
>
> as it would be the line ..that has minimum deviation from all the points in
> space.
>
>
>
>
>
> On Tue, Nov 30, 2010 at 9:48 PM, Prims  wrote:
> > Given n points of structure
> > struct point
> > {
> >  double x;
> > double y;
> > };
> > Your function should return two points which are present on a line
> > passing through maximum number of these n points.
>
> > --
> > 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.
>
> --
> Lalit Kishore Sharma
>
> IIIT Allahabad (Amethi Capmus)
> 5th Sem- 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.

Re: [algogeeks] Re: Google Interview Question

[pratik kathalkar]

On Fri, Sep 17, 2010 at 3:36 PM, Krunal Modi  wrote:

> Your solutions are pretty impressive.
> Which place(country) are you from ?
> where are you studying (or done :) ) ?
>
> Keep it up...
> Good Wishes..
> --Krunal
>
> On Sep 14, 9:29 pm, Gene  wrote:
> > You can approach this the same way you'd do it by hand.  Build up the
> > string of brackets left to right.  For each position, you have a
> > decision of either ( or ) bracket except for two constraints:
> > (1) if you've already decided to use n left brackets, then you can't
> > use a another left bracket and
> > (2) if you've already used as many right as left brackets, then you
> > can't use another right one.
> >
> > This suggests the following alorithm. Showing what happens on the
> > stack is a silly activity.
> >
> > #include 
> >
> > // Buffer for strings of ().
> > char buf[1000];
> >
> > // Continue the printing of bracket strings.
> > //   need is the number of ('s still needed in our string.
> > //   open is tne number of ('s already used _without_ a matching ).
> > //   tail is the buffer location to place the next ) or (.
> > void cont(int need, int open, int tail)
> > {
> >   // If nothing needed or open, we're done.  Print.
> >   if (need == 0 && open == 0) {
> > printf("%s\n", buf);
> > return;
> >   }
> >
> >   // If still a need for (, add a ( and continue.
> >   if (need > 0) {
> > buf[tail] = '(';
> > cont(need - 1, open + 1, tail + 1);
> >   }
> >
> >   // If still an open (, add a ) and continue.
> >   if (open > 0) {
> > buf[tail] = ')';
> > cont(need, open - 1, tail + 1);
> >   }
> >
> > }
> >
> > void Brackets(int n)
> > {
> >   cont(n, 0, 0);
> >
> > }
> >
> > int main(void)
> > {
> >   Brackets(3);
> >   return 0;
> >
> > }
> >
> > On Sep 14, 10:57 am, bittu  wrote:
> >
> >
> >
> > > Write a function Brackets(int n) that prints all combinations of well-
> > > formed brackets. For Brackets(3) the output would be ((())) (()()) (())
> > > () ()(()) ()()()
> >
> > > with explaination dat is at every call what is contant of stack during
> > > pushing and popping
>
> --
> 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.
>
> #include
#include
#include

void addb(int n,int cnt,int i,char *a)
{
if(n==0) {


{
while(cnt!=0){
a[i++]=')';
 cnt--;  }
//if(cnt==0)
{

   // printf("%s\n",a);
cout

Re: [algogeeks] Re: Google Interview Question-Snake and Ladder Design

[Anil Kumar S. R.]

@bittu, we are here to discuss the way to solve it. Posting a code here will
not do anything good.

Anil Kumar S. R.
http://sranil.googlepages.com/

"The best way to succeed in this world is to act on the advice you give to
others."


On 14 September 2010 13:33, bittu  wrote:

> #include
> #include
> #include
> #include
>  ///O(N^2) solution  Does solution exits
> in O(n) or (nlogn)..? reply me sum1 git dis..
> //i will post analysis of dsi program later
> int turn, square;
> long game, totalgames;
> int seed;
> int chutehit[10], ladderhit[9];
> float RunningTurnTotal;
> float average;
>
> char reply;
>
>
> void ChuteStats()
> {printf("Chute and Ladder Statistics:\n\n");
>
> printf("Chute0: %d Ladder0: %d\n", chutehit[0], ladderhit[0]);
> printf("Chute1: %d Ladder1: %d\n", chutehit[1], ladderhit[1]);
> printf("Chute2: %d Ladder2: %d\n", chutehit[2], ladderhit[2]);
> printf("Chute3: %d Ladder3: %d\n", chutehit[3], ladderhit[3]);
> printf("Chute4: %d Ladder4: %d\n", chutehit[4], ladderhit[4]);
> printf("Chute5: %d Ladder5: %d\n", chutehit[5], ladderhit[5]);
> printf("Chute6: %d Ladder6: %d\n", chutehit[6], ladderhit[6]);
> printf("Chute7: %d Ladder7: %d\n", chutehit[7], ladderhit[7]);
> printf("Chute8: %d Ladder8: %d\n", chutehit[8], ladderhit[8]);
> printf("Chute9: %d\n", chutehit[9]);
> }
>
>
>
> int main()
> {
> printf("Welcome to the Chutes and Ladders simulation \n");
> printf("...\n");
> srand(1);
>
> //printf("How many games would you like me to run? __ ");
> //scanf("%i",&totalgames);
> ///printf("\n You have chosen to run %i games... thank you! \n",
> totalgames);
>
> totalgames+=2;
> RunningTurnTotal=0.0;
>game=1;
>do{
>
>turn=0;
>square=0; /** Reset game **/
> do   /** Begin game loop
> **/
>
>{
>++turn;
>RunningTurnTotal = RunningTurnTotal + 1;
>
>square = square + 1 + rand()%6;   /** Spin and move
> **/
>
>printf("square =%d \n",square);
>
>if (square == 1) {square=23; ++ladderhit[0];} /** Ladders?
> **/
>if (square == 4) {square=14; ++ladderhit[1];}
>if (square == 9) {square=31; ++ladderhit[2];}
>if (square == 21) {square=42; ++ladderhit[3];}
>if (square == 28) {square=84; ++ladderhit[4];}
>if (square == 36) {square=44; ++ladderhit[5];}
>if (square == 51) {square=67; ++ladderhit[6];}
>if (square == 71) {square=91; ++ladderhit[7];}
>if (square == 80) {square=100;++ladderhit[8];}/// so when 80
> comes raech to our goal exit
>
>
>
>if (square == 98) {square=78; ++chutehit[0];} /** Chutes ?
> **/
>if (square == 95) {square=75; ++chutehit[1];}
>if (square == 93) {square=73; ++chutehit[2];}
>if (square == 87) {square=24; ++chutehit[3];}
>if (square == 62) {square=19; ++chutehit[4];}
>if (square == 64) {square=60; ++chutehit[5];}
>if (square == 56) {square=53; ++chutehit[6];}
>if (square == 49) {square=11; ++chutehit[7];}
>if (square == 48) {square=26; ++chutehit[8];}
>if (square == 16) {square=6; ++chutehit[9];}
>
>   } while (square<100);//terminate if random no. is > 100
>
>   printf("\n\n Game over after %d turns\n", turn);
>   printf("\nSimulation complete... beginning statistical
> analysis...\n\n");
>  printf("Total number of games played: %d \n", game);
>  printf("Total number of turns: %f \n", RunningTurnTotal);
>  average = RunningTurnTotal / game;
>  printf("Avg number of turns per game: %f \n", average);
>  printf("\n");
>  ChuteStats();
>  printf("\n");
>
> ++game;
> printf("\n\n Would you like to run the simulation again?
> (1=Yes)...");
> scanf("%i",&reply);
> if(reply==1)//e.g. reply==1
> totalgames+=1;
> else
> exit(0);// exit
>
>
>  } while (game
>
>
> getch();
> }
>
> --
> 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.

[algogeeks] Re: Google Interview Question

[Krunal Modi]

Your solutions are pretty impressive.
Which place(country) are you from ?
where are you studying (or done :) ) ?

Keep it up...
Good Wishes..
--Krunal

On Sep 14, 9:29 pm, Gene  wrote:
> You can approach this the same way you'd do it by hand.  Build up the
> string of brackets left to right.  For each position, you have a
> decision of either ( or ) bracket except for two constraints:
> (1) if you've already decided to use n left brackets, then you can't
> use a another left bracket and
> (2) if you've already used as many right as left brackets, then you
> can't use another right one.
>
> This suggests the following alorithm. Showing what happens on the
> stack is a silly activity.
>
> #include 
>
> // Buffer for strings of ().
> char buf[1000];
>
> // Continue the printing of bracket strings.
> //   need is the number of ('s still needed in our string.
> //   open is tne number of ('s already used _without_ a matching ).
> //   tail is the buffer location to place the next ) or (.
> void cont(int need, int open, int tail)
> {
>   // If nothing needed or open, we're done.  Print.
>   if (need == 0 && open == 0) {
>     printf("%s\n", buf);
>     return;
>   }
>
>   // If still a need for (, add a ( and continue.
>   if (need > 0) {
>     buf[tail] = '(';
>     cont(need - 1, open + 1, tail + 1);
>   }
>
>   // If still an open (, add a ) and continue.
>   if (open > 0) {
>     buf[tail] = ')';
>     cont(need, open - 1, tail + 1);
>   }
>
> }
>
> void Brackets(int n)
> {
>   cont(n, 0, 0);
>
> }
>
> int main(void)
> {
>   Brackets(3);
>   return 0;
>
> }
>
> On Sep 14, 10:57 am, bittu  wrote:
>
>
>
> > Write a function Brackets(int n) that prints all combinations of well-
> > formed brackets. For Brackets(3) the output would be ((())) (()()) (())
> > () ()(()) ()()()
>
> > with explaination dat is at every call what is contant of stack during
> > pushing and popping

-- 
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: Google Interview Question-Snake and Ladder Design

[vikas kumar]

take this approach

fill array of snakes starting position in snake[num_snake]

for each snake[i] , take the end of snake and fill in some other array
take random number gen and fill these arrays-->
e.g. end_snake[i] = ran(start_snake[i]-10) // so that snake does not
end up in same row

same logic for ladders

after filling check snake start/end /ladder start/end are not
coinciding

after that u need to make dice object and again ran will come to
rescue :)

now current pos of board can be controlled using player color and
board array
incr /decr  using dice move and snake start/end, ladder start/end
array





On Sep 15, 2:38 am, Minotauraus  wrote:
> And please stop posting the same thing twice. It's been happening for
> the past couple of days at least.
>
> @Question:
> I think you can use graphs and flood fill algo for this. Every
> possible move can be represented with an edge. Flood fill will help
> you figure out possible moves from you current position.
>
> What do you think?
>
> On Sep 14, 2:51 am, ankur aggarwal  wrote:
>
>
>
> > @bittuu
> > write your algo then code
>
> > On Tue, Sep 14, 2010 at 1:36 PM, bittu  wrote:
> > > #include
> > > #include
> > > #include
> > > #include
>
> > > int turn, square;
> > > long game, totalgames;
> > > int seed;
> > > int chutehit[10], ladderhit[9];
> > > float RunningTurnTotal;
> > > float average;
>
> > > char reply;
>
> > > void ChuteStats()
> > > {printf("Chute and Ladder Statistics:\n\n");
>
> > > printf("Chute0: %d     Ladder0: %d\n", chutehit[0], ladderhit[0]);
> > > printf("Chute1: %d     Ladder1: %d\n", chutehit[1], ladderhit[1]);
> > > printf("Chute2: %d     Ladder2: %d\n", chutehit[2], ladderhit[2]);
> > > printf("Chute3: %d     Ladder3: %d\n", chutehit[3], ladderhit[3]);
> > > printf("Chute4: %d     Ladder4: %d\n", chutehit[4], ladderhit[4]);
> > > printf("Chute5: %d     Ladder5: %d\n", chutehit[5], ladderhit[5]);
> > > printf("Chute6: %d     Ladder6: %d\n", chutehit[6], ladderhit[6]);
> > > printf("Chute7: %d     Ladder7: %d\n", chutehit[7], ladderhit[7]);
> > > printf("Chute8: %d     Ladder8: %d\n", chutehit[8], ladderhit[8]);
> > > printf("Chute9: %d                \n", chutehit[9]);
> > > }
>
> > > int main()
> > > {
> > > printf("Welcome to the Chutes and Ladders simulation \n");
> > > printf("...\n");
> > > srand(1);
>
> > > //printf("How many games would you like me to run? __ ");
> > > //scanf("%i",&totalgames);
> > > ///printf("\n You have chosen to run %i games... thank you! \n",
> > > totalgames);
>
> > > totalgames+=2;
> > > RunningTurnTotal=0.0;
> > >            game=1;
> > >        do{
>
> > >        turn=0;
> > >                square=0;                             /** Reset game **/
> > >         do                                           /** Begin game loop
> > > **/
>
> > >                {
> > >            ++turn;
> > >            RunningTurnTotal = RunningTurnTotal + 1;
>
> > >            square = square + 1 + rand()%6;       /** Spin and move
> > > **/
>
> > >                printf("square =%d \n",square);
>
> > >                if (square == 1) {square=23; ++ladderhit[0];} /** Ladders?
> > > **/
> > >                if (square == 4) {square=14; ++ladderhit[1];}
> > >                if (square == 9) {square=31; ++ladderhit[2];}
> > >                if (square == 21) {square=42; ++ladderhit[3];}
> > >                if (square == 28) {square=84; ++ladderhit[4];}
> > >                if (square == 36) {square=44; ++ladderhit[5];}
> > >                if (square == 51) {square=67; ++ladderhit[6];}
> > >                if (square == 71) {square=91; ++ladderhit[7];}
> > >                if (square == 80) {square=100;++ladderhit[8];}/// so when 
> > > 80
> > > comes raech to our goal exit
>
> > >                if (square == 98) {square=78; ++chutehit[0];} /** Chutes ?
> > > **/
> > >                if (square == 95) {square=75; ++chutehit[1];}
> > >                if (square == 93) {square=73; ++chutehit[2];}
> > >                if (square == 87) {square=24; ++chutehit[3];}
> > >                if (square == 62) {square=19; ++chutehit[4];}
> > >                if (square == 64) {square=60; ++chutehit[5];}
> > >                if (square == 56) {square=53; ++chutehit[6];}
> > >                if (square == 49) {square=11; ++chutehit[7];}
> > >                if (square == 48) {square=26; ++chutehit[8];}
> > >                if (square == 16) {square=6; ++chutehit[9];}
>
> > >       } while (square<100);//terminate if random no. is > 100
>
> > >       printf("\n\n Game over after %d turns\n", turn);
> > >       printf("\nSimulation complete... beginning statistical
> > > analysis...\n\n");
> > >      printf("Total number of games played: %d \n", game);
> > >      printf("Total number of turns: %f \n", RunningTurnTotal);
> > >      average = RunningTurnTotal / game;
> > >      printf("Avg number of turns per game: %f \n", average);
> > >      printf("\n");
> > >      ChuteStats();
> > >      printf("\n");
>
> > >         ++game;
> 

[algogeeks] Re: Google Interview Question

[vikas kumar]

nice recurrence

On Sep 14, 9:29 pm, Gene  wrote:
> You can approach this the same way you'd do it by hand.  Build up the
> string of brackets left to right.  For each position, you have a
> decision of either ( or ) bracket except for two constraints:
> (1) if you've already decided to use n left brackets, then you can't
> use a another left bracket and
> (2) if you've already used as many right as left brackets, then you
> can't use another right one.
>
> This suggests the following alorithm. Showing what happens on the
> stack is a silly activity.
>
> #include 
>
> // Buffer for strings of ().
> char buf[1000];
>
> // Continue the printing of bracket strings.
> //   need is the number of ('s still needed in our string.
> //   open is tne number of ('s already used _without_ a matching ).
> //   tail is the buffer location to place the next ) or (.
> void cont(int need, int open, int tail)
> {
>   // If nothing needed or open, we're done.  Print.
>   if (need == 0 && open == 0) {
>     printf("%s\n", buf);
>     return;
>   }
>
>   // If still a need for (, add a ( and continue.
>   if (need > 0) {
>     buf[tail] = '(';
>     cont(need - 1, open + 1, tail + 1);
>   }
>
>   // If still an open (, add a ) and continue.
>   if (open > 0) {
>     buf[tail] = ')';
>     cont(need, open - 1, tail + 1);
>   }
>
> }
>
> void Brackets(int n)
> {
>   cont(n, 0, 0);
>
> }
>
> int main(void)
> {
>   Brackets(3);
>   return 0;
>
> }
>
> On Sep 14, 10:57 am, bittu  wrote:
>
>
>
> > Write a function Brackets(int n) that prints all combinations of well-
> > formed brackets. For Brackets(3) the output would be ((())) (()()) (())
> > () ()(()) ()()()
>
> > with explaination dat is at every call what is contant of stack during
> > pushing and popping- 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: Google Interview Question

[Gene]

Some people have sent email asking what the stack looks like as the
program runs.  It's pretty silly to worry about this.  If you really
want to know, it's easy to modify the program to print a stack
trace.

Here you go:

#include 

// Buffer for strings of ().
char buf[1000];

typedef struct stack_record_s {
  struct stack_record_s *prev;
  int need, open, tail;
} STACK_RECORD;

void dump_state(STACK_RECORD *sr)
{
  int i = 0;
  printf("\nstate: buf=%.*s\n", sr->tail, buf);
  while (sr) {
printf("%d: need=%d, open=%d, tail=%d\n",
   i++, sr->need, sr->open, sr->tail);
sr = sr->prev;
  }
}

// Continue the printing of bracket strings.
//   need is the number of ('s still needed in our string.
//   open is tne number of ('s already used _without_ a matching ).
//   tail is the buffer location to place the next ) or (.
void cont(STACK_RECORD *sr)
{
  // Dump the entire program state as we enter the continuation.
  dump_state(sr);

  // If nothing needed or open, we're done.  Print.
  if (sr->need == 0 && sr->open == 0) {
printf("output: %s\n", buf);
return;
  }

  // If still a need for (, add a ( and continue.
  if (sr->need > 0) {
STACK_RECORD new_sr[1] = {{ sr, sr->need - 1, sr->open + 1, sr-
>tail + 1 }};
buf[sr->tail] = '(';
cont(new_sr);
  }

  // If still an open (, add a ) and continue.
  if (sr->open > 0) {
STACK_RECORD new_sr[1] = {{ sr, sr->need, sr->open - 1, sr->tail +
1 }};
buf[sr->tail] = ')';
cont(new_sr);
  }
}

void Brackets(int n)
{
  STACK_RECORD sr[1] = {{ NULL, n, 0, 0 }};
  cont(sr);
}

int main(void)
{
  Brackets(3);
  return 0;
}

When you run it, you get this output:

state: buf=
0: need=3, open=0, tail=0

state: buf=(
0: need=2, open=1, tail=1
1: need=3, open=0, tail=0

state: buf=((
0: need=1, open=2, tail=2
1: need=2, open=1, tail=1
2: need=3, open=0, tail=0

state: buf=(((
0: need=0, open=3, tail=3
1: need=1, open=2, tail=2
2: need=2, open=1, tail=1
3: need=3, open=0, tail=0

state: buf=((()
0: need=0, open=2, tail=4
1: need=0, open=3, tail=3
2: need=1, open=2, tail=2
3: need=2, open=1, tail=1
4: need=3, open=0, tail=0

state: buf=((())
0: need=0, open=1, tail=5
1: need=0, open=2, tail=4
2: need=0, open=3, tail=3
3: need=1, open=2, tail=2
4: need=2, open=1, tail=1
5: need=3, open=0, tail=0

state: buf=((()))
0: need=0, open=0, tail=6
1: need=0, open=1, tail=5
2: need=0, open=2, tail=4
3: need=0, open=3, tail=3
4: need=1, open=2, tail=2
5: need=2, open=1, tail=1
6: need=3, open=0, tail=0
output: ((()))

state: buf=(()
0: need=1, open=1, tail=3
1: need=1, open=2, tail=2
2: need=2, open=1, tail=1
3: need=3, open=0, tail=0

state: buf=(()(
0: need=0, open=2, tail=4
1: need=1, open=1, tail=3
2: need=1, open=2, tail=2
3: need=2, open=1, tail=1
4: need=3, open=0, tail=0

state: buf=(()()
0: need=0, open=1, tail=5
1: need=0, open=2, tail=4
2: need=1, open=1, tail=3
3: need=1, open=2, tail=2
4: need=2, open=1, tail=1
5: need=3, open=0, tail=0

state: buf=(()())
0: need=0, open=0, tail=6
1: need=0, open=1, tail=5
2: need=0, open=2, tail=4
3: need=1, open=1, tail=3
4: need=1, open=2, tail=2
5: need=2, open=1, tail=1
6: need=3, open=0, tail=0
output: (()())

state: buf=(())
0: need=1, open=0, tail=4
1: need=1, open=1, tail=3
2: need=1, open=2, tail=2
3: need=2, open=1, tail=1
4: need=3, open=0, tail=0

state: buf=(())(
0: need=0, open=1, tail=5
1: need=1, open=0, tail=4
2: need=1, open=1, tail=3
3: need=1, open=2, tail=2
4: need=2, open=1, tail=1
5: need=3, open=0, tail=0

state: buf=(())()
0: need=0, open=0, tail=6
1: need=0, open=1, tail=5
2: need=1, open=0, tail=4
3: need=1, open=1, tail=3
4: need=1, open=2, tail=2
5: need=2, open=1, tail=1
6: need=3, open=0, tail=0
output: (())()

state: buf=()
0: need=2, open=0, tail=2
1: need=2, open=1, tail=1
2: need=3, open=0, tail=0

state: buf=()(
0: need=1, open=1, tail=3
1: need=2, open=0, tail=2
2: need=2, open=1, tail=1
3: need=3, open=0, tail=0

state: buf=()((
0: need=0, open=2, tail=4
1: need=1, open=1, tail=3
2: need=2, open=0, tail=2
3: need=2, open=1, tail=1
4: need=3, open=0, tail=0

state: buf=()(()
0: need=0, open=1, tail=5
1: need=0, open=2, tail=4
2: need=1, open=1, tail=3
3: need=2, open=0, tail=2
4: need=2, open=1, tail=1
5: need=3, open=0, tail=0

state: buf=()(())
0: need=0, open=0, tail=6
1: need=0, open=1, tail=5
2: need=0, open=2, tail=4
3: need=1, open=1, tail=3
4: need=2, open=0, tail=2
5: need=2, open=1, tail=1
6: need=3, open=0, tail=0
output: ()(())

state: buf=()()
0: need=1, open=0, tail=4
1: need=1, open=1, tail=3
2: need=2, open=0, tail=2
3: need=2, open=1, tail=1
4: need=3, open=0, tail=0

state: buf=()()(
0: need=0, open=1, tail=5
1: need=1, open=0, tail=4
2: need=1, open=1, tail=3
3: need=2, open=0, tail=2
4: need=2, open=1, tail=1
5: need=3, open=0, tail=0

state: buf=()()()
0: need=0, open=0, tail=6
1: need=0, open=1, tail=5
2: need=1, open=0, tail=4
3: need=1, open=1, tail=3
4: need=2, open=0, tail=2
5: need=2, open=1, tail=1
6: need=3, open=0, tail=0
output: ()()

Re: [algogeeks] Re: Google Interview Question-Snake and Ladder Design

[siddharth srivastava]

Hi

On 14 September 2010 13:33, bittu  wrote:

> #include
> #include
> #include
> #include
>  ///O(N^2) solution  Does solution exits
> in O(n) or (nlogn)..? reply me sum1 git dis..
> //i will post analysis of dsi program later
> int turn, square;
> long game, totalgames;
> int seed;
> int chutehit[10], ladderhit[9];
> float RunningTurnTotal;
> float average;
>
> char reply;
>
>
> void ChuteStats()
> {printf("Chute and Ladder Statistics:\n\n");
>
> printf("Chute0: %d Ladder0: %d\n", chutehit[0], ladderhit[0]);
> printf("Chute1: %d Ladder1: %d\n", chutehit[1], ladderhit[1]);
> printf("Chute2: %d Ladder2: %d\n", chutehit[2], ladderhit[2]);
> printf("Chute3: %d Ladder3: %d\n", chutehit[3], ladderhit[3]);
> printf("Chute4: %d Ladder4: %d\n", chutehit[4], ladderhit[4]);
> printf("Chute5: %d Ladder5: %d\n", chutehit[5], ladderhit[5]);
> printf("Chute6: %d Ladder6: %d\n", chutehit[6], ladderhit[6]);
> printf("Chute7: %d Ladder7: %d\n", chutehit[7], ladderhit[7]);
> printf("Chute8: %d Ladder8: %d\n", chutehit[8], ladderhit[8]);
> printf("Chute9: %d\n", chutehit[9]);
> }
>
>
>
> int main()
> {
> printf("Welcome to the Chutes and Ladders simulation \n");
> printf("...\n");
> srand(1);
>
> //printf("How many games would you like me to run? __ ");
> //scanf("%i",&totalgames);
> ///printf("\n You have chosen to run %i games... thank you! \n",
> totalgames);
>
> totalgames+=2;
> RunningTurnTotal=0.0;
>game=1;
>do{
>
>turn=0;
>square=0; /** Reset game **/
> do   /** Begin game loop
> **/
>
>{
>++turn;
>RunningTurnTotal = RunningTurnTotal + 1;
>
>square = square + 1 + rand()%6;   /** Spin and move
> **/
>
>printf("square =%d \n",square);
>
>if (square == 1) {square=23; ++ladderhit[0];} /** Ladders?
> **/
>if (square == 4) {square=14; ++ladderhit[1];}
>if (square == 9) {square=31; ++ladderhit[2];}
>if (square == 21) {square=42; ++ladderhit[3];}
>if (square == 28) {square=84; ++ladderhit[4];}
>if (square == 36) {square=44; ++ladderhit[5];}
>if (square == 51) {square=67; ++ladderhit[6];}
>if (square == 71) {square=91; ++ladderhit[7];}
>if (square == 80) {square=100;++ladderhit[8];}/// so when 80
> comes raech to our goal exit
>
>
>
>if (square == 98) {square=78; ++chutehit[0];} /** Chutes ?
> **/
>if (square == 95) {square=75; ++chutehit[1];}
>if (square == 93) {square=73; ++chutehit[2];}
>if (square == 87) {square=24; ++chutehit[3];}
>if (square == 62) {square=19; ++chutehit[4];}
>if (square == 64) {square=60; ++chutehit[5];}
>if (square == 56) {square=53; ++chutehit[6];}
>if (square == 49) {square=11; ++chutehit[7];}
>if (square == 48) {square=26; ++chutehit[8];}
>if (square == 16) {square=6; ++chutehit[9];}
>
>   } while (square<100);//terminate if random no. is > 100
>
>   printf("\n\n Game over after %d turns\n", turn);
>   printf("\nSimulation complete... beginning statistical
> analysis...\n\n");
>  printf("Total number of games played: %d \n", game);
>  printf("Total number of turns: %f \n", RunningTurnTotal);
>  average = RunningTurnTotal / game;
>  printf("Avg number of turns per game: %f \n", average);
>  printf("\n");
>  ChuteStats();
>  printf("\n");
>
> ++game;
> printf("\n\n Would you like to run the simulation again?
> (1=Yes)...");
> scanf("%i",&reply);
> if(reply==1)//e.g. reply==1
> totalgames+=1;
> else
> exit(0);// exit
>
>
>  } while (game
>
>
> getch();
> }
>
> --
> 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.
>
>
Can you please write an algo for your program ?

-- 
Siddharth Srivastava

When you have learned to snatch the error code from the trap frame, it will
be time for you to leave.

-- 
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: Google Interview Question-Snake and Ladder Design

[Minotauraus]

And please stop posting the same thing twice. It's been happening for
the past couple of days at least.

@Question:
I think you can use graphs and flood fill algo for this. Every
possible move can be represented with an edge. Flood fill will help
you figure out possible moves from you current position.

What do you think?

On Sep 14, 2:51 am, ankur aggarwal  wrote:
> @bittuu
> write your algo then code
>
>
>
>
>
>
>
>
>
> On Tue, Sep 14, 2010 at 1:36 PM, bittu  wrote:
> > #include
> > #include
> > #include
> > #include
>
> > int turn, square;
> > long game, totalgames;
> > int seed;
> > int chutehit[10], ladderhit[9];
> > float RunningTurnTotal;
> > float average;
>
> > char reply;
>
> > void ChuteStats()
> > {printf("Chute and Ladder Statistics:\n\n");
>
> > printf("Chute0: %d     Ladder0: %d\n", chutehit[0], ladderhit[0]);
> > printf("Chute1: %d     Ladder1: %d\n", chutehit[1], ladderhit[1]);
> > printf("Chute2: %d     Ladder2: %d\n", chutehit[2], ladderhit[2]);
> > printf("Chute3: %d     Ladder3: %d\n", chutehit[3], ladderhit[3]);
> > printf("Chute4: %d     Ladder4: %d\n", chutehit[4], ladderhit[4]);
> > printf("Chute5: %d     Ladder5: %d\n", chutehit[5], ladderhit[5]);
> > printf("Chute6: %d     Ladder6: %d\n", chutehit[6], ladderhit[6]);
> > printf("Chute7: %d     Ladder7: %d\n", chutehit[7], ladderhit[7]);
> > printf("Chute8: %d     Ladder8: %d\n", chutehit[8], ladderhit[8]);
> > printf("Chute9: %d                \n", chutehit[9]);
> > }
>
> > int main()
> > {
> > printf("Welcome to the Chutes and Ladders simulation \n");
> > printf("...\n");
> > srand(1);
>
> > //printf("How many games would you like me to run? __ ");
> > //scanf("%i",&totalgames);
> > ///printf("\n You have chosen to run %i games... thank you! \n",
> > totalgames);
>
> > totalgames+=2;
> > RunningTurnTotal=0.0;
> >            game=1;
> >        do{
>
> >        turn=0;
> >                square=0;                             /** Reset game **/
> >         do                                           /** Begin game loop
> > **/
>
> >                {
> >            ++turn;
> >            RunningTurnTotal = RunningTurnTotal + 1;
>
> >            square = square + 1 + rand()%6;       /** Spin and move
> > **/
>
> >                printf("square =%d \n",square);
>
> >                if (square == 1) {square=23; ++ladderhit[0];} /** Ladders?
> > **/
> >                if (square == 4) {square=14; ++ladderhit[1];}
> >                if (square == 9) {square=31; ++ladderhit[2];}
> >                if (square == 21) {square=42; ++ladderhit[3];}
> >                if (square == 28) {square=84; ++ladderhit[4];}
> >                if (square == 36) {square=44; ++ladderhit[5];}
> >                if (square == 51) {square=67; ++ladderhit[6];}
> >                if (square == 71) {square=91; ++ladderhit[7];}
> >                if (square == 80) {square=100;++ladderhit[8];}/// so when 80
> > comes raech to our goal exit
>
> >                if (square == 98) {square=78; ++chutehit[0];} /** Chutes ?
> > **/
> >                if (square == 95) {square=75; ++chutehit[1];}
> >                if (square == 93) {square=73; ++chutehit[2];}
> >                if (square == 87) {square=24; ++chutehit[3];}
> >                if (square == 62) {square=19; ++chutehit[4];}
> >                if (square == 64) {square=60; ++chutehit[5];}
> >                if (square == 56) {square=53; ++chutehit[6];}
> >                if (square == 49) {square=11; ++chutehit[7];}
> >                if (square == 48) {square=26; ++chutehit[8];}
> >                if (square == 16) {square=6; ++chutehit[9];}
>
> >       } while (square<100);//terminate if random no. is > 100
>
> >       printf("\n\n Game over after %d turns\n", turn);
> >       printf("\nSimulation complete... beginning statistical
> > analysis...\n\n");
> >      printf("Total number of games played: %d \n", game);
> >      printf("Total number of turns: %f \n", RunningTurnTotal);
> >      average = RunningTurnTotal / game;
> >      printf("Avg number of turns per game: %f \n", average);
> >      printf("\n");
> >      ChuteStats();
> >      printf("\n");
>
> >         ++game;
> >         printf("\n\n Would you like to run the simulation again?
> > (1=Yes)...");
> >         scanf("%i",&reply);
> >         if(reply==1)//e.g. reply==1
> >         totalgames+=1;
> >         else
> >         exit(0);// exit
>
> >  } while (game
> > getch();
> > }
>
> >  ///O(N^2) solution  Does solution exits
> > in O(n) or (nlogn)..? reply me sum1 git dis..
> > //i will post analysis of dsi program later   i m solving usig OOPS
> > (Java) to represnt everything as object
> > //right me if i m wrong or hw we can improve dis alog.
>
> > Regards
> > Shashank Mani " Don't Be Evil u Can Earn While U Learn"
> > BIT Mesra-2010
> > 09166674831
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to al

[algogeeks] Re: Google Interview Question

[Gene]

You can approach this the same way you'd do it by hand.  Build up the
string of brackets left to right.  For each position, you have a
decision of either ( or ) bracket except for two constraints:
(1) if you've already decided to use n left brackets, then you can't
use a another left bracket and
(2) if you've already used as many right as left brackets, then you
can't use another right one.

This suggests the following alorithm. Showing what happens on the
stack is a silly activity.

#include 

// Buffer for strings of ().
char buf[1000];

// Continue the printing of bracket strings.
//   need is the number of ('s still needed in our string.
//   open is tne number of ('s already used _without_ a matching ).
//   tail is the buffer location to place the next ) or (.
void cont(int need, int open, int tail)
{
  // If nothing needed or open, we're done.  Print.
  if (need == 0 && open == 0) {
printf("%s\n", buf);
return;
  }

  // If still a need for (, add a ( and continue.
  if (need > 0) {
buf[tail] = '(';
cont(need - 1, open + 1, tail + 1);
  }

  // If still an open (, add a ) and continue.
  if (open > 0) {
buf[tail] = ')';
cont(need, open - 1, tail + 1);
  }
}

void Brackets(int n)
{
  cont(n, 0, 0);
}

int main(void)
{
  Brackets(3);
  return 0;
}


On Sep 14, 10:57 am, bittu  wrote:
> Write a function Brackets(int n) that prints all combinations of well-
> formed brackets. For Brackets(3) the output would be ((())) (()()) (())
> () ()(()) ()()()
>
> with explaination dat is at every call what is contant of stack during
> pushing and popping

-- 
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: Google Interview Question-Snake and Ladder Design

[bittu]

#include
#include
#include
#include
 ///O(N^2) solution  Does solution exits
in O(n) or (nlogn)..? reply me sum1 git dis..
//i will post analysis of dsi program later
int turn, square;
long game, totalgames;
int seed;
int chutehit[10], ladderhit[9];
float RunningTurnTotal;
float average;

char reply;


void ChuteStats()
{printf("Chute and Ladder Statistics:\n\n");

printf("Chute0: %d Ladder0: %d\n", chutehit[0], ladderhit[0]);
printf("Chute1: %d Ladder1: %d\n", chutehit[1], ladderhit[1]);
printf("Chute2: %d Ladder2: %d\n", chutehit[2], ladderhit[2]);
printf("Chute3: %d Ladder3: %d\n", chutehit[3], ladderhit[3]);
printf("Chute4: %d Ladder4: %d\n", chutehit[4], ladderhit[4]);
printf("Chute5: %d Ladder5: %d\n", chutehit[5], ladderhit[5]);
printf("Chute6: %d Ladder6: %d\n", chutehit[6], ladderhit[6]);
printf("Chute7: %d Ladder7: %d\n", chutehit[7], ladderhit[7]);
printf("Chute8: %d Ladder8: %d\n", chutehit[8], ladderhit[8]);
printf("Chute9: %d\n", chutehit[9]);
}



int main()
{
printf("Welcome to the Chutes and Ladders simulation \n");
printf("...\n");
srand(1);

//printf("How many games would you like me to run? __ ");
//scanf("%i",&totalgames);
///printf("\n You have chosen to run %i games... thank you! \n",
totalgames);

totalgames+=2;
RunningTurnTotal=0.0;
game=1;
do{

turn=0;
square=0; /** Reset game **/
 do   /** Begin game loop
**/

{
++turn;
RunningTurnTotal = RunningTurnTotal + 1;

square = square + 1 + rand()%6;   /** Spin and move
**/

printf("square =%d \n",square);

if (square == 1) {square=23; ++ladderhit[0];} /** Ladders? **/
if (square == 4) {square=14; ++ladderhit[1];}
if (square == 9) {square=31; ++ladderhit[2];}
if (square == 21) {square=42; ++ladderhit[3];}
if (square == 28) {square=84; ++ladderhit[4];}
if (square == 36) {square=44; ++ladderhit[5];}
if (square == 51) {square=67; ++ladderhit[6];}
if (square == 71) {square=91; ++ladderhit[7];}
if (square == 80) {square=100;++ladderhit[8];}/// so when 80
comes raech to our goal exit



if (square == 98) {square=78; ++chutehit[0];} /** Chutes ? **/
if (square == 95) {square=75; ++chutehit[1];}
if (square == 93) {square=73; ++chutehit[2];}
if (square == 87) {square=24; ++chutehit[3];}
if (square == 62) {square=19; ++chutehit[4];}
if (square == 64) {square=60; ++chutehit[5];}
if (square == 56) {square=53; ++chutehit[6];}
if (square == 49) {square=11; ++chutehit[7];}
if (square == 48) {square=26; ++chutehit[8];}
if (square == 16) {square=6; ++chutehit[9];}

   } while (square<100);//terminate if random no. is > 100

   printf("\n\n Game over after %d turns\n", turn);
   printf("\nSimulation complete... beginning statistical
analysis...\n\n");
  printf("Total number of games played: %d \n", game);
  printf("Total number of turns: %f \n", RunningTurnTotal);
  average = RunningTurnTotal / game;
  printf("Avg number of turns per game: %f \n", average);
  printf("\n");
  ChuteStats();
  printf("\n");

 ++game;
 printf("\n\n Would you like to run the simulation again?
(1=Yes)...");
 scanf("%i",&reply);
 if(reply==1)//e.g. reply==1
 totalgames+=1;
 else
 exit(0);// exit


  } while (gamehttp://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Google Interview Question

[bittu]

@debajyoti

can u xplain ur problm more clearly e.g. by example

Regards
Shashank

-- 
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: Google Interview Question

[ashish agarwal]

but addition also should be in array

On Sun, Aug 22, 2010 at 3:05 AM, arpit agarwal wrote:

> Just find out the max and 2nd max in n + log(n) -2 steps and add them.
> there is no need for sorting as such
>
> --
> 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.

[algogeeks] Re: Google Interview Question

[arpit agarwal]

Just find out the max and 2nd max in n + log(n) -2 steps and add them.
there is no need for sorting as such

-- 
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: Google Interview Question: find shortest summary containing all key words

[Andrey]

You'd better write a program.

On Oct 11, 10:42 am, "Vaibhav Jain" <[EMAIL PROTECTED]> wrote:
> Algo:
>
> 1. initialize final_result array with whole sequence and count number of
> keywords in no_of_keys and initialize counter array for keywords with value
> zero.
>
> 2. if sequence_ptr is not null then start scanning the sequence if
> keyword_matches() in sequence put into temp_array and update pointer to read
> next character and repeat it till keyword unmatches.
>
> 3. put the value of temp_array into result_array and make temp_array null.
> then if
> strlen(result_array)< no_of_keys then go to step 2 with updated pointer to
> read remaining sequence.
>
> 4. else check each character of temp_array and if keyword_matches() in
> temp_array then increment counter in counter array at corresponding keyword
> place in counter array.
>
> 5. check counter array if all places in array contain non-zero values, then
> compare if strlen(result_array) final_result=result_array.
>
> 6. else (if some places still have zero in counter array) then make zero in
> each place of counter array and make result array null and go to step 2 with
> updated pointer to read remaining sequence.
>
> 7. else (if sequence_ptr is null) then print final result.
>
>  Assume keyword_matches() is checking characters of given sequence/pattern
> in hash table(hash table stores all the keywords), so it is giving O(1)
> complexity.
>
> This will give O(N) time complexity where N is total no of characters in
> sequence(If no_of keywords k<
> Please correct me if i have done any mistake.
>
> On 9/25/07, Sticker <[EMAIL PROTECTED]> wrote:
>
>
>
>
>
> > Declare: this question is originally from Google. The original form
> > is: given a document, how to find a shortest summary containing all
> > the key words. After translated, it will be: given a sequence, how to
> > find a shortest substring that contains all the items required.
> > Example: a sequence "abaccdefgacel" and a set of key words "a", "c",
> > "d" and "e". The shortest substring contianing all of the key words is
> > "accde". Find one of such shortest substrings. In the original
> > question, there is time complexity boundary O(N), where N is the
> > length of the sequence.
>
> > To me, this problem is rather questionable. So far my solution
> > requires a hash table that gives no conflict and can locate a key word
> > in O(1) time. Otherwise the time complexity will definitely be related
> > to the number of key words.
>
> > Does anyone have idea for a O(N) algorithm to solve this problem?
>
> --
> Vaibhav Jain


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[Andrey]

You'd better wite a program.

On 11 окт, 10:42, "Vaibhav Jain" <[EMAIL PROTECTED]> wrote:
> Algo:
>
> 1. initialize final_result array with whole sequence and count number of
> keywords in no_of_keys and initialize counter array for keywords with value
> zero.
>
> 2. if sequence_ptr is not null then start scanning the sequence if
> keyword_matches() in sequence put into temp_array and update pointer to read
> next character and repeat it till keyword unmatches.
>
> 3. put the value of temp_array into result_array and make temp_array null.
> then if
> strlen(result_array)< no_of_keys then go to step 2 with updated pointer to
> read remaining sequence.
>
> 4. else check each character of temp_array and if keyword_matches() in
> temp_array then increment counter in counter array at corresponding keyword
> place in counter array.
>
> 5. check counter array if all places in array contain non-zero values, then
> compare if strlen(result_array) final_result=result_array.
>
> 6. else (if some places still have zero in counter array) then make zero in
> each place of counter array and make result array null and go to step 2 with
> updated pointer to read remaining sequence.
>
> 7. else (if sequence_ptr is null) then print final result.
>
>  Assume keyword_matches() is checking characters of given sequence/pattern
> in hash table(hash table stores all the keywords), so it is giving O(1)
> complexity.
>
> This will give O(N) time complexity where N is total no of characters in
> sequence(If no_of keywords k<
> Please correct me if i have done any mistake.
>
> On 9/25/07, Sticker <[EMAIL PROTECTED]> wrote:
>
>
>
>
>
> > Declare: this question is originally from Google. The original form
> > is: given a document, how to find a shortest summary containing all
> > the key words. After translated, it will be: given a sequence, how to
> > find a shortest substring that contains all the items required.
> > Example: a sequence "abaccdefgacel" and a set of key words "a", "c",
> > "d" and "e". The shortest substring contianing all of the key words is
> > "accde". Find one of such shortest substrings. In the original
> > question, there is time complexity boundary O(N), where N is the
> > length of the sequence.
>
> > To me, this problem is rather questionable. So far my solution
> > requires a hash table that gives no conflict and can locate a key word
> > in O(1) time. Otherwise the time complexity will definitely be related
> > to the number of key words.
>
> > Does anyone have idea for a O(N) algorithm to solve this problem?
>
> --
> Vaibhav Jain


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[Vaibhav Jain]

Algo:

1. initialize final_result array with whole sequence and count number of
keywords in no_of_keys and initialize counter array for keywords with value
zero.

2. if sequence_ptr is not null then start scanning the sequence if
keyword_matches() in sequence put into temp_array and update pointer to read
next character and repeat it till keyword unmatches.

3. put the value of temp_array into result_array and make temp_array null.
then if
strlen(result_array)< no_of_keys then go to step 2 with updated pointer to
read remaining sequence.

4. else check each character of temp_array and if keyword_matches() in
temp_array then increment counter in counter array at corresponding keyword
place in counter array.

5. check counter array if all places in array contain non-zero values, then
compare if strlen(result_array) wrote:
>
>
> Declare: this question is originally from Google. The original form
> is: given a document, how to find a shortest summary containing all
> the key words. After translated, it will be: given a sequence, how to
> find a shortest substring that contains all the items required.
> Example: a sequence "abaccdefgacel" and a set of key words "a", "c",
> "d" and "e". The shortest substring contianing all of the key words is
> "accde". Find one of such shortest substrings. In the original
> question, there is time complexity boundary O(N), where N is the
> length of the sequence.
>
> To me, this problem is rather questionable. So far my solution
> requires a hash table that gives no conflict and can locate a key word
> in O(1) time. Otherwise the time complexity will definitely be related
> to the number of key words.
>
> Does anyone have idea for a O(N) algorithm to solve this problem?
>
>
> >
>


-- 
Vaibhav Jain

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[Andrey]

>
> Try Suffix Tries ( FYI : reTRIEval )
>
Thank you!


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[Venkatraman S]

>
>
> I just wanted to see the trei.
>
>
Try Suffix Tries ( FYI : reTRIEval )

-vEnKAt

-- 
Blog @ http://blizzardzblogs.blogspot.com

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[Andrey]

> No, I am not trying to do that at all. The trie is built to contain
> only keywords. It can then be used to answer the question for the
> current character 'Is this character part of a candidate keyword?' and
> do this O(1). Candidate keywords are identified initially by the trei
> root returning a reference to the node representing the first
> character of the keyword rather than a null. (or, if you prefer, the
> node linked to the root by that character's edge)

I see.
This is kind of data structure that I don't know.

> This is what I meant by longer and longer subsequences. For example,
> once the subsequence cdfagb has been identified it is then impossible
> that a shorter subsequence exists that starts with the same word 'c'
> at the same location in the complete sequence. Logically the next
> possible shorter subsequence starts with the next word 'a'. Checks
> (result.size() > range.size()) on other 'c' start subsequences are
> redundant.

Very impressive! I spent half an hour at most on that program, and
didn't thought about it deeply. Obviously you are better expert in
it. :)

> Thank you for asking. I was not going to spend time on this if nobody
> was interested. I will make a start this evening and make sure there
> is sufficient debug output that you all can criticise it without
> ploughing through the source code.

It certainly not worth spending time on it, if you don't want.
I just wanted to see the trei.


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[Andrey]

> No, I am not trying to do that at all. The trie is built to contain
> only keywords. It can then be used to answer the question for the
> current character 'Is this character part of a candidate keyword?' and
> do this O(1). Candidate keywords are identified initially by the trei
> root returning a reference to the node representing the first
> character of the keyword rather than a null. (or, if you prefer, the
> node linked to the root by that character's edge)

I see.
This is some kind of data structure that I don't know.


> Calm down. I am not asserting or even suggesting that your algorithm
> does not find the shortest subsequence in all cases. Forget the nested
> loop. A subsequence start pointer is needed and it is probably
> irrelevant whether this is updated in the main loop or a sub-loop.
>
> However, compiling and running the listing I got output shown below
> with initial complete sequence added, subsequences offset to align,
> and subsequence sizes etc. omitted:
>
>abrebbqbcdfagbasdfbbaggqqebbcg--324c
>abrebbqbc
>   bcdfa
>cdfagb
>cdfagba
>cdfagbasdfb
>cdfagbasdfbb
>cdfagbasdfbba
>cdfagbasdfbbaggqqeb
>cdfagbasdfbbaggqqebb
>aggqqebbc
>aggqqebbcg--324c
>The shortest subsequence is: range size: 5 [bcdfa]
>
> This is what I meant by longer and longer subsequences. For example,
> once the subsequence cdfagb has been identified it is then impossible
> that a shorter subsequence exists that starts with the same word 'c'
> at the same location in the complete sequence. Logically the next
> possible shorter subsequence starts with the next word 'a'. Checks
> (result.size() > range.size()) on other 'c' start subsequences are
> redundant.

Very impressive! I spent half an hour at most on that program, and
didn't thought about it deeply. Obviously you are better expert in
it. :)

>
> Thank you for asking. I was not going to spend time on this if nobody
> was interested. I will make a start this evening and make sure there
> is sufficient debug output that you all can criticise it without
> ploughing through the source code.
>

It's certainly not worth spending time on it if you don't want.
I just wanted to see trei.


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[MartinH]

Hi Andrey,

On Oct 8, 7:56 pm you wrote:

> ... Enumerating of the words makes no sense.

Agreed.

> > ... As Vishal suggested a trie looks more realistic. Building the
> > trie can be done O(m), with m - total characters in keywords.
> > Identifying whether a document character is part of a keyword
> > candidate is then O(1).
>
> What is 'trie' ?
> What are you trying to do? Find keyword in input sequence? They are
> separated by spaces and punctuations, aren't they?

No, I am not trying to do that at all. The trie is built to contain
only keywords. It can then be used to answer the question for the
current character 'Is this character part of a candidate keyword?' and
do this O(1). Candidate keywords are identified initially by the trei
root returning a reference to the node representing the first
character of the keyword rather than a null. (or, if you prefer, the
node linked to the root by that character's edge)

> > You asked for O(n) on the length of the sequence...
> > ... this is Big O so we can argue that
> > O(n)<=>O(doc_words) i.e. n = K(doc_words) with K average wordlength in
> > document.
>
> If n is size of input sequence, d - number of words in input sequence
> and n ~ K d then
> O(n) ~ O(d).

Thanks for that.

> > ... Andrey's listing
> > has a nested loop to do trimming that rechecks words already checked
> > in the main loop. Also the algorithm has a tendency to find longer and
> > longer sequences with the same start word that clearly cannot provide
> > a new minimum.
>
> Completely wrong! the algorithm is based on the following invariant:
>   - It always keeps the shortest possible subsequence that ends at the
> current position.
> Therefore it will eventually find the shortest one in entire sequence.

Calm down. I am not asserting or even suggesting that your algorithm
does not find the shortest subsequence in all cases. Forget the nested
loop. A subsequence start pointer is needed and it is probably
irrelevant whether this is updated in the main loop or a sub-loop.

However, compiling and running the listing I got output shown below
with initial complete sequence added, subsequences offset to align,
and subsequence sizes etc. omitted:

   abrebbqbcdfagbasdfbbaggqqebbcg--324c
   abrebbqbc
  bcdfa
   cdfagb
   cdfagba
   cdfagbasdfb
   cdfagbasdfbb
   cdfagbasdfbba
   cdfagbasdfbbaggqqeb
   cdfagbasdfbbaggqqebb
   aggqqebbc
   aggqqebbcg--324c
   The shortest subsequence is: range size: 5 [bcdfa]

This is what I meant by longer and longer subsequences. For example,
once the subsequence cdfagb has been identified it is then impossible
that a shorter subsequence exists that starts with the same word 'c'
at the same location in the complete sequence. Logically the next
possible shorter subsequence starts with the next word 'a'. Checks
(result.size() > range.size()) on other 'c' start subsequences are
redundant.

> > I'm no expert but does this give O(n+m)?
>
> Yes, and I professed that in listing. But O(n + m) is still O(n)
>
> Where
>   n  - size of input sequence
>   m - number of keywords

O.k, still O(n), but only because redundant checks ~ m in the worst
case, or I think they do.

> > I could perhaps do a small application (in Pascal) to test this point.
> > Meanwhile what do you think?
>
> How is your program? Can we have a glimpse of that?

Thank you for asking. I was not going to spend time on this if nobody
was interested. I will make a start this evening and make sure there
is sufficient debug output that you all can criticise it without
ploughing through the source code.

MartinH.


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[Andrey]

I have to admit that I was wrong in my previous post. I stated that if
we have all words in the enumerated we can operate with them "better
(faster)" but it is true. Enumeraing of the words makes no sence..

> Similar objections to using a hash table to assign integers to words.
> If collisions are allowed, not 0(1). Might just as well have hashed in
> the keywords first and accepted worse than O(1). As Vishal suggested a
> trie looks more realistic. Building the trie can be done O(m), with m
> - total characters in keywords. Identifying whether a docut ment
> character is part of a keyword candidate is then O(1).


What is 'trie' ?
What are you trying to do? Find keyword in input sequence? They are
separated by spaces and punctuations, aren't they?

>
> You asked for O(n) on the length of the sequence. I think this can be
> taken as n, the number of characters in the document. Fair because we
> have to iterate through all the characters to find the position of
> words and keywords. Anyway, this is Big O so we can argue that
> O(n)<=>O(doc_words) i.e. n = K(doc_words) with K average wordlength in
> document.
>

If n is size of input sequence, d - number of words in input sequence
and n ~ K d then
O(n) ~ O(d).

>... Andrey's listing
> has a nested loop to do trimming that rechecks words already checked
> in the main loop. Also the algorithm has a tendency to find longer and
> longer sequences with the same start word that clearly cannot provide
> a new minimum.

Completely wrong! the algoritm is based on the following invariant:
  - It always keeps the shortest possible subsequence that ends at the
current possition.
Therefore it will eventually find the shortest one in entire sequence.


> I'm no expert but does this give O(n+m)?

Yes, and I professed that in listing. But O(n + m) is still O(n)

Where
  n  - size of input sequence
  m - number of keywords


> I could perhaps do a small application (in Pascal) to test this point.
> Meanwhile what do you think?

How is your program? Can we have a glimpse of that?


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[Shrenik]

A small variation of Vishal's algorithm to eliminate the need of the
bitmap. I use a hash table of integers index by the keyword,
initialized to all 0. I also make use of the property that in the
shortest summary the first and the last keyword will appear exactly
once.

1. foreach word in document
hash[word]++; // by the end of this loop we should have
frequencies of all keywords

2. Do a preliminary check to see if each hash[keyword] has frequency
>= 0. If at least one has frequency = 0, stop and return null to
indicate summary not found.

4. startp = pointer to first word, endp = pointer to last word

3. for (; startp <= endp; startp++)
if (hash[*startp] == 1)  // stop when keyword with frequency =
1 is found
   break;
else
   hash[*startp]--; // by end of this loop, startp will point
to the first word of the summary, i.e. keyword that appears once

4. for (; startp <= endp; endp--)
if (hash[*endp] == 1)  // stop when keyword with frequency = 1
is found
   break;
else
   hash[*endp]--; // by end of this loop, endp will point to
the last word of the summary, i.e. keyword that appears once

5. return summary which is from startp to endp

Worst case is O(2N) = O(N). Also, if there are more than one shortest
summaries, this will return the last one.

-Shrenik

On Sep 24, 10:15 pm, Vishal <[EMAIL PROTECTED]> wrote:
> How about keeping two pointers - startp and endp.
> Keep a count of frequencies of keywords between startp and endp, both
> inclusive. We can use an array / hash table for this.
> Now, the minimum length substring has to start with a keyword and has to end
> with a keyword.
>
> 1. Initially startp=0 and endp=1. L = infinity
> 2. Increment endp till you encounter a keyword or it exceeds the total
> length. Update frequencies. Check if you have all the keywords. (This can be
> done in O(1) using a bitmap or similar). If it exceeds the total length,
> QUIT.
> 3. If the str(startp,endp) contains all keywords and length < L, save values
> of startp and endp.
> 4. Now, increment startp, till you get a keyword. If the str(startp,endp)
> still contains all keywords, update saved values of startp and endp.
> 5. Repeat step 4 till str(startp,endp) does NOT contain all keywords.
> 6. Goto step 2.
>
> The final values of startp and endp should give you the minimum summary.
> Since both values go from 0 to N-1, its O(N).
>
> ~Vishal
>
> On 9/24/07, daizisheng <[EMAIL PROTECTED]> wrote:
>
>
>
> > I think hash method is ok, at lease in expectation way it's O(n)
> > why not use it? it's very effeciently
>
> > I think there should be some worst case O(n) algorithm, but it will be
> > more complex and not as effecient as the above one in practise
>
> > Sticker 写道:
> > > Declare: this question is originally from Google. The original form
> > > is: given a document, how to find a shortest summary containing all
> > > the key words. After translated, it will be: given a sequence, how to
> > > find a shortest substring that contains all the items required.
> > > Example: a sequence "abaccdefgacel" and a set of key words "a", "c",
> > > "d" and "e". The shortest substring contianing all of the key words is
> > > "accde". Find one of such shortest substrings. In the original
> > > question, there is time complexity boundary O(N), where N is the
> > > length of the sequence.
>
> > > To me, this problem is rather questionable. So far my solution
> > > requires a hash table that gives no conflict and can locate a key word
> > > in O(1) time. Otherwise the time complexity will definitely be related
> > > to the number of key words.
>
> > > Does anyone have idea for a O(N) algorithm to solve this problem?


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[Shrenik]

A small variation of Vishal's algorithm to eliminate the need of the
bitmap. I use a hash table of integers index by the keyword,
initialized to all 0. I also make use of the property that in the
shortest summary the first and the last keyword will appear exactly
once.

1. foreach word in document
hash[word]++; // by the end of this loop we should have
frequencies of all keywords

2. Do a preliminary check to see if each hash[keyword] has frequency
>= 0. If at least one has frequency = 0, stop and return null to
indicate summary not found.

4. startp = pointer to first word, endp = pointer to last word

3. for (; startp <= endp; startp++)
if (hash[*startp] == 1)  // stop when keyword with frequency =
1 is found
   break;
else
   hash[*startp]--; // by end of this loop, startp will point
to the first word of the summary, i.e. keyword that appears once

4. for (; startp <= endp; endp--)
if (hash[*endp] == 1)  // stop when keyword with frequency = 1
is found
   break;
else
   hash[*endp]--; // by end of this loop, endp will point to
the last word of the summary, i.e. keyword that appears once

5. return summary which is from startp to endp

Worst case is O(2N) = O(N). Also, if more than one shortest summaries
are present, this will return the last one.

-Shrenik

On Oct 5, 6:34 am, MartinH <[EMAIL PROTECTED]> wrote:
> {I already posted this yesterday but did not appear: apologies if
> duplicate results}
>
> This looks to be a hard to solve and nastily realistic problem. By
> nastily realistic I mean it looks like the kind of thing we might be
> asked to code by lunchtime tomorrow.
>
> As daizisheng wrote there is nothing wrong with perfect hashing to
> identify keywords, but it may be impractical to implement. With just
> 'a'..'z' allowed in keywords, max data compression and max keyword
> length 10, the hash table needs 2^48 entries. With full 8 bit or ISO
> characters its size becomes completely untenable. Obviously not all
> locations represent real words but any hash function that takes this
> into account to compress the range won't be O(1) and/or can't be
> guaranteed perfect.
>
> Similar objections to using a hash table to assign integers to words.
> If collisions are allowed, not 0(1). Might just as well have hashed in
> the keywords first and accepted worse than O(1). As Vishal suggested a
> trie looks more realistic. Building the trie can be done O(m), with m
> - total characters in keywords. Identifying whether a document
> character is part of a keyword candidate is then O(1).
>
> You asked for O(n) on the length of the sequence. I think this can be
> taken as n, the number of characters in the document. Fair because we
> have to iterate through all the characters to find the position of
> words and keywords. Anyway, this is Big O so we can argue that
> O(n)<=>O(doc_words) i.e. n = K(doc_words) with K average wordlength in
> document.
>
> Having got O(1) for keyword identification, to get O(n) we need a
> scanning algorithm containing a simple loop that advances a pointer to
> the next current character in the document, or do we? Andrey's listing
> has a nested loop to do trimming that rechecks words already checked
> in the main loop. Also the algorithm has a tendency to find longer and
> longer sequences with the same start word that clearly cannot provide
> a new minimum. I'm no expert but does this give O(n+m)?
>
> A simple loop can be got by maintaining an advancing list of
> candidate  keyword locations. By advancing I mean that all words
> referenced from the list are as far from the start of the document as
> logically possible. Say keywords are a,b,c,d: suppose a,b,c have been
> identified and another b is found - the candidate becomes a,c,b. Now a
> is found and the candidate becomes c,b,a. Any subsequence starting
> with the old word a, must be longer that one starting with word c. If
> d is found next, completing the set, the subsequent candidate is
> b,a,d.
>
> Doing this avoids maintaining a list of all keyword locations from the
> first word found in a candidate subsequence and then using a nested
> loop to advance a pointer when a complete set is found. Deletion when
> a duplicate occurs can be done by maintaining references from relevant
> trie nodes to list elements. List -> trie node references are also
> needed to reset a node's reference to null when the tail is deleted
> after a complete set.
>
> Sticker wrote
>
> > May I draw the final conclusion that the final time complexity "must"
> > have to involve the total length of keywords and the length of the
> > input text, rather than linear to the input text's length?
>
> Even storing all relevant keyword data in a single pass through the
> document, a case when a keyword is identified is more complex than
> otherwise. Actual time complexity is O(n+m+t) - t number of keywords
> in document. But we are not magicians, as far as meeting the O(n)
> requireme

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[MartinH]

{I already posted this yesterday but did not appear: apologies if
duplicate results}

This looks to be a hard to solve and nastily realistic problem. By
nastily realistic I mean it looks like the kind of thing we might be
asked to code by lunchtime tomorrow.

As daizisheng wrote there is nothing wrong with perfect hashing to
identify keywords, but it may be impractical to implement. With just
'a'..'z' allowed in keywords, max data compression and max keyword
length 10, the hash table needs 2^48 entries. With full 8 bit or ISO
characters its size becomes completely untenable. Obviously not all
locations represent real words but any hash function that takes this
into account to compress the range won't be O(1) and/or can't be
guaranteed perfect.

Similar objections to using a hash table to assign integers to words.
If collisions are allowed, not 0(1). Might just as well have hashed in
the keywords first and accepted worse than O(1). As Vishal suggested a
trie looks more realistic. Building the trie can be done O(m), with m
- total characters in keywords. Identifying whether a document
character is part of a keyword candidate is then O(1).

You asked for O(n) on the length of the sequence. I think this can be
taken as n, the number of characters in the document. Fair because we
have to iterate through all the characters to find the position of
words and keywords. Anyway, this is Big O so we can argue that
O(n)<=>O(doc_words) i.e. n = K(doc_words) with K average wordlength in
document.

Having got O(1) for keyword identification, to get O(n) we need a
scanning algorithm containing a simple loop that advances a pointer to
the next current character in the document, or do we? Andrey's listing
has a nested loop to do trimming that rechecks words already checked
in the main loop. Also the algorithm has a tendency to find longer and
longer sequences with the same start word that clearly cannot provide
a new minimum. I'm no expert but does this give O(n+m)?

A simple loop can be got by maintaining an advancing list of
candidate  keyword locations. By advancing I mean that all words
referenced from the list are as far from the start of the document as
logically possible. Say keywords are a,b,c,d: suppose a,b,c have been
identified and another b is found - the candidate becomes a,c,b. Now a
is found and the candidate becomes c,b,a. Any subsequence starting
with the old word a, must be longer that one starting with word c. If
d is found next, completing the set, the subsequent candidate is
b,a,d.

Doing this avoids maintaining a list of all keyword locations from the
first word found in a candidate subsequence and then using a nested
loop to advance a pointer when a complete set is found. Deletion when
a duplicate occurs can be done by maintaining references from relevant
trie nodes to list elements. List -> trie node references are also
needed to reset a node's reference to null when the tail is deleted
after a complete set.

Sticker wrote

> May I draw the final conclusion that the final time complexity "must"
> have to involve the total length of keywords and the length of the
> input text, rather than linear to the input text's length?

Even storing all relevant keyword data in a single pass through the
document, a case when a keyword is identified is more complex than
otherwise. Actual time complexity is O(n+m+t) - t number of keywords
in document. But we are not magicians, as far as meeting the O(n)
requirement we must assume that m and t are negligible compared to n.
I could perhaps do a small application (in Pascal) to test this point.
Meanwhile what do you think?

MartinH.

On Oct 1, 3:20 am, Sticker <[EMAIL PROTECTED]> wrote:
> En, it is the idea. You assume each keyword is a single character and
> you use a map to hash key words and their counts. Each time you extend
> the range to right hand side, you may increase the counts of some
> found key words and each time you shrink the range from the left hand
> side, you decrease the counts of some out-of-range key words.
>
> For the case that keywords are not single characters, you need a
> complex hash. Even if keywords are single characters, you need
> lg(number of keywords) to locate the position of each keyword in the
> map,which is implemented in the STL map container.
>
> May I draw the final conclusion that the final time complexity "must"
> have to involve the total length of keywords and the length of the
> input text, rather than linear to the input text's length? (Of course
> you can say that in usual case the length of keywords << length of
> input text. But this assumption should not remove the length of
> keywords in the time complexity analysis thus should not sufficient to
> make the algorithm works linear to the length of text.) Am I right?
>
> On Oct 1, 4:10 am, Andrey <[EMAIL PROTECTED]> wrote:
>
>
>
> > Check this program:
>
> > #include 
> > #include 
> > #include 
> > #include 
> > #include 
>
> > using namespace std;
>
> > class Range : p

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[Andrey]

On 1 окт, 06:20, Sticker <[EMAIL PROTECTED]> wrote:
> En, it is the idea. You assume each keyword is a single character and
> you use a map to hash key words and their counts. Each time you extend
> the range to right hand side, you may increase the counts of some
> found key words and each time you shrink the range from the left hand
> side, you decrease the counts of some out-of-range key words.
>
Exactly! pretty simple algorithm.


> For the case that keywords are not single characters, you need a
> complex hash. Even if keywords are single characters, you need
> lg(number of keywords) to locate the position of each keyword in the
> map,which is implemented in the STL map container.


Look at
> Example: a sequence "abaccdefgacel" and a set of key words "a", "c",
> "d" and "e". The shortest substring contianing all of the key words is
> "accde".

each word is a single character! more over It makes no difference we
can numerate all the words in the world :) and rewrite the program
using numbers instead of characters.


> May I draw the final conclusion that the final time complexity "must"
> have to involve the total length of keywords and the length of the
> input text, rather than linear to the input text's length? (Of course
> you can say that in usual case the length of keywords << length of
> input text. But this assumption should not remove the length of
> keywords in the time complexity analysis thus should not sufficient to
> make the algorithm works linear to the length of text.) Am I right?
>

Let's write new algorithm based on my previous with integers instead
words.

Ruby like code :)

  @words = {}# Hash {word => sequence number }

1.
  for word in inputSequence
 words[word] = words.size unless words[word]   #  If word not in
hash put it there
 
#  and assign sequence number.
  end
2.
  for word in keyWords
 words[word] = words.size unless words[word]
  end

# This procedure takes N log(N) + M * log(N + M)
#   N - size of input sequence
#   M - number of keywords

3. Run previous algorithm on integers!

The total time will be
N log(N) + M * log (N + M) + N + M


So if we don't have all word already enumerated you are right.

> On Oct 1, 4:10 am, Andrey <[EMAIL PROTECTED]> wrote:
>
> > Check this program:
>
> > #include 
> > #include 
> > #include 
> > #include 
> > #include 
>
> > using namespace std;
>
> > class Range : public pair {
> >   public:
> > size_t size() const { return second - first; }
> > Range(const char* f=0, const char * s=0)
> > : pair(f ,s) {}
>
> > };
>
> > ostream & operator << (ostream & out, const Range& r) {
> > out<<"range size: "< > copy(r.first, r.second, ostream_iterator(out, ""));
> > out<<"]";
> > return out;
>
> > }
>
> > typedef map SetCnt;
>
> > // array based implementation will have complexity O(m)
> > bool checkSet(const SetCnt & setCnt) {
> > SetCnt::const_iterator sIt = setCnt.begin(), sEnd = setCnt.end();
> > for (SetCnt::const_iterator sIt = setCnt.begin(); sIt != sEnd; +
> > +sIt ) {
> > if (sIt->second == 0) {
> > return false;
> > }
> > }
> > return true;
>
> > }
>
> > // array based implementation will have complexity O(1)
> > bool checkAndShrink(SetCnt & setCnt, char c) {
> > SetCnt::iterator sIt = setCnt.find(c);
> > if (sIt == setCnt.end()) {
> > return true;
> > }
> > if (sIt->second > 1) {
> > sIt->second--;
> > return true;
> > }
> > return false;
>
> > }
>
> > // aproximate complexity is O(n*m + m)
> > //   where n - is size of input sequence and m - is number of key
> > words.
> > Range solve(const char * strBegin, const char * strEnd,
> > const char * setBegin, const char * setEnd) {
> > SetCnt setCnt;
>
> > // complexity O(m)
> > for (const char * cIt = setBegin; cIt != setEnd; cIt++ ) {
> > setCnt[*cIt] = 0;
> > }
>
> > bool solved = false;
> > Range range(strBegin, strEnd), result(range);
> > for (const char * sIt = strBegin; sIt != strEnd; sIt++ ) {
> > SetCnt::iterator it = setCnt.find(*sIt);
> > if (it != setCnt.end()) {
> > setCnt[*sIt] += 1;
> > range.second = sIt + 1;
> > if (checkSet(setCnt)) {
> > solved = true;
> > while (checkAndShrink(setCnt, 
> > *range.first)) {
> > range.first++;
> > }
> > if (result.size() > range.size()) {
> > result = range;
> > }
> > // Debug
> > 

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[Sticker]

En, it is the idea. You assume each keyword is a single character and
you use a map to hash key words and their counts. Each time you extend
the range to right hand side, you may increase the counts of some
found key words and each time you shrink the range from the left hand
side, you decrease the counts of some out-of-range key words.

For the case that keywords are not single characters, you need a
complex hash. Even if keywords are single characters, you need
lg(number of keywords) to locate the position of each keyword in the
map,which is implemented in the STL map container.

May I draw the final conclusion that the final time complexity "must"
have to involve the total length of keywords and the length of the
input text, rather than linear to the input text's length? (Of course
you can say that in usual case the length of keywords << length of
input text. But this assumption should not remove the length of
keywords in the time complexity analysis thus should not sufficient to
make the algorithm works linear to the length of text.) Am I right?

On Oct 1, 4:10 am, Andrey <[EMAIL PROTECTED]> wrote:
> Check this program:
>
> #include 
> #include 
> #include 
> #include 
> #include 
>
> using namespace std;
>
> class Range : public pair {
>   public:
> size_t size() const { return second - first; }
> Range(const char* f=0, const char * s=0)
> : pair(f ,s) {}
>
> };
>
> ostream & operator << (ostream & out, const Range& r) {
> out<<"range size: "< copy(r.first, r.second, ostream_iterator(out, ""));
> out<<"]";
> return out;
>
> }
>
> typedef map SetCnt;
>
> // array based implementation will have complexity O(m)
> bool checkSet(const SetCnt & setCnt) {
> SetCnt::const_iterator sIt = setCnt.begin(), sEnd = setCnt.end();
> for (SetCnt::const_iterator sIt = setCnt.begin(); sIt != sEnd; +
> +sIt ) {
> if (sIt->second == 0) {
> return false;
> }
> }
> return true;
>
> }
>
> // array based implementation will have complexity O(1)
> bool checkAndShrink(SetCnt & setCnt, char c) {
> SetCnt::iterator sIt = setCnt.find(c);
> if (sIt == setCnt.end()) {
> return true;
> }
> if (sIt->second > 1) {
> sIt->second--;
> return true;
> }
> return false;
>
> }
>
> // aproximate complexity is O(n*m + m)
> //   where n - is size of input sequence and m - is number of key
> words.
> Range solve(const char * strBegin, const char * strEnd,
> const char * setBegin, const char * setEnd) {
> SetCnt setCnt;
>
> // complexity O(m)
> for (const char * cIt = setBegin; cIt != setEnd; cIt++ ) {
> setCnt[*cIt] = 0;
> }
>
> bool solved = false;
> Range range(strBegin, strEnd), result(range);
> for (const char * sIt = strBegin; sIt != strEnd; sIt++ ) {
> SetCnt::iterator it = setCnt.find(*sIt);
> if (it != setCnt.end()) {
> setCnt[*sIt] += 1;
> range.second = sIt + 1;
> if (checkSet(setCnt)) {
> solved = true;
> while (checkAndShrink(setCnt, *range.first)) {
> range.first++;
> }
> if (result.size() > range.size()) {
> result = range;
> }
> // Debug
> cout< }
> }
> }
> return solved ? result : Range(0, 0);
>
> }
>
> int main() {
> const char * string = "abrebbqbcdfagbasdfbbaggqqebbcg--324c";
> const char * set = "abc";
>
> Range range = solve(string, string + strlen(string), set, set +
> strlen(set));
> if (range.size()) {
> cout<<"The shortes subsequence is: "< } else {
> cout<<"No solution..."< }
> 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 algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[Andrey]

Check this program:

#include 
#include 
#include 
#include 
#include 

using namespace std;

class Range : public pair {
  public:
size_t size() const { return second - first; }
Range(const char* f=0, const char * s=0)
: pair(f ,s) {}
};

ostream & operator << (ostream & out, const Range& r) {
out<<"range size: "<(out, ""));
out<<"]";
return out;
}


typedef map SetCnt;

// array based implementation will have complexity O(m)
bool checkSet(const SetCnt & setCnt) {
SetCnt::const_iterator sIt = setCnt.begin(), sEnd = setCnt.end();
for (SetCnt::const_iterator sIt = setCnt.begin(); sIt != sEnd; +
+sIt ) {
if (sIt->second == 0) {
return false;
}
}
return true;
}

// array based implementation will have complexity O(1)
bool checkAndShrink(SetCnt & setCnt, char c) {
SetCnt::iterator sIt = setCnt.find(c);
if (sIt == setCnt.end()) {
return true;
}
if (sIt->second > 1) {
sIt->second--;
return true;
}
return false;
}


// aproximate complexity is O(n*m + m)
//   where n - is size of input sequence and m - is number of key
words.
Range solve(const char * strBegin, const char * strEnd,
const char * setBegin, const char * setEnd) {
SetCnt setCnt;

// complexity O(m)
for (const char * cIt = setBegin; cIt != setEnd; cIt++ ) {
setCnt[*cIt] = 0;
}

bool solved = false;
Range range(strBegin, strEnd), result(range);
for (const char * sIt = strBegin; sIt != strEnd; sIt++ ) {
SetCnt::iterator it = setCnt.find(*sIt);
if (it != setCnt.end()) {
setCnt[*sIt] += 1;
range.second = sIt + 1;
if (checkSet(setCnt)) {
solved = true;
while (checkAndShrink(setCnt, *range.first)) {
range.first++;
}
if (result.size() > range.size()) {
result = range;
}
// Debug
cout

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[Vishal]

We might even use String Trie. The search time would be O(m) where m is the
length of maximum length keyword. Since m< wrote:
>
>
> To Vishal: My idea is similar to yours. I like to use hash table as
> well. But I wonder which hash function can you use to insert and find
> keywords with O(1) time? Keywords are not single characters. They are
> normal words. That's basically what I am aftering.
>
> On Sep 25, 2:11 pm, Mayur <[EMAIL PROTECTED]> wrote:
> > Another possibility is to first pre-process the keywords into
> > automaton-like structure (Google for Aho Corasick string matcher), and
> > then use it over the document. This would probably be helpful only if
> > the number of keywords is much smaller than the document itself..
> >
> > On 9/25/07, daizisheng <[EMAIL PROTECTED]> wrote:
> >
> >
> >
> > > Vishal 写道:
> > > > Hash table should give you O(1) insertion and search complexity;
> which
> > > > is what we need, right?
> > > > There is no constraint on space complexity, I believe.
> >
> > > > On 9/24/07, * daizisheng* <[EMAIL PROTECTED]
> > > > > wrote:
> >
> > > > the problem is you need a hash table to maintain all the
> keywords,:)
> > > > because they do not have to be a single characters, or you can
> > > > store them in
> > > > array, but then you need binary search,:)
> >
> > > > Vishal 写道:
> > > > > How about keeping two pointers - startp and endp.
> > > > > Keep a count of frequencies of keywords between startp and
> endp,
> > > > both
> > > > > inclusive. We can use an array / hash table for this.
> > > > > Now, the minimum length substring has to start with a keyword
> > > > and has
> > > > > to end with a keyword.
> >
> > > > > 1. Initially startp=0 and endp=1. L = infinity
> > > > > 2. Increment endp till you encounter a keyword or it exceeds
> the
> > > > total
> > > > > length. Update frequencies. Check if you have all the
> keywords.
> > > > (This
> > > > > can be done in O(1) using a bitmap or similar). If it exceeds
> the
> > > > > total length, QUIT.
> > > > > 3. If the str(startp,endp) contains all keywords and length <
> L,
> > > > save
> > > > > values of startp and endp.
> > > > > 4. Now, increment startp, till you get a keyword. If the
> > > > > str(startp,endp) still contains all keywords, update saved
> values of
> > > > > startp and endp.
> > > > > 5. Repeat step 4 till str(startp,endp) does NOT contain all
> > > > keywords.
> > > > > 6. Goto step 2.
> >
> > > > > The final values of startp and endp should give you the
> minimum
> > > > summary.
> > > > > Since both values go from 0 to N-1, its O(N).
> >
> > > > > ~Vishal
> >
> > > > > On 9/24/07, *daizisheng* < [EMAIL PROTECTED]
> > > > 
> > > > > >>
> wrote:
> >
> > > > > I think hash method is ok, at lease in expectation way
> it's
> > > > O(n)
> > > > > why not use it? it's very effeciently
> >
> > > > > I think there should be some worst case O(n) algorithm,
> but
> > > > it will be
> > > > > more complex and not as effecient as the above one in
> practise
> >
> > > > > Sticker 写道:
> > > > > > Declare: this question is originally from Google. The
> > > > original form
> > > > > > is: given a document, how to find a shortest summary
> > > > containing all
> > > > > > the key words. After translated, it will be: given a
> > > > sequence,
> > > > > how to
> > > > > > find a shortest substring that contains all the items
> > > > required.
> > > > > > Example: a sequence "abaccdefgacel" and a set of key
> words
> > > > "a", "c",
> > > > > > "d" and "e". The shortest substring contianing all of
> the key
> > > > > words is
> > > > > > "accde". Find one of such shortest substrings. In the
> original
> > > > > > question, there is time complexity boundary O(N), where
> N
> > > > is the
> > > > > > length of the sequence.
> >
> > > > > > To me, this problem is rather questionable. So far my
> solution
> > > > > > requires a hash table that gives no conflict and can
> locate a
> > > > > key word
> > > > > > in O(1) time. Otherwise the time complexity will
> > > > definitely be
> > > > > related
> > > > > > to the number of key words.
> >
> > > > > > Does anyone have idea for a O(N) algorithm to solve this
> > > > problem?
> >
> > > yes, that's we need. but seems the starter of this thread who did not
> > > like hash,:)
>
>
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this g

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[Sticker]

To Vishal: My idea is similar to yours. I like to use hash table as
well. But I wonder which hash function can you use to insert and find
keywords with O(1) time? Keywords are not single characters. They are
normal words. That's basically what I am aftering.

On Sep 25, 2:11 pm, Mayur <[EMAIL PROTECTED]> wrote:
> Another possibility is to first pre-process the keywords into
> automaton-like structure (Google for Aho Corasick string matcher), and
> then use it over the document. This would probably be helpful only if
> the number of keywords is much smaller than the document itself..
>
> On 9/25/07, daizisheng <[EMAIL PROTECTED]> wrote:
>
>
>
> > Vishal 写道:
> > > Hash table should give you O(1) insertion and search complexity; which
> > > is what we need, right?
> > > There is no constraint on space complexity, I believe.
>
> > > On 9/24/07, * daizisheng* <[EMAIL PROTECTED]
> > > > wrote:
>
> > > the problem is you need a hash table to maintain all the keywords,:)
> > > because they do not have to be a single characters, or you can
> > > store them in
> > > array, but then you need binary search,:)
>
> > > Vishal 写道:
> > > > How about keeping two pointers - startp and endp.
> > > > Keep a count of frequencies of keywords between startp and endp,
> > > both
> > > > inclusive. We can use an array / hash table for this.
> > > > Now, the minimum length substring has to start with a keyword
> > > and has
> > > > to end with a keyword.
>
> > > > 1. Initially startp=0 and endp=1. L = infinity
> > > > 2. Increment endp till you encounter a keyword or it exceeds the
> > > total
> > > > length. Update frequencies. Check if you have all the keywords.
> > > (This
> > > > can be done in O(1) using a bitmap or similar). If it exceeds the
> > > > total length, QUIT.
> > > > 3. If the str(startp,endp) contains all keywords and length < L,
> > > save
> > > > values of startp and endp.
> > > > 4. Now, increment startp, till you get a keyword. If the
> > > > str(startp,endp) still contains all keywords, update saved values of
> > > > startp and endp.
> > > > 5. Repeat step 4 till str(startp,endp) does NOT contain all
> > > keywords.
> > > > 6. Goto step 2.
>
> > > > The final values of startp and endp should give you the minimum
> > > summary.
> > > > Since both values go from 0 to N-1, its O(N).
>
> > > > ~Vishal
>
> > > > On 9/24/07, *daizisheng* < [EMAIL PROTECTED]
> > > 
> > > > >> wrote:
>
> > > > I think hash method is ok, at lease in expectation way it's
> > > O(n)
> > > > why not use it? it's very effeciently
>
> > > > I think there should be some worst case O(n) algorithm, but
> > > it will be
> > > > more complex and not as effecient as the above one in practise
>
> > > > Sticker 写道:
> > > > > Declare: this question is originally from Google. The
> > > original form
> > > > > is: given a document, how to find a shortest summary
> > > containing all
> > > > > the key words. After translated, it will be: given a
> > > sequence,
> > > > how to
> > > > > find a shortest substring that contains all the items
> > > required.
> > > > > Example: a sequence "abaccdefgacel" and a set of key words
> > > "a", "c",
> > > > > "d" and "e". The shortest substring contianing all of the key
> > > > words is
> > > > > "accde". Find one of such shortest substrings. In the original
> > > > > question, there is time complexity boundary O(N), where N
> > > is the
> > > > > length of the sequence.
>
> > > > > To me, this problem is rather questionable. So far my solution
> > > > > requires a hash table that gives no conflict and can locate a
> > > > key word
> > > > > in O(1) time. Otherwise the time complexity will
> > > definitely be
> > > > related
> > > > > to the number of key words.
>
> > > > > Does anyone have idea for a O(N) algorithm to solve this
> > > problem?
>
> > yes, that's we need. but seems the starter of this thread who did not
> > like hash,:)


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[Mayur]

Another possibility is to first pre-process the keywords into
automaton-like structure (Google for Aho Corasick string matcher), and
then use it over the document. This would probably be helpful only if
the number of keywords is much smaller than the document itself..

On 9/25/07, daizisheng <[EMAIL PROTECTED]> wrote:
>
> Vishal 写道:
> > Hash table should give you O(1) insertion and search complexity; which
> > is what we need, right?
> > There is no constraint on space complexity, I believe.
> >
> > On 9/24/07, * daizisheng* <[EMAIL PROTECTED]
> > > wrote:
> >
> >
> > the problem is you need a hash table to maintain all the keywords,:)
> > because they do not have to be a single characters, or you can
> > store them in
> > array, but then you need binary search,:)
> >
> > Vishal 写道:
> > > How about keeping two pointers - startp and endp.
> > > Keep a count of frequencies of keywords between startp and endp,
> > both
> > > inclusive. We can use an array / hash table for this.
> > > Now, the minimum length substring has to start with a keyword
> > and has
> > > to end with a keyword.
> > >
> > > 1. Initially startp=0 and endp=1. L = infinity
> > > 2. Increment endp till you encounter a keyword or it exceeds the
> > total
> > > length. Update frequencies. Check if you have all the keywords.
> > (This
> > > can be done in O(1) using a bitmap or similar). If it exceeds the
> > > total length, QUIT.
> > > 3. If the str(startp,endp) contains all keywords and length < L,
> > save
> > > values of startp and endp.
> > > 4. Now, increment startp, till you get a keyword. If the
> > > str(startp,endp) still contains all keywords, update saved values of
> > > startp and endp.
> > > 5. Repeat step 4 till str(startp,endp) does NOT contain all
> > keywords.
> > > 6. Goto step 2.
> > >
> > > The final values of startp and endp should give you the minimum
> > summary.
> > > Since both values go from 0 to N-1, its O(N).
> > >
> > > ~Vishal
> > >
> > > On 9/24/07, *daizisheng* < [EMAIL PROTECTED]
> > 
> > > >> wrote:
> > >
> > >
> > > I think hash method is ok, at lease in expectation way it's
> > O(n)
> > > why not use it? it's very effeciently
> > >
> > > I think there should be some worst case O(n) algorithm, but
> > it will be
> > > more complex and not as effecient as the above one in practise
> > >
> > >
> > > Sticker 写道:
> > > > Declare: this question is originally from Google. The
> > original form
> > > > is: given a document, how to find a shortest summary
> > containing all
> > > > the key words. After translated, it will be: given a
> > sequence,
> > > how to
> > > > find a shortest substring that contains all the items
> > required.
> > > > Example: a sequence "abaccdefgacel" and a set of key words
> > "a", "c",
> > > > "d" and "e". The shortest substring contianing all of the key
> > > words is
> > > > "accde". Find one of such shortest substrings. In the original
> > > > question, there is time complexity boundary O(N), where N
> > is the
> > > > length of the sequence.
> > > >
> > > > To me, this problem is rather questionable. So far my solution
> > > > requires a hash table that gives no conflict and can locate a
> > > key word
> > > > in O(1) time. Otherwise the time complexity will
> > definitely be
> > > related
> > > > to the number of key words.
> > > >
> > > > Does anyone have idea for a O(N) algorithm to solve this
> > problem?
> > > >
> > > >
> > > > >
> > > >
> > > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > >
> >
> >
> >
> >
> >
> >
> > >
> yes, that's we need. but seems the starter of this thread who did not
> like hash,:)
>
>
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[daizisheng]

Vishal 写道:
> Hash table should give you O(1) insertion and search complexity; which 
> is what we need, right?
> There is no constraint on space complexity, I believe.
>
> On 9/24/07, * daizisheng* <[EMAIL PROTECTED] 
> > wrote:
>
>
> the problem is you need a hash table to maintain all the keywords,:)
> because they do not have to be a single characters, or you can
> store them in
> array, but then you need binary search,:)
>
> Vishal 写道:
> > How about keeping two pointers - startp and endp.
> > Keep a count of frequencies of keywords between startp and endp,
> both
> > inclusive. We can use an array / hash table for this.
> > Now, the minimum length substring has to start with a keyword
> and has
> > to end with a keyword.
> >
> > 1. Initially startp=0 and endp=1. L = infinity
> > 2. Increment endp till you encounter a keyword or it exceeds the
> total
> > length. Update frequencies. Check if you have all the keywords.
> (This
> > can be done in O(1) using a bitmap or similar). If it exceeds the
> > total length, QUIT.
> > 3. If the str(startp,endp) contains all keywords and length < L,
> save
> > values of startp and endp.
> > 4. Now, increment startp, till you get a keyword. If the
> > str(startp,endp) still contains all keywords, update saved values of
> > startp and endp.
> > 5. Repeat step 4 till str(startp,endp) does NOT contain all
> keywords.
> > 6. Goto step 2.
> >
> > The final values of startp and endp should give you the minimum
> summary.
> > Since both values go from 0 to N-1, its O(N).
> >
> > ~Vishal
> >
> > On 9/24/07, *daizisheng* < [EMAIL PROTECTED]
> 
> > >> wrote:
> >
> >
> > I think hash method is ok, at lease in expectation way it's
> O(n)
> > why not use it? it's very effeciently
> >
> > I think there should be some worst case O(n) algorithm, but
> it will be
> > more complex and not as effecient as the above one in practise
> >
> >
> > Sticker 写道:
> > > Declare: this question is originally from Google. The
> original form
> > > is: given a document, how to find a shortest summary
> containing all
> > > the key words. After translated, it will be: given a
> sequence,
> > how to
> > > find a shortest substring that contains all the items
> required.
> > > Example: a sequence "abaccdefgacel" and a set of key words
> "a", "c",
> > > "d" and "e". The shortest substring contianing all of the key
> > words is
> > > "accde". Find one of such shortest substrings. In the original
> > > question, there is time complexity boundary O(N), where N
> is the
> > > length of the sequence.
> > >
> > > To me, this problem is rather questionable. So far my solution
> > > requires a hash table that gives no conflict and can locate a
> > key word
> > > in O(1) time. Otherwise the time complexity will
> definitely be
> > related
> > > to the number of key words.
> > >
> > > Does anyone have idea for a O(N) algorithm to solve this
> problem?
> > >
> > >
> > > >
> > >
> > >
> >
> >
> >
> >
> >
> >
> > >
>
>
>
>
>
>
> >
yes, that's we need. but seems the starter of this thread who did not 
like hash,:)


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[Vishal]

Hash table should give you O(1) insertion and search complexity; which is
what we need, right?
There is no constraint on space complexity, I believe.

On 9/24/07, daizisheng <[EMAIL PROTECTED]> wrote:
>
>
> the problem is you need a hash table to maintain all the keywords,:)
> because they do not have to be a single characters, or you can store them
> in
> array, but then you need binary search,:)
>
> Vishal 写道:
> > How about keeping two pointers - startp and endp.
> > Keep a count of frequencies of keywords between startp and endp, both
> > inclusive. We can use an array / hash table for this.
> > Now, the minimum length substring has to start with a keyword and has
> > to end with a keyword.
> >
> > 1. Initially startp=0 and endp=1. L = infinity
> > 2. Increment endp till you encounter a keyword or it exceeds the total
> > length. Update frequencies. Check if you have all the keywords. (This
> > can be done in O(1) using a bitmap or similar). If it exceeds the
> > total length, QUIT.
> > 3. If the str(startp,endp) contains all keywords and length < L, save
> > values of startp and endp.
> > 4. Now, increment startp, till you get a keyword. If the
> > str(startp,endp) still contains all keywords, update saved values of
> > startp and endp.
> > 5. Repeat step 4 till str(startp,endp) does NOT contain all keywords.
> > 6. Goto step 2.
> >
> > The final values of startp and endp should give you the minimum summary.
> > Since both values go from 0 to N-1, its O(N).
> >
> > ~Vishal
> >
> > On 9/24/07, *daizisheng* <[EMAIL PROTECTED]
> > > wrote:
> >
> >
> > I think hash method is ok, at lease in expectation way it's O(n)
> > why not use it? it's very effeciently
> >
> > I think there should be some worst case O(n) algorithm, but it will
> be
> > more complex and not as effecient as the above one in practise
> >
> >
> > Sticker 写道:
> > > Declare: this question is originally from Google. The original
> form
> > > is: given a document, how to find a shortest summary containing
> all
> > > the key words. After translated, it will be: given a sequence,
> > how to
> > > find a shortest substring that contains all the items required.
> > > Example: a sequence "abaccdefgacel" and a set of key words "a",
> "c",
> > > "d" and "e". The shortest substring contianing all of the key
> > words is
> > > "accde". Find one of such shortest substrings. In the original
> > > question, there is time complexity boundary O(N), where N is the
> > > length of the sequence.
> > >
> > > To me, this problem is rather questionable. So far my solution
> > > requires a hash table that gives no conflict and can locate a
> > key word
> > > in O(1) time. Otherwise the time complexity will definitely be
> > related
> > > to the number of key words.
> > >
> > > Does anyone have idea for a O(N) algorithm to solve this problem?
> > >
> > >
> > > >
> > >
> > >
> >
> >
> >
> >
> >
> >
> > >
>
>
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[daizisheng]

the problem is you need a hash table to maintain all the keywords,:) 
because they do not have to be a single characters, or you can store them in
array, but then you need binary search,:)

Vishal 写道:
> How about keeping two pointers - startp and endp.
> Keep a count of frequencies of keywords between startp and endp, both 
> inclusive. We can use an array / hash table for this.
> Now, the minimum length substring has to start with a keyword and has 
> to end with a keyword.
>
> 1. Initially startp=0 and endp=1. L = infinity
> 2. Increment endp till you encounter a keyword or it exceeds the total 
> length. Update frequencies. Check if you have all the keywords. (This 
> can be done in O(1) using a bitmap or similar). If it exceeds the 
> total length, QUIT.
> 3. If the str(startp,endp) contains all keywords and length < L, save 
> values of startp and endp.
> 4. Now, increment startp, till you get a keyword. If the 
> str(startp,endp) still contains all keywords, update saved values of 
> startp and endp.
> 5. Repeat step 4 till str(startp,endp) does NOT contain all keywords.
> 6. Goto step 2.
>
> The final values of startp and endp should give you the minimum summary.
> Since both values go from 0 to N-1, its O(N).
>
> ~Vishal
>
> On 9/24/07, *daizisheng* <[EMAIL PROTECTED] 
> > wrote:
>
>
> I think hash method is ok, at lease in expectation way it's O(n)
> why not use it? it's very effeciently
>
> I think there should be some worst case O(n) algorithm, but it will be
> more complex and not as effecient as the above one in practise
>
>
> Sticker 写道:
> > Declare: this question is originally from Google. The original form
> > is: given a document, how to find a shortest summary containing all
> > the key words. After translated, it will be: given a sequence,
> how to
> > find a shortest substring that contains all the items required.
> > Example: a sequence "abaccdefgacel" and a set of key words "a", "c",
> > "d" and "e". The shortest substring contianing all of the key
> words is
> > "accde". Find one of such shortest substrings. In the original
> > question, there is time complexity boundary O(N), where N is the
> > length of the sequence.
> >
> > To me, this problem is rather questionable. So far my solution
> > requires a hash table that gives no conflict and can locate a
> key word
> > in O(1) time. Otherwise the time complexity will definitely be
> related
> > to the number of key words.
> >
> > Does anyone have idea for a O(N) algorithm to solve this problem?
> >
> >
> > >
> >
> >
>
>
>
>
>
>
> >


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[Vishal]

How about keeping two pointers - startp and endp.
Keep a count of frequencies of keywords between startp and endp, both
inclusive. We can use an array / hash table for this.
Now, the minimum length substring has to start with a keyword and has to end
with a keyword.

1. Initially startp=0 and endp=1. L = infinity
2. Increment endp till you encounter a keyword or it exceeds the total
length. Update frequencies. Check if you have all the keywords. (This can be
done in O(1) using a bitmap or similar). If it exceeds the total length,
QUIT.
3. If the str(startp,endp) contains all keywords and length < L, save values
of startp and endp.
4. Now, increment startp, till you get a keyword. If the str(startp,endp)
still contains all keywords, update saved values of startp and endp.
5. Repeat step 4 till str(startp,endp) does NOT contain all keywords.
6. Goto step 2.

The final values of startp and endp should give you the minimum summary.
Since both values go from 0 to N-1, its O(N).

~Vishal

On 9/24/07, daizisheng <[EMAIL PROTECTED]> wrote:
>
>
> I think hash method is ok, at lease in expectation way it's O(n)
> why not use it? it's very effeciently
>
> I think there should be some worst case O(n) algorithm, but it will be
> more complex and not as effecient as the above one in practise
>
>
> Sticker 写道:
> > Declare: this question is originally from Google. The original form
> > is: given a document, how to find a shortest summary containing all
> > the key words. After translated, it will be: given a sequence, how to
> > find a shortest substring that contains all the items required.
> > Example: a sequence "abaccdefgacel" and a set of key words "a", "c",
> > "d" and "e". The shortest substring contianing all of the key words is
> > "accde". Find one of such shortest substrings. In the original
> > question, there is time complexity boundary O(N), where N is the
> > length of the sequence.
> >
> > To me, this problem is rather questionable. So far my solution
> > requires a hash table that gives no conflict and can locate a key word
> > in O(1) time. Otherwise the time complexity will definitely be related
> > to the number of key words.
> >
> > Does anyone have idea for a O(N) algorithm to solve this problem?
> >
> >
> > >
> >
> >
>
>
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Google Interview Question: find shortest summary containing all key words

[daizisheng]

I think hash method is ok, at lease in expectation way it's O(n)
why not use it? it's very effeciently

I think there should be some worst case O(n) algorithm, but it will be 
more complex and not as effecient as the above one in practise


Sticker 写道:
> Declare: this question is originally from Google. The original form
> is: given a document, how to find a shortest summary containing all
> the key words. After translated, it will be: given a sequence, how to
> find a shortest substring that contains all the items required.
> Example: a sequence "abaccdefgacel" and a set of key words "a", "c",
> "d" and "e". The shortest substring contianing all of the key words is
> "accde". Find one of such shortest substrings. In the original
> question, there is time complexity boundary O(N), where N is the
> length of the sequence.
>
> To me, this problem is rather questionable. So far my solution
> requires a hash table that gives no conflict and can locate a key word
> in O(1) time. Otherwise the time complexity will definitely be related
> to the number of key words.
>
> Does anyone have idea for a O(N) algorithm to solve this problem?
>
>
> >
>
>   


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---