Re: [algogeeks] Reverse dutch flag problem

[ravindra patel]

This is a special case of shuffling problem. In shuffling problem we have
to merge k (here k = 3) parts of array such that each kth element is from
the same sub-array and in same order. For eg -
a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 should become = a1 b1 c1 a2 b2 c2 a3
b3 c3 a4 b4 c4.

Usually shuffling problem can be solved only in O(n*logn) time without
additional space, but here you have an added advantage. You know what the
sequence should look like exactly. So here goes the O(n) solution with
constant space.

1- Take 2 pointers p1 and p2 initialize both of them to index 1 (second
element)
2- now for each element at p2 find the right index where it should go and
put it thr. The right index is -
 (k*p2 -1) % (n-1); // k=3 here

3- Keep doing it until p2 becomes same as p1 again.
4- Now advance p1 till the elements are in order 0 1 2 0 
5- if p1 is less than n-1 than set p2 = p1. Repeat thru step 2-5 again.

Here is a primitive C code to do the same.

int p1 = p2 = 1;
int preVal, next, temp;

while (p1  n)
{
   preVal = a[p1];
   p2 = p1;

  do{
  next = (k*p2 -1) % (n-1); // k=3 here
  temp = a[next];
  a[next] = preVal;
  preVal = temp;
  p2 = next;
  } while (p2 != p1)

  while(p1  n)
  {
   if( ((a[p1] - a[p1-1]) == 1) || (a[p1] - a[p1-1]) == -2)) //
elements are in sequence 0 1 2 0
p1++;
else
break;
  }
}


Feedback welcome :-).
- Ravindra

On Wed, Nov 2, 2011 at 6:43 PM, shady sinv...@gmail.com wrote:

 any solutions for this ?
 dutch national flag problem could be done in O(n) time and O(1) space by
 considering two pointers, but how to do this (reverse dutch national flag
 problem) ?


 On Sat, Aug 20, 2011 at 3:27 PM, Sanjay Rajpal srn...@gmail.com wrote:

 Suppose we are given a string .

 Make it 012012012012 in O(n) time and O(1) space.
 Sanju
 :)

  --
 You received this message because you are subscribed to the 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] Reverse dutch flag problem

[ravindra patel]

Sorry, small mistake in designated index calculation.
It should be k*p2 % (n-1) instead of (k*p2 -1) % (n - 1).

Thanks,
- Ravindra

On Thu, Nov 3, 2011 at 11:37 PM, ravindra patel ravindra.it...@gmail.comwrote:

 This is a special case of shuffling problem. In shuffling problem we have
 to merge k (here k = 3) parts of array such that each kth element is from
 the same sub-array and in same order. For eg -
 a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 should become = a1 b1 c1 a2 b2 c2 a3
 b3 c3 a4 b4 c4.

 Usually shuffling problem can be solved only in O(n*logn) time without
 additional space, but here you have an added advantage. You know what the
 sequence should look like exactly. So here goes the O(n) solution with
 constant space.

 1- Take 2 pointers p1 and p2 initialize both of them to index 1 (second
 element)
 2- now for each element at p2 find the right index where it should go and
 put it thr. The right index is -
  (k*p2 -1) % (n-1); // k=3 here

 3- Keep doing it until p2 becomes same as p1 again.
 4- Now advance p1 till the elements are in order 0 1 2 0 
 5- if p1 is less than n-1 than set p2 = p1. Repeat thru step 2-5 again.

 Here is a primitive C code to do the same.

 int p1 = p2 = 1;
 int preVal, next, temp;

 while (p1  n)
 {
preVal = a[p1];
p2 = p1;

   do{
   next = (k*p2 -1) % (n-1); // k=3 here
   temp = a[next];
   a[next] = preVal;
   preVal = temp;
   p2 = next;
   } while (p2 != p1)

   while(p1  n)
   {
if( ((a[p1] - a[p1-1]) == 1) || (a[p1] - a[p1-1]) == -2)) //
 elements are in sequence 0 1 2 0
 p1++;
 else
 break;
   }
 }


 Feedback welcome :-).
 - Ravindra


 On Wed, Nov 2, 2011 at 6:43 PM, shady sinv...@gmail.com wrote:

 any solutions for this ?
 dutch national flag problem could be done in O(n) time and O(1) space by
 considering two pointers, but how to do this (reverse dutch national flag
 problem) ?


 On Sat, Aug 20, 2011 at 3:27 PM, Sanjay Rajpal srn...@gmail.com wrote:

 Suppose we are given a string .

 Make it 012012012012 in O(n) time and O(1) space.
 Sanju
 :)

  --
 You received this message because you are subscribed to the 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: Searching In a large file

[ravindra patel]

@Dave
yes Dave, you got it right. I assumed that the problem is to find a missing
number out of given 300 million consecutive (but not neccessarily ordered)
9 digit numbers. And so my algo looks strictly in the given range.


Thanks,
- Ravindra

On Sun, Oct 30, 2011 at 2:30 AM, Dave dave_and_da...@juno.com wrote:

 @Ravindra: As given in the problem, the lower bound is 100,000,000 (my
 interpretation of 9 digit number) and the upper bound is
 999,999,999. Suppose that the numbers in the file are the first 300
 million of these, i.e., 100,000,000 to 299,999,999. It is not obvious
 that your algorithm finds a number in the range 300,000,000 to
 999,999,999. Does it?

 Dave

 On Oct 29, 12:30 pm, ravindra patel ravindra.it...@gmail.com wrote:
  Assuming that we know the lower bound and upper bound of the range of
  numbers (If not then we can determine it in one pass).
 
  // Solution 1
  let lb = lower bound, ub = upper bound, sum = 0;
 
  for each number read from file - sum = sum - number + ub--;
 
  at the end of for loop sum += lb; // This is the missing number.
 
  // Problem with above solution is that the variable sum may overflow if
 the
  contiguous numbers read from the file are very small
  // This problem can be solved by changing the second line to this -
 
  for each number read from file -
 sum -= number;
 if(sum  0)  sum += lb++;
 else sum += ub--;
 
  Feedback welcome :-).
  - Ravindra
 
  On Sat, Oct 29, 2011 at 9:17 PM, bharat b bagana.bharatku...@gmail.com
 wrote:
 
 
 
   @Dave
   Your solution works if the total no.of records(ssn numbers) is 1000
   million.
   But the question states that there are only 300 million numbers.
 
   I think some modification is needed to your answer.
   Correct me if i am wrong.
 
   On Fri, Oct 28, 2011 at 2:04 AM, Dave dave_and_da...@juno.com wrote:
 
   @Shiva: Using an integer array a[10], initialized to 0, read
   through the file and for each number n, increment a[n%10]. At the
   end of the file, find any k such that a[k] != 1. Then read through
   the file again. For any number n such that n%10 == k, set a[n/
   10] = -1. At the end of file, find any j  1 such that a[j] =
   0. Then 10 * j + k is a number that is missing from the file.
 
   Dave
 
   On Oct 27, 10:25 am, shiva@Algo shiv.jays...@gmail.com wrote:
Given a file containing roughly 300 million social security
numbers(9-digit numbers), find a 9-digit number that is not in the
 file.
You have unlimited drive space but only 2megabytes of RAM at your
disposal.
 
   --
   You received this message because you are subscribed to the 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.

Re: [algogeeks] Re: Searching In a large file

[ravindra patel]

Assuming that we know the lower bound and upper bound of the range of
numbers (If not then we can determine it in one pass).

// Solution 1
let lb = lower bound, ub = upper bound, sum = 0;

for each number read from file - sum = sum - number + ub--;

at the end of for loop sum += lb; // This is the missing number.

// Problem with above solution is that the variable sum may overflow if the
contiguous numbers read from the file are very small
// This problem can be solved by changing the second line to this -

for each number read from file -
   sum -= number;
   if(sum  0)  sum += lb++;
   else sum += ub--;


Feedback welcome :-).
- Ravindra

On Sat, Oct 29, 2011 at 9:17 PM, bharat b bagana.bharatku...@gmail.comwrote:

 @Dave
 Your solution works if the total no.of records(ssn numbers) is 1000
 million.
 But the question states that there are only 300 million numbers.

 I think some modification is needed to your answer.
 Correct me if i am wrong.



 On Fri, Oct 28, 2011 at 2:04 AM, Dave dave_and_da...@juno.com wrote:

 @Shiva: Using an integer array a[10], initialized to 0, read
 through the file and for each number n, increment a[n%10]. At the
 end of the file, find any k such that a[k] != 1. Then read through
 the file again. For any number n such that n%10 == k, set a[n/
 10] = -1. At the end of file, find any j  1 such that a[j] =
 0. Then 10 * j + k is a number that is missing from the file.

 Dave

 On Oct 27, 10:25 am, shiva@Algo shiv.jays...@gmail.com wrote:
  Given a file containing roughly 300 million social security
  numbers(9-digit numbers), find a 9-digit number that is not in the file.
  You have unlimited drive space but only 2megabytes of RAM at your
  disposal.

 --
 You received this message because you are subscribed to the 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: Minimize bins

[ravindra patel]

I dont think the greedy approach gives the optimal solution here. Take the
below case -

Items are - 5, 4X2, 3, 2X2 and bins are of size 10. Greedy approach will
make choice in order -
bin1 - 5 + 4
bin2 - 4 + 3 + 2
bin3 - 2
Total bins required - 3

While in optimal solution -
bin1 - 5 + 3 +2
bi2 - 4 + 4 + 2
Total bins required - 2

Need to used DP approach similar to 0-1 knapsack.

Feedback welcome :-),
- Ravindra

On Sat, Oct 29, 2011 at 7:52 PM, icy` vipe...@gmail.com wrote:

 yea, i'd go with greedy also.   Fill bin with biggest size s1 as much
 as possible (and same for other bins),  then try to squeeze in next
 biggest size s2, etc.

 On Oct 29, 7:17 am, teja bala pawanjalsa.t...@gmail.com wrote:
  Greedy knapsack algorithm will work fine in this case as in each bin
 
  n1s1+n2s2+..nrsr=C gives the optimal solution...
 
 
 
 
 
 
 
  On Sat, Oct 29, 2011 at 4:34 AM, SAMMM somnath.nit...@gmail.com wrote:
   Suppose u have n1 items of size s1,
   n2 items of size s2 and n3 items of size s3. You'd like to pack
   all of these items into bins each of capacity C, such that the
   total number of bins used is minimized.
 
   --
   You received this message because you are subscribed to the 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] Search an element in an Infinite array

[ravindra patel]

using power of 2 approach doubles the scope of search each time.
How about using approximation. Say I have lower bound lb and upper bound ub.
Now -

initially lb = 0, ub = 1;

while (a[ub]  k)
{
lb = ub;
ub = (ub*k) / a[ub];
}

after end of this loop we'll have a lower bound and upper which should
provide a narrow scope.

Feedback welcome :-),
- Ravindra

On Mon, Oct 24, 2011 at 7:09 PM, Bittu Sarkar bittu...@gmail.com wrote:

 @Ankur Don't think there's any major reason for using powers of 2 except
 the fact that computing the powers of 2 can be done very efficiently than
 computing the powers of any other number. Complexity in any case remains the
 same.


 On 24 October 2011 10:29, rahul sharma rahul23111...@gmail.com wrote:

 +1 ankur


 On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.com wrote:

 Use Binary Search

 start = 2^n-1 high =2^n where n=0,1

 On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal sunny816.i...@gmail.com
  wrote:

 hint 1: try to find 2 indexes i, j such that a[i] = K = a[j]


 On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta ankuj2...@gmail.comwrote:

 Given a sorted array of Infinite size, find an element ‘K’ in the
 array without using extra memory in O (lgn) time

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




 --
 Sunny Aggrawal
 B.Tech. V 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.




 --
 Bittu Sarkar
 5th Year Dual Degree Student
 Department of Computer Science  Engineering
 Indian Institute of Technology Kharagpur


  --
 You received this message because you are subscribed to the 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] Amazon Onsite

[ravindra patel]

@Nitin, excellent algo.

 if S  0  j = i-1 return 0  // I believe this mean there is no
solution, you might want to return -1.


Thanks,
- Ravindra


On Mon, Oct 24, 2011 at 8:39 PM, Nitin Garg nitin.garg.i...@gmail.comwrote:

 Lets say the Amount of petrol is Pi and distance to next petrol pump is Di
 for ith petrol pump.

 start from i=1, j=1 S =0
 while (i=n)
   S += Pj - Dj;
   if S = 0  j = i-1 return i
   if S  0  j = i-1 return 0
   else if S = 0 j++ mod n;
   else  if S  0  j ++ mod n, i = j , S = 0;

 return 0



 it will traverse atmost twice, and hence O(n). no extra space required.


 On Mon, Oct 24, 2011 at 4:06 AM, Aniket aniket...@gmail.com wrote:

 Suppose there is a circle. You have five points on that circle. Each
 point corresponds to a petrol pump. You are given two sets of data.

 1. The amount of petrol that petrol pump will give.
 2. Distance from that petrol pump to the next petrol pump.


 (Assume for 1 lit Petrol the truck will go 1 km)

 Now calculate the first point from where a truck will be able to
 complete the circle.
 (The truck will stop at each petrol pump and it has infinite
 capacity).
 Give o(n) solution. You may use o(n) extra space.

 --
 You received this message because you are subscribed to the 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.




 --
 Nitin Garg

 Personality can open doors, but only Character can keep them open

 --
 You received this message because you are subscribed to the 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] what is the use of fflush ?

[ravindra patel]

Excerpt from The C Programming Language by Kerninghan  Ritchie -

*int fflush(FILE *stream) - *On an output stream, fflush causes any
buffered but unwritten data to be written; *on an input stream, the effect
is undefined*.

So fflush was never meant for stdin.

- Ravindra

On Sun, Oct 9, 2011 at 10:09 PM, Hatta tmd...@gmail.com wrote:

 don't fflush(stdin) it doesn't make any sense.
 fflush(stdout) and fflush(stderr) only.

 On Sun, Oct 9, 2011 at 8:20 AM, Saravanan Selvamani
 saravananselvam...@gmail.com wrote:
  Hi,
   In the following programming when i gave character input rather
  than integer , the following scanf statement is not working . so i
 introduce
  the fflush(stdin) before the last scanf statement.
  But i get the same error as i before .
   #includestdio.h
   int main()
   {
   int a,b;
   scanf(%d,a);
  
  fflush(stdin);
  scanf(%d,b);
  printf(%d,b); //prints some
  garbage value.
  return 0;
   }
  so then what is the use of the fflush(stdin) and how to correct the above
  error? Thanks in advance.
  Regards
  P.S.Saravanan.
  --
  why so serious?
 
  --
  You received this message because you are subscribed to the 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.
 



 --
 Hatta

 --
 You received this message because you are subscribed to the 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] Amazon Question - Find Pythagorean triplet in an unsorted array

[ravindra patel]

@Anshu

 first check that particular number can be written as the sum of two
squares or not
What would be the way to figure it out.

 O(n * (number of side which is largest one for any triplet))
Didn't get it.

Thanks,
- Ravindra

On Wed, Oct 19, 2011 at 11:09 AM, anshu mishra anshumishra6...@gmail.comwrote:

 @Ravindra
 may be the interviewer wants from u that instead of blindly checking for
 every number. first check that particular number can be written as the sum
 of two squares or not if yes than only search for that number. So the order
 will be decrease from O(n^2) to O(n * (number of side which is largest one
 for any triplet)) and in practical it will be much less compare to 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] Amazon Question - Find Pythagorean triplet in an unsorted array

[ravindra patel]

@Wladimir, yeah I have heard about that. Another way of populating primitive
pythagoreans is, for any natural number m  1  (m^2 - 1, 2m, m^2 + 1) forms
a pythagorean triplet. This is useful in populating pythagorean tiplets but
here the problem is to search such triplets from a given int array.

@ rahul, Hash of z^2 - x^2 for each pair of z,x itself will of the size
n*(n-1). I am not sure how it will work in O(n) time then.

Thanks,
- Ravindra

On Fri, Oct 14, 2011 at 12:25 AM, Ankur Garg ankurga...@gmail.com wrote:

 @rahul...How do u choose z and x for computing z^2 -x^2 ?

 On Thu, Oct 13, 2011 at 11:34 PM, rahul rahul...@gmail.com wrote:

 You can create a hash with sqrt(z2-x2). This will make it o(n). The
 interviewer just made it lil tricky. That's all

 --
 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/-/2Ge2pjt4N-4J.
 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: Inplace Array Convertion

[ravindra patel]

Is there a pattern in the indices of the numbers we are swapping. some
formula which may tell the next two indices to swap.


Thanks,
- Ravindra

On Fri, Oct 14, 2011 at 9:40 PM, gaurav yadav gauravyadav1...@gmail.comwrote:

 @shiva...keep swapping the underline elements

 a1*a2*a3a4a5*b1*b2b3b4b5c1c2c3c4c5
 a1b1*a3*a4a5a2b2b3b4b5*c1*c2c3c4c5
 a1b1c1*a4*a5*a2*b2b3b4b5a3c2c3c4c5
 a1b1c1a2*a5*a4*b2*b3b4b5a3c2c3c4c5
 a1b1c1a2b2*a4*a5b3b4b5a3*c2*c3c4c5
 a1b1c1a2b2c2*a5*b3b4b5*a3*a4c3c4c5
 a1b1c1a2b2c2a3b3*b4*b5a5a4*c3*c4c5
 a1b1c1a2b2c2a3b3c3*b5*a5*a4*b4c4c5
 a1b1c1a2b2c2a3b3c3a4*a5*b5*b4*c4c5
 a1b1c1a2b2c2a3b3c3a4b4*b5*a5*c4*c5
 a1b1c1a2b2c2a3b3c3a4b4*c4*a5*b5*c5
 a1b1c1a2b2c2a3b3c3a4b4c4a5b5c5



  --
 You received this message because you are subscribed to the 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] Amazon Question - Find Pythagorean triplet in an unsorted array

[ravindra patel]

Hi,
Another question I faced in Amazon F2F.

Given an unsorted array of integers, find all triplets that satisfy x^2 +
y^2 = z^2.

For example if given array is -  1, 3, 7, 5, 4, 12, 13
The answer should be -
5, 12, 13 and
3, 4, 5

I suggested below algo with complexity O(n^2) -

- Sort the array in descending order. - O(nlogn)
- square each element. - O(n)

Now it reduces to the problem of  finding all triplets(a,b,c) in a
sorted array such that a = b+c.

The interviewer was insisting on a solution better than O(n^2) which I dont
think is feasible, but I couldn't prove that. Anyone has any idea.



Thanks,
- Ravindra

-- 
You received this message because you are subscribed to the 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: Algo for Search in a 2D Matrix

[ravindra patel]

Here is a solution based on the fact that the matrix is quiet similar to a
min heap. each cell is smaller than its down and right neighbor.

Note :- This solution modifies the original matrix.

Algo -
repeat k-1 times
set a[0][0] = INFINITY
minHeapify the Matrix (see implementation below). This will create
holes in the matrix that can be filled with INFINITY.
return a[0][0];

- Complexity O(k*(m+n))  for a m x n matrix.
- Here is a java implementation of the same.

public static int kthSmallest(int[][] a, int k)
{
final int INF = Integer.MAX_VALUE;

int rows = a.length;
int cols = a[0].length;

if (k  rows*cols)
{
System.out.println(Matrix has less than  + k +  elements.);
return INF;
}

while(--k  0)
{
a[0][0] = INF; int i=0, j=0;

// MinHeapify the matrix again.

while(true)
{
int down = INF; int right = INF;

if(i  rows-1)   down = a[i+1][j];
if(j  cols-1)right = a[i][j+1];

if((down == INF) (right == INF))
break;

if(down  right)
{
int temp = a[i][j];
a[i][j] = down;
a[i+1][j] = temp;
i++;
}
else
{
int temp = a[i][j];
a[i][j] = right;
a[i][j+1] = temp;
j++;
}
}
}
return a[0][0];
}


Feedback welcome :-)
- Ravindra


On Wed, Oct 12, 2011 at 8:18 PM, sunny agrawal sunny816.i...@gmail.comwrote:

 i dont think k*k submatrix approach works at all
 what if k =n size of submatrix will be n*n, which is matrix itself
 heap seems to be a good approach with a coloring scheme that helps in
 avoiding duplicates in heap ??


 On Wed, Oct 12, 2011 at 7:18 PM, vikas vikas.rastogi2...@gmail.comwrote:

 @Shiva, not necessarily in upper half

 take the transpose of example put by Dave and see by yourself

 There are few observations for this question:
1. kth smallest will always lie in first k*k matrix
2. it wont be part of sqrt(k)*sqrt(k) matrix
  Thus rest all need to be searched recursively to find the element

 Any suggestions ?


 On Oct 10, 10:55 am, shiva@Algo shiv.jays...@gmail.com wrote:
  id we see the pattern then we can easily find that the kth smallest
 element
  lie on the upper half of the k*k submatrix(on the upperleft corner )
  we can do search on  (k*k)/2 elements to find that
 
  On Mon, Oct 10, 2011 at 10:36 AM, Dave dave_and_da...@juno.com wrote:
   @Shubham: So if the matrix is
   1 2
   3 4
   and you want the 2nd smallest, are you saying that it is 4?
 
   Dave
 
   On Oct 9, 7:40 pm, shubham goyal shubhamgoyal.n...@gmail.com wrote:
im assuming it be a square matrix
then kth smallest element will be in a first k*k sub matrix.
jst look for smallest element in the diagonal of this matrix.
it will give the kth smallest element .
 
On Mon, Oct 10, 2011 at 4:45 AM, Ankur Garg ankurga...@gmail.com
   wrote:
 Given a 2D matrix which is both row wise and column wise sorted.
   Propose an
 algorithm for finding the kth smallest element in it in least time
 complexity
 
 A General Max Heap can be used with k space and n+klogk complexity
 
 Any other solution  or even a way by which we dont scan the whole
   matrix to
 find the solution ?
 
 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.

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




 --
 Sunny Aggrawal
 B.Tech. V 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
 

Re: [algogeeks] DE shaw question- urgent

[ravindra patel]

it usually works like this -

public class Test1
{
  private static Test1 obj; // Static member hence singleton

  private Test1()  // To prevent the Compiler from creating default
constructor
  {
   // Do whatever initialization required
  }

  public static Test1 getInstance()
  {
   if (obj == null)
   {
   obj = new Test1(); // can call private constructor from
within the class
return obj;
   }
   // Will come here only if obj != null
   return obj;
  }
}

 You can call Test1.getInstance to get the singleton object.

HTH,
- Ravindra

On Mon, Sep 5, 2011 at 10:15 PM, Neha Singh neha.ndelhi.1...@gmail.comwrote:

 Guys hv a doubt, plz clarify ..
 You mentioned that if a class has a private constructor then the object of
 that class can be created using call to a static method which internally
 calls the constructor and returns its reference. I can't understand why only
 1 object can be created as mentioned by you. As in, we can call the static
 method multiple times and create multiple objects..

 --
 You received this message because you are subscribed to the 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: Largest BST subtree in Binary Tree

[ravindra patel]

OR

10
  / \
   5 15
  /  \/  \
18 14  17
  /  \
16  19

:-)



Thanks,
- Ravindra


On Thu, Jul 14, 2011 at 12:04 AM, vikas vikas.rastogi2...@gmail.com wrote:

 correction : ans should be :)

 10
\
 15
  /  \
 14  17
   /  \
 16  19


 On Jul 10, 8:20 pm, Decipher ankurseth...@gmail.com wrote:
  Write a code in C/C++ to find the largest BST sub-tree in a binary tree .
  Eg:-
 10
   / \
5 15
   /  \/  \
 18 14  17
   /  \
 16  19
  Then answer should be -
 
  15
  14 17
   16   19

 --
 You received this message because you are subscribed to the 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: Improve upon O(m^2)

[ravindra patel]

@Bittu, Vaibhav
   Can you please illustrate your algo for below arrays.

Array1 - {1, 3, 5, 7}
Array2 - {0,0,0,2,0,4,6,8}


Thanks,
- Ravindra


On Wed, Jul 13, 2011 at 9:47 PM, vaibhav shukla vaibhav200...@gmail.comwrote:

 start from the end of both the arrays... and try simple merge process not
 from the start but from where the last element is... and keep inserting the
 greater element at the end of the larger array.


 On Wed, Jul 13, 2011 at 8:41 PM, bittu shashank7andr...@gmail.com wrote:

 @dumanshu check it

 Algo is simply start putting elemnt in bigger array by comparing then
 from last logic is same as merge part of merg sort :)

  void merge(int[] a, int[] b, int n, int m)
 {
  int k = m + n - 1; // Index of last location of array b
  int i = n - 1; // Index of last element in array b
  int j = m - 1; // Index of last element in array a

 // Start comparing from the last element and merge a and b
  while (i = 0  j = 0)
  {
  if (a[i]  b[j])
{
 a[k--] = a[i--];
   }
   else
  {
   a[k--] = b[j--];
   }
  }

  while (j = 0)
  {
   a[k--] = b[j--];
  }

  //no need to do for a array as its alraedy filled in B array :)

  }
 Time O(N)

 Thanks
 Shashank Mani Narayan
 Computer Science  Engg.
 Birla Institute of Technlogy Mesra

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




 --
   best wishes!!
 Vaibhav Shukla
 DU-MCA


  --
 You received this message because you are subscribed to the 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: Improve upon O(m^2)

[ravindra patel]

@Sandeep,
If we do compaction then it becomes the same algo what Ankit suggested
earlier. Compaction will require 2 pass on the bigger array. Can we do it in
a single pass?

P.S. - I can not say for sure if doing it in one pass is really feasible. I
am still trying to work it out :-).

Thanks,
- Ravindra

On Wed, Jul 13, 2011 at 10:22 PM, Sandeep Jain sandeep6...@gmail.comwrote:

 @Ravindra: Since both the array contain m elements, you can assume that all
 elements lie from index [0] to index [m-1]
 However, because in your example we can consider 0, as a valid value of the
 sorted array.

 PS: Still, if you are suggesting that we should not consider 0 as a value.
 Then you can perform an compaction operation on 2nd array.


 Regards,
 Sandeep Jain



 On Wed, Jul 13, 2011 at 10:18 PM, ravindra patel ravindra.it...@gmail.com
  wrote:

 @Bittu, Vaibhav
Can you please illustrate your algo for below arrays.

 Array1 - {1, 3, 5, 7}
 Array2 - {0,0,0,2,0,4,6,8}


 Thanks,
 - Ravindra



 On Wed, Jul 13, 2011 at 9:47 PM, vaibhav shukla 
 vaibhav200...@gmail.comwrote:

 start from the end of both the arrays... and try simple merge process not
 from the start but from where the last element is... and keep inserting the
 greater element at the end of the larger array.


 On Wed, Jul 13, 2011 at 8:41 PM, bittu shashank7andr...@gmail.comwrote:

 @dumanshu check it

 Algo is simply start putting elemnt in bigger array by comparing then
 from last logic is same as merge part of merg sort :)

  void merge(int[] a, int[] b, int n, int m)
 {
  int k = m + n - 1; // Index of last location of array b
  int i = n - 1; // Index of last element in array b
  int j = m - 1; // Index of last element in array a

 // Start comparing from the last element and merge a and b
  while (i = 0  j = 0)
  {
  if (a[i]  b[j])
{
 a[k--] = a[i--];
   }
   else
  {
   a[k--] = b[j--];
   }
  }

  while (j = 0)
  {
   a[k--] = b[j--];
  }

  //no need to do for a array as its alraedy filled in B array :)

  }
 Time O(N)

 Thanks
 Shashank Mani Narayan
 Computer Science  Engg.
 Birla Institute of Technlogy Mesra

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




 --
   best wishes!!
 Vaibhav Shukla
 DU-MCA


  --
 You received this message because you are subscribed to the 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.

Re: [algogeeks] Re: Improve upon O(m^2)

[ravindra patel]

On Wed, Jul 13, 2011 at 11:00 PM, Sandeep Jain sandeep6...@gmail.comwrote:

 @Ravindra: Dude, so far in this question, I've always seen 2nd array to
 contain all elements on one side of the array, as this avoids any
 constraints on the values allowed within the array.


I am not saying that what I proposed is the original problem. I am just
asking you to assume is as a slightly more complicated variant of the
orginal problem :-).



 Regards,
 Sandeep Jain




 On Wed, Jul 13, 2011 at 10:53 PM, ravindra patel ravindra.it...@gmail.com
  wrote:

 @Sandeep,
 If we do compaction then it becomes the same algo what Ankit suggested
 earlier. Compaction will require 2 pass on the bigger array. Can we do it in
 a single pass?

 P.S. - I can not say for sure if doing it in one pass is really feasible.
 I am still trying to work it out :-).

 Thanks,
 - Ravindra


 On Wed, Jul 13, 2011 at 10:22 PM, Sandeep Jain sandeep6...@gmail.comwrote:

 @Ravindra: Since both the array contain m elements, you can assume that
 all elements lie from index [0] to index [m-1]
 However, because in your example we can consider 0, as a valid value of
 the sorted array.

 PS: Still, if you are suggesting that we should not consider 0 as a
 value. Then you can perform an compaction operation on 2nd array.


 Regards,
 Sandeep Jain



 On Wed, Jul 13, 2011 at 10:18 PM, ravindra patel 
 ravindra.it...@gmail.com wrote:

 @Bittu, Vaibhav
Can you please illustrate your algo for below arrays.

 Array1 - {1, 3, 5, 7}
 Array2 - {0,0,0,2,0,4,6,8}


 Thanks,
 - Ravindra



 On Wed, Jul 13, 2011 at 9:47 PM, vaibhav shukla 
 vaibhav200...@gmail.com wrote:

 start from the end of both the arrays... and try simple merge process
 not from the start but from where the last element is... and keep 
 inserting
 the greater element at the end of the larger array.


 On Wed, Jul 13, 2011 at 8:41 PM, bittu shashank7andr...@gmail.comwrote:

 @dumanshu check it

 Algo is simply start putting elemnt in bigger array by comparing then
 from last logic is same as merge part of merg sort :)

  void merge(int[] a, int[] b, int n, int m)
 {
  int k = m + n - 1; // Index of last location of array b
  int i = n - 1; // Index of last element in array b
  int j = m - 1; // Index of last element in array a

 // Start comparing from the last element and merge a and b
  while (i = 0  j = 0)
  {
  if (a[i]  b[j])
{
 a[k--] = a[i--];
   }
   else
  {
   a[k--] = b[j--];
   }
  }

  while (j = 0)
  {
   a[k--] = b[j--];
  }

  //no need to do for a array as its alraedy filled in B array :)

  }
 Time O(N)

 Thanks
 Shashank Mani Narayan
 Computer Science  Engg.
 Birla Institute of Technlogy Mesra

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




 --
   best wishes!!
 Vaibhav Shukla
 DU-MCA


  --
 You received this message because you are subscribed to the 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.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email

Re: [algogeeks] A Puzzling Puzzle

[ravindra patel]

There are infinite solutions to this problem. Say x flowers are plucked and
y flowers are offered in each temple. then -

2(2(2(2x-y) -y) -y) -y =0
i.e.
16x-15y=0;

any pair the x and y satisfying this equation is a solution.Smallest numbers
are 15, 16 as Abhishek told.


Thanks,
- Ravindra

On Wed, Mar 16, 2011 at 4:37 PM, abhishek agrawal
neo.iiita2...@gmail.comwrote:

 Total Flowers plucked = 15
 Flowers  offered at each temple = 16


 On Wed, Mar 16, 2011 at 3:44 PM, bittu shashank7andr...@gmail.com wrote:

 There is a lake, of square shape. There are four temples on each
 corner. There is a flower tree next to, say temple no 1. The pond has
 this magic power, if a flower is dip into the water it doubles the
 quantity. There is a warning note from the priest, saying No flower
 should be wasted.

 So the puzzle is, how many flowers should be plucked from the tree and
 should be offered in the temple and after offering at each temple, no
 flower should be left. Each temple has to be offered the same number
 of flower. Before offering, flowers has to be dipped in to the pond to
 get it double, as he can pluck the flowers from the tree only once, so
 he has to be carefull in choosing, the total number of flowers



 Thanks
 Shashank

 --
 You received this message because you are subscribed to the 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.




 --
 Abhishek Agrawal

 +919533890833

 --
 You received this message because you are subscribed to the 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: Yahoo coding round question

[ravindra patel]

Here is a simple implementation. Complexity O(n). Please let me know if you
find any issues with this.

Assumptions as stated in original problem -
1- Required sub array is contiguous
2- Given array has only integers (+ve and -)


//  Params are array arr, length of array n, given sum and product
void subarr( int* arr, int n, int sum, int prod)
{
  int lb = 0; // Lower bound of sub array
  int s = 0;  // Temporary sum
  int p = 1;  // Temporary prod

  int mod_p = (prod  0) ? prod : (prod * -1);  // |prod|
  int min_p = mod_p * -1; // -|prod|
  int i=0;
  int found = 0;

  for(i=0; in; i++)
  {
 // Zero can't be sub array element if given product in not zero
if((arr[i] == 0)  (prod != 0))
{
  lb = i+1;
  s = 0;
  p = 1;
  continue;
}
s += arr[i];
p *= arr[i];

// If product is out of range bring it back in
while (p  min_p || p  mod_p)
{
  p /= arr[lb];
  s -= arr[lb];
  lb++;
}

if( s== sum  p == prod)
{
  printf (Sub array is from index %d to %d\n, lb, i);
  found = 1;
  break;
}
  }
  if(!found)
printf(No Matching sub-array found\n);
}


Thanks,
- Ravindra

On Mon, Oct 25, 2010 at 2:04 AM, Kishen Das kishen@gmail.com wrote:

 @Ravindra, Ligerdave
 You guys are all right. But with GPUs, you can literally have thousands of
 threads running in parallel.
 Again, my aim was not to prove that my O(n ^ 2) algorithm is O ( n) on a
 single processor system.
 It was more towards making the members of this group to think on the lines
 of Parallelism.
 I long back agreed that the worst case for my algorithm is O(n^2 ) on
 single processor systems.

 The current problem is a variation of original subset problem which is
 NP-complete. ( http://en.wikipedia.org/wiki/Subset_sum_problem )

 I really appreciate a O(n) solution to this problem on a single-processor
 system.

 Kishen

 On Sun, Oct 24, 2010 at 1:50 PM, ravindra patel 
 ravindra.it...@gmail.comwrote:

  It has nothing to do with time complexity.
 My bad. Wrong choice of words. So in the PRAM model you can say the time
 complexity is O(1), a pure theoretical concept. But the cost still remains
 O(n), isn't it.

 I guess now onwards we'll have to specifically ask interviewers whether
 they are asking for time complexity on scalar machine or on a parallel
 machine. Unless specified otherwise, my assumption by default would be a
 scalar one though.

 - Ravindra


 On Sun, Oct 24, 2010 at 11:50 PM, ravindra patel 
 ravindra.it...@gmail.com wrote:

 @ Kishen
 So lets say you have 100 parallel processors and you are given an array
 of 100 elements, then the loop will execute in 1 clock. Now lets say on the
 same machine you are given a problem array of 1 million elements. So how
 many clocks are you gonna consume, assuming all your 100 processors are
 running in parallel.

 Buddy, with parallel processors you can reduce total computation time at
 most by a factor of number of processors you have (which will always be a
 constant, no matter how big it is). It has nothing to do with time
 complexity.

 Thanks,
 - Ravindra


 On Fri, Oct 22, 2010 at 8:17 AM, Kishen Das kishen@gmail.comwrote:

 Ok, if you look at the inner loop, it is -

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

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

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

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

 Kishen

 On Thu, Oct 21, 2010 at 9:08 AM, ligerdave david.c...@gmail.comwrote:

 @Kishen

 I don't have much knowledge on parallel computation in OpenCL or CUDA.
 Do you mean parallelised=not have to do the computation at all?
 did you mean without knowing the boundary of the inner loop which is
 depended on the outer loop, the inner loop would be smart enough to
 figure out the i and j?

 On Oct 20, 7:33 pm, Kishen Das kishen@gmail.com wrote:
  Well, looks like people are not understanding when I say run a loop
 in
  parallel !!!
 
  Please look at some of the examples on Nvidia website on how
 computations
  can be parallelised in OpenCL or CUDA.
  And also some of the high level programming languages like Scala
 which is
  also providing these parallel constructs.
 
  If you don't understand GPUs or not familiar with parallel constructs
 in
  Java, then my algorithm will definitely look like O ( n ^ 2 ).
 
  Kishen
 
 
 
  On Wed, Oct 20, 2010 at 4:25 PM, ligerdave david.c...@gmail.com
 wrote:
   @Kishen
   as long as you have one

Re: [algogeeks] Re: Algorithm to find whether any 3point on the same line

[ravindra patel]

@Dave
I was wrong. It can't be done in O(n^2) time. The best we can do is sort
each row like you suggested in your other post. That will still be
O((n^2)logn).

Thanks,
- Ravindra

On Sun, Oct 24, 2010 at 7:06 PM, Meng Yan mengyan.fu...@gmail.com wrote:

 for the 3th step,
 for i=1 to n
for j=i+1 to n
   for k=j+1 to n
compare A[i,j] and A[j,k]
 if A[i,j]==A[j,k]
 find i,j,k are collinear.

 so we should need O(n^3), is it right?

 On Sun, Oct 24, 2010 at 1:05 AM, ravindra patel 
 ravindra.it...@gmail.comwrote:

 Can be done in O(n^2) time using the slope as people suggested above.

 1- Sort the points in increasing order of x cord. O(nlogn)
 2- prepare a n*n matrix A where A[i,j] = slope( point(i), point(j) )  -
 O(n^2) [Note that point i and j are sorted in increasing order of x]
 3- find a pair of A[i,j] and A[j,k] with same slope. [Can be done in
 O(n^2)]

 Thanks,
 - Ravindra


 On Sun, Oct 24, 2010 at 10:11 AM, Dave dave_and_da...@juno.com wrote:

 @Preetika: Then you have to look for duplicates in an array of n(n-1)/
 2 real numbers. I think this takes the complexity above O(n^2).

 Dave

 On Oct 23, 10:54 pm, preetika tyagi preetikaty...@gmail.com wrote:
  You have to scan every pair of points only once to get the value of 'm'
 and
  'a', so the time complexity would be O(n^2).
 
 
 
  On Sat, Oct 23, 2010 at 6:22 PM, Meng Yan mengyan.fu...@gmail.com
 wrote:
   there are (n*(n-1))/2pairs of points. I think if we use your method,
 the
   time complexity should be O(n^4).
 
   Is it possible to put all points into k different domain and using
   T(n)=T(n/k)+f(n) to solve this problem?
 
   On Sat, Oct 23, 2010 at 7:51 PM, preetika tyagi 
 preetikaty...@gmail.comwrote:
 
   Is there any specific need to use recursion?
 
   One alternate is to find slope and constant (m and c) for every pair
 of
   points and same value of m  c will specify the points on the same
 line.
   Time complexity is O(n*n).
 
   On Sat, Oct 23, 2010 at 4:31 PM, Meng Yan mengyan.fu...@gmail.com
 wrote:
 
   Given n point on the plane, find out whether any 3point on the same
   line.
 
   How to use recursion to solve the problem? Could you help me find
 the
   algorithm and give the time complexity?
 
   Bests,
   Claire
 
--
   You received this message because you are subscribed to the Google
 Groups
   Algorithm Geeks group.
   To post to this group, send email to algoge...@googlegroups.com.
   To unsubscribe from this group, send email to
   algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 algogeeks%2bunsubscr...@googlegroups­.com
   .
   For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.
 
--
   You received this message because you are subscribed to the Google
 Groups
   Algorithm Geeks group.
   To post to this group, send email to algoge...@googlegroups.com.
   To unsubscribe from this group, send email to
   algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 algogeeks%2bunsubscr...@googlegroups­.com
   .
   For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.
 
--
   You received this message because you are subscribed to the Google
 Groups
   Algorithm Geeks group.
   To post to this group, send email to algoge...@googlegroups.com.
   To unsubscribe from this group, send email to
   algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 algogeeks%2bunsubscr...@googlegroups­.com
   .
   For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
 
  - Show quoted text -

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


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


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


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com

Re: [algogeeks] Re: Yahoo coding round question

[ravindra patel]

@ Kishen
So lets say you have 100 parallel processors and you are given an array of
100 elements, then the loop will execute in 1 clock. Now lets say on the
same machine you are given a problem array of 1 million elements. So how
many clocks are you gonna consume, assuming all your 100 processors are
running in parallel.

Buddy, with parallel processors you can reduce total computation time at
most by a factor of number of processors you have (which will always be a
constant, no matter how big it is). It has nothing to do with time
complexity.

Thanks,
- Ravindra

On Fri, Oct 22, 2010 at 8:17 AM, Kishen Das kishen@gmail.com wrote:

 Ok, if you look at the inner loop, it is -

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

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

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

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

 Kishen

 On Thu, Oct 21, 2010 at 9:08 AM, ligerdave david.c...@gmail.com wrote:

 @Kishen

 I don't have much knowledge on parallel computation in OpenCL or CUDA.
 Do you mean parallelised=not have to do the computation at all?
 did you mean without knowing the boundary of the inner loop which is
 depended on the outer loop, the inner loop would be smart enough to
 figure out the i and j?

 On Oct 20, 7:33 pm, Kishen Das kishen@gmail.com wrote:
  Well, looks like people are not understanding when I say run a loop in
  parallel !!!
 
  Please look at some of the examples on Nvidia website on how
 computations
  can be parallelised in OpenCL or CUDA.
  And also some of the high level programming languages like Scala which
 is
  also providing these parallel constructs.
 
  If you don't understand GPUs or not familiar with parallel constructs in
  Java, then my algorithm will definitely look like O ( n ^ 2 ).
 
  Kishen
 
 
 
  On Wed, Oct 20, 2010 at 4:25 PM, ligerdave david.c...@gmail.com
 wrote:
   @Kishen
   as long as you have one for loop in another, you wont have O(n). it
   will most likely run O(n^2)
 
   On Oct 19, 7:41 pm, Kishen Das kishen@gmail.com wrote:
In the below code the jth and kth inner for loops can be run in
 parallel
making them O(1) and the entire thing O(n).
 
for ( i=0 to i=N-1 )
{
 
for ( j = i to j = 0 ) {
sum[j] +=  A[ i]
product[j] *= A [ i]
 
}
 
for( k=0 to k= i )
if ( sum[k] == S and product[k] == P ) {
Answer is the sub array A[k to i ]
break
 
}
}
 
Kishen
 
On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh 
 iiita2007...@gmail.com
   wrote:
 
 @ Rahul patil  ofcourse array may have negative or positive
 integers
 
 @ Kishen   both O(n) and O(n logn) solutions was asked in this
 yahoo
   coding
 round question
 
 On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh 
 iiita2007...@gmail.com wrote:
 
 Given an array of length N. How will you find the minimum length
 contiguous sub - array of whose sum is S and whose product is P .
 Here
 S and P will be given to you.
 
 --
 You received this message because you are subscribed to the
 Google
   Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 algogeeks%2bunsubscr...@googlegroups .com
   algogeeks%2bunsubscr...@googlegroups .com
 .
 For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
 
 --
 ABHISHEK KUMAR SINGH
 BTECH (INFORMATION TECHNOLOGY)
 IIIT ALLAHABAD
 9956640538
 
 --
 You received this message because you are subscribed to the Google
   Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 algogeeks%2bunsubscr...@googlegroups .com
   algogeeks%2bunsubscr...@googlegroups .com
 .
 For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
 
   --
   You received this message because you are subscribed to the Google
 Groups
   Algorithm Geeks group.
   To post to this group, send email to algoge...@googlegroups.com.
   To unsubscribe from this group, send email to
   algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 

Re: [algogeeks] Re: Yahoo coding round question

[ravindra patel]

 It has nothing to do with time complexity.
My bad. Wrong choice of words. So in the PRAM model you can say the time
complexity is O(1), a pure theoretical concept. But the cost still remains
O(n), isn't it.

I guess now onwards we'll have to specifically ask interviewers whether they
are asking for time complexity on scalar machine or on a parallel machine.
Unless specified otherwise, my assumption by default would be a scalar one
though.

- Ravindra

On Sun, Oct 24, 2010 at 11:50 PM, ravindra patel
ravindra.it...@gmail.comwrote:

 @ Kishen
 So lets say you have 100 parallel processors and you are given an array of
 100 elements, then the loop will execute in 1 clock. Now lets say on the
 same machine you are given a problem array of 1 million elements. So how
 many clocks are you gonna consume, assuming all your 100 processors are
 running in parallel.

 Buddy, with parallel processors you can reduce total computation time at
 most by a factor of number of processors you have (which will always be a
 constant, no matter how big it is). It has nothing to do with time
 complexity.

 Thanks,
 - Ravindra


 On Fri, Oct 22, 2010 at 8:17 AM, Kishen Das kishen@gmail.com wrote:

 Ok, if you look at the inner loop, it is -

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

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

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

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

 Kishen

 On Thu, Oct 21, 2010 at 9:08 AM, ligerdave david.c...@gmail.com wrote:

 @Kishen

 I don't have much knowledge on parallel computation in OpenCL or CUDA.
 Do you mean parallelised=not have to do the computation at all?
 did you mean without knowing the boundary of the inner loop which is
 depended on the outer loop, the inner loop would be smart enough to
 figure out the i and j?

 On Oct 20, 7:33 pm, Kishen Das kishen@gmail.com wrote:
  Well, looks like people are not understanding when I say run a loop in
  parallel !!!
 
  Please look at some of the examples on Nvidia website on how
 computations
  can be parallelised in OpenCL or CUDA.
  And also some of the high level programming languages like Scala which
 is
  also providing these parallel constructs.
 
  If you don't understand GPUs or not familiar with parallel constructs
 in
  Java, then my algorithm will definitely look like O ( n ^ 2 ).
 
  Kishen
 
 
 
  On Wed, Oct 20, 2010 at 4:25 PM, ligerdave david.c...@gmail.com
 wrote:
   @Kishen
   as long as you have one for loop in another, you wont have O(n). it
   will most likely run O(n^2)
 
   On Oct 19, 7:41 pm, Kishen Das kishen@gmail.com wrote:
In the below code the jth and kth inner for loops can be run in
 parallel
making them O(1) and the entire thing O(n).
 
for ( i=0 to i=N-1 )
{
 
for ( j = i to j = 0 ) {
sum[j] +=  A[ i]
product[j] *= A [ i]
 
}
 
for( k=0 to k= i )
if ( sum[k] == S and product[k] == P ) {
Answer is the sub array A[k to i ]
break
 
}
}
 
Kishen
 
On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh 
 iiita2007...@gmail.com
   wrote:
 
 @ Rahul patil  ofcourse array may have negative or positive
 integers
 
 @ Kishen   both O(n) and O(n logn) solutions was asked in this
 yahoo
   coding
 round question
 
 On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh 
 iiita2007...@gmail.com wrote:
 
 Given an array of length N. How will you find the minimum length
 contiguous sub - array of whose sum is S and whose product is P
 . Here
 S and P will be given to you.
 
 --
 You received this message because you are subscribed to the
 Google
   Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com
 .
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 algogeeks%2bunsubscr...@googlegroups .com
   algogeeks%2bunsubscr...@googlegroups .com
 .
 For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
 
 --
 ABHISHEK KUMAR SINGH
 BTECH (INFORMATION TECHNOLOGY)
 IIIT ALLAHABAD
 9956640538
 
 --
 You received this message because you are subscribed to the
 Google
   Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr

Re: [algogeeks] Re: Algorithm to find whether any 3point on the same line

[ravindra patel]

Can be done in O(n^2) time using the slope as people suggested above.

1- Sort the points in increasing order of x cord. O(nlogn)
2- prepare a n*n matrix A where A[i,j] = slope( point(i), point(j) )  -
O(n^2) [Note that point i and j are sorted in increasing order of x]
3- find a pair of A[i,j] and A[j,k] with same slope. [Can be done in O(n^2)]

Thanks,
- Ravindra

On Sun, Oct 24, 2010 at 10:11 AM, Dave dave_and_da...@juno.com wrote:

 @Preetika: Then you have to look for duplicates in an array of n(n-1)/
 2 real numbers. I think this takes the complexity above O(n^2).

 Dave

 On Oct 23, 10:54 pm, preetika tyagi preetikaty...@gmail.com wrote:
  You have to scan every pair of points only once to get the value of 'm'
 and
  'a', so the time complexity would be O(n^2).
 
 
 
  On Sat, Oct 23, 2010 at 6:22 PM, Meng Yan mengyan.fu...@gmail.com
 wrote:
   there are (n*(n-1))/2pairs of points. I think if we use your method,
 the
   time complexity should be O(n^4).
 
   Is it possible to put all points into k different domain and using
   T(n)=T(n/k)+f(n) to solve this problem?
 
   On Sat, Oct 23, 2010 at 7:51 PM, preetika tyagi 
 preetikaty...@gmail.comwrote:
 
   Is there any specific need to use recursion?
 
   One alternate is to find slope and constant (m and c) for every pair
 of
   points and same value of m  c will specify the points on the same
 line.
   Time complexity is O(n*n).
 
   On Sat, Oct 23, 2010 at 4:31 PM, Meng Yan mengyan.fu...@gmail.com
 wrote:
 
   Given n point on the plane, find out whether any 3point on the same
   line.
 
   How to use recursion to solve the problem? Could you help me find the
   algorithm and give the time complexity?
 
   Bests,
   Claire
 
--
   You received this message because you are subscribed to the Google
 Groups
   Algorithm Geeks group.
   To post to this group, send email to algoge...@googlegroups.com.
   To unsubscribe from this group, send email to
   algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 algogeeks%2bunsubscr...@googlegroups­.com
   .
   For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.
 
--
   You received this message because you are subscribed to the Google
 Groups
   Algorithm Geeks group.
   To post to this group, send email to algoge...@googlegroups.com.
   To unsubscribe from this group, send email to
   algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 algogeeks%2bunsubscr...@googlegroups­.com
   .
   For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.
 
--
   You received this message because you are subscribed to the Google
 Groups
   Algorithm Geeks group.
   To post to this group, send email to algoge...@googlegroups.com.
   To unsubscribe from this group, send email to
   algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 algogeeks%2bunsubscr...@googlegroups­.com
   .
   For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
 
  - Show quoted text -

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



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

Re: [algogeeks] Re: missing 2 nums in an array

[ravindra patel]

@Asquare

If you have additional array, why'd you take so much pain. Just put each
number in corresponding bucket (read same index in the new array). The empty
buckets are the missing numbers.

Thanks,
- Ravindra

On Wed, Oct 13, 2010 at 12:03 AM, Asquare anshika.sp...@gmail.com wrote:

 Thanks everyone for putting in ur efforts..

 @lingerdave -
 the array is not sorted..

 @ Dave -

 although the equations will ultimately solve the problem
 but I guess it will get tedious and may also go out of bounds
 in case of the 4th power equation..

 As for the other method of placing the number at its index using a
 temp variable,
 that'll be great.. without requirement of extra space..

 @Nikhil -

 Thanks for that method.. it saves space but as vijay pointed out it
 would alter the array..
 I dnt know to wht extent that would be permitted but not a bad
 thought..
 Its a good application of the same logic we use wen we tk an
 additional array..

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



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

Re: [algogeeks] double tower of hanoi

[ravindra patel]

@Terence
Sorry, had misunderstood your solutions earlier. Your approach and
calculations both are correct and more efficient than my soln.
Initially I was not much convinced with the assumption that in the first
solution, all but last pair are in their original order. Later realized that
its happening because every pair except last one is moved even number of
times causing original order of disks to be recovered. This makes me think
on another very simple solution.
1- Move all disks from source to temp. (using approach in first soln)
2- Move all disks from temp to dest.

This will cause even number of moves even for last pair. takes 2f(n) moves
[one extra move from your approach though  :)].

Thanks,
- Ravindra

On Sat, Oct 9, 2010 at 8:18 AM, Terence technic@gmail.com wrote:

  @ravindra

 Great solution. But I need some clarification on my solution to the second.

 My solution to the second is based on the solution to the first.

 As I stated, in the solution to the first, only the last 2 disks are
 swapped, while the order of all other disks are preserved.
 So moving the same pile of disks twice will preserve the original order of
 all disks.

 In step 1) 3) 5) 7) of my solution to the second,  the process of a) is
 performed for the first (2n-2) disks. (No need to preserve order)
 After step 1)-3) and 5)-7), the order of the first (2n-2) disks is
 preserved. So order of all disks is preserved after 1)-7).

 Denote the number of moves as f(n) in case a), and g(n) in case b).
 We have:
 f(n) = 2^(n+1) - 2 and
 g(n) = 4f(n-1)+3.
 So  g(n) = 4*2^n-5



 On 2010-10-9 1:56, ravindra patel wrote:

 @Terence

 Solution for first one is trivial. Just double the number of moves of
 typical ToH as each pair requires now 2 moves.

 In second one the approach is correct but the calculation is wrong.
 F(n) = 4f(n-1) + 3 = 3(4^n -1)/(4-1) = 4^n-1 = 2^2n -1.

 This can however be optimized as you can reduce the number of recursions.

 1- Move (2n-2, From source, to dest) [f(n-1)]
 2- Move the last 2 disks from source to temp (2 moves and order reversed)
 3- Move (2n-2, From dest, to source) [f(n-1)]
 4- Move the last 2 disks from temp to dest (2 moves and original order
 recovered)
 5- Move(2n-2, From source, to dest) [f(n-1)]

 so f(n) = 3f(n-1) + 4, f(1) = 4
 f(n) = 4(3^n -1)/(3-1) = 2(3^n -1)

 For larger n(2) this is more efficient.

 Thanks,
 - Ravindra

 On Fri, Oct 8, 2010 at 1:42 PM, Terence technic@gmail.com wrote:



 On 2010-10-8 15:14, snehal jain wrote:

 A Double Tower of Hanoi contains 2n disks of n different sizes, two of
 each size. As usual, we’re required to move only one disk at a time,
 without putting a larger one over a smaller one.
 a. How many moves does it take to transfer a double tower from one
 peg to another, if disks of equal size are indistinguishable from each
 other?

  Denote the minimum moves as f(n).
 Like the classical Tower of Hanoi:
 1) move the first (2n-2) disks from Peg 0 to Peg 1 -- f(n-1) moves
 2) move the last 2 disks from Peg 0 to Peg 2  -- 2 moves
 3) move the (2n-2) disks from Peg1 to Peg 2 -- f(n-1) moves
 f(n) = 2f(n-1) + 2,  f(1) = 2
 So f(n) = 2^(n+1) - 2



  b. What if we are required to reproduce the original top-to-bottom
 order of all the equal-size disks in the final arrangement?

  Denote the minimum moves as g(n).
 It can be proved that, in case a, only the last 2 disks are swapped. The
 order of all other disks are preserved.
 So we only need to modify the process to restore the order of the last 2
 disks.
 1) move the first (2n-2) disks from Peg 0 to Peg 2 -- f(n-1) moves
 2) move the second last disk from Peg 0 to Peg 1  -- 1 move
 3) move the (2n-2) disks from Peg 2 to Peg 1 -- f(n-1) moves
 4) move the last disk from Peg 0 to Peg 2 -- 1 move
 5) move the first (2n-2) disks from Peg 1 to Peg 0 -- f(n-1) moves
 6) move the second last disk from Peg 1 to Peg 2  -- 1 move
 7) move the (2n-2) disks from Peg 0 to Peg 2 -- f(n-1) moves
 g(n) = 4f(n-1)+3
= 2^(n+2)-5


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


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

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

Re: [algogeeks] double tower of hanoi

[ravindra patel]

@Terence

Solution for first one is trivial. Just double the number of moves of
typical ToH as each pair requires now 2 moves.

In second one the approach is correct but the calculation is wrong.
F(n) = 4f(n-1) + 3 = 3(4^n -1)/(4-1) = 4^n-1 = 2^2n -1.

This can however be optimized as you can reduce the number of recursions.

1- Move (2n-2, From source, to dest) [f(n-1)]
2- Move the last 2 disks from source to temp (2 moves and order reversed)
3- Move (2n-2, From dest, to source) [f(n-1)]
4- Move the last 2 disks from temp to dest (2 moves and original order
recovered)
5- Move(2n-2, From source, to dest) [f(n-1)]

so f(n) = 3f(n-1) + 4, f(1) = 4
f(n) = 4(3^n -1)/(3-1) = 2(3^n -1)

For larger n(2) this is more efficient.

Thanks,
- Ravindra

On Fri, Oct 8, 2010 at 1:42 PM, Terence technic@gmail.com wrote:



 On 2010-10-8 15:14, snehal jain wrote:

 A Double Tower of Hanoi contains 2n disks of n different sizes, two of
 each size. As usual, we’re required to move only one disk at a time,
 without putting a larger one over a smaller one.
 a. How many moves does it take to transfer a double tower from one
 peg to another, if disks of equal size are indistinguishable from each
 other?

 Denote the minimum moves as f(n).
 Like the classical Tower of Hanoi:
 1) move the first (2n-2) disks from Peg 0 to Peg 1 -- f(n-1) moves
 2) move the last 2 disks from Peg 0 to Peg 2  -- 2 moves
 3) move the (2n-2) disks from Peg1 to Peg 2 -- f(n-1) moves
 f(n) = 2f(n-1) + 2,  f(1) = 2
 So f(n) = 2^(n+1) - 2



  b. What if we are required to reproduce the original top-to-bottom
 order of all the equal-size disks in the final arrangement?

  Denote the minimum moves as g(n).
 It can be proved that, in case a, only the last 2 disks are swapped. The
 order of all other disks are preserved.
 So we only need to modify the process to restore the order of the last 2
 disks.
 1) move the first (2n-2) disks from Peg 0 to Peg 2 -- f(n-1) moves
 2) move the second last disk from Peg 0 to Peg 1  -- 1 move
 3) move the (2n-2) disks from Peg 2 to Peg 1 -- f(n-1) moves
 4) move the last disk from Peg 0 to Peg 2 -- 1 move
 5) move the first (2n-2) disks from Peg 1 to Peg 0 -- f(n-1) moves
 6) move the second last disk from Peg 1 to Peg 2  -- 1 move
 7) move the (2n-2) disks from Peg 0 to Peg 2 -- f(n-1) moves
 g(n) = 4f(n-1)+3
= 2^(n+2)-5


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



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

Re: [algogeeks] Re: apple problem

[ravindra patel]

@Mridul

Thats correct. You can however optimize on space complexity. At any point of
time you need only current max row and previous max row, so you can manage
with only 2 rows (in fact just 1 if you optimize furthure).


On Sun, Oct 3, 2010 at 1:02 PM, Mridul Malpani malpanimri...@gmail.comwrote:

 @anand: the greedy appoach will not work in this test case:
 {2,10,25,
  1,20,10,
  100, 5, 100}

 i think use DP. create an 'max matrix of same order.
 max[i,j]= maximum( max[i-1][j] + a[i][j], max[i][j-1]+a[i][j] );

 max[n-1][n-1] will be the answer.

 Tell me if i m wrong.


 On Oct 2, 10:29 pm, Anand anandut2...@gmail.com wrote:
  Since in our case starting point is fixed ie top left corner so dynamic
  programmng will not make any difference. Dynamic programing makes
 difference
  only when starting point is not fixed. Solution from Greedy and Dynamic
  programming will be same in this case. Correct me if I am wrong
 
  On Sat, Oct 2, 2010 at 8:27 AM, Mridul Malpani malpanimri...@gmail.com
 wrote:
 
   @ anand: the code u have given is an greedy approach.  it will not
   work.
 
   On Oct 1, 12:34 am, Anand anandut2...@gmail.com wrote:
Here is a code for solving the problem using DP.
  http://codepad.org/AoPtCmwA
 
On Thu, Sep 30, 2010 at 3:01 AM, Modeling Expert 
 
cs.modelingexp...@gmail.com wrote:
 recurssion...
 
 At any point X
 
 val_t  getMax( position X){
 
( ! End of Table )
sum =  GetApples[X] +  MAX ( getMax(X_down) , getMax
 ( X_right) ) ;
 
returnn sum ;
 }
 
 --
 You received this message because you are subscribed to the Google
   Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
 
   algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
 algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@googlegroups.com
 
 
 .
 For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
 
   --
   You received this message because you are subscribed to the Google
 Groups
   Algorithm Geeks group.
   To post to this group, send email to algoge...@googlegroups.com.
   To unsubscribe from this group, send email to
   algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
 
   .
   For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.

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



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

Re: [algogeeks] Find the duplicate

[ravindra patel]

Your test case is wrong. With this pattern you can have at max n/3
occurrences of 1. The questions says that repeated element has n/2
occurrences

On Thu, Aug 5, 2010 at 8:37 PM, Manjunath Manohar
manjunath.n...@gmail.comwrote:

 consider the test case of...

 1 2 3 1...

 1 repeated n/2 times and 2,3 are distinct n/2 elements

 for this the algo will not work

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


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

Re: [algogeeks] Find the duplicate

[ravindra patel]

Nice solution. Reduces number of comparisons to half of Ashish's algo. The
complexity remains O[n] though. Can it be made more efficient, like O[log n]

On Thu, Aug 5, 2010 at 10:59 PM, Pramod Negi negi.1...@gmail.com wrote:

 compare pair wise i.e a[0] and a[1]a[2] and a[3]..

 leave out last 4 elements...

 repeated element can be found in 3 comparison for these 3 elements...


 total no of comparison in worst case
 (n/2+1)

 Negi


 On Thu, Aug 5, 2010 at 10:55 PM, Shiv ... shivsinha2...@gmail.com wrote:

 In constant space??? How? will you please elaborate?



 On Thu, Aug 5, 2010 at 9:29 PM, dinesh bansal bansal...@gmail.comwrote:

 If I understand the question correctly... there is an array of size n
 which has n/2 distinct elements and one element is repeated n/2 times.

 For e.g.:
n = 4:   1 2 3 3
n = 61 2 3 4 4 4
n = 81 2 3 4 5 5 5 5

 So now this problem can be reduced to finding the first duplicate element
 in the array because remaining other elements will be unique. I think this
 can be done in linear time.


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


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


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