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

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 sharadsin...@gmail.com 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

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

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

[Navneet]

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

On Oct 1, 3:37 pm, Siddhartha Banerjee thefourrup...@gmail.com
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

[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 mans.aus...@gmail.com wrote:
 Your code does not works proper;y for all cases







 On Mon, Aug 1, 2011 at 10:42 PM, Rohit jalan jalanha...@gmail.com 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.comwrote:

  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

[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 gdroc...@gmail.com 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 mans.aus...@gmail.com wrote:
 Your code does not works proper;y for all cases







 On Mon, Aug 1, 2011 at 10:42 PM, Rohit jalan jalanha...@gmail.com 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.comwrote:

  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.

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 dgdi...@gmail.com 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 gdroc...@gmail.com 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 mans.aus...@gmail.com wrote:
  Your code does not works proper;y for all cases
 
 
 
 
 
 
 
  On Mon, Aug 1, 2011 at 10:42 PM, Rohit jalan jalanha...@gmail.com
 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.comwrote:
 
   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

[surender sanke]

@Dave awesome..!

On Sat, Jul 16, 2011 at 7:15 PM, Dave dave_and_da...@juno.com 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[j0x]++. 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[(j16)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 anand.shastr...@gmail.com 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

[Dumanshu]

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

On Jul 16, 6:28 am, Anand Shastri anand.shastr...@gmail.com 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

[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[j0x]++. 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[(j16)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 anand.shastr...@gmail.com 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 sunny816.i...@gmail.comwrote:

 @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
 algorithm.h

 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]

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.

[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

[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 jainv...@gmail.com 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 ashg...@gmail.com 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, adityasir...@gmail.com 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 wujinchen...@gmail.comwrote:

  @Piyush， how to deal with this case :100 , 10

  2011/5/27 Piyush Sinha ecstasy.piy...@gmail.com

  we can work out if we sort according to the leftmost integer

  On 5/27/11, adityasir...@gmail.com 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 jagadish1...@gmail.com
  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 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 

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.

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
sravanreddy...@gmail.comwrote:

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

[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 crazy.logic.k...@gmail.com 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 dave_and_da...@juno.com wrote:
  @Shubham: Try 8, 89, 7. Your algorithm gives 8897, but the right
  answer is 8987.

  Dave

  On May 27, 1:11 pm, shubham shubh2...@gmail.com 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

[sanjeev chakravarty]

Here is a Java impl...

public class LargestPossibleNumber {

static class LPNComparator implements ComparatorString {

@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(TreeSetString set) {

IteratorString 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[]) {

TreeSetString set = new TreeSetString(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.

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

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.

[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 suprajasank...@gmail.com
wrote:
 Hi

 Isnt this the Kadane's (largest subarray) problem ?

 Rgds
 Supraja J

 On Fri, May 27, 2011 at 9:41 AM, anshu mishra 
 anshumishra6...@gmail.comwrote:









  @all go through this code

  #includeiostream
  #includealgorithm

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

[Dave]

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

Dave

On May 27, 1:11 pm, shubham shubh2...@gmail.com 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.

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 dave_and_da...@juno.com wrote:

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

 Dave

 On May 27, 1:11 pm, shubham shubh2...@gmail.com 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

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

[algogeeks] Re: GOOGLE INTERVIEW QUESTION

[shubham]

check this one out:

#includeiostream
#includecstdio
#includevector
#includecstring
using namespace std;
int check_palin(string str,int *start)
{
int pos=-1,ret,size=str.size()-1;
char last_char=str[size];
while(possize)
{
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;
vectorstring palin,str;
cinarr;str.push_back(arr);
while(arr!=)
{
int s=0,e=0,max=0,start=0,end=0,len;
string tmp=;
for(int i=0;iarr.size();i++)
{
tmp+=arr[i];
len=check_palin(tmp,s);
if(lenmax){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;ipalin.size();i++) coutpalin[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.

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 shubh2...@gmail.com wrote:
 check this one out:

 #includeiostream
 #includecstdio
 #includevector
 #includecstring
 using namespace std;
 int check_palin(string str,int *start)
 {
    int pos=-1,ret,size=str.size()-1;
    char last_char=str[size];
    while(possize)
    {
        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;
    vectorstring palin,str;
    cinarr;str.push_back(arr);
    while(arr!=)
    {
        int s=0,e=0,max=0,start=0,end=0,len;
        string tmp=;
        for(int i=0;iarr.size();i++)
        {
            tmp+=arr[i];
            len=check_palin(tmp,s);
            if(lenmax){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;ipalin.size();i++) coutpalin[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

[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 web...@gmail.com wrote:

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

 2011/1/7 vaibhav agrawal agrvaib...@gmail.com

 @Douglas, nicely put!!!


 On Fri, Jan 7, 2011 at 8:37 PM, Douglas Diniz dgdi...@gmail.com 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++ avpostni...@gmail.com 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.

[algogeeks] Re: Google Interview Question

[SM]

Corrupted heap may be the case.

On Jan 6, 8:38 pm, soundar soundha...@gmail.com 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

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

Re: [algogeeks] Re: Google Interview Question

[vaibhav agrawal]

@Douglas, nicely put!!!

On Fri, Jan 7, 2011 at 8:37 PM, Douglas Diniz dgdi...@gmail.com 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++ avpostni...@gmail.com 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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

[Pedro Rezende]

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

2011/1/7 vaibhav agrawal agrvaib...@gmail.com

 @Douglas, nicely put!!!


 On Fri, Jan 7, 2011 at 8:37 PM, Douglas Diniz dgdi...@gmail.com 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++ avpostni...@gmail.com 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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

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

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 suhash.venkat...@gmail.com 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 anandut2...@gmail.com 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 technic@gmail.com 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
   

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 pacificpacific4...@gmail.com  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, Anandanandut2...@gmail.com  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, Terencetechnic@gmail.com  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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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

[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, Anandanandut2...@gmail.com  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, Terencetechnic@gmail.com  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 

[algogeeks] Re: Google Interview Question

[suhash]

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

On Dec 28, 12:10 pm, Terence technic@gmail.com 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, Anandanandut2...@gmail.com  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, Terencetechnic@gmail.com  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

[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 technic@gmail.com 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 pacificpacific4...@gmail.com  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, Anandanandut2...@gmail.com  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, Terencetechnic@gmail.com  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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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 anandut2...@gmail.com 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 technic@gmail.com 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.comalgogeeks%2bunsubscr...@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]

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 pacific4...@gmail.com 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 anandut2...@gmail.com 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 technic@gmail.com 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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

[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 sourabhjak...@gmail.com 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 gobind@gmail.com 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.comalgogeeks%2bunsubscr...@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

[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 vention.goth...@gmail.com 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 sourabhjak...@gmail.com 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 gobind@gmail.com 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.comalgogeeks%2bunsubscr...@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

[pratik kathalkar]

On Fri, Sep 17, 2010 at 3:36 PM, Krunal Modi krunalam...@gmail.com 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 gene.ress...@gmail.com 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 stdio.h
 
  // 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 shashank7andr...@gmail.com 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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

 #includeiostream.h
#includeconio.h
#includemath.h

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);
couta\n;

}
return;
}
 }
else
{
 a[i]='(';
addb(n-1,cnt+1,i+1,a);
if(cnt!=0)
 {
a[i]=')';
addb(n,cnt-1,i+1,a);
 }
}
}

void main()
{
 clrscr();
 char *a;
 int n;
 coutn = ;
 cinn;

 a=new char[n*2+1];

 a[n*2]='\0';
 addb(n,0,0,a);

 getch();
}


-- 
Pratik Kathalkar
CoEP
BTech IT
8149198343

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

[vikas kumar]

nice recurrence

On Sep 14, 9:29 pm, Gene gene.ress...@gmail.com 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 stdio.h

 // 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 shashank7andr...@gmail.com 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-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 anike...@gmail.com 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 ankur.mast@gmail.com wrote:



  @bittuu
  write your algo then code

  On Tue, Sep 14, 2010 at 1:36 PM, bittu shashank7andr...@gmail.com wrote:
   #includestdlib.h
   #includestdio.h
   #includemath.h
   #includeconio.h

   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 (square100);//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 

[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 gene.ress...@gmail.com 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 stdio.h

 // 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 shashank7andr...@gmail.com 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.

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 shashank7andr...@gmail.com wrote:

 #includestdlib.h
 #includestdio.h
 #includemath.h
 #includeconio.h
  ///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 (square100);//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 (gametotalgames);



 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.comalgogeeks%2bunsubscr...@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

[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 stdio.h

// 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: ()()()

On Sep 14, 

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

[bittu]

#includestdlib.h
#includestdio.h
#includemath.h
#includeconio.h
 ///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 (square100);//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 (gametotalgames);



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.

[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 stdio.h

// 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 shashank7andr...@gmail.com 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.

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

[siddharth srivastava]

Hi

On 14 September 2010 13:33, bittu shashank7andr...@gmail.com wrote:

 #includestdlib.h
 #includestdio.h
 #includemath.h
 #includeconio.h
  ///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 (square100);//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 (gametotalgames);



 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.comalgogeeks%2bunsubscr...@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 ankur.mast@gmail.com wrote:
 @bittuu
 write your algo then code









 On Tue, Sep 14, 2010 at 1:36 PM, bittu shashank7andr...@gmail.com wrote:
  #includestdlib.h
  #includestdio.h
  #includemath.h
  #includeconio.h

  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 (square100);//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 (gametotalgames);

  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 algoge...@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups 
  .com
  .
  For more options, visit this group at
 

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

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 erarpitagar...@gmail.comwrote:

 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.comalgogeeks%2bunsubscr...@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: 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)strlen(final_result) array then
 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 kN).

 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 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)strlen(final_result) array then
 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 kN).

 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)strlen(final_result) array then
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 kN).


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]

 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

[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

[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

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

reposting since it didn't appear yesterday, apologies

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)
 requirement we must assume that m 

[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 map
  #include string
  #include iostream
  #include algorithm
  #include iterator

  using namespace std;

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

  };

  ostream  operator  (ostream  out, const Range r) {
  outrange size: r.size() [;
  copy(r.first, r.second, ostream_iteratorchar(out, ));
  out];
  return out;

  }

  typedef mapchar, int 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
  coutrangeendl;
  }
  }
  }
  

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

[Andrey]

Check this program:

#include map
#include string
#include iostream
#include algorithm
#include iterator

using namespace std;

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

ostream  operator  (ostream  out, const Range r) {
outrange size: r.size() [;
copy(r.first, r.second, ostream_iteratorchar(out, ));
out];
return out;
}


typedef mapchar, int 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
coutrangeendl;
}
}
}
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()) {
coutThe shortes subsequence is: rangeendl;
} else {
coutNo solution...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 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

[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 map
 #include string
 #include iostream
 #include algorithm
 #include iterator

 using namespace std;

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

 };

 ostream  operator  (ostream  out, const Range r) {
 outrange size: r.size() [;
 copy(r.first, r.second, ostream_iteratorchar(out, ));
 out];
 return out;

 }

 typedef mapchar, int 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
 coutrangeendl;
 }
 }
 }
 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()) {
 coutThe shortes subsequence is: rangeendl;
 } else {
 coutNo solution...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 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]

We might even use String Trie. The search time would be O(m) where m is the
length of maximum length keyword. Since mN (normally), it would be as good
as O(1).
This would of course require preprocessing. Again, I am assuming no
constraint on space.

On 9/25/07, Sticker [EMAIL PROTECTED] 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]
mailto:[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]
mailto:[EMAIL PROTECTED]
 mailto:[EMAIL PROTECTED] mailto:[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

[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]
   mailto:[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]
   mailto:[EMAIL PROTECTED]
mailto:[EMAIL PROTECTED] mailto:[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]

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] 
 mailto:[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]

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]
  mailto:[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]

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] 
 mailto:[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]
 mailto:[EMAIL PROTECTED]
  mailto:[EMAIL PROTECTED] mailto:[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]
  mailto:[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]
  mailto:[EMAIL PROTECTED]
   mailto:[EMAIL PROTECTED] mailto:[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
-~--~~~~--~~--~--~---