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

[Ian Martin Ajzenszmidt]

On Friday, 8 July 2011 04:13:38 UTC+10, Piyush Sinha wrote:
 

 Given an array of integers A, give an algorithm to find the longest
 Arithmetic progression in it, i.e find a sequence i1  i2  …  ik,
 such that

 A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
 largest possible.

 The sequence S1, S2, …, Sk is called an arithmetic progression if

 Sj+1 – Sj is a constant.

Click on the following links or copy and paste them  into your browser. 
Many interesting possibilities.
https://www.google.com.au/search?client=ubuntuchannel=fsq=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that+A[i1ie=utf-8oe=utf-8redir_esc=ei=GpQRUZXnJKaeiAen7oDYAw
 


http://scholar.google.com/scholar?hl=enq=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that++A[i1]%2C+A[i2]%2C+%E2%80%A6%2C+A[ik]+forms+an+arithmetic+progression%2C+and+k+is+the+largest+possible.btnG=as_sdt=1%2C5as_sdtp=

 -- 
 *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 unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: GOOGLE Q1

[Vandana Bachani]

In the first pass create a difference array of size n-1 where n is the size
of the input array.
D[i] = A[i+1] - A[i]
Look for for the longest consecutive no. of times an element is repeated in
the difference array.

public void longestAP(int[] a, int n) {
 int[] diff = new int[n-1];
 for(int i = 0; i  n-1; i++) {
  diff[i] = a[i+1]-a[i];
 }
 int maxDiff = diff[0], maxi = 0, maxCount = 1;
 int currentDiff = -1, currentCount = 0, currenti = -1;
 for(int i = 1; i  n-1; i++) {
  if(diff[i] == maxDiff) { maxCount++; }
  else {
   if(diff[i] == currentDiff) { currentCount++; if (currentCount 
maxCount) { maxDiff = currentDiff; maxCount = currentCount; maxi =
currenti;}}
   else {
currentDiff = diff[i]; currenti = i; currentCount = 1;
   }
  }
 }
 System.out.print(Elements of the AP: ) ;
 for(int i = maxi; i = maxi+maxCount; i++) {
  System.out.print(a[i]+ );
 }
 System.out.println();
}

On Tue, Feb 5, 2013 at 5:33 PM, Ian Martin Ajzenszmidt iajzens...@gmail.com
 wrote:



 On Friday, 8 July 2011 04:13:38 UTC+10, Piyush Sinha wrote:


 Given an array of integers A, give an algorithm to find the longest
 Arithmetic progression in it, i.e find a sequence i1  i2  …  ik,
 such that

 A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
 largest possible.

 The sequence S1, S2, …, Sk is called an arithmetic progression if

 Sj+1 – Sj is a constant.

 Click on the following links or copy and paste them  into your browser.
 Many interesting possibilities.

 https://www.google.com.au/search?client=ubuntuchannel=fsq=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that+A[i1ie=utf-8oe=utf-8redir_esc=ei=GpQRUZXnJKaeiAen7oDYAw


 http://scholar.google.com/scholar?hl=enq=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that++A[i1]%2C+A[i2]%2C+%E2%80%A6%2C+A[ik]+forms+an+arithmetic+progression%2C+and+k+is+the+largest+possible.btnG=as_sdt=1%2C5as_sdtp=

 --
 *Piyush Sinha*
 *IIIT, Allahabad*
 *+91-8792136657*
 *+91-7483122727*
 *https://www.facebook.com/**profile.php?id=10655377926https://www.facebook.com/profile.php?id=10655377926*

  --
 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.
 For more options, visit https://groups.google.com/groups/opt_out.






-- 
Vandana Bachani
Graduate Student, MSCE
Computer Science  Engineering Department
Texas AM University, College Station

-- 
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.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: GOOGLE Q1

[bharat b]

http://theory.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf

On Fri, Nov 16, 2012 at 8:55 PM, rajesh pandey rajesh.pandey.i...@gmail.com
 wrote:

 I think its the stricter version of LIS ,  where when you  see for the
 increasing number  , just see the number which is greater with the number k
 than the previous one.

 Thanks ,
 Rajesh Pandey


 On Fri, Nov 16, 2012 at 7:55 PM, bharat b bagana.bharatku...@gmail.comwrote:

 @deepak : all the numbers in the array should be continuous or those k
 elemenst can be any where ?


 On Thu, Nov 15, 2012 at 2:18 PM, deepak mishra 
 deepakmnni...@gmail.comwrote:



 On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote:

 Given an array of integers A, give an algorithm to find the longest
 Arithmetic progression in it, i.e find a sequence i1  i2  …  ik,
 such that

 A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
 largest possible.

 The sequence S1, S2, …, Sk is called an arithmetic progression if

 Sj+1 – Sj is a constant.

 --
 *Piyush Sinha*
 *IIIT, Allahabad*
 *+91-8792136657*
 *+91-7483122727*
 *https://www.facebook.com/**profile.php?id=10655377926https://www.facebook.com/profile.php?id=10655377926*

  --
 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/-/umM2YKQz-9oJ.

 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.


-- 

Re: [algogeeks] Re: GOOGLE Q1

[bharat b]

@deepak : all the numbers in the array should be continuous or those k
elemenst can be any where ?

On Thu, Nov 15, 2012 at 2:18 PM, deepak mishra deepakmnni...@gmail.comwrote:



 On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote:

 Given an array of integers A, give an algorithm to find the longest
 Arithmetic progression in it, i.e find a sequence i1  i2  …  ik,
 such that

 A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
 largest possible.

 The sequence S1, S2, …, Sk is called an arithmetic progression if

 Sj+1 – Sj is a constant.

 --
 *Piyush Sinha*
 *IIIT, Allahabad*
 *+91-8792136657*
 *+91-7483122727*
 *https://www.facebook.com/**profile.php?id=10655377926https://www.facebook.com/profile.php?id=10655377926*

  --
 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/-/umM2YKQz-9oJ.

 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 Q1

[rajesh pandey]

I think its the stricter version of LIS ,  where when you  see for the
increasing number  , just see the number which is greater with the number k
than the previous one.

Thanks ,
Rajesh Pandey

On Fri, Nov 16, 2012 at 7:55 PM, bharat b bagana.bharatku...@gmail.comwrote:

 @deepak : all the numbers in the array should be continuous or those k
 elemenst can be any where ?


 On Thu, Nov 15, 2012 at 2:18 PM, deepak mishra deepakmnni...@gmail.comwrote:



 On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote:

 Given an array of integers A, give an algorithm to find the longest
 Arithmetic progression in it, i.e find a sequence i1  i2  …  ik,
 such that

 A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
 largest possible.

 The sequence S1, S2, …, Sk is called an arithmetic progression if

 Sj+1 – Sj is a constant.

 --
 *Piyush Sinha*
 *IIIT, Allahabad*
 *+91-8792136657*
 *+91-7483122727*
 *https://www.facebook.com/**profile.php?id=10655377926https://www.facebook.com/profile.php?id=10655377926*

  --
 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/-/umM2YKQz-9oJ.

 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.

[algogeeks] Re: GOOGLE Q1

[deepak mishra]

On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote:

 Given an array of integers A, give an algorithm to find the longest
 Arithmetic progression in it, i.e find a sequence i1  i2  …  ik,
 such that

 A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
 largest possible.

 The sequence S1, S2, …, Sk is called an arithmetic progression if

 Sj+1 – Sj is a constant.

 -- 
 *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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/yoGvjEFsqc4J.
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 Q1

[deepak mishra]

sdfsdfsdfsdfsdf

On Monday, 11 July 2011 17:01:36 UTC+5:30, Sunny wrote:

 @Divye sir
 yeah that will work fine if D is in reasonable limits ..

 On Mon, Jul 11, 2011 at 4:26 PM, DK divye...@gmail.com javascript:wrote:

 @Ritu: Your solution is incorrect.

 Consider

 1 3 41 43 47 49 90 100 110

 Maximum repeated 'd' value:
 '2' for the pairs (1,3), (41,43), (47,49) = 3 repeats. However, the 
 sequences themselves are not part of an AP.
 The longest AP is of size 3 - (90, 100, 110) with a d of 10.


 --
 DK

 http://twitter.com/divyekapoor
 http://www.divye.in

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

 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/zUK_Qh6FshsJ.
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 Q1

[deepak mishra]

On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote:

 Given an array of integers A, give an algorithm to find the longest
 Arithmetic progression in it, i.e find a sequence i1  i2  …  ik,
 such that

 A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
 largest possible.

 The sequence S1, S2, …, Sk is called an arithmetic progression if

 Sj+1 – Sj is a constant.

 -- 
 *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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/Y0gqhC9c0I4J.
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 Q1

[deepak mishra]

On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote:

 Given an array of integers A, give an algorithm to find the longest
 Arithmetic progression in it, i.e find a sequence i1  i2  …  ik,
 such that

 A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
 largest possible.

 The sequence S1, S2, …, Sk is called an arithmetic progression if

 Sj+1 – Sj is a constant.

 -- 
 *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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/umM2YKQz-9oJ.
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 Q : all anagrams next to each other

[shashi kant]

A solution given below taken from cracking the Coding interview  book...

Solution is create a Comparator and a small change in compare method is
that u sort the characters of that string and then compare.

and just sort the arrays, using this compareTo method instead of the usual
one.
Arrays.sort(array, new AnagramComparator());



public class AnagramComparator implements ComparatorString {
public String sortChars(String s) {
char[] content = s.toCharArray();
Arrays.sort(content);
return new String(content);
}
public int compare(String s1, String s2) {
return sortChars(s1).compareTo(sortChars(s2));
}
}






*Shashi Kant *
***Think positive and find fuel in failure*
http://thinkndoawesome.blogspot.com/
*System/Software Engineer*
*Hewlett-Packard India Software Operations.
*



On Sun, May 27, 2012 at 2:56 AM, Navin Gupta navin.nit...@gmail.com wrote:

 @jalaj :-  we will be sorting a copy of the word and then matching the
 sorted_sequence with the sorted_sequence of the copy of other words.
 It will still be in-place, because we are using a space of Word size where
 the input is a dictionary.
 This is an amortized in-place.

 --
 Navin Kumar Gupta
 Computer Science  Engg.
 National Institute of Technology,Jamshedpur

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

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

[Lucifer]

@vikas
I believe that if we generalize the question saying that there are N
students and K schools, such that each school can accommodate at max
(N/K) students (which means each school needs to accommodate exactly
(N/K) students. Given this we need to find the minimum distance.

By O(n^3), in this case it means O((N/K ^ 3)) .

Am I right ?


On 1 Aug, 11:48, vikas rai vikasloves...@gmail.com wrote:
 There is a set of 9 students and 3 schools Every school can be alloted
 atmax 3 students .Every school and student has its coordinates .Now we have
 to allot student in such a way that the sum of distance from all the
 student to the school should be minimum.
 We have to solve this in less than O(n^3) .

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

[Lucifer]

@ above
small correction..
/*
By O(n^3), in this case it means O((N/K ^ K)) .
*/
Therefore, N = 9, K=3.. hence (9/3)^3 = 27

On Aug 4, 4:24 am, Lucifer sourabhd2...@gmail.com wrote:
 @vikas
 I believe that if we generalize the question saying that there are N
 students and K schools, such that each school can accommodate at max
 (N/K) students (which means each school needs to accommodate exactly
 (N/K) students. Given this we need to find the minimum distance.

 By O(n^3), in this case it means O((N/K ^ 3)) .

 Am I right ?

 On 1 Aug, 11:48, vikas rai vikasloves...@gmail.com wrote:







  There is a set of 9 students and 3 schools Every school can be alloted
  atmax 3 students .Every school and student has its coordinates .Now we have
  to allot student in such a way that the sum of distance from all the
  student to the school should be minimum.
  We have to solve this in less than O(n^3) .

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

[Don]

What is N? This is a fixed-size problem so by definition, every
solution will be constant time.
Don

On Aug 1, 2:48 am, vikas rai vikasloves...@gmail.com wrote:
 There is a set of 9 students and 3 schools Every school can be alloted
 atmax 3 students .Every school and student has its coordinates .Now we have
 to allot student in such a way that the sum of distance from all the
 student to the school should be minimum.
 We have to solve this in less than O(n^3) .

-- 
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] Finds all the elements that appear more than n/3 times

[Abhishek Sharma]

I think it can be done by using some randomized algorithm.
Divide the array into subarrays of equal size and then pick a random
element from each group.Do it 3-4 times,if random number comes out equal
for most of the times,return that element.
I haven't tried it.

On Fri, Jul 13, 2012 at 10:53 AM, Ganesh M ganesh.muniya...@gmail.comwrote:

 I guess the 
 linkhttp://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.htmltalks
  about modified quick sort approach. Remember, if your choise of pivot
 is bad everytime, this will have a worst case performance of O(n). You
 should refer to Selection 
 Algorithmhttp://en.wikipedia.org/wiki/Selection_algorithmfor better worst 
 case performance.

 On Wednesday, July 11, 2012 3:12:07 PM UTC+8, Navin Kumar wrote:

 @sachin:

 http://valis.cs.uiuc.edu/~**sariel/research/CG/applets/**
 linear_prog/median.htmlhttp://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html

 On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal sachingoyal@gmail.com
  wrote:

 To Mr. B
 how will you find median in O(n) time? please elaborate.


 On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote:

 I found a similar solution looking somewhere else.

 The solution for this problem is:
 a. There can be atmost 3 elements (only 3 distinct elements with each
 repeating n/3 times) -- check for this and done. -- O(n) time.
 b. There can be atmost 2 elements if not above case.

 1. Find the median of the input. O(N)
 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark
 for output if yes}*
 3. partition the array based on median found above. - O(n)  --
 {partition is single step in quicksort}
 4. find median in left partition from (3). - O(n)
 5. check if median element is repeared n/3 times or more - O(n)  *{mark
 for output if yes}*
 6. find median in right partition from (3). - O(n)
 7.  check if median element is repeared n/3 times or more - O(n)  *{mark
 for output if yes}*

 its 7*O(N) = O(N) solution. Constant space.

 we need not check further down or recursively. {why? reason it.. its
 simple}


 On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote:


 Design an algorithm that, given a list of n elements in an array,
 finds all the elements that appear more than n/3 times in the list. The
 algorithm should run in linear time

 ( n =0 ).

 You are expected to use comparisons and achieve linear time. No
 hashing/excessive space/ and don't use standard linear time deterministic
 selection algo.

  --
 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/-/PxIJd3So3tkJhttps://groups.google.com/d/msg/algogeeks/-/PxIJd3So3tkJ.


 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+unsubscribe@**
 googlegroups.com algogeeks%2bunsubscr...@googlegroups.com.
 For more options, visit this group at http://groups.google.com/**
 group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.


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

 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.




-- 
Abhishek Sharma
Under-Graduate Student,
PEC University of Technology

-- 
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] Finds all the elements that appear more than n/3 times

[Ganesh M]

I guess the 
linkhttp://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.htmltalks
 about modified quick sort approach. Remember, if your choise of pivot 
is bad everytime, this will have a worst case performance of O(n). You 
should refer to Selection 
Algorithmhttp://en.wikipedia.org/wiki/Selection_algorithmfor better worst 
case performance.

On Wednesday, July 11, 2012 3:12:07 PM UTC+8, Navin Kumar wrote:

 @sachin:


 http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html

 On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal 
 sachingoyal@gmail.comwrote:

 To Mr. B 
 how will you find median in O(n) time? please elaborate. 


 On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote: 

 I found a similar solution looking somewhere else.

 The solution for this problem is:
 a. There can be atmost 3 elements (only 3 distinct elements with each 
 repeating n/3 times) -- check for this and done. -- O(n) time.
 b. There can be atmost 2 elements if not above case.

 1. Find the median of the input. O(N)
 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark 
 for output if yes}*
 3. partition the array based on median found above. - O(n)  -- 
 {partition is single step in quicksort} 
 4. find median in left partition from (3). - O(n)
 5. check if median element is repeared n/3 times or more - O(n)  *{mark 
 for output if yes}* 
 6. find median in right partition from (3). - O(n)
 7.  check if median element is repeared n/3 times or more - O(n)  *{mark 
 for output if yes}*  

 its 7*O(N) = O(N) solution. Constant space.

 we need not check further down or recursively. {why? reason it.. its 
 simple}


 On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote: 


 Design an algorithm that, given a list of n elements in an array, finds 
 all the elements that appear more than n/3 times in the list. The 
 algorithm 
 should run in linear time

 ( n =0 ).

 You are expected to use comparisons and achieve linear time. No 
 hashing/excessive space/ and don't use standard linear time deterministic 
 selection algo.

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

 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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/lZKI47459WgJ.
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] Finds all the elements that appear more than n/3 times

[sachin goyal]

To Mr. B
how will you find median in O(n) time? please elaborate.

On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote:

 I found a similar solution looking somewhere else.

 The solution for this problem is:
 a. There can be atmost 3 elements (only 3 distinct elements with each 
 repeating n/3 times) -- check for this and done. -- O(n) time.
 b. There can be atmost 2 elements if not above case.

 1. Find the median of the input. O(N)
 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark 
 for output if yes}*
 3. partition the array based on median found above. - O(n)  -- {partition 
 is single step in quicksort}
 4. find median in left partition from (3). - O(n)
 5. check if median element is repeared n/3 times or more - O(n)  *{mark 
 for output if yes}* 
 6. find median in right partition from (3). - O(n)
 7.  check if median element is repeared n/3 times or more - O(n)  *{mark 
 for output if yes}*  

 its 7*O(N) = O(N) solution. Constant space.

 we need not check further down or recursively. {why? reason it.. its 
 simple}


 On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote:


 Design an algorithm that, given a list of n elements in an array, finds 
 all the elements that appear more than n/3 times in the list. The algorithm 
 should run in linear time

 ( n =0 ).

 You are expected to use comparisons and achieve linear time. No 
 hashing/excessive space/ and don't use standard linear time deterministic 
 selection algo.



-- 
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/-/PxIJd3So3tkJ.
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] Finds all the elements that appear more than n/3 times

[Navin Kumar]

@sachin: you can find median in linear sort.

http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html

On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal sachingoyal@gmail.comwrote:

 To Mr. B
 how will you find median in O(n) time? please elaborate.


 On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote:

 I found a similar solution looking somewhere else.

 The solution for this problem is:
 a. There can be atmost 3 elements (only 3 distinct elements with each
 repeating n/3 times) -- check for this and done. -- O(n) time.
 b. There can be atmost 2 elements if not above case.

 1. Find the median of the input. O(N)
 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark
 for output if yes}*
 3. partition the array based on median found above. - O(n)  -- {partition
 is single step in quicksort}
 4. find median in left partition from (3). - O(n)
 5. check if median element is repeared n/3 times or more - O(n)  *{mark
 for output if yes}*
 6. find median in right partition from (3). - O(n)
 7.  check if median element is repeared n/3 times or more - O(n)  *{mark
 for output if yes}*

 its 7*O(N) = O(N) solution. Constant space.

 we need not check further down or recursively. {why? reason it.. its
 simple}


 On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote:


 Design an algorithm that, given a list of n elements in an array, finds
 all the elements that appear more than n/3 times in the list. The algorithm
 should run in linear time

 ( n =0 ).

 You are expected to use comparisons and achieve linear time. No
 hashing/excessive space/ and don't use standard linear time deterministic
 selection algo.

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

 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] Finds all the elements that appear more than n/3 times

[Navin Kumar]

@sachin:

http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html

On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal sachingoyal@gmail.comwrote:

 To Mr. B
 how will you find median in O(n) time? please elaborate.


 On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote:

 I found a similar solution looking somewhere else.

 The solution for this problem is:
 a. There can be atmost 3 elements (only 3 distinct elements with each
 repeating n/3 times) -- check for this and done. -- O(n) time.
 b. There can be atmost 2 elements if not above case.

 1. Find the median of the input. O(N)
 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark
 for output if yes}*
 3. partition the array based on median found above. - O(n)  -- {partition
 is single step in quicksort}
 4. find median in left partition from (3). - O(n)
 5. check if median element is repeared n/3 times or more - O(n)  *{mark
 for output if yes}*
 6. find median in right partition from (3). - O(n)
 7.  check if median element is repeared n/3 times or more - O(n)  *{mark
 for output if yes}*

 its 7*O(N) = O(N) solution. Constant space.

 we need not check further down or recursively. {why? reason it.. its
 simple}


 On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote:


 Design an algorithm that, given a list of n elements in an array, finds
 all the elements that appear more than n/3 times in the list. The algorithm
 should run in linear time

 ( n =0 ).

 You are expected to use comparisons and achieve linear time. No
 hashing/excessive space/ and don't use standard linear time deterministic
 selection algo.

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

 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] Finds all the elements that appear more than n/3 times

[Nishant Pandey]

can some body please explain voting algo to me .

On Wed, Jul 11, 2012 at 12:42 PM, Navin Kumar algorithm.i...@gmail.comwrote:

 @sachin:


 http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html

 On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal 
 sachingoyal@gmail.comwrote:

 To Mr. B
 how will you find median in O(n) time? please elaborate.


 On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote:

 I found a similar solution looking somewhere else.

 The solution for this problem is:
 a. There can be atmost 3 elements (only 3 distinct elements with each
 repeating n/3 times) -- check for this and done. -- O(n) time.
 b. There can be atmost 2 elements if not above case.

 1. Find the median of the input. O(N)
 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark
 for output if yes}*
 3. partition the array based on median found above. - O(n)  --
 {partition is single step in quicksort}
 4. find median in left partition from (3). - O(n)
 5. check if median element is repeared n/3 times or more - O(n)  *{mark
 for output if yes}*
 6. find median in right partition from (3). - O(n)
 7.  check if median element is repeared n/3 times or more - O(n)  *{mark
 for output if yes}*

 its 7*O(N) = O(N) solution. Constant space.

 we need not check further down or recursively. {why? reason it.. its
 simple}


 On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote:


 Design an algorithm that, given a list of n elements in an array, finds
 all the elements that appear more than n/3 times in the list. The algorithm
 should run in linear time

 ( n =0 ).

 You are expected to use comparisons and achieve linear time. No
 hashing/excessive space/ and don't use standard linear time deterministic
 selection algo.

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

 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.

[algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times

[Mr.B]

I found a similar solution looking somewhere else.

The solution for this problem is:
a. There can be atmost 3 elements (only 3 distinct elements with each 
repeating n/3 times) -- check for this and done. -- O(n) time.
b. There can be atmost 2 elements if not above case.

1. Find the median of the input. O(N)
2. Check if median element is repeated N/3 times or more -- O(n) - *{mark 
for output if yes}*
3. partition the array based on median found above. - O(n)  -- {partition 
is single step in quicksort}
4. find median in left partition from (3). - O(n)
5. check if median element is repeared n/3 times or more - O(n)  *{mark for 
output if yes}* 
6. find median in right partition from (3). - O(n)
7.  check if median element is repeared n/3 times or more - O(n)  *{mark 
for output if yes}*  

its 7*O(N) = O(N) solution. Constant space.

we need not check further down or recursively. {why? reason it.. its simple}


On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote:


 Design an algorithm that, given a list of n elements in an array, finds 
 all the elements that appear more than n/3 times in the list. The algorithm 
 should run in linear time

 ( n =0 ).

 You are expected to use comparisons and achieve linear time. No 
 hashing/excessive space/ and don't use standard linear time deterministic 
 selection algo.



-- 
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/-/OYZtR1iwbGQJ.
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] Finds all the elements that appear more than n/3 times

[Balaji Subramanian]

My previous email got sent accidentally.. 

Assume if we have 90 elements and need to find 30 elements that are 
repeating..as per Sanjay's algo,divide it to 45 elements.. To find majority in 
45 elements, the number should repeat =  23 times.. This might not be valid 
since the number could repeat only 15 times if it's distributed uniformly 
across two sub arrays..

Let me know if am wrong..

Thanks,
Balaji

Apologies for brevity and spelling.

On Jul 2, 2012, at 11:47 PM, Balaji Subramanian balaji.subraman...@gmail.com 
wrote:

 Seems to be a nice algorithm. But won't think it would work..Majority number 
 element should repeat for more than n/2 times.. 
 
 Apologies for brevity and spelling.
 
 On Jul 2, 2012, at 1:46 PM, sanjay pandey sanjaypandey...@gmail.com wrote:
 
 i think the concept of majority elemnt can be applied here .
 1.divide array into 2 halves
 2.apply majority in each
 3.den from d two majority found do linear counts of dere frequency??
 
 
 -- 
 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] Finds all the elements that appear more than n/3 times

[Lomash Goyal]

we can use voting algorithm this..
maintain a variable count and a variable index.now make a scan for 1 to
n-3.during a scan initialize count with 1 and index with 0.now if
a[i]==a[index] then increment count else decrement count.when count reached
0.start again incrementing it when u get a new element and also update the
indexes.
now when the loop terminates then u might have got a suitable candidate.now
u have to make 3 more scans in order to check the frequency of
arr[index],arr[n-1] and arr[n].

On Sat, Jun 30, 2012 at 6:41 PM, saurabh singh saurab...@gmail.com wrote:


 @above


 On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote:


 Design an algorithm that, given a list of n elements in an array, finds
 all the elements that appear more than n/3 times in the list. The algorithm
 should run in linear time

 ( n =0 ).

 You are expected to use comparisons and achieve linear time. No 
 hashing/excessive
 space/ and don't use standard linear time deterministic selection algo.


 On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote:


 Design an algorithm that, given a list of n elements in an array, finds
 all the elements that appear more than n/3 times in the list. The algorithm
 should run in linear time

 ( n =0 ).

 You are expected to use comparisons and achieve linear time. No
 hashing/excessive space/ and don't use standard linear time deterministic
 selection algo.


 On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote:


 Design an algorithm that, given a list of n elements in an array, finds
 all the elements that appear more than n/3 times in the list. The algorithm
 should run in linear time

 ( n =0 ).

 You are expected to use comparisons and achieve linear time. No
 hashing/excessive space/ and don't use standard linear time deterministic
 selection algo.

  --
 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/-/0myz4OIStO8J.

 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.




-- 
Regards

Lomash Goyal
*
*

-- 
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] Finds all the elements that appear more than n/3 times

[saurabh singh]

@above


 On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote:


 Design an algorithm that, given a list of n elements in an array, finds
 all the elements that appear more than n/3 times in the list. The algorithm
 should run in linear time

 ( n =0 ).

 You are expected to use comparisons and achieve linear time. No 
 hashing/excessive
 space/ and don't use standard linear time deterministic selection algo.


 On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote:


 Design an algorithm that, given a list of n elements in an array, finds
 all the elements that appear more than n/3 times in the list. The algorithm
 should run in linear time

 ( n =0 ).

 You are expected to use comparisons and achieve linear time. No
 hashing/excessive space/ and don't use standard linear time deterministic
 selection algo.


 On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote:


 Design an algorithm that, given a list of n elements in an array, finds
 all the elements that appear more than n/3 times in the list. The algorithm
 should run in linear time

 ( n =0 ).

 You are expected to use comparisons and achieve linear time. No
 hashing/excessive space/ and don't use standard linear time deterministic
 selection algo.

  --
 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/-/0myz4OIStO8J.

 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 Q : all anagrams next to each other

[Navin Gupta]

@jalaj :-  we will be sorting a copy of the word and then matching the 
sorted_sequence with the sorted_sequence of the copy of other words.
It will still be in-place, because we are using a space of Word size where 
the input is a dictionary.
This is an amortized in-place.

-- 
Navin Kumar Gupta
Computer Science  Engg.
National Institute of Technology,Jamshedpur

-- 
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/-/n2tGzVxSLIYJ.
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 Q : all anagrams next to each other

[Gene]

This will work in fine, but multiplying primes requires arbitrary
precision arithmetic for keys of any significant length.

You don't need to compute a hash at all.  Just maintain two buffers
long enough to hold the longest word and an O(n) sort like counting
sort.  If you are using Latin (8-bit) characters, you don't even need
to complete the counting sort.  Just do the counting into arrays of
256 ints.  You'll end up with character histograms.  It's easy to
compare these rather than sorted strings.  They require O(2 log C) =
O(log C) storage and comparing them needs O(log C) int comparisons,
where C is the number of characters in the alphabet.  Since C is a
constant, this would normally be considered O(1) time and space.

On May 26, 2:52 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
 If you sort every word , then you will lose the original word as Ankita
 pointed out and if you keep a hashmap to track that it will not be inplace
 .,

 Is there any problem in the solution I gave Above , please point it out .









 On Fri, May 25, 2012 at 1:14 AM, Anika Jain anika.jai...@gmail.com wrote:
  I have a doubt. If u r doing inplace sorting of a word during checks for a
  word, wouldnt that change that word there itself? then how will the
  original anagram get restored to arrange in the output in sorted manner?

  On Thu, May 24, 2012 at 5:54 PM, Jitender Kumar 
  jitender...@gmail.comwrote:

  The complexity will be (N^2)W because the sorting can be done linear time
  O(W) for strings.

  On Thu, May 24, 2012 at 3:44 PM, WgpShashank bshashank7andr...@gmail.com
   wrote:

  Yeah , its the in-place approach strikes in mind at first look , just
  slightly clearing the complexity to O(N^2* Wlog(W)) , N is number of
  words in array  W is length of longest word in array , let me know i
  missed something ?

   original                 eat I ate att I the eel eth het
   after sorting          I I ate att can eat eel eth het the

  output should be  I I ate eat att can eel eth het the

  Shashank Mani Narayan
  Computer Science  Engineering
  Birla Institute of Technology,Mesra
  Founder Cracking The Code Lab  http://shashank7s.blogspot.com/;
  FB Pagehttp://www.facebook.com/pages/LestCode
  Google+http://gplus.to/wgpshashank
  Twitter https://twitter.com/wgpshashank;
  Puzzled Guy @ http://ashutosh7s.blogspot.com;
  FB Pagehttp://www.facebook.com/Puzzles.For.Puzzled.Minds

  On May 22, 8:18 am, Navin Gupta navin.nit...@gmail.com wrote:
   It can be done inplace, then Time Complexity will be O( N^2 x W )
  where N
   is no. of words and  W is word size.
   Start from the left and sort the current word.
   Keep a pointer  PTR  to the first index of the element left to process.
   Initially it will be 0.As we add words this pointer moves forwards.
   Now iterate the whole list of words to find all those words having same
   sorted sequence i.e. anagrams
   Whenver we get a word which is anagram of the current string, swap it
  with
   the string  pointed by PTR, move PTR forward.

   pseudoCode :-

   func( vectorstring v)
   {
      int n=v.size();
      for(int i=0;in;i++)
      {
         string currentWord = v[i];
         sort(currentWord);
         for(int j=i+1;jn;j++)
         {
             if ( sort(v[j]) == currentWord )    // anagrams found,
             {
                  swap( v[i] , v[j] );                 //move this string
  to
   the position next to pos of currentWord
                    i++;                                //and move the
  index
   of currentWord forward
             }
        }

   }

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

  --
  With regards,

  Jitender Kumar
  3rd year (Computer Engineering)
  NIT Kurukshetra
  Kurukshetra- 136119
   Mobile  +91-8529035751

   --
  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
  Anika 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
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

 --
 Regards,

 Jalaj Jaiswal
 Software Developer,
  Adobe Systems
 +91-9019947895
 *
 *
 FACEBOOK http://www.facebook.com/jalaj.jaiswal89
 

Re: [algogeeks] Re: Google Q : all anagrams next to each other

[Anika Jain]

I have a doubt. If u r doing inplace sorting of a word during checks for a
word, wouldnt that change that word there itself? then how will the
original anagram get restored to arrange in the output in sorted manner?

On Thu, May 24, 2012 at 5:54 PM, Jitender Kumar jitender...@gmail.comwrote:

 The complexity will be (N^2)W because the sorting can be done linear time
 O(W) for strings.


 On Thu, May 24, 2012 at 3:44 PM, WgpShashank 
 shashank7andr...@gmail.comwrote:

 Yeah , its the in-place approach strikes in mind at first look , just
 slightly clearing the complexity to O(N^2* Wlog(W)) , N is number of
 words in array  W is length of longest word in array , let me know i
 missed something ?

  original eat I ate att I the eel eth het
  after sorting  I I ate att can eat eel eth het the

 output should be  I I ate eat att can eel eth het the

 Shashank Mani Narayan
 Computer Science  Engineering
 Birla Institute of Technology,Mesra
 Founder Cracking The Code Lab  http://shashank7s.blogspot.com/;
 FB Page http://www.facebook.com/pages/LestCode
 Google+ http://gplus.to/wgpshashank
 Twitter https://twitter.com/wgpshashank;
 Puzzled Guy @ http://ashutosh7s.blogspot.com;
 FB Page http://www.facebook.com/Puzzles.For.Puzzled.Minds


 On May 22, 8:18 am, Navin Gupta navin.nit...@gmail.com wrote:
  It can be done inplace, then Time Complexity will be O( N^2 x W ) where
 N
  is no. of words and  W is word size.
  Start from the left and sort the current word.
  Keep a pointer  PTR  to the first index of the element left to process.
  Initially it will be 0.As we add words this pointer moves forwards.
  Now iterate the whole list of words to find all those words having same
  sorted sequence i.e. anagrams
  Whenver we get a word which is anagram of the current string, swap it
 with
  the string  pointed by PTR, move PTR forward.
 
  pseudoCode :-
 
  func( vectorstring v)
  {
 int n=v.size();
 for(int i=0;in;i++)
 {
string currentWord = v[i];
sort(currentWord);
for(int j=i+1;jn;j++)
{
if ( sort(v[j]) == currentWord )// anagrams found,
{
 swap( v[i] , v[j] ); //move this string
 to
  the position next to pos of currentWord
   i++;//and move the
 index
  of currentWord forward
}
   }
 
 
 
 
 
 
 
  }

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




 --
 With regards,

 Jitender Kumar
 3rd year (Computer Engineering)
 NIT Kurukshetra
 Kurukshetra- 136119
  Mobile  +91-8529035751

  --
 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
Anika 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 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Google Q : all anagrams next to each other

[Navin Gupta]

It can be done inplace, then Time Complexity will be O( N^2 x W ) where N 
is no. of words and  W is word size.
Start from the left and sort the current word.
Keep a pointer  PTR  to the first index of the element left to process. 
Initially it will be 0.As we add words this pointer moves forwards.
Now iterate the whole list of words to find all those words having same 
sorted sequence i.e. anagrams 
Whenver we get a word which is anagram of the current string, swap it with 
the string  pointed by PTR, move PTR forward.

pseudoCode :- 

func( vectorstring v)
{
   int n=v.size();
   for(int i=0;in;i++)
   {
  string currentWord = v[i];
  sort(currentWord);
  for(int j=i+1;jn;j++)
  {
  if ( sort(v[j]) == currentWord )// anagrams found, 
  {
   swap( v[i] , v[j] ); //move this string to 
the position next to pos of currentWord 
 i++;//and move the index 
of currentWord forward
  }
 }
}

-- 
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/-/h04_lKqCILQJ.
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 Q: longest word made of subwords within the list

[Abhishek]

@prem: can you please explain the approach clearly, I did't get the
approach.

regards
Abhishek

On May 23, 7:43 pm, Doom duman...@gmail.com wrote:
 I am trying to understand the question.. please let me know the answer for
 the following cases..

 case1:
 test
 testlong
 testlongtest
 testlongtestlong
 testtesttest

 case2:
 test
 testlong
 testlongtest

 case3:
 test
 longest

 case4:
 test
 testtes
 ttes
 testtesttes







 On Tuesday, 22 May 2012 18:15:16 UTC+5:30, ashgoel wrote:

  write a program to find the longest word made of other words. For
  instance, If my file has the following words (sorted):
  test
  tester
  testertest
  testing
  testingtester

  The longest word should be testingtester. Trie is the solution, what is
  the best Order possible?
  Best Regards
  Ashish Goel
  Think positive and find fuel in failure
  +919985813081
  +919966006652

-- 
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 Question Invoice -bills

[Don]

Atul,
I think that your approach will work, although it may take a huge
amount of time.
One way to potentially make it faster is to select the invoices with
the smallest number of combinations first.
If you first select all of the invoices with exactly one possible
combination, this will prevent you from wasting a lot of time
considering combinations for other invoices which require those bills.
After assigning all of the invoices with exactly one possible
combination, you can clear out all combinations for the other invoices
which use any of the assigned bills. That might result in more
invoices with exactly one possible combination, but it will almost
certainly narrow down the options significantly for the rest of the
problem.
This approach doesn't ensure a faster solution. I could come up with a
diabolical input set which would defeat it. But in most cases it
should speed things up a lot.
Don

On Mar 26, 11:32 pm, atul anand atul.87fri...@gmail.com wrote:
 @ankush: i told one approach above , but may i want clear . i am not saying
 this is the best approach to do so but it is one naive soln i came up with.

 so find all possible combination for each invoice and save it in some data
 structure.
 now start from 1st invoice and select 1st invoice combination say for
 invoice 80 = 50 + 30
 now search in next invoice(210) combination , if there is any combination
 for this invoice which does not include 50 and 30
 if yes there is one say  210= 10 + 10 +20 + 70 + 100 , we have a hit and do
 similar with other invoice . every time you move fwd make sure that you
 should search for combination which does not include any of those bill used
 in prev finding.
 if no, then we know that there is no point of moving fwd , so select
 another combination from prev invoice in this case its 80 and follow same
 as above.



 On Mon, Mar 26, 2012 at 5:56 PM, ankush.bago...@gmail.com wrote:
  **
  You can use dp to find subsets . But how is dp used for the overall
  probkem
  Sent from BlackBerry® on Airtel
  --
  *From: * atul anand atul.87fri...@gmail.com
  *Sender: * algogeeks@googlegroups.com
  *Date: *Mon, 26 Mar 2012 16:52:08 +0530
  *To: *algogeeks@googlegroups.com
  *ReplyTo: * algogeeks@googlegroups.com
  *Subject: *Re: [algogeeks] Google Question Invoice -bills

  @umer : dp approach is given in above post.

  On Mon, Mar 26, 2012 at 4:11 PM, Umer Farooq the.um...@gmail.com wrote:

  Well, they have specified in the question that you are dealing with
  big-data sets. So, recursion won't be a good option I guess.

  Can we solve it with dynamic programming technique?

  On Mon, Mar 26, 2012 at 2:24 PM, atul anand atul.87fri...@gmail.comwrote:

  one way to do it , is say first combination for invoice 80= 50 + 30
  now remove 80 and 30 from the input bills while finding combination from
  210 , check if it is possible
  if yes , we got one solution
  not select another invoice combination 80= 50 + 10 + 20
  now dont consider these values while find combination for 210.

  i guess there can be better way to solve this..

  On Mon, Mar 26, 2012 at 2:36 PM, Ankush Bagotra 
  ankush.bago...@gmail.com wrote:

  Ok now you have combination of each invoice .  What is the approach to
  take mutual exclusive combinations for so that sum of all bills equals
  sum of all invoices

  On Mon, Mar 26, 2012 at 2:16 PM, atul anand atul.87fri...@gmail.com
  wrote:
   it is similar to sum-subset problem following recurrance will solve
  this
   problem , you need to run algo for each invoice to find all
  combination

   F(n,k) = F(n,k-1) or F(n - a[k], k-1)
   base case :F(0,k)=1 for k=0
                           F(n,0)= 0 for n0.

   On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra 
  ankush.bago...@gmail.com
   wrote:

   There are 210 Invoices and 1700 bills – these bills add up to these
   invoices

   The association between  bills and invoices is lost . The only way to
   match them is by adding them up to correct amounts that are equal to
   the invoices.

   For Example :  there were 2 invoices for 80, 210 and you have bills
   for these 50, 10 ,10, 30 , 20, 70, 100 values

   One of the possible solution is :

   80=50 + 30
   210= 10 + 10 +20 + 70 + 100

   Other possible solution is

   80=50 + 10 + 20
   210= 30 +20 + 70 + 100

   What is the best possible way to get all solutions ? Remember you are
   dealing with big datasets

   -Kabir

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

Re: [algogeeks] Re: Google written test

[atul anand]

@Hemesh : dats would be an over kill , you are converting O(n) solution to
a subset sum problem which NP

On Tue, Mar 20, 2012 at 7:35 PM, Hemesh Singh hemesh.mn...@gmail.comwrote:

 Isn't it a standard subset sum problem? You can generate the Fibonacci
 numbers and put them in an array. Now just apply the standard algorithm to
 find that which Fibonacci numbers add up to make the given sum. Please
 correct me if I am wrong.


 On Mon, Mar 19, 2012 at 8:58 PM, atul anand atul.87fri...@gmail.comwrote:

 @Gene : yeah i skipped ur updated code...its dere

 @shady : it is similar to fib encoding...you just need to reverse the
 output from gene code and append '1' at the end...
 while decoding it ...this extra '1' is not considered..
 i am nt sure but maybe the reason for adding '1' at the end is to mark
 end of word
 On 19 Mar 2012 19:10, shady sinv...@gmail.com wrote:

 @gene it does show your updated code.

 @atul from the given input it seems different from Fibonacci encoding.

 On Mon, Mar 19, 2012 at 5:32 PM, Gene gene.ress...@gmail.com wrote:

 Thanks.

 I noticed this too.  If the n'th 1/0 digit is supposed to correspond
 with the n'th fibonacci number, then my original code would have been
 right.  But the example isn't done this way.

 I  fixed the code to match the example the evening of the 18th
 (Eastern time), but I guess the change is not showing on your server
 yet.


 On Mar 19, 3:16 am, atul anand atul.87fri...@gmail.com wrote:
  @Gene :  your code will work fine by changing the argument passed from
  main(), you just need to call rite  f(n, 1, 1); from main instead of
  f(n,
  1, 0);
 
  On Mon, Mar 19, 2012 at 10:10 AM, atul anand atul.87fri...@gmail.com
 wrote:
 
 
 
 
 
 
 
   @all : i guess question is on Fibonacci coding.
 
   here you can find the algo :-
 
  http://en.wikipedia.org/wiki/Fibonacci_coding
 
   On Sun, Mar 18, 2012 at 2:58 AM, Atul Singh 
 atulsingh7...@gmail.comwrote:
 
   @Ravi...  there should be only one answer as for fibonacci
 representation
   of a number we have to include the part of the fibonacci number
 just less
   than the number then remaining part of the sum is filled by
 fibonacci
   numbers starting from 1
 
   suppose we have to convert 6 into fibonacci representation
   then 6 has two sum sets as {1,2,3} or {1,5}
 
   then the fibonacci number just less than 6 is 5 so bit
 representing 5 is
   set then for completing the sum to 6 bit 1 is also set.
   so *fibonacci representation of 6 is 1001 .* not 0111
 
   ATul Singh | Final Year  | Computer Science  Engineering | NIT
   Jalandhar  | 9530739855 |
 
--
   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 group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 Hemesh singh

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

[Hemesh Singh]

Isn't it a standard subset sum problem? You can generate the Fibonacci
numbers and put them in an array. Now just apply the standard algorithm to
find that which Fibonacci numbers add up to make the given sum. Please
correct me if I am wrong.

On Mon, Mar 19, 2012 at 8:58 PM, atul anand atul.87fri...@gmail.com wrote:

 @Gene : yeah i skipped ur updated code...its dere

 @shady : it is similar to fib encoding...you just need to reverse the
 output from gene code and append '1' at the end...
 while decoding it ...this extra '1' is not considered..
 i am nt sure but maybe the reason for adding '1' at the end is to mark end
 of word
 On 19 Mar 2012 19:10, shady sinv...@gmail.com wrote:

 @gene it does show your updated code.

 @atul from the given input it seems different from Fibonacci encoding.

 On Mon, Mar 19, 2012 at 5:32 PM, Gene gene.ress...@gmail.com wrote:

 Thanks.

 I noticed this too.  If the n'th 1/0 digit is supposed to correspond
 with the n'th fibonacci number, then my original code would have been
 right.  But the example isn't done this way.

 I  fixed the code to match the example the evening of the 18th
 (Eastern time), but I guess the change is not showing on your server
 yet.


 On Mar 19, 3:16 am, atul anand atul.87fri...@gmail.com wrote:
  @Gene :  your code will work fine by changing the argument passed from
  main(), you just need to call rite  f(n, 1, 1); from main instead of
  f(n,
  1, 0);
 
  On Mon, Mar 19, 2012 at 10:10 AM, atul anand atul.87fri...@gmail.com
 wrote:
 
 
 
 
 
 
 
   @all : i guess question is on Fibonacci coding.
 
   here you can find the algo :-
 
  http://en.wikipedia.org/wiki/Fibonacci_coding
 
   On Sun, Mar 18, 2012 at 2:58 AM, Atul Singh atulsingh7...@gmail.com
 wrote:
 
   @Ravi...  there should be only one answer as for fibonacci
 representation
   of a number we have to include the part of the fibonacci number
 just less
   than the number then remaining part of the sum is filled by
 fibonacci
   numbers starting from 1
 
   suppose we have to convert 6 into fibonacci representation
   then 6 has two sum sets as {1,2,3} or {1,5}
 
   then the fibonacci number just less than 6 is 5 so bit representing
 5 is
   set then for completing the sum to 6 bit 1 is also set.
   so *fibonacci representation of 6 is 1001 .* not 0111
 
   ATul Singh | Final Year  | Computer Science  Engineering | NIT
   Jalandhar  | 9530739855 |
 
--
   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 group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
Hemesh singh

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

[Gene]

Thanks.

I noticed this too.  If the n'th 1/0 digit is supposed to correspond
with the n'th fibonacci number, then my original code would have been
right.  But the example isn't done this way.

I  fixed the code to match the example the evening of the 18th
(Eastern time), but I guess the change is not showing on your server
yet.


On Mar 19, 3:16 am, atul anand atul.87fri...@gmail.com wrote:
 @Gene :  your code will work fine by changing the argument passed from
 main(), you just need to call rite  f(n, 1, 1); from main instead of  f(n,
 1, 0);

 On Mon, Mar 19, 2012 at 10:10 AM, atul anand atul.87fri...@gmail.comwrote:







  @all : i guess question is on Fibonacci coding.

  here you can find the algo :-

 http://en.wikipedia.org/wiki/Fibonacci_coding

  On Sun, Mar 18, 2012 at 2:58 AM, Atul Singh atulsingh7...@gmail.comwrote:

  @Ravi...  there should be only one answer as for fibonacci representation
  of a number we have to include the part of the fibonacci number just less
  than the number then remaining part of the sum is filled by fibonacci
  numbers starting from 1

  suppose we have to convert 6 into fibonacci representation
  then 6 has two sum sets as {1,2,3} or {1,5}

  then the fibonacci number just less than 6 is 5 so bit representing 5 is
  set then for completing the sum to 6 bit 1 is also set.
  so *fibonacci representation of 6 is 1001 .* not 0111

  ATul Singh | Final Year  | Computer Science  Engineering | NIT
  Jalandhar  | 9530739855 |

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

[shady]

@gene it does show your updated code.

@atul from the given input it seems different from Fibonacci encoding.

On Mon, Mar 19, 2012 at 5:32 PM, Gene gene.ress...@gmail.com wrote:

 Thanks.

 I noticed this too.  If the n'th 1/0 digit is supposed to correspond
 with the n'th fibonacci number, then my original code would have been
 right.  But the example isn't done this way.

 I  fixed the code to match the example the evening of the 18th
 (Eastern time), but I guess the change is not showing on your server
 yet.


 On Mar 19, 3:16 am, atul anand atul.87fri...@gmail.com wrote:
  @Gene :  your code will work fine by changing the argument passed from
  main(), you just need to call rite  f(n, 1, 1); from main instead of
  f(n,
  1, 0);
 
  On Mon, Mar 19, 2012 at 10:10 AM, atul anand atul.87fri...@gmail.com
 wrote:
 
 
 
 
 
 
 
   @all : i guess question is on Fibonacci coding.
 
   here you can find the algo :-
 
  http://en.wikipedia.org/wiki/Fibonacci_coding
 
   On Sun, Mar 18, 2012 at 2:58 AM, Atul Singh atulsingh7...@gmail.com
 wrote:
 
   @Ravi...  there should be only one answer as for fibonacci
 representation
   of a number we have to include the part of the fibonacci number just
 less
   than the number then remaining part of the sum is filled by fibonacci
   numbers starting from 1
 
   suppose we have to convert 6 into fibonacci representation
   then 6 has two sum sets as {1,2,3} or {1,5}
 
   then the fibonacci number just less than 6 is 5 so bit representing 5
 is
   set then for completing the sum to 6 bit 1 is also set.
   so *fibonacci representation of 6 is 1001 .* not 0111
 
   ATul Singh | Final Year  | Computer Science  Engineering | NIT
   Jalandhar  | 9530739855 |
 
--
   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.

Re: [algogeeks] Re: Google written test

[atul anand]

@Gene : yeah i skipped ur updated code...its dere

@shady : it is similar to fib encoding...you just need to reverse the
output from gene code and append '1' at the end...
while decoding it ...this extra '1' is not considered..
i am nt sure but maybe the reason for adding '1' at the end is to mark end
of word
On 19 Mar 2012 19:10, shady sinv...@gmail.com wrote:

 @gene it does show your updated code.

 @atul from the given input it seems different from Fibonacci encoding.

 On Mon, Mar 19, 2012 at 5:32 PM, Gene gene.ress...@gmail.com wrote:

 Thanks.

 I noticed this too.  If the n'th 1/0 digit is supposed to correspond
 with the n'th fibonacci number, then my original code would have been
 right.  But the example isn't done this way.

 I  fixed the code to match the example the evening of the 18th
 (Eastern time), but I guess the change is not showing on your server
 yet.


 On Mar 19, 3:16 am, atul anand atul.87fri...@gmail.com wrote:
  @Gene :  your code will work fine by changing the argument passed from
  main(), you just need to call rite  f(n, 1, 1); from main instead of
  f(n,
  1, 0);
 
  On Mon, Mar 19, 2012 at 10:10 AM, atul anand atul.87fri...@gmail.com
 wrote:
 
 
 
 
 
 
 
   @all : i guess question is on Fibonacci coding.
 
   here you can find the algo :-
 
  http://en.wikipedia.org/wiki/Fibonacci_coding
 
   On Sun, Mar 18, 2012 at 2:58 AM, Atul Singh atulsingh7...@gmail.com
 wrote:
 
   @Ravi...  there should be only one answer as for fibonacci
 representation
   of a number we have to include the part of the fibonacci number just
 less
   than the number then remaining part of the sum is filled by fibonacci
   numbers starting from 1
 
   suppose we have to convert 6 into fibonacci representation
   then 6 has two sum sets as {1,2,3} or {1,5}
 
   then the fibonacci number just less than 6 is 5 so bit representing
 5 is
   set then for completing the sum to 6 bit 1 is also set.
   so *fibonacci representation of 6 is 1001 .* not 0111
 
   ATul Singh | Final Year  | Computer Science  Engineering | NIT
   Jalandhar  | 9530739855 |
 
--
   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 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 written test

[Gene]

It looks from the example like you pick the largest (as if the digits
were a binary number).  Here's what I get:

#include stdio.h

unsigned f(unsigned n, unsigned fi, unsigned fim1)
{
  if (fi  n) return n;
  unsigned r = f(n, fi + fim1, fi);
  if (r = fi) {
putchar('1');
return r - fi;
  }
  putchar('0');
  return r;
}

int main(int argc, char *argv[])
{
  unsigned n;
  if (argc  1  sscanf(argv[1], %u, n) == 1) {
f(n, 1, 0);
putchar('\n');
  }
  return 0;
}


On Mar 17, 2:08 pm, Ravi Ranjan ravi.cool2...@gmail.com wrote:
 @ if for a given number more than 1 answer exist then whats the answer???

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

[Gene]

It looks from the example like you pick the largest (as if the digits
were a binary number).  Here's what I get:

#include stdio.h

unsigned f(unsigned n, unsigned fi, unsigned fim1)
{
  if (fi  n) return n;
  unsigned r = f(n, fi + fim1, fi);
  if (r = fi) {
putchar('1');
return r - fi;
  }
  putchar('0');
  return r;
}

int main(int argc, char *argv[])
{
  unsigned n;
  if (argc  1  sscanf(argv[1], %u, n) == 1) {
f(n, 1, 1);
putchar('\n');
  }
  return 0;
}

On Mar 17, 2:08 pm, Ravi Ranjan ravi.cool2...@gmail.com wrote:
 @ if for a given number more than 1 answer exist then whats the answer???

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

[teja bala]

VCE hyderabad

On Mon, Mar 5, 2012 at 3:28 PM, adarsh kumar algog...@gmail.com wrote:

 Which college?

 On Sun, Mar 4, 2012 at 10:16 AM, teja bala pawanjalsa.t...@gmail.comwrote:

 Google is visiting our campus 4 different roles As  of now IT field
 technician is confirmed so how to approach 4 written test. ??

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

Re: [algogeeks] Re: Google

[adarsh kumar]

Which college?

On Sun, Mar 4, 2012 at 10:16 AM, teja bala pawanjalsa.t...@gmail.comwrote:

 Google is visiting our campus 4 different roles As  of now IT field
 technician is confirmed so how to approach 4 written test. ??

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

[teja bala]

Google is visiting our campus 4 different roles As  of now IT field
technician is confirmed so how to approach 4 written test. ??

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

[atul anand]

@Dave : is it a working code??
i have executed your code but getting wrong output...and value of s is
becoming -ve inside loops.

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

[Ashish Goel]

0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) should be 0.5 ( G(h - 1, i - 1) + G(h
- 1, i+1) )

i am not clear why the parents of a cup in upper row are consecutive?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652


On Tue, Feb 28, 2012 at 10:43 AM, Gene gene.ress...@gmail.com wrote:

 G is just a helper function.  You can in line this function and
 eliminate it.

 When you do this, you'll end up with

 F(h, i) = 0.5 * (l + r)
  where l = F(h-1,i-1) - C if 0 = i-1 = h-1 and F(h-1,i-1)  C else
 0
  and r = F(h-1,i) - C if 0 = i = h-1 and F(h-1,i)  C else 0

 Here l is the left parent's outflow and r is the right parent's.

 So you are always computing the h'th row in terms of the (h-1)'th.
 For many DPs this means you'll need 2 row buffers.  In this one you
 only need 1 element back in the current row. You can save this element
 in a single variable and get by with one buffer.  I.e. note l for a
 given value of i is always the previous value of r.  And for i=0, l is
 always 0 because there is no left parent.

 So you end up with

 f[0] = L; // fill in the first row
 for (ih = 1; ih = h; ih++) { // loop thru rest of rows
  double l = 0; // left parent outflow at ii=0 is always 0.
  for (ii = 0; ii = ih; ii++) { // loop thru columns
// new right parent outflow
double r = (ii  ih  f[ii]  C) ? f[ii] - C : 0;
f[ii] = 0.5 * (l + r);
l = r; // right parent is left of next row entry
  }
 }
 return (0 = i  i = h) ? f[i] : 0;

 This is doing the same as Dave's code for all practical purposes. It's
 untested but ought to work.

 On Feb 27, 10:05 pm, Ashish Goel ashg...@gmail.com wrote:
  Gene, your DP is what i was thinking of but in code i could not coreleate
  G(h - 1, i - 1) + G(h - 1, i)  part (:
  Best Regards
  Ashish Goel
  Think positive and find fuel in failure
  +919985813081
  +919966006652
 
 
 
 
 
 
 
  On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote:
   G(h - 1, i - 1) + G(h - 1, i)

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

[Gene]

Well the OP is not clear. You could be right. I solved this problem
once before, and there the glasses were arranged in a pyramid like
they do at weddings in my country  (this will only look right if you
set the fixed-width font in Groups:

 U
U U
   U U U
  U U U U
 U U U U U
---
You pour in the wine at the top and each glass trickles down to the 2
below it.  So in this version I assumed the OP meant the children were
the ones below and to the right.  I could be wrong.

On Feb 28, 8:46 am, Ashish Goel ashg...@gmail.com wrote:
 0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) should be 0.5 ( G(h - 1, i - 1) + G(h
 - 1, i+1) )

 i am not clear why the parents of a cup in upper row are consecutive?
 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652







 On Tue, Feb 28, 2012 at 10:43 AM, Gene gene.ress...@gmail.com wrote:
  G is just a helper function.  You can in line this function and
  eliminate it.

  When you do this, you'll end up with

  F(h, i) = 0.5 * (l + r)
   where l = F(h-1,i-1) - C if 0 = i-1 = h-1 and F(h-1,i-1)  C else
  0
   and r = F(h-1,i) - C if 0 = i = h-1 and F(h-1,i)  C else 0

  Here l is the left parent's outflow and r is the right parent's.

  So you are always computing the h'th row in terms of the (h-1)'th.
  For many DPs this means you'll need 2 row buffers.  In this one you
  only need 1 element back in the current row. You can save this element
  in a single variable and get by with one buffer.  I.e. note l for a
  given value of i is always the previous value of r.  And for i=0, l is
  always 0 because there is no left parent.

  So you end up with

  f[0] = L; // fill in the first row
  for (ih = 1; ih = h; ih++) { // loop thru rest of rows
   double l = 0; // left parent outflow at ii=0 is always 0.
   for (ii = 0; ii = ih; ii++) { // loop thru columns
     // new right parent outflow
     double r = (ii  ih  f[ii]  C) ? f[ii] - C : 0;
     f[ii] = 0.5 * (l + r);
     l = r; // right parent is left of next row entry
   }
  }
  return (0 = i  i = h) ? f[i] : 0;

  This is doing the same as Dave's code for all practical purposes. It's
  untested but ought to work.

  On Feb 27, 10:05 pm, Ashish Goel ashg...@gmail.com wrote:
   Gene, your DP is what i was thinking of but in code i could not coreleate
   G(h - 1, i - 1) + G(h - 1, i)  part (:
   Best Regards
   Ashish Goel
   Think positive and find fuel in failure
   +919985813081
   +919966006652

   On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote:
G(h - 1, i - 1) + G(h - 1, i)

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

[Dave]

The previous proposed solutions all seem far too complicated. It is
not necessary to use a graph data structure. We can simply use an
array to store the quantities of the cups in a row, and update the
array to move to the next row. It would look something like this:

double cupQuan(double L, double C, int h, int i)
// h is the row number of the cup in question, the top cup has h = 1.
// i is the index of the cup in question; the first cup in a row has i
= 0.
{
int j, k;
double r, s;
double* p;
if( (L = 0) || (C = 0) || (h = 0) || (i  0) || (i = h) )
return 0.0;
p = malloc(h * sizeof(double));
p[0] = L;// all liquid into top cup
for( j = 1 ; j  h ; ++j )// advance from row j to j+1
{
r = 0.0;  // nothing coming in from the
left
for( k = 0 ; k  j ; ++k )
{
s = p[k] - C;
if( s = 0.0 )
{// if this cup does not
overflow
p[k] = r; // only overflow from previous
cup
r = 0.0;  // no overflow to next cup in
row
}
else
{  // if this cup does
overflow
p[k] = 0.5 * s + r; // overflow from this cup and
previous
r = 0.5 * s;   // overflow to next cup in row
}
p[j] = r; // overflow into last cup in
row
}
}
s = p[i] = C ? p[i] : C; // result, but not  C
free(p);
return s;
}

Dave

On Feb 25, 5:35 am, Ravi Ranjan ravi.cool2...@gmail.com wrote:
 |_|
 |_| |_|
 |_| |_| |_|
 |_| |_| |_| |_|
 |_| |_| |_| |_| |_|

 Each cup has capacity C and once a cup gets full, it drops half extra
 amount to left child and half extra amount to right child

 for Eg : let' first cups get 2C amount of liquid then extra amount C(2C-C)
 will be divided equally to left and right child cup of next level

 i.e. C/2 to left child and C/2 to right child

 Write a function which takes input parameter as amount of liquid poured at
 top (L) and height of particular cup (h) index of that cup (i) and it
 should return amount of liquid absorbed in that cup.

 source

 http://www.careercup.com/question?id=12770661

 whats exactly the qestion???

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

[Ashish Goel]

Dave, why the assumption that nothing is coming from left side.

Every cup gets something from cup left above and right above itself when
they have something extra?

Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652


On Mon, Feb 27, 2012 at 8:17 PM, Dave dave_and_da...@juno.com wrote:

 // nothing coming in from the
 left


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

[Dave]

@Ashish: I didn't make any assumption that nothing comes from the
left. Does my code give the wrong answer?

Dave

On Feb 27, 10:36 am, Ashish Goel ashg...@gmail.com wrote:
 Dave, why the assumption that nothing is coming from left side.

 Every cup gets something from cup left above and right above itself when
 they have something extra?

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652



 On Mon, Feb 27, 2012 at 8:17 PM, Dave dave_and_da...@juno.com wrote:
  // nothing coming in from the
  left

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

[Gene]

Dave's code is good.  Here is a more abstract way of thinking about
it. Maybe helpful?

Number the rows starting at the top with h=0, and the left i=0. Then
the parents of cup(h,i) are always cup(h-1,i-1) and cup(h-1,i).  When
h0, i0 or i h, the parent does not exist.

Let F(h, i) be the amount that has flowed in to cup(h,i) after L went
in at the top and let G(h, i) be the amount that has flowed out.

So note that what flowed out is either what flowed in minus C or else
nothing if less than C has flowed in. It's also zero if cup(h,i)
doesn't exist:

G(h,i) = { F(h, i) - C if  0 = i = h and F(h, i)  C
  { 0 otherwise

Now note that what flows in is equal to half of what flowed out of
each parent unless we have the top cup, which means L flowed in!

F(h, i) = { L if h = i = 0
  { 0.5 ( G(h - 1, i - 1) + G(h - 1, i) )   otherwise

The answer we want is given by F.  Dave's code is a nice
implementation of this DP.

On Feb 27, 5:23 pm, Dave dave_and_da...@juno.com wrote:
 @Ashish: I didn't make any assumption that nothing comes from the
 left. Does my code give the wrong answer?

 Dave

 On Feb 27, 10:36 am, Ashish Goel ashg...@gmail.com wrote:







  Dave, why the assumption that nothing is coming from left side.

  Every cup gets something from cup left above and right above itself when
  they have something extra?

  Best Regards
  Ashish Goel
  Think positive and find fuel in failure
  +919985813081
  +919966006652

  On Mon, Feb 27, 2012 at 8:17 PM, Dave dave_and_da...@juno.com wrote:
   // nothing coming in from the
   left

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

[Ashish Goel]

Gene, your DP is what i was thinking of but in code i could not coreleate
G(h - 1, i - 1) + G(h - 1, i)  part (:
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652


On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote:

 G(h - 1, i - 1) + G(h - 1, i)

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

[atul anand]

@Dave : my code is not that complicated ...if you ignore the helper
function and check fillCup();
it just similar to preorder travesal and pour half to left and right child.

here is the explanation :-

node* fillCup(node *root,float pour,float capacity)
{
float temp;
if(root==NULL)
return NULL;

if(root-data+pour = capacity)
{
if(root-data==0) //  if cup is empty then fill cup to full and
reduce pour value for the next level
{
root-data=capacity;
pour=pour-capacity;
}
else
{
// if there is alreday some water in the cup , then it will
fill the cup and reduce pour =pour - empty volume in partially filled cup.
temp=capacity-(root-data);
root-data=capacity;
pour=pour-temp;
if(pour==0)
{
return root;
}

}
}
else
{
   // this is for the part where overflow will never happen , even
after adding the poured quantity to the cup.
root-data+=pour;
return root;

}

fillCup(root-left,pour/2,capacity);// pour 1/2 to the left
fillCup(root-right,pour/2,capacity); //  pour 1/2 to the right
}

Time complexity = O(n).

your approach is nice but it O(n^2) .

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

[Dave]

@Atul: I don't have an n in my algorithm, so I'm not sure what your
assessment that my algorithm is O(n^2) means. My algorithm is O(h^2),
where h is the height of the triangle of cups, but the number of cups
is n = h(h+1)/2, which is O(h^2), so my algorithm is O(n), as is
yours.

You'll have to admit that my data structure, an array, is simpler than
your graph.

Dave

On Feb 27, 10:09 pm, atul anand atul.87fri...@gmail.com wrote:
 @Dave : my code is not that complicated ...if you ignore the helper
 function and check fillCup();
 it just similar to preorder travesal and pour half to left and right child.

 here is the explanation :-

 node* fillCup(node *root,float pour,float capacity)
 {
 float temp;
     if(root==NULL)
         return NULL;

     if(root-data+pour = capacity)
     {
         if(root-data==0) //  if cup is empty then fill cup to full and
 reduce pour value for the next level
         {
             root-data=capacity;
             pour=pour-capacity;
         }
         else
         {
             // if there is alreday some water in the cup , then it will
 fill the cup and reduce pour =pour - empty volume in partially filled cup.
             temp=capacity-(root-data);
             root-data=capacity;
             pour=pour-temp;
             if(pour==0)
             {
                 return root;
             }

         }
     }
     else
     {
        // this is for the part where overflow will never happen , even
 after adding the poured quantity to the cup.
         root-data+=pour;
         return root;

     }

     fillCup(root-left,pour/2,capacity);    // pour 1/2 to the left
     fillCup(root-right,pour/2,capacity); //  pour 1/2 to the right

 }

 Time complexity = O(n).

 your approach is nice but it O(n^2) .

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

[Gene]

G is just a helper function.  You can in line this function and
eliminate it.

When you do this, you'll end up with

F(h, i) = 0.5 * (l + r)
  where l = F(h-1,i-1) - C if 0 = i-1 = h-1 and F(h-1,i-1)  C else
0
  and r = F(h-1,i) - C if 0 = i = h-1 and F(h-1,i)  C else 0

Here l is the left parent's outflow and r is the right parent's.

So you are always computing the h'th row in terms of the (h-1)'th.
For many DPs this means you'll need 2 row buffers.  In this one you
only need 1 element back in the current row. You can save this element
in a single variable and get by with one buffer.  I.e. note l for a
given value of i is always the previous value of r.  And for i=0, l is
always 0 because there is no left parent.

So you end up with

f[0] = L; // fill in the first row
for (ih = 1; ih = h; ih++) { // loop thru rest of rows
  double l = 0; // left parent outflow at ii=0 is always 0.
  for (ii = 0; ii = ih; ii++) { // loop thru columns
// new right parent outflow
double r = (ii  ih  f[ii]  C) ? f[ii] - C : 0;
f[ii] = 0.5 * (l + r);
l = r; // right parent is left of next row entry
  }
}
return (0 = i  i = h) ? f[i] : 0;

This is doing the same as Dave's code for all practical purposes. It's
untested but ought to work.

On Feb 27, 10:05 pm, Ashish Goel ashg...@gmail.com wrote:
 Gene, your DP is what i was thinking of but in code i could not coreleate
 G(h - 1, i - 1) + G(h - 1, i)  part (:
 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652







 On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote:
  G(h - 1, i - 1) + G(h - 1, i)

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

[atul anand]

@Dave : yeah sorry its O(n) where n is number of nodes.
yeah as i said before its a nice approach...

On Tue, Feb 28, 2012 at 10:15 AM, Dave dave_and_da...@juno.com wrote:

 @Atul: I don't have an n in my algorithm, so I'm not sure what your
 assessment that my algorithm is O(n^2) means. My algorithm is O(h^2),
 where h is the height of the triangle of cups, but the number of cups
 is n = h(h+1)/2, which is O(h^2), so my algorithm is O(n), as is
 yours.

 You'll have to admit that my data structure, an array, is simpler than
 your graph.

 Dave

 On Feb 27, 10:09 pm, atul anand atul.87fri...@gmail.com wrote:
  @Dave : my code is not that complicated ...if you ignore the helper
  function and check fillCup();
  it just similar to preorder travesal and pour half to left and right
 child.
 
  here is the explanation :-
 
  node* fillCup(node *root,float pour,float capacity)
  {
  float temp;
  if(root==NULL)
  return NULL;
 
  if(root-data+pour = capacity)
  {
  if(root-data==0) //  if cup is empty then fill cup to full and
  reduce pour value for the next level
  {
  root-data=capacity;
  pour=pour-capacity;
  }
  else
  {
  // if there is alreday some water in the cup , then it will
  fill the cup and reduce pour =pour - empty volume in partially filled
 cup.
  temp=capacity-(root-data);
  root-data=capacity;
  pour=pour-temp;
  if(pour==0)
  {
  return root;
  }
 
  }
  }
  else
  {
 // this is for the part where overflow will never happen , even
  after adding the poured quantity to the cup.
  root-data+=pour;
  return root;
 
  }
 
  fillCup(root-left,pour/2,capacity);// pour 1/2 to the left
  fillCup(root-right,pour/2,capacity); //  pour 1/2 to the right
 
  }
 
  Time complexity = O(n).
 
  your approach is nice but it O(n^2) .

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

[atul anand]

@Gene , @dave : +1 +1

On Tue, Feb 28, 2012 at 10:49 AM, atul anand atul.87fri...@gmail.comwrote:

 @Dave : yeah sorry its O(n) where n is number of nodes.
 yeah as i said before its a nice approach...


 On Tue, Feb 28, 2012 at 10:15 AM, Dave dave_and_da...@juno.com wrote:

 @Atul: I don't have an n in my algorithm, so I'm not sure what your
 assessment that my algorithm is O(n^2) means. My algorithm is O(h^2),
 where h is the height of the triangle of cups, but the number of cups
 is n = h(h+1)/2, which is O(h^2), so my algorithm is O(n), as is
 yours.

 You'll have to admit that my data structure, an array, is simpler than
 your graph.

 Dave

 On Feb 27, 10:09 pm, atul anand atul.87fri...@gmail.com wrote:
  @Dave : my code is not that complicated ...if you ignore the helper
  function and check fillCup();
  it just similar to preorder travesal and pour half to left and right
 child.
 
  here is the explanation :-
 
  node* fillCup(node *root,float pour,float capacity)
  {
  float temp;
  if(root==NULL)
  return NULL;
 
  if(root-data+pour = capacity)
  {
  if(root-data==0) //  if cup is empty then fill cup to full and
  reduce pour value for the next level
  {
  root-data=capacity;
  pour=pour-capacity;
  }
  else
  {
  // if there is alreday some water in the cup , then it will
  fill the cup and reduce pour =pour - empty volume in partially filled
 cup.
  temp=capacity-(root-data);
  root-data=capacity;
  pour=pour-temp;
  if(pour==0)
  {
  return root;
  }
 
  }
  }
  else
  {
 // this is for the part where overflow will never happen , even
  after adding the poured quantity to the cup.
  root-data+=pour;
  return root;
 
  }
 
  fillCup(root-left,pour/2,capacity);// pour 1/2 to the left
  fillCup(root-right,pour/2,capacity); //  pour 1/2 to the right
 
  }
 
  Time complexity = O(n).
 
  your approach is nice but it O(n^2) .

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

[Dumanshu]

You are assuming is to be a binary tree, its not. Some nodes will
share a common pour.

On Feb 25, 9:24 pm, atul anand atul.87fri...@gmail.com wrote:
 i guess this would work...
 n=number of nodes
 h=height;
 pour=quantity poured;
 capacity = capacity of each cup

 n=pow(2,h+1) -1;
 call(capacity,pour,0,n)

 node* fillCup(float capacity,float pour,int left,int right)
 {
 node *root;
 int mid;
 if(left  right)
 return NULL;

 root=(node *)malloc(sizeof(node));
 if(left==right)
 {
 if(pour =capacity)
 root-data=capacity;
 else
 root-data=pour;
 root-left=root-right=NULL;}

 else
 {
 mid=left+(right-left)/2;
 if(pour = capacity)
 {
 root-data=capacity;
 pour=pour-capacity;
 pour=pour/2;}

 else
 {
 root-data=pour;
 root-left=root-right=NULL;
 return root;

 }

 root-left=fillCup(capacity,pour,left,mid-1);
 root-right=fillCup(capacity,pour,mid+1,right);

 }

 return root;

 }

 On Sat, Feb 25, 2012 at 5:05 PM, Ravi Ranjan ravi.cool2...@gmail.comwrote:







  |_|
  |_| |_|
  |_| |_| |_|
  |_| |_| |_| |_|
  |_| |_| |_| |_| |_|

  Each cup has capacity C and once a cup gets full, it drops half extra
  amount to left child and half extra amount to right child

  for Eg : let' first cups get 2C amount of liquid then extra amount C(2C-C)
  will be divided equally to left and right child cup of next level

  i.e. C/2 to left child and C/2 to right child

  Write a function which takes input parameter as amount of liquid poured at
  top (L) and height of particular cup (h) index of that cup (i) and it
  should return amount of liquid absorbed in that cup.

  source

 http://www.careercup.com/question?id=12770661

  whats exactly the qestion???

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

[Ravi Ranjan]

@all
same doubt qstn appears to be of binary tree DS
but the diagram given in between qstn is not like Binary tree  so
sharing is there

so how sharing is done plz explain??

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

[atul anand]

@Ravi: checkout this code...i have created tree where there is sharing of
nodes..

here is my code :-
please let me know is case you find any bug.

#includestdio.h

typedef struct tree{
int idx;
float data;
struct tree *left;
struct tree *right;

}node;

node *createNode(int index)
{

node *temp;

temp=(node *)malloc(sizeof(node));
temp-idx=index;
temp-data=0.0;
temp-left=temp-right=NULL;

return temp;

}

void inorder(node *root)
{
if(root!=NULL)
{
inorder(root-left);
printf(%d ) %f \n,root-idx,root-data);
inorder(root-right);


}

}

node* fillCup(node *root,float pour,float capacity)
{
float temp;
if(root==NULL)
return NULL;

if(root-data+pour = capacity)
{
if(root-data==0)
{
root-data=capacity;
pour=pour-capacity;
}
else
{
temp=capacity-(root-data);
root-data=capacity;
pour=pour-temp;
if(pour==0)
{
return root;
}

}
}
else
{
root-data+=pour;
return root;

}

fillCup(root-left,pour/2,capacity);
fillCup(root-right,pour/2,capacity);
}

int main()
{
node *root;
float pour,capacity;
root=createNode(1);//1
root-left=createNode(2);//2
root-right=createNode(3);//3
root-left-left=createNode(4);//4
root-left-left-left=createNode(7);//7
root-right-right=createNode(6);//6
root-right-right-right=createNode(10);//10
root-left-right=createNode(5);//5
root-right-left=root-left-right;
root-left-left-right=createNode(8); // 8
root-left-right-left=root-left-left-right;
root-left-right-right=createNode(9);//9
root-right-right-left=root-left-right-right;
printf(\nEnter capacity = );
scanf(%f,capacity);
printf(\nEnter quantity poured = );
scanf(%f,pour);
fillCup(root,pour,capacity);
printf(\nPrinting tree\n\n);
inorder(root);
printf(\n\n);
return 1;

}

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

[karthikeya s]

buddy i said that kadane's algo(max subsum) wouldn't work..

On Feb 25, 1:31 pm, Ashish Goel ashg...@gmail.com wrote:
 max subsum problem
 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652

 On Sat, Feb 25, 2012 at 1:03 PM, karthikeya s 
 karthikeya.a...@gmail.comwrote:







  You have a circular track containing fuel pits at irregular intervals.
  The total amount of fuel available from all the pits together is just
  sufficient to travel round the track and finish where you started.
  Given the the circuit perimeter, list of each fuel pit location and
  the amount of fuel they contain, find the optimal start point on the
  track such that you never run out of fuel and complete circuit.

  my logic:
  we can use an array having element as
  fuel(in km)-dist to next pit

  so now aim is to traverse the array as always having some +ve
  resultant sum.nd plz we cant use here kadane's algo.there are
  cases in which it will not hold here

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

[Ashish Goel]

it will

the diff is of fuel and dist forms the content of array which moves from 1
to 2n-1 elements(break the circle and instead of elem like 1,2,n have
1,2,n,1,2,...n-1
i.e. total 2n-1 so that mod stuff is not required.

now find maxsubSum such that sum=0 and count of nodes is n

not clear ehy it wont work.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652


On Sat, Feb 25, 2012 at 2:54 PM, karthikeya s karthikeya.a...@gmail.comwrote:

 buddy i said that kadane's algo(max subsum) wouldn't work..

 On Feb 25, 1:31 pm, Ashish Goel ashg...@gmail.com wrote:
  max subsum problem
  Best Regards
  Ashish Goel
  Think positive and find fuel in failure
  +919985813081
  +919966006652
 
  On Sat, Feb 25, 2012 at 1:03 PM, karthikeya s karthikeya.a...@gmail.com
 wrote:
 
 
 
 
 
 
 
   You have a circular track containing fuel pits at irregular intervals.
   The total amount of fuel available from all the pits together is just
   sufficient to travel round the track and finish where you started.
   Given the the circuit perimeter, list of each fuel pit location and
   the amount of fuel they contain, find the optimal start point on the
   track such that you never run out of fuel and complete circuit.
 
   my logic:
   we can use an array having element as
   fuel(in km)-dist to next pit
 
   so now aim is to traverse the array as always having some +ve
   resultant sum.nd plz we cant use here kadane's algo.there are
   cases in which it will not hold here
 
   --
   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.

Re: [algogeeks] Re: google questions

[Arun Vishwanathan]

@all: how is the problem solved using a heap...can someone explain. did not
understand what was on the net...

On Thu, Feb 3, 2011 at 2:23 AM, Avik Mitra tutai...@gmail.com wrote:

 I am proposing a solution for problem 2..
 2.
  Given a text file, implement a solution to find out if a pattern
  similar to wild cards can be detected.
  fort example find if a*b*cd*, or *win or *def* exists in the text.

 Whatever be the pattern sort it must be regular expression. So in
 principle, there always exists a deterministic finite automata with
 exactly one finite state to accept the pattern.
 Thus, the problem can be solved. For example take the case for
 a*b*cd*. The automaton can  can written as:

 1.Set state=1.
 2. Scan the string until end of string is reached.
2.1. If state is 1 and the letter is a then do not change the
 state.
   If the state is 1 and the letter is b then go to state 2.
   if the state is 1 and the letter is c then go to state 3.
   if the state is 1 and the letter is d then go to state 4.

   if the state is 2 and letter is a then go to state 4.
   if the state is 2 and the letter is b then do not change
 the state.
   if the state is 2 and the letter is c the go to state 3.
   if the state is 2 and the letter is d then go to state 4.

   if the state is 3 and the letter is a,b or c then go to
 state 4.
   if the state is 3 and the letter is d then do not change
 state.

   if the state is 4 then do not change state.

   3. If the state is 3 output accept else output reject.

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




-- 
 People often say that motivation doesn't last. Well, neither does bathing
- that's why we recommend it daily.

-- 
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 Question--Suggest Algo

[Nitin Garg]

@Sourabh - whats the running time?

On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg ankurga...@gmail.com wrote:

 Cool Solution...I was thinking of DP but wasnt clear on the recurrence...

 Nice thinking man and thanks :)




 On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote:

 Consider the example that you have given:
 [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3

 Now we need to partition the array into 3 contiguous sub arrays such
 that :
 a) The expected sum value is maximum
 b) and the size of each sub array should be between 2 and 6, both
 inclusive. In case, this constraint is not satisfied then its not a
 valid candidate for the solution even if the partition produces the
 max value.

  2 = ceil (n / 2k) = ceil (12/6)
  6 = floor (3n / 2k) = floor (36/6)
 -
  As mentioned above the following equation :
 F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
 { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
 k-1) }

 /**
 For understanding how partitioning of the array is represented by the
 above equation:

 Say there is an array denoted by A[i] and it needs to be divided into
 3 contiguous parts, one of the ways to do so would be to take the
 following steps :

 Let K(partition no.) be initialized to 3.
 Let array size N be 12.

 a) If N is 0, the goto step 'f'
 b) If K == 1 then call it as partition K and goto step 'e'.
 c) Lets take X no. of elements from the end of array A of size N and
 call it partition K.
 d) Decrement K by 1 and N by X { --K; and N-=X;}
 d) Goto step 'a'
 e) Valid partition and End.
 f) Not a valid partition and End.

 Now if the above set of steps is run for all values of X such that
 2=X=6 , then it will generate all possible candidates (partitions)
 as per the given problem statement. And for all the valid
 partitions(the ones that will hit step 'e') we need to calculate the
 expected sum value.
 **/

 can be translated into,
 // I am using 1-based array indexing for better clarity
 // A[x .. y] means all elements from A[y] to A[x]..

 F(12, 3) = MAX
   {
  ExpVal (A[12 .. 11])  +  F(10, 2) ,
  ExpVal (A[12 .. 10])  +  F(9, 2) ,
  ExpVal (A[12 .. 9])+  F(8, 2) ,   //
 this will yield the maximum sum..
  ExpVal (A[12 .. 8])+  F(7, 2) ,
  ExpVal (A[12 .. 7])+  F(6, 2)
   }

 which is nothing but,
 F(12, 3) = MAX
   {
  1/2  +  F(10, 2) ,
  2/3  +  F(9, 2) ,
  2/4  +  F(8, 2) , // this will yield the
 maximum sum..
  3/5  +  F(7, 2) ,
  4/6  +  F(6, 2)
   }

 Trace the above equation and you should get it..

 On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
  Hey Sourabh
 
  Could you please explain the solution in a bit detail perhaps using an
  example or so..It wud be really helpful ..Just logic not code
 
 
 
 
 
 
 
  On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com
 wrote:
   Looks like a dynamic programming problem
 
   Say F(n,k) denotes the maximum expected sum value for an array of n
   elements and partition k , then
 
   F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
   { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
   k-1) }
 
   Base condition:
   1) F(N, 1) = expected value for array A[n] such that  ceil(n/2k) = N
   =  floor(3n/2k)
   2) If any of the sub problems where the array size is not between
   ceil(n/2k) and  floor(3n/2k) , both inclusive, then its not a valid
   candidate for the final solution. This is can be handled by giving
   initial value to all such combination a value of -1.
 
   To store that the intermediate computations take an array Max[N][K],
   F(N,K) = Max[N][K]
 
   On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
 
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com
 wrote:
 
 Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
 Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
 why this is not the optimal split???
 
 On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
 
   wrote:
  You have an array with *n* elements. The elements are either 0
 or 1.
   You
  want to *split the array into kcontiguous subarrays*. The size
 of
   each
  subarray can vary between ceil(n/2k) and floor(3n/2k). You can
   assume that
  k  n. After you split the array into k subarrays. One element
 of
   each
  subarray will be randomly selected.
 
  Devise an algorithm for maximizing the sum of the randomly
 selected
  elements from the k subarrays. Basically means that we will
 want to
   split
  the array in such way such that the sum 

[algogeeks] Re: Google Question--Suggest Algo

[sourabh]

O(N*K)

On Nov 28, 1:04 pm, Nitin Garg nitin.garg.i...@gmail.com wrote:
 @Sourabh - whats the running time?









 On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg ankurga...@gmail.com wrote:
  Cool Solution...I was thinking of DP but wasnt clear on the recurrence...

  Nice thinking man and thanks :)

  On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote:

  Consider the example that you have given:
  [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3

  Now we need to partition the array into 3 contiguous sub arrays such
  that :
  a) The expected sum value is maximum
  b) and the size of each sub array should be between 2 and 6, both
  inclusive. In case, this constraint is not satisfied then its not a
  valid candidate for the solution even if the partition produces the
  max value.

       2 = ceil (n / 2k) = ceil (12/6)
       6 = floor (3n / 2k) = floor (36/6)
  -
   As mentioned above the following equation :
  F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
  { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
  k-1) }

  /**
  For understanding how partitioning of the array is represented by the
  above equation:

  Say there is an array denoted by A[i] and it needs to be divided into
  3 contiguous parts, one of the ways to do so would be to take the
  following steps :

  Let K(partition no.) be initialized to 3.
  Let array size N be 12.

  a) If N is 0, the goto step 'f'
  b) If K == 1 then call it as partition K and goto step 'e'.
  c) Lets take X no. of elements from the end of array A of size N and
  call it partition K.
  d) Decrement K by 1 and N by X { --K; and N-=X;}
  d) Goto step 'a'
  e) Valid partition and End.
  f) Not a valid partition and End.

  Now if the above set of steps is run for all values of X such that
  2=X=6 , then it will generate all possible candidates (partitions)
  as per the given problem statement. And for all the valid
  partitions(the ones that will hit step 'e') we need to calculate the
  expected sum value.
  **/

  can be translated into,
  // I am using 1-based array indexing for better clarity
  // A[x .. y] means all elements from A[y] to A[x]..

  F(12, 3) = MAX
                        {
                           ExpVal (A[12 .. 11])  +  F(10, 2) ,
                           ExpVal (A[12 .. 10])  +  F(9, 2) ,
                           ExpVal (A[12 .. 9])    +  F(8, 2) ,   //
  this will yield the maximum sum..
                           ExpVal (A[12 .. 8])    +  F(7, 2) ,
                           ExpVal (A[12 .. 7])    +  F(6, 2)
                        }

  which is nothing but,
  F(12, 3) = MAX
                        {
                           1/2  +  F(10, 2) ,
                           2/3  +  F(9, 2) ,
                           2/4  +  F(8, 2) , // this will yield the
  maximum sum..
                           3/5  +  F(7, 2) ,
                           4/6  +  F(6, 2)
                        }

  Trace the above equation and you should get it..

  On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
   Hey Sourabh

   Could you please explain the solution in a bit detail perhaps using an
   example or so..It wud be really helpful ..Just logic not code

   On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com
  wrote:
Looks like a dynamic programming problem

Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then

F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }

Base condition:
1) F(N, 1) = expected value for array A[n] such that  ceil(n/2k) = N
=  floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and  floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.

To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]

On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
 Because in the previous example k = 3.

 On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com
  wrote:

  Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
  Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
  why this is not the optimal split???

  On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com

wrote:
   You have an array with *n* elements. The elements are either 0
  or 1.
You
   want to *split the array into kcontiguous subarrays*. The size
  of
each
   subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
   k  n. After you split the array into k subarrays. One element
  of
each
   subarray will be randomly selected.

   Devise an algorithm for maximizing 

[algogeeks] Re: Google Question--Suggest Algo

[Dumanshu]

Hi

I may not have understood your solution properly. But i think that
your solution is an implementation of brute force where you are
dealing with all cases valid in the range n/2k and 3n/2k without any
optimization with regard to DP. Am i right?

On Nov 28, 2:17 am, sourabh sourabhd2...@gmail.com wrote:
 Consider the example that you have given:
 [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3

 Now we need to partition the array into 3 contiguous sub arrays such
 that :
 a) The expected sum value is maximum
 b) and the size of each sub array should be between 2 and 6, both
 inclusive. In case, this constraint is not satisfied then its not a
 valid candidate for the solution even if the partition produces the
 max value.

       2 = ceil (n / 2k) = ceil (12/6)
       6 = floor (3n / 2k) = floor (36/6)
 -
  As mentioned above the following equation :
 F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
 { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
 k-1) }

 /**
 For understanding how partitioning of the array is represented by the
 above equation:

 Say there is an array denoted by A[i] and it needs to be divided into
 3 contiguous parts, one of the ways to do so would be to take the
 following steps :

 Let K(partition no.) be initialized to 3.
 Let array size N be 12.

 a) If N is 0, the goto step 'f'
 b) If K == 1 then call it as partition K and goto step 'e'.
 c) Lets take X no. of elements from the end of array A of size N and
 call it partition K.
 d) Decrement K by 1 and N by X { --K; and N-=X;}
 d) Goto step 'a'
 e) Valid partition and End.
 f) Not a valid partition and End.

 Now if the above set of steps is run for all values of X such that
 2=X=6 , then it will generate all possible candidates (partitions)
 as per the given problem statement. And for all the valid
 partitions(the ones that will hit step 'e') we need to calculate the
 expected sum value.
 **/

 can be translated into,
 // I am using 1-based array indexing for better clarity
 // A[x .. y] means all elements from A[y] to A[x]..

 F(12, 3) = MAX
                        {
                           ExpVal (A[12 .. 11])  +  F(10, 2) ,
                           ExpVal (A[12 .. 10])  +  F(9, 2) ,
                           ExpVal (A[12 .. 9])    +  F(8, 2) ,   //
 this will yield the maximum sum..
                           ExpVal (A[12 .. 8])    +  F(7, 2) ,
                           ExpVal (A[12 .. 7])    +  F(6, 2)
                        }

 which is nothing but,
 F(12, 3) = MAX
                        {
                           1/2  +  F(10, 2) ,
                           2/3  +  F(9, 2) ,
                           2/4  +  F(8, 2) , // this will yield the
 maximum sum..
                           3/5  +  F(7, 2) ,
                           4/6  +  F(6, 2)
                        }

 Trace the above equation and you should get it..

 On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:







  Hey Sourabh

  Could you please explain the solution in a bit detail perhaps using an
  example or so..It wud be really helpful ..Just logic not code

  On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
   Looks like a dynamic programming problem

   Say F(n,k) denotes the maximum expected sum value for an array of n
   elements and partition k , then

   F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
   { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
   k-1) }

   Base condition:
   1) F(N, 1) = expected value for array A[n] such that  ceil(n/2k) = N
   =  floor(3n/2k)
   2) If any of the sub problems where the array size is not between
   ceil(n/2k) and  floor(3n/2k) , both inclusive, then its not a valid
   candidate for the final solution. This is can be handled by giving
   initial value to all such combination a value of -1.

   To store that the intermediate computations take an array Max[N][K],
   F(N,K) = Max[N][K]

   On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.

On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:

 Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
 Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
 why this is not the optimal split???

 On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
   wrote:
  You have an array with *n* elements. The elements are either 0 or 1.
   You
  want to *split the array into kcontiguous subarrays*. The size of
   each
  subarray can vary between ceil(n/2k) and floor(3n/2k). You can
   assume that
  k  n. After you split the array into k subarrays. One element of
   each
  subarray will be randomly selected.

  Devise an algorithm for maximizing the sum of the randomly selected
  elements from the k subarrays. Basically means that we will want to
   split
  the array in such way such that the 

[algogeeks] Re: Google Question--Suggest Algo

[sourabh]

Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking N/K
(3n/2k - n/2k) sub problems..
Hence, the running time would be,
O( N * K * N / K ) i.e O( N^2)...

On Nov 28, 6:42 pm, Nitin Garg nitin.garg.i...@gmail.com wrote:
 I don't think it is O(N*K)
 It is O(N^2)
 Just to confirm if i have understood correctly

 Lets say n and k are given and are global to all subproblems
 Subproblem Definition
 F[i,j] - maximum expected sum that we can get by partitioning array from 0
 to i into j subarrays. Each subarray satisfies the size bound
 [ceiling(n/2k),floor(3n/2k)]

 F[i,j] = max over all r in our size bound {F[i-r,j-1] + expected sum of
 subarray from i-r+1 to i}

 So to calculate every subsequent subproblem we need to check solutions to
 O(N/k) previous subproblems. And there are N subproblems,  O((1/k)*N^2)









 On Mon, Nov 28, 2011 at 6:46 PM, Dumanshu duman...@gmail.com wrote:
  Hi

  I may not have understood your solution properly. But i think that
  your solution is an implementation of brute force where you are
  dealing with all cases valid in the range n/2k and 3n/2k without any
  optimization with regard to DP. Am i right?

  On Nov 28, 2:17 am, sourabh sourabhd2...@gmail.com wrote:
   Consider the example that you have given:
   [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3

   Now we need to partition the array into 3 contiguous sub arrays such
   that :
   a) The expected sum value is maximum
   b) and the size of each sub array should be between 2 and 6, both
   inclusive. In case, this constraint is not satisfied then its not a
   valid candidate for the solution even if the partition produces the
   max value.

         2 = ceil (n / 2k) = ceil (12/6)
         6 = floor (3n / 2k) = floor (36/6)
   -
    As mentioned above the following equation :
   F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
   { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
   k-1) }

   /**
   For understanding how partitioning of the array is represented by the
   above equation:

   Say there is an array denoted by A[i] and it needs to be divided into
   3 contiguous parts, one of the ways to do so would be to take the
   following steps :

   Let K(partition no.) be initialized to 3.
   Let array size N be 12.

   a) If N is 0, the goto step 'f'
   b) If K == 1 then call it as partition K and goto step 'e'.
   c) Lets take X no. of elements from the end of array A of size N and
   call it partition K.
   d) Decrement K by 1 and N by X { --K; and N-=X;}
   d) Goto step 'a'
   e) Valid partition and End.
   f) Not a valid partition and End.

   Now if the above set of steps is run for all values of X such that
   2=X=6 , then it will generate all possible candidates (partitions)
   as per the given problem statement. And for all the valid
   partitions(the ones that will hit step 'e') we need to calculate the
   expected sum value.
   **/

   can be translated into,
   // I am using 1-based array indexing for better clarity
   // A[x .. y] means all elements from A[y] to A[x]..

   F(12, 3) = MAX
                          {
                             ExpVal (A[12 .. 11])  +  F(10, 2) ,
                             ExpVal (A[12 .. 10])  +  F(9, 2) ,
                             ExpVal (A[12 .. 9])    +  F(8, 2) ,   //
   this will yield the maximum sum..
                             ExpVal (A[12 .. 8])    +  F(7, 2) ,
                             ExpVal (A[12 .. 7])    +  F(6, 2)
                          }

   which is nothing but,
   F(12, 3) = MAX
                          {
                             1/2  +  F(10, 2) ,
                             2/3  +  F(9, 2) ,
                             2/4  +  F(8, 2) , // this will yield the
   maximum sum..
                             3/5  +  F(7, 2) ,
                             4/6  +  F(6, 2)
                          }

   Trace the above equation and you should get it..

   On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:

Hey Sourabh

Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code

On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com
  wrote:
 Looks like a dynamic programming problem

 Say F(n,k) denotes the maximum expected sum value for an array of n
 elements and partition k , then

 F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
 { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
 k-1) }

 Base condition:
 1) F(N, 1) = expected value for array A[n] such that  ceil(n/2k) = N
 =  floor(3n/2k)
 2) If any of the sub problems where the array size is not between
 ceil(n/2k) and  floor(3n/2k) , both inclusive, then its not a valid
 candidate for the final solution. 

[algogeeks] Re: Google Question--Suggest Algo

[sourabh]

Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking at N/
K
(3n/2k - n/2k) sub problems..
Hence, the running time would be,
O( N * K * N / K ) i.e O( N^2)...

On Nov 28, 6:42 pm, Nitin Garg nitin.garg.i...@gmail.com wrote:
 I don't think it is O(N*K)
 It is O(N^2)
 Just to confirm if i have understood correctly

 Lets say n and k are given and are global to all subproblems
 Subproblem Definition
 F[i,j] - maximum expected sum that we can get by partitioning array from 0
 to i into j subarrays. Each subarray satisfies the size bound
 [ceiling(n/2k),floor(3n/2k)]

 F[i,j] = max over all r in our size bound {F[i-r,j-1] + expected sum of
 subarray from i-r+1 to i}

 So to calculate every subsequent subproblem we need to check solutions to
 O(N/k) previous subproblems. And there are N subproblems,  O((1/k)*N^2)









 On Mon, Nov 28, 2011 at 6:46 PM, Dumanshu duman...@gmail.com wrote:
  Hi

  I may not have understood your solution properly. But i think that
  your solution is an implementation of brute force where you are
  dealing with all cases valid in the range n/2k and 3n/2k without any
  optimization with regard to DP. Am i right?

  On Nov 28, 2:17 am, sourabh sourabhd2...@gmail.com wrote:
   Consider the example that you have given:
   [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3

   Now we need to partition the array into 3 contiguous sub arrays such
   that :
   a) The expected sum value is maximum
   b) and the size of each sub array should be between 2 and 6, both
   inclusive. In case, this constraint is not satisfied then its not a
   valid candidate for the solution even if the partition produces the
   max value.

         2 = ceil (n / 2k) = ceil (12/6)
         6 = floor (3n / 2k) = floor (36/6)
   -
    As mentioned above the following equation :
   F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
   { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
   k-1) }

   /**
   For understanding how partitioning of the array is represented by the
   above equation:

   Say there is an array denoted by A[i] and it needs to be divided into
   3 contiguous parts, one of the ways to do so would be to take the
   following steps :

   Let K(partition no.) be initialized to 3.
   Let array size N be 12.

   a) If N is 0, the goto step 'f'
   b) If K == 1 then call it as partition K and goto step 'e'.
   c) Lets take X no. of elements from the end of array A of size N and
   call it partition K.
   d) Decrement K by 1 and N by X { --K; and N-=X;}
   d) Goto step 'a'
   e) Valid partition and End.
   f) Not a valid partition and End.

   Now if the above set of steps is run for all values of X such that
   2=X=6 , then it will generate all possible candidates (partitions)
   as per the given problem statement. And for all the valid
   partitions(the ones that will hit step 'e') we need to calculate the
   expected sum value.
   **/

   can be translated into,
   // I am using 1-based array indexing for better clarity
   // A[x .. y] means all elements from A[y] to A[x]..

   F(12, 3) = MAX
                          {
                             ExpVal (A[12 .. 11])  +  F(10, 2) ,
                             ExpVal (A[12 .. 10])  +  F(9, 2) ,
                             ExpVal (A[12 .. 9])    +  F(8, 2) ,   //
   this will yield the maximum sum..
                             ExpVal (A[12 .. 8])    +  F(7, 2) ,
                             ExpVal (A[12 .. 7])    +  F(6, 2)
                          }

   which is nothing but,
   F(12, 3) = MAX
                          {
                             1/2  +  F(10, 2) ,
                             2/3  +  F(9, 2) ,
                             2/4  +  F(8, 2) , // this will yield the
   maximum sum..
                             3/5  +  F(7, 2) ,
                             4/6  +  F(6, 2)
                          }

   Trace the above equation and you should get it..

   On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:

Hey Sourabh

Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code

On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com
  wrote:
 Looks like a dynamic programming problem

 Say F(n,k) denotes the maximum expected sum value for an array of n
 elements and partition k , then

 F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
 { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
 k-1) }

 Base condition:
 1) F(N, 1) = expected value for array A[n] such that  ceil(n/2k) = N
 =  floor(3n/2k)
 2) If any of the sub problems where the array size is not between
 ceil(n/2k) and  floor(3n/2k) , both inclusive, then its not a valid
 candidate for the final 

[algogeeks] Re: Google Question--Suggest Algo

[sourabh]

Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking at N/
K
(3n/2k - n/2k) sub problems..
Hence, the running time will be,
O( N * K * N / K ) i.e O( N^2)...

On Nov 28, 6:42 pm, Nitin Garg nitin.garg.i...@gmail.com wrote:
 I don't think it is O(N*K)
 It is O(N^2)
 Just to confirm if i have understood correctly

 Lets say n and k are given and are global to all subproblems
 Subproblem Definition
 F[i,j] - maximum expected sum that we can get by partitioning array from 0
 to i into j subarrays. Each subarray satisfies the size bound
 [ceiling(n/2k),floor(3n/2k)]

 F[i,j] = max over all r in our size bound {F[i-r,j-1] + expected sum of
 subarray from i-r+1 to i}

 So to calculate every subsequent subproblem we need to check solutions to
 O(N/k) previous subproblems. And there are N subproblems,  O((1/k)*N^2)









 On Mon, Nov 28, 2011 at 6:46 PM, Dumanshu duman...@gmail.com wrote:
  Hi

  I may not have understood your solution properly. But i think that
  your solution is an implementation of brute force where you are
  dealing with all cases valid in the range n/2k and 3n/2k without any
  optimization with regard to DP. Am i right?

  On Nov 28, 2:17 am, sourabh sourabhd2...@gmail.com wrote:
   Consider the example that you have given:
   [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3

   Now we need to partition the array into 3 contiguous sub arrays such
   that :
   a) The expected sum value is maximum
   b) and the size of each sub array should be between 2 and 6, both
   inclusive. In case, this constraint is not satisfied then its not a
   valid candidate for the solution even if the partition produces the
   max value.

         2 = ceil (n / 2k) = ceil (12/6)
         6 = floor (3n / 2k) = floor (36/6)
   -
    As mentioned above the following equation :
   F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
   { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
   k-1) }

   /**
   For understanding how partitioning of the array is represented by the
   above equation:

   Say there is an array denoted by A[i] and it needs to be divided into
   3 contiguous parts, one of the ways to do so would be to take the
   following steps :

   Let K(partition no.) be initialized to 3.
   Let array size N be 12.

   a) If N is 0, the goto step 'f'
   b) If K == 1 then call it as partition K and goto step 'e'.
   c) Lets take X no. of elements from the end of array A of size N and
   call it partition K.
   d) Decrement K by 1 and N by X { --K; and N-=X;}
   d) Goto step 'a'
   e) Valid partition and End.
   f) Not a valid partition and End.

   Now if the above set of steps is run for all values of X such that
   2=X=6 , then it will generate all possible candidates (partitions)
   as per the given problem statement. And for all the valid
   partitions(the ones that will hit step 'e') we need to calculate the
   expected sum value.
   **/

   can be translated into,
   // I am using 1-based array indexing for better clarity
   // A[x .. y] means all elements from A[y] to A[x]..

   F(12, 3) = MAX
                          {
                             ExpVal (A[12 .. 11])  +  F(10, 2) ,
                             ExpVal (A[12 .. 10])  +  F(9, 2) ,
                             ExpVal (A[12 .. 9])    +  F(8, 2) ,   //
   this will yield the maximum sum..
                             ExpVal (A[12 .. 8])    +  F(7, 2) ,
                             ExpVal (A[12 .. 7])    +  F(6, 2)
                          }

   which is nothing but,
   F(12, 3) = MAX
                          {
                             1/2  +  F(10, 2) ,
                             2/3  +  F(9, 2) ,
                             2/4  +  F(8, 2) , // this will yield the
   maximum sum..
                             3/5  +  F(7, 2) ,
                             4/6  +  F(6, 2)
                          }

   Trace the above equation and you should get it..

   On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:

Hey Sourabh

Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code

On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com
  wrote:
 Looks like a dynamic programming problem

 Say F(n,k) denotes the maximum expected sum value for an array of n
 elements and partition k , then

 F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
 { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
 k-1) }

 Base condition:
 1) F(N, 1) = expected value for array A[n] such that  ceil(n/2k) = N
 =  floor(3n/2k)
 2) If any of the sub problems where the array size is not between
 ceil(n/2k) and  floor(3n/2k) , both inclusive, then its not a valid
 candidate for the final solution. 

[algogeeks] Re: Google Question--Suggest Algo

[sourabh]

Because in the previous example k = 3.

On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:
 Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
 Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
 why this is not the optimal split???







 On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com wrote:
  You have an array with *n* elements. The elements are either 0 or 1. You
  want to *split the array into kcontiguous subarrays*. The size of each
  subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that
  k  n. After you split the array into k subarrays. One element of each
  subarray will be randomly selected.

  Devise an algorithm for maximizing the sum of the randomly selected
  elements from the k subarrays. Basically means that we will want to split
  the array in such way such that the sum of all the expected values for the
  elements selected from each subarray is maximum.

  You can assume that n is a power of 2.

  Example:

  Array: [0,0,1,1,0,0,1,1,0,1,1,0]
  n = 12
  k = 3
  Size of subarrays can be: 2,3,4,5,6

  Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
  Expected Value of the sum of the elements randomly selected from the 
  subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433

  Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
  Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333

  Source -  
  http://stackoverflow.com/questions/8189334/google-combinatorial-optim...

   --
  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 Question--Suggest Algo

[sourabh]

Looks like a dynamic programming problem

Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then

F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }

Base condition:
1) F(N, 1) = expected value for array A[n] such that  ceil(n/2k) = N
=  floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and  floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.

To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]


On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
 Because in the previous example k = 3.

 On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:







  Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
  Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
  why this is not the optimal split???

  On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com wrote:
   You have an array with *n* elements. The elements are either 0 or 1. You
   want to *split the array into kcontiguous subarrays*. The size of each
   subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that
   k  n. After you split the array into k subarrays. One element of each
   subarray will be randomly selected.

   Devise an algorithm for maximizing the sum of the randomly selected
   elements from the k subarrays. Basically means that we will want to split
   the array in such way such that the sum of all the expected values for the
   elements selected from each subarray is maximum.

   You can assume that n is a power of 2.

   Example:

   Array: [0,0,1,1,0,0,1,1,0,1,1,0]
   n = 12
   k = 3
   Size of subarrays can be: 2,3,4,5,6

   Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
   Expected Value of the sum of the elements randomly selected from the 
   subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433

   Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
   Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333

   Source -  
   http://stackoverflow.com/questions/8189334/google-combinatorial-optim...

    --
   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 Question--Suggest Algo

[Ankur Garg]

Hey Sourabh

Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code

On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:

 Looks like a dynamic programming problem

 Say F(n,k) denotes the maximum expected sum value for an array of n
 elements and partition k , then

 F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
 { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
 k-1) }

 Base condition:
 1) F(N, 1) = expected value for array A[n] such that  ceil(n/2k) = N
 =  floor(3n/2k)
 2) If any of the sub problems where the array size is not between
 ceil(n/2k) and  floor(3n/2k) , both inclusive, then its not a valid
 candidate for the final solution. This is can be handled by giving
 initial value to all such combination a value of -1.

 To store that the intermediate computations take an array Max[N][K],
 F(N,K) = Max[N][K]


 On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
  Because in the previous example k = 3.
 
  On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:
 
 
 
 
 
 
 
   Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
   Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
   why this is not the optimal split???
 
   On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
 wrote:
You have an array with *n* elements. The elements are either 0 or 1.
 You
want to *split the array into kcontiguous subarrays*. The size of
 each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
 assume that
k  n. After you split the array into k subarrays. One element of
 each
subarray will be randomly selected.
 
Devise an algorithm for maximizing the sum of the randomly selected
elements from the k subarrays. Basically means that we will want to
 split
the array in such way such that the sum of all the expected values
 for the
elements selected from each subarray is maximum.
 
You can assume that n is a power of 2.
 
Example:
 
Array: [0,0,1,1,0,0,1,1,0,1,1,0]
n = 12
k = 3
Size of subarrays can be: 2,3,4,5,6
 
Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
Expected Value of the sum of the elements randomly selected from the
 subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433
 
Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333
 
Source -
 http://stackoverflow.com/questions/8189334/google-combinatorial-optim...
 
 --
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.

[algogeeks] Re: Google Question--Suggest Algo

[sourabh]

Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3

Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.

  2 = ceil (n / 2k) = ceil (12/6)
  6 = floor (3n / 2k) = floor (36/6)
-
 As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }

/**
For understanding how partitioning of the array is represented by the
above equation:

Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :

Let K(partition no.) be initialized to 3.
Let array size N be 12.

a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.

Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/

can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..

F(12, 3) = MAX
   {
  ExpVal (A[12 .. 11])  +  F(10, 2) ,
  ExpVal (A[12 .. 10])  +  F(9, 2) ,
  ExpVal (A[12 .. 9])+  F(8, 2) ,   //
this will yield the maximum sum..
  ExpVal (A[12 .. 8])+  F(7, 2) ,
  ExpVal (A[12 .. 7])+  F(6, 2)
   }

which is nothing but,
F(12, 3) = MAX
   {
  1/2  +  F(10, 2) ,
  2/3  +  F(9, 2) ,
  2/4  +  F(8, 2) , // this will yield the
maximum sum..
  3/5  +  F(7, 2) ,
  4/6  +  F(6, 2)
   }

Trace the above equation and you should get it..

On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
 Hey Sourabh

 Could you please explain the solution in a bit detail perhaps using an
 example or so..It wud be really helpful ..Just logic not code







 On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
  Looks like a dynamic programming problem

  Say F(n,k) denotes the maximum expected sum value for an array of n
  elements and partition k , then

  F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
  { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
  k-1) }

  Base condition:
  1) F(N, 1) = expected value for array A[n] such that  ceil(n/2k) = N
  =  floor(3n/2k)
  2) If any of the sub problems where the array size is not between
  ceil(n/2k) and  floor(3n/2k) , both inclusive, then its not a valid
  candidate for the final solution. This is can be handled by giving
  initial value to all such combination a value of -1.

  To store that the intermediate computations take an array Max[N][K],
  F(N,K) = Max[N][K]

  On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
   Because in the previous example k = 3.

   On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:

Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???

On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
  wrote:
 You have an array with *n* elements. The elements are either 0 or 1.
  You
 want to *split the array into kcontiguous subarrays*. The size of
  each
 subarray can vary between ceil(n/2k) and floor(3n/2k). You can
  assume that
 k  n. After you split the array into k subarrays. One element of
  each
 subarray will be randomly selected.

 Devise an algorithm for maximizing the sum of the randomly selected
 elements from the k subarrays. Basically means that we will want to
  split
 the array in such way such that the sum of all the expected values
  for the
 elements selected from each subarray is maximum.

 You can assume that n is a power of 2.

 Example:

 Array: [0,0,1,1,0,0,1,1,0,1,1,0]
 n = 12
 k = 3
 Size of subarrays can be: 2,3,4,5,6

 Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
 Expected Value of the sum of the elements randomly selected from the
  subarrays: 1/3 + 2/4 

Re: [algogeeks] Re: Google Question--Suggest Algo

[Ankur Garg]

Cool Solution...I was thinking of DP but wasnt clear on the recurrence...

Nice thinking man and thanks :)



On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote:

 Consider the example that you have given:
 [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3

 Now we need to partition the array into 3 contiguous sub arrays such
 that :
 a) The expected sum value is maximum
 b) and the size of each sub array should be between 2 and 6, both
 inclusive. In case, this constraint is not satisfied then its not a
 valid candidate for the solution even if the partition produces the
 max value.

  2 = ceil (n / 2k) = ceil (12/6)
  6 = floor (3n / 2k) = floor (36/6)
 -
  As mentioned above the following equation :
 F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
 { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
 k-1) }

 /**
 For understanding how partitioning of the array is represented by the
 above equation:

 Say there is an array denoted by A[i] and it needs to be divided into
 3 contiguous parts, one of the ways to do so would be to take the
 following steps :

 Let K(partition no.) be initialized to 3.
 Let array size N be 12.

 a) If N is 0, the goto step 'f'
 b) If K == 1 then call it as partition K and goto step 'e'.
 c) Lets take X no. of elements from the end of array A of size N and
 call it partition K.
 d) Decrement K by 1 and N by X { --K; and N-=X;}
 d) Goto step 'a'
 e) Valid partition and End.
 f) Not a valid partition and End.

 Now if the above set of steps is run for all values of X such that
 2=X=6 , then it will generate all possible candidates (partitions)
 as per the given problem statement. And for all the valid
 partitions(the ones that will hit step 'e') we need to calculate the
 expected sum value.
 **/

 can be translated into,
 // I am using 1-based array indexing for better clarity
 // A[x .. y] means all elements from A[y] to A[x]..

 F(12, 3) = MAX
   {
  ExpVal (A[12 .. 11])  +  F(10, 2) ,
  ExpVal (A[12 .. 10])  +  F(9, 2) ,
  ExpVal (A[12 .. 9])+  F(8, 2) ,   //
 this will yield the maximum sum..
  ExpVal (A[12 .. 8])+  F(7, 2) ,
  ExpVal (A[12 .. 7])+  F(6, 2)
   }

 which is nothing but,
 F(12, 3) = MAX
   {
  1/2  +  F(10, 2) ,
  2/3  +  F(9, 2) ,
  2/4  +  F(8, 2) , // this will yield the
 maximum sum..
  3/5  +  F(7, 2) ,
  4/6  +  F(6, 2)
   }

 Trace the above equation and you should get it..

 On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
  Hey Sourabh
 
  Could you please explain the solution in a bit detail perhaps using an
  example or so..It wud be really helpful ..Just logic not code
 
 
 
 
 
 
 
  On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
   Looks like a dynamic programming problem
 
   Say F(n,k) denotes the maximum expected sum value for an array of n
   elements and partition k , then
 
   F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
   { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
   k-1) }
 
   Base condition:
   1) F(N, 1) = expected value for array A[n] such that  ceil(n/2k) = N
   =  floor(3n/2k)
   2) If any of the sub problems where the array size is not between
   ceil(n/2k) and  floor(3n/2k) , both inclusive, then its not a valid
   candidate for the final solution. This is can be handled by giving
   initial value to all such combination a value of -1.
 
   To store that the intermediate computations take an array Max[N][K],
   F(N,K) = Max[N][K]
 
   On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
 
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com
 wrote:
 
 Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
 Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
 why this is not the optimal split???
 
 On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
   wrote:
  You have an array with *n* elements. The elements are either 0
 or 1.
   You
  want to *split the array into kcontiguous subarrays*. The size of
   each
  subarray can vary between ceil(n/2k) and floor(3n/2k). You can
   assume that
  k  n. After you split the array into k subarrays. One element
 of
   each
  subarray will be randomly selected.
 
  Devise an algorithm for maximizing the sum of the randomly
 selected
  elements from the k subarrays. Basically means that we will want
 to
   split
  the array in such way such that the sum of all the expected
 values
   for the
  elements selected from each subarray is maximum.
 
  You can assume 

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

Re: [algogeeks] Re: google os ques on pipelining

[Aditya Virmani]

585 + (160 + 5)for slowest transactions *999 for the rest of the
instructions!

On Tue, Sep 27, 2011 at 12:49 AM, Gene gene.ress...@gmail.com wrote:

 You guys have the right idea except that since it's multiple choice
 you can do this with no math.  With 1000 data items and only 4 stages,
 the bottleneck has to be the slowest pipeline stage with its register
 delay.  So you can answer b in 10 seconds and move on to the next
 question!

 On Sep 26, 8:50 pm, Dumanshu duman...@gmail.com wrote:
  @bharat:
  for the second part where u multiplied (160+5) with 999, it should be
  160*999 because it is max of (150,120,160,140,5). Correct me if i am
  wrong.
 
  On Sep 26, 4:02 pm, bharatkumar bagana bagana.bharatku...@gmail.com
  wrote:
 
 
 
   for the first instruction : 150+5+120+5+160+5+140=585 ns
   for the rest of the instructions , though pipeline
   max(150,120,160,140)=160
 
   (160+5)*999=164835 ns
we assume that there will be no extra stalls existed in our system
   -585 + 164835 =165420 ns =165.4 us...
   correct me if I'm wrong .
 
   On Sun, Sep 25, 2011 at 9:25 AM, siva viknesh sivavikne...@gmail.com
 wrote:
 
A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns
(nano seconds)
respectively. Registers that are used between the stages have a delay
of 5 ns each. Assuming
constant clocking rate, the total time taken to process 1000 data
items on this pipeline will
approximately be
a. 120 us (micro seconds)
b. 165 us
c. 180 us
d. 175 us
 
...plz give detailed explanation for the ans
 
--
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
   *BharatKumar Bagana*
   **http://www.google.com/profiles/bagana.bharatkumar
 http://www.google.com/profiles/bagana.bharatkumar
   *
   Mobile +91 8056127652*
   bagana.bharatku...@gmail.com- 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 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 os ques on pipelining

[praneethn]

clock period=(slowest stage delay)+(Buffer delay).

slowest stage delay is 160 ns and Buffer delay is 5ns. Buffer delay will
always be there between two stages .

clock period=165ns.

In the pipelining the time it takes =(k+n-1) * (clock period)

k=number of stages and n=number of instructions(data items)

hence time it takes=(4+1000-1)*(165)=165.4 microsec



On Tue, Sep 27, 2011 at 11:51 AM, Aditya Virmani
virmanisadi...@gmail.comwrote:

 585 + (160 + 5)for slowest transactions *999 for the rest of the
 instructions!


 On Tue, Sep 27, 2011 at 12:49 AM, Gene gene.ress...@gmail.com wrote:

 You guys have the right idea except that since it's multiple choice
 you can do this with no math.  With 1000 data items and only 4 stages,
 the bottleneck has to be the slowest pipeline stage with its register
 delay.  So you can answer b in 10 seconds and move on to the next
 question!

 On Sep 26, 8:50 pm, Dumanshu duman...@gmail.com wrote:
  @bharat:
  for the second part where u multiplied (160+5) with 999, it should be
  160*999 because it is max of (150,120,160,140,5). Correct me if i am
  wrong.
 
  On Sep 26, 4:02 pm, bharatkumar bagana bagana.bharatku...@gmail.com
  wrote:
 
 
 
   for the first instruction : 150+5+120+5+160+5+140=585 ns
   for the rest of the instructions , though pipeline
   max(150,120,160,140)=160
 
   (160+5)*999=164835 ns
we assume that there will be no extra stalls existed in our system
   -585 + 164835 =165420 ns =165.4 us...
   correct me if I'm wrong .
 
   On Sun, Sep 25, 2011 at 9:25 AM, siva viknesh sivavikne...@gmail.com
 wrote:
 
A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns
(nano seconds)
respectively. Registers that are used between the stages have a
 delay
of 5 ns each. Assuming
constant clocking rate, the total time taken to process 1000 data
items on this pipeline will
approximately be
a. 120 us (micro seconds)
b. 165 us
c. 180 us
d. 175 us
 
...plz give detailed explanation for the ans
 
--
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
   *BharatKumar Bagana*
   **http://www.google.com/profiles/bagana.bharatkumar
 http://www.google.com/profiles/bagana.bharatkumar
   *
   Mobile +91 8056127652*
   bagana.bharatku...@gmail.com- 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 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.

Re: [algogeeks] Re: google os ques on pipelining

[Varun Nagpal]

Thats right. Clock speed is governed by slowest processing stage + register
delay. With clock cycle of  (160+5) ns even the faster stages will be forced
to run slowly. As a result 1st instruction will take 165*4 ns and rest of
following 999 instructions will take 165*999 ns.

On Tue, Sep 27, 2011 at 4:03 PM, praneethn praneeth...@gmail.com wrote:


 clock period=(slowest stage delay)+(Buffer delay).

 slowest stage delay is 160 ns and Buffer delay is 5ns. Buffer delay will
 always be there between two stages .

 clock period=165ns.

 In the pipelining the time it takes =(k+n-1) * (clock period)

 k=number of stages and n=number of instructions(data items)

 hence time it takes=(4+1000-1)*(165)=165.4 microsec




 On Tue, Sep 27, 2011 at 11:51 AM, Aditya Virmani virmanisadi...@gmail.com
  wrote:

 585 + (160 + 5)for slowest transactions *999 for the rest of the
 instructions!


 On Tue, Sep 27, 2011 at 12:49 AM, Gene gene.ress...@gmail.com wrote:

 You guys have the right idea except that since it's multiple choice
 you can do this with no math.  With 1000 data items and only 4 stages,
 the bottleneck has to be the slowest pipeline stage with its register
 delay.  So you can answer b in 10 seconds and move on to the next
 question!

 On Sep 26, 8:50 pm, Dumanshu duman...@gmail.com wrote:
  @bharat:
  for the second part where u multiplied (160+5) with 999, it should be
  160*999 because it is max of (150,120,160,140,5). Correct me if i am
  wrong.
 
  On Sep 26, 4:02 pm, bharatkumar bagana bagana.bharatku...@gmail.com
  wrote:
 
 
 
   for the first instruction : 150+5+120+5+160+5+140=585 ns
   for the rest of the instructions , though pipeline
   max(150,120,160,140)=160
 
   (160+5)*999=164835 ns
we assume that there will be no extra stalls existed in our system
   -585 + 164835 =165420 ns =165.4 us...
   correct me if I'm wrong .
 
   On Sun, Sep 25, 2011 at 9:25 AM, siva viknesh 
 sivavikne...@gmail.comwrote:
 
A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns
(nano seconds)
respectively. Registers that are used between the stages have a
 delay
of 5 ns each. Assuming
constant clocking rate, the total time taken to process 1000 data
items on this pipeline will
approximately be
a. 120 us (micro seconds)
b. 165 us
c. 180 us
d. 175 us
 
...plz give detailed explanation for the ans
 
--
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
   *BharatKumar Bagana*
   **http://www.google.com/profiles/bagana.bharatkumar
 http://www.google.com/profiles/bagana.bharatkumar
   *
   Mobile +91 8056127652*
   bagana.bharatku...@gmail.com- 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 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 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 os ques on pipelining

[Dumanshu]

@bharat:
for the second part where u multiplied (160+5) with 999, it should be
160*999 because it is max of (150,120,160,140,5). Correct me if i am
wrong.

On Sep 26, 4:02 pm, bharatkumar bagana bagana.bharatku...@gmail.com
wrote:
 for the first instruction : 150+5+120+5+160+5+140=585 ns
 for the rest of the instructions , though pipeline
 max(150,120,160,140)=160

 (160+5)*999=164835 ns
  we assume that there will be no extra stalls existed in our system
 -585 + 164835 =165420 ns =165.4 us...
 correct me if I'm wrong .

 On Sun, Sep 25, 2011 at 9:25 AM, siva viknesh sivavikne...@gmail.comwrote:









  A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns
  (nano seconds)
  respectively. Registers that are used between the stages have a delay
  of 5 ns each. Assuming
  constant clocking rate, the total time taken to process 1000 data
  items on this pipeline will
  approximately be
  a. 120 us (micro seconds)
  b. 165 us
  c. 180 us
  d. 175 us

  ...plz give detailed explanation for the ans

  --
  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
 *BharatKumar Bagana*
 **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
 *
 Mobile +91 8056127652*
 bagana.bharatku...@gmail.com

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: google os ques on pipelining

[Gene]

You guys have the right idea except that since it's multiple choice
you can do this with no math.  With 1000 data items and only 4 stages,
the bottleneck has to be the slowest pipeline stage with its register
delay.  So you can answer b in 10 seconds and move on to the next
question!

On Sep 26, 8:50 pm, Dumanshu duman...@gmail.com wrote:
 @bharat:
 for the second part where u multiplied (160+5) with 999, it should be
 160*999 because it is max of (150,120,160,140,5). Correct me if i am
 wrong.

 On Sep 26, 4:02 pm, bharatkumar bagana bagana.bharatku...@gmail.com
 wrote:



  for the first instruction : 150+5+120+5+160+5+140=585 ns
  for the rest of the instructions , though pipeline
  max(150,120,160,140)=160

  (160+5)*999=164835 ns
   we assume that there will be no extra stalls existed in our system
  -585 + 164835 =165420 ns =165.4 us...
  correct me if I'm wrong .

  On Sun, Sep 25, 2011 at 9:25 AM, siva viknesh sivavikne...@gmail.comwrote:

   A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns
   (nano seconds)
   respectively. Registers that are used between the stages have a delay
   of 5 ns each. Assuming
   constant clocking rate, the total time taken to process 1000 data
   items on this pipeline will
   approximately be
   a. 120 us (micro seconds)
   b. 165 us
   c. 180 us
   d. 175 us

   ...plz give detailed explanation for the ans

   --
   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
  *BharatKumar Bagana*
  **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
  *
  Mobile +91 8056127652*
  bagana.bharatku...@gmail.com- 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 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 maps

[Dave]

@Sukran: Well, I would hire about 1000 smart people and let them do
it. :-)

Dave

On Sep 20, 2:12 am, sukran dhawan sukrandha...@gmail.com wrote:
 How do you implement google maps ?

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

[Deepak Garg]

they are using a highly optimized A* algo for rout finding

On Tue, Sep 20, 2011 at 10:01 PM, Dave dave_and_da...@juno.com wrote:

 @Sukran: Well, I would hire about 1000 smart people and let them do
 it. :-)

 Dave

 On Sep 20, 2:12 am, sukran dhawan sukrandha...@gmail.com wrote:
  How do you implement google maps ?

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




-- 
U.D.I.T

Sent by Nokia OVI (c)

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

[sandeep nagamalli]

Well, I think its not that the algorithm be written with all Google maps
features in place. Rather it is a open ended question, where interviewer is
trying to find
the candidates view of algorithm design.
@Deepak: It should be fine even if some reasonably good algo is given.

my 2 cents:
For the shortest route finding feature:
I would say: Create a graph with nodes as stations and graphs as the
roads/paths between station. Now Dijkstra's algo can be used to find the
shortest path


On Tue, Sep 20, 2011 at 10:03 PM, Deepak Garg deepakgarg...@gmail.comwrote:

 they are using a highly optimized A* algo for rout finding


 On Tue, Sep 20, 2011 at 10:01 PM, Dave dave_and_da...@juno.com wrote:

 @Sukran: Well, I would hire about 1000 smart people and let them do
 it. :-)

 Dave

 On Sep 20, 2:12 am, sukran dhawan sukrandha...@gmail.com wrote:
  How do you implement google maps ?

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




 --
 U.D.I.T

 Sent by Nokia OVI (c)

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

[shady]

hi,
I am not able to add a person to the algogeeks group. Is there a limit on
the number of people who could join a particular google groups ?
At present there are 7960 people :)

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

[sumit kumar pathak]

*no, there is no such limit
*regards
- Sumit Kumar Pathak
(Sumit/ Pathak/ SKP ...)
*Smile is only good contagious thing.*
*Spread it*!



On Fri, Sep 9, 2011 at 1:59 PM, shady sinv...@gmail.com wrote:

 hi,
 I am not able to add a person to the algogeeks group. Is there a limit on
 the number of people who could join a particular google groups ?
 At present there are 7960 people :)

 --
 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 Question:Given a BST and a number, Find the closest node to that number in the BST.

[vikas]

   It seems Dipankar Algo is appropriate at this point of time.
each time successor and predecessor check needs to be done at each
node and the value need to be updated, This is O(log n) approach
because once we check, we move into particular direction.



On Aug 21, 4:59 pm, rahul aravind rahularavin...@gmail.com wrote:
 @Abhishek:nice algo dude..

 On Sat, Aug 20, 2011 at 12:56 PM, Abhishek Yadav algowithabhis...@gmail.com







  wrote:
  Hey i tried it now and got to another solution
  O(log n) solution:
  1. try searching for the number , if found,return the node, otherwise, you
  will ultimately reach a leaf node say 'nd'
  2.  Now the two candidates for the answer would be
             1. TreeSuccessor(nd)      2. TreePredecessor(nd)
  Now compare the original number with these two and minimum would be the
  answer.

  (TreeSuccessor and TreePredecessor are the next and previous node resp. in
  the Inorder traversal of the tree.)

  On Sat, Aug 20, 2011 at 12:46 PM, Dipankar Patro dip10c...@gmail.comwrote:

  why traverse the whole tree?

  at each root keep the difference in a min_diff and min_ele.
  if the entered value is less root then move to left or right.
  repeat above two until whole tree is checked or min_diff becomes 0.

  pseudo code:

  min_diff = INF; // global variables
  min_ele = 0;

  find_min_diff(node *root, int num)
  {

   if (root == null)
   return;

  // update the difference
   if(abs(root-val - num)  min_diff)
   {
    min_diff = abs(root-val - num);
    min_ele = root-val;
   }
   if ( min_diff == 0)
    return; // search is over

  // proceed to next element in tree which might be closer to the num
   if ( num  root- val)
     find_min_ele(root-left, num);
   else
     find_min_ele(root-right, num);
  }

  ^^ Complexity : O(logn)

  On 20 August 2011 12:36, Abhishek Yadav algowithabhis...@gmail.comwrote:

  yes, the interviewer said that there is a solution in O(log n)

  On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan 
  sukrandha...@gmail.comwrote:

  ur traversing the tree once so it shud be o(n).does the question demand
  0(logn) ?

  On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav 
  algowithabhis...@gmail.com wrote:

  what would be the complexity of your solution O(n) or O(log n)..?

   On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan 
  sukrandha...@gmail.com wrote:

  traverse bst inorder and each time u encounter a node find the
  difference between the element and given element in question . if the
  absolute difference is minimum after traversing the tree that is the 
  element
  . u can getback the element using another element which keeps sign of 
  the
  element so that original element can be obtained from diff

  On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav 
  algowithabhis...@gmail.com wrote:

  Given a BST and a number, Find the closest node to that number in the
  BST. Give an algorithm for that.
  Let there be binary search tree having nodes with values
  12,34,64,23,64,25,76,6 and the number given is 28, then the answer
  would be 25 as it is the closest node.

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

  --

  ___
   

  Please do not print 

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

[surender sanke]

Hi, here i maintained two pair of indexes with respect to a and b, reply if
u found any test case which fails..

int npairs()
{
 int a[] = {0,1,4,5,9,11,20};
 int b[] = {0,2,3,6,8,11,15};
 int c[20];
 int len = sizeof(a)/sizeof(a[0]);
 int i1,j1,i2,j2;
 i1=len-1;
 j1=len-2;
 i2=len-2;
 j2=len-1;

 int count = 0;
c[count++] = a[len-1]+b[len-1]; //obvious
 while(count=len)
 {
  if( (a[i1-1]+a[j2-1]  a[i1]+b[j1])   (a[i1-1]+a[j2-1]  a[i1]+b[j1]) )
  {
   c[count++] = a[i1-1]+b[j2-1];  //highest  sum with higher numbers
have exhausted
   i1 = i1-1,j2=j2-1,j1=j2-1,i2=i1-1;
   continue;
  }
  if(a[i1]+b[j1] = a[i2]+b[j2] )
  {
   c[count++] = a[i1]+b[j1];
   j1--;
  }
  else
  {
   c[count++] = a[i2]+b[j2];
   i2--;
  }
 }

 for(int i =0;ilen;i++)
  printf(%d ,c[i]);
 return 0;
}

surender
On Mon, Jul 11, 2011 at 10:46 AM, sunny agrawal sunny816.i...@gmail.comwrote:

 A = 0, 1, 4, 5, 9, 11, 20
 B = 0, 2, 3, 6, 8, 13, 15

 (20, 15)  (20, 15) - (20,15)
 (20,13)   (11,15)  - (20,13)
 (20,8) (11,15)  - (20,8)
 (20,6) (11,15)  - assume (20,6)
 (20,3) (11,15)  - (11,15)
 (20,3) (9,15)- (9,15)
 (20,3) (5,15)- (20,3)  .problem (11,13) has higher value but

 did i missed something ??


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

Re: [algogeeks] Re: GOOGLE Q

[shambo]

Find the largest ceil(sqrt(n)) elements of A and B using a sliding window in
time O(n) and then take their cross in time sqrt(n)^2 ie O(n).

--Shambo

On Mon, Jul 11, 2011 at 12:37 PM, surender sanke surend...@gmail.comwrote:

 Hi, here i maintained two pair of indexes with respect to a and b, reply if
 u found any test case which fails..

 int npairs()
 {
  int a[] = {0,1,4,5,9,11,20};
  int b[] = {0,2,3,6,8,11,15};
  int c[20];
  int len = sizeof(a)/sizeof(a[0]);
  int i1,j1,i2,j2;
  i1=len-1;
  j1=len-2;
  i2=len-2;
  j2=len-1;

  int count = 0;
 c[count++] = a[len-1]+b[len-1]; //obvious
  while(count=len)
  {
   if( (a[i1-1]+a[j2-1]  a[i1]+b[j1])   (a[i1-1]+a[j2-1]  a[i1]+b[j1]) )
   {
c[count++] = a[i1-1]+b[j2-1];  //highest  sum with higher numbers
 have exhausted
i1 = i1-1,j2=j2-1,j1=j2-1,i2=i1-1;
continue;
   }
   if(a[i1]+b[j1] = a[i2]+b[j2] )
   {
c[count++] = a[i1]+b[j1];
j1--;
   }
   else
   {
c[count++] = a[i2]+b[j2];
i2--;
   }
  }

  for(int i =0;ilen;i++)
   printf(%d ,c[i]);
  return 0;
 }

 surender
 On Mon, Jul 11, 2011 at 10:46 AM, sunny agrawal 
 sunny816.i...@gmail.comwrote:

 A = 0, 1, 4, 5, 9, 11, 20
 B = 0, 2, 3, 6, 8, 13, 15

 (20, 15)  (20, 15) - (20,15)
 (20,13)   (11,15)  - (20,13)
 (20,8) (11,15)  - (20,8)
 (20,6) (11,15)  - assume (20,6)
 (20,3) (11,15)  - (11,15)
 (20,3) (9,15)- (9,15)
 (20,3) (5,15)- (20,3)  .problem (11,13) has higher value but

 did i missed something ??


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


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

[DK]

@Shambo: That doesn't work.
Consider:
A = 1 10 100 1000
B = 1 2 3 4

The top 4 pairs are: (1000,4), (1000,3), (1000,2) and (1000,1)

--
DK

http://twitter.com/divyekapoor
http://www.divye.in

-- 
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/-/WyVibLRFx9kJ.
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 Q1

[ritu]

it has O(n2) solution

take nxn matrix and for every a[j](j=1 to n)  store the d (a[j]-a[i])
value for all i  j
the trick is that d of the longest AP will occur maximum number of
times in matrix

count the maximum occuring d value and reconstruct the sequence by
going through matrix



-Ritu

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

[DK]

@Sunny: Thanks for this counterexample. The O(N) algorithm currently seems 
unfeasible to me. 
@Piyush: Are you sure an O(N) algo exists?

Here's an O(N log N) algo (without the N^2 memory requirements of Sunny's 
algo as it doesn't generate duplicates)

For arrays
A = a1 a2 ... an
B = b1 b2  bn

Maintain a max priority_queue ordered by Val(a,b). (Use a BST for this).
Insert (an, bn).

Repeat N Times {
   Pop off and output the max value from the priority queue. Let that be 
(ai, bj) // O(log N)
   if(i == j) {
  Insert (ai-1, bj), (ai, bj-1), (ai-1, bj-1) in the priority queue. // 
O(log n)
   } else if(i  j) {
  Insert (ai-1, bj) in the priority queue. // O(log n)
   } else {
  Insert (ai, bj-1) in the priority queue. // O(log n)
   }
}

Time complexity: O(N log N)
Space complexity: O(N) ??

--
DK

http://twitter.com/divyekapoor
http://www.divye.in

-- 
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/-/XCjyFaTFD-UJ.
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 Q

[Piyush Sinha]

@Dk..i dint frame the question buddy...:P

I found it over here
http://geeksforgeeks.org/forum/topic/google-interview-question-for-software-engineerdeveloper-about-algorithms-75

On Mon, Jul 11, 2011 at 3:14 PM, DK divyekap...@gmail.com wrote:

 @Sunny: Thanks for this counterexample. The O(N) algorithm currently seems
 unfeasible to me.
 @Piyush: Are you sure an O(N) algo exists?

 Here's an O(N log N) algo (without the N^2 memory requirements of Sunny's
 algo as it doesn't generate duplicates)

 For arrays
 A = a1 a2 ... an
 B = b1 b2  bn

 Maintain a max priority_queue ordered by Val(a,b). (Use a BST for this).
 Insert (an, bn).

 Repeat N Times {
Pop off and output the max value from the priority queue. Let that be
 (ai, bj) // O(log N)
if(i == j) {
   Insert (ai-1, bj), (ai, bj-1), (ai-1, bj-1) in the priority queue. //
 O(log n)
} else if(i  j) {
   Insert (ai-1, bj) in the priority queue. // O(log n)
} else {
   Insert (ai, bj-1) in the priority queue. // O(log n)
}
 }

 Time complexity: O(N log N)
 Space complexity: O(N) ??

 --
 DK

 http://twitter.com/divyekapoor
 http://www.divye.in

  --
 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/-/XCjyFaTFD-UJ.

 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.

Re: [algogeeks] Re: GOOGLE Q

[surender sanke]

small mistake change a to b
if( (a[i1-1]+b[j2-1]  a[i1]+b[j1])   (a[i1-1]+a[j2-1]  a[i1]+b[j1]) )

surender
On Mon, Jul 11, 2011 at 3:54 PM, DK divyekap...@gmail.com wrote:

 @surender: Your algo fails. See the counterexample posted by Sunny.

 --
 DK

 http://twitter.com/divyekapoor
 http://www.divye.in

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

 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.