Re: [algogeeks] amazon question

[bharat b]

If the requirement is only searching in 3-D .. there is a famous data
structure K-D tree.

On Tue, Oct 23, 2012 at 5:54 PM, bharat b wrote:

> we can represent in 3-D array ..
> what type of elements are those .. is there any special kind of formation
> among elements for searching? we have to think about searching based on the
> criteria ..
>
>
> On Tue, Oct 23, 2012 at 3:34 PM, saket  wrote:
>
>> We have a long chain of cuboids in all the six directions (six faces).
>> One start node is given and one end node is given. Give a data structure to
>> represent this also search for the given node from start node.
>>
>> --
>> 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/-/5GuOVuTne4cJ.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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

[bharat b]

we can represent in 3-D array ..
what type of elements are those .. is there any special kind of formation
among elements for searching? we have to think about searching based on the
criteria ..

On Tue, Oct 23, 2012 at 3:34 PM, saket  wrote:

> We have a long chain of cuboids in all the six directions (six faces). One
> start node is given and one end node is given. Give a data structure to
> represent this also search for the given node from start node.
>
> --
> 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/-/5GuOVuTne4cJ.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[Amol Sharma]

but the worst case still remains O(sqrt(E))
--


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
 







On Fri, Mar 23, 2012 at 7:12 AM, Rujin Cao  wrote:

> @atul:
> Anurag's code has illustrated the idea of O(sqrt(E)) solution.
>
> One more thing to optimize is that we can safely break after finding the
> first factor of E which is less than sqrt(E).
> So the code could be changed to:
>
> #include#include#include#include#includeusing
>  namespace std;
> #define INFY 17
> int main()
> {
>int n, i, j;
>int val, minDiv, minDis;
>while(1)
>{
>cin >> n;
>minDis = INFY;
>for (i = n; i <= n+
> 2; i++)
>{
>*for (j = sqrt(i * 1.0); j > 0; j--)*
>
>{
>   if (i % j == 0  &&  minDis > (i/j - j) )
>   {
>  minDis = i/j - j;
>  minDiv = j;
>  val =
>  i;
>  *break;*
>
>   }
>}
>}
>cout<}
>//system("pause");
>return 0;
> }
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

[Rujin Cao]

@atul:
Anurag's code has illustrated the idea of O(sqrt(E)) solution.

One more thing to optimize is that we can safely break after finding the
first factor of E which is less than sqrt(E).
So the code could be changed to:

#include#include#include#include#includeusing
namespace std;#define INFY 17int main()
{
   int n, i, j;
   int val, minDiv, minDis;
   while(1)
   {
   cin >> n;
   minDis = INFY;
   for (i = n; i <= n+2; i++)
   {
   *for (j = sqrt(i * 1.0); j > 0; j--)*
   {
  if (i % j == 0  &&  minDis > (i/j - j) )
  {
 minDis = i/j - j;
 minDiv = j;
 val = i;
 *break;*
  }
   }
   }
   cout

Re: [algogeeks] Amazon question

[atul anand]

@Rujin : mathematically point 2.2 seems straight forward but can we achieve
value of x and y with an algo whose complexity wud be  O(sqrt(E)) ??

On Wed, Mar 21, 2012 at 2:37 PM, Rujin Cao  wrote:

> One possible way is:
>
> 1) Put the three candidate number together into an array [n, n + 1, n + 2]
> 2) Iterate each element *E* in that array and test whether *E* is a prime
> number
>2.1) If it is, there will be only one way to find the two numbers
> product to be *E*, i.e.  {x = 1, y = E} OR {x = E, y = 1}, so the result
> is E - 1
>2.2) Otherwise, we should choose x and y that are closest to the
> sqrt of *E*, which is quite straight forward.
>E.g.  72 = 8 * 9 and 72 = 2 * 36  (2 < 8 and 36 > 9, so |9
> - 8| < |36 - 2|)
>
>
> So total time complexity is O(sqrt(E)).
>
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[Rujin Cao]

One possible way is:

1) Put the three candidate number together into an array [n, n + 1, n + 2]
2) Iterate each element *E* in that array and test whether *E* is a prime
number
   2.1) If it is, there will be only one way to find the two numbers
product to be *E*, i.e.  {x = 1, y = E} OR {x = E, y = 1}, so the result is
E - 1
   2.2) Otherwise, we should choose x and y that are closest to the
sqrt of *E*, which is quite straight forward.
   E.g.  72 = 8 * 9 and 72 = 2 * 36  (2 < 8 and 36 > 9, so |9 -
8| < |36 - 2|)


So total time complexity is O(sqrt(E)).

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

[Nitin Garg]

@surendra - converse is not true.
aabbcc will be reduced 2.
aabbcc can be reduced to acbcc
acbcc has unequal number of a's,b's and c's. Hence it should be reducable
to 1.


On Sun, Nov 13, 2011 at 3:42 PM, Anika Jain  wrote:

> its coming out be either 1 or 2 in all cases
>
>
> On Sun, Nov 13, 2011 at 1:55 PM, UTKARSH SRIVASTAV <
> usrivastav...@gmail.com> wrote:
>
>> @Surinder give some proof or logic
>>
>>
>> On Sun, Nov 13, 2011 at 10:25 AM, surender sanke wrote:
>>
>>> @nitin
>>> yes i meant the same, if each different character have equal number of
>>> frequency like abcabcabc  a's -3, b's - 3 c's- 3
>>> then resultant string size is 2 else 1
>>>
>>> surender
>>>
>>>
>>> On Sun, Nov 13, 2011 at 12:21 AM, Ankur Garg wrote:
>>>
 @Srinivas

 Wat if the string is abc
 then it reduces to cc :) ...So  size 2 can also be there.so u cant say
 it will be 1 "always"


 On Sun, Nov 13, 2011 at 12:01 AM, Srinivasa Chaitanya T <
 tschaitanya@gmail.com> wrote:

>
>
> On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me wrote:
>
>> Given a string consisting of a,b and c's, we can perform the
>> following
>> operation:
>>  Take any two adjacent distinct characters and replace it with the
>> third character. For example, if 'a' and 'c' are adjacent, they can
>> replaced with 'b'.
>> What is the smallest string which can result by applying this
>> operation repeatedly?
>>
>> 1) if the string a..aaa, or bb..bb, etc... string cannot be
> modified
> 2) if string starts with ac => this can be reduced to b ->
> aaac -> aab -> ac -> b
> 3) So if string not of type (1), then it can be reduced to single
> character "always" using  method 2
>e.g:
>   *aab*cacaab // first reduce aab to b
>   *bbc*acaab  // reduce bbc to c
>   *ca*caab
>   *bc*aab
>   *aaab*
>   c
> .. i guess u got the idea
>
>
>
>
>
>>  --
>> You received this message because you are subscribed to the Google
>> Groups "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> T Srinivasa Chaitanya
>
>
>  --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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.
>>>
>>
>>
>>
>> --
>> *UTKARSH SRIVASTAV
>> CSE-3
>> B-Tech 3rd Year
>> @MNNIT ALLAHABAD*
>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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.
>



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

Re: [algogeeks] Amazon Question

[Anika Jain]

its coming out be either 1 or 2 in all cases

On Sun, Nov 13, 2011 at 1:55 PM, UTKARSH SRIVASTAV
wrote:

> @Surinder give some proof or logic
>
>
> On Sun, Nov 13, 2011 at 10:25 AM, surender sanke wrote:
>
>> @nitin
>> yes i meant the same, if each different character have equal number of
>> frequency like abcabcabc  a's -3, b's - 3 c's- 3
>> then resultant string size is 2 else 1
>>
>> surender
>>
>>
>> On Sun, Nov 13, 2011 at 12:21 AM, Ankur Garg wrote:
>>
>>> @Srinivas
>>>
>>> Wat if the string is abc
>>> then it reduces to cc :) ...So  size 2 can also be there.so u cant say
>>> it will be 1 "always"
>>>
>>>
>>> On Sun, Nov 13, 2011 at 12:01 AM, Srinivasa Chaitanya T <
>>> tschaitanya@gmail.com> wrote:
>>>


 On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me wrote:

> Given a string consisting of a,b and c's, we can perform the
> following
> operation:
>  Take any two adjacent distinct characters and replace it with the
> third character. For example, if 'a' and 'c' are adjacent, they can
> replaced with 'b'.
> What is the smallest string which can result by applying this
> operation repeatedly?
>
> 1) if the string a..aaa, or bb..bb, etc... string cannot be
 modified
 2) if string starts with ac => this can be reduced to b -> aaac
 -> aab -> ac -> b
 3) So if string not of type (1), then it can be reduced to single
 character "always" using  method 2
e.g:
   *aab*cacaab // first reduce aab to b
   *bbc*acaab  // reduce bbc to c
   *ca*caab
   *bc*aab
   *aaab*
   c
 .. i guess u got the idea





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


 --
 T Srinivasa Chaitanya


  --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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.
>>
>
>
>
> --
> *UTKARSH SRIVASTAV
> CSE-3
> B-Tech 3rd Year
> @MNNIT ALLAHABAD*
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[UTKARSH SRIVASTAV]

@Surinder give some proof or logic

On Sun, Nov 13, 2011 at 10:25 AM, surender sanke wrote:

> @nitin
> yes i meant the same, if each different character have equal number of
> frequency like abcabcabc  a's -3, b's - 3 c's- 3
> then resultant string size is 2 else 1
>
> surender
>
>
> On Sun, Nov 13, 2011 at 12:21 AM, Ankur Garg  wrote:
>
>> @Srinivas
>>
>> Wat if the string is abc
>> then it reduces to cc :) ...So  size 2 can also be there.so u cant say it
>> will be 1 "always"
>>
>>
>> On Sun, Nov 13, 2011 at 12:01 AM, Srinivasa Chaitanya T <
>> tschaitanya@gmail.com> wrote:
>>
>>>
>>>
>>> On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me wrote:
>>>
 Given a string consisting of a,b and c's, we can perform the
 following
 operation:
  Take any two adjacent distinct characters and replace it with the
 third character. For example, if 'a' and 'c' are adjacent, they can
 replaced with 'b'.
 What is the smallest string which can result by applying this
 operation repeatedly?

 1) if the string a..aaa, or bb..bb, etc... string cannot be
>>> modified
>>> 2) if string starts with ac => this can be reduced to b -> aaac
>>> -> aab -> ac -> b
>>> 3) So if string not of type (1), then it can be reduced to single
>>> character "always" using  method 2
>>>e.g:
>>>   *aab*cacaab // first reduce aab to b
>>>   *bbc*acaab  // reduce bbc to c
>>>   *ca*caab
>>>   *bc*aab
>>>   *aaab*
>>>   c
>>> .. i guess u got the idea
>>>
>>>
>>>
>>>
>>>
  --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


>>>
>>>
>>> --
>>> T Srinivasa Chaitanya
>>>
>>>
>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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.
>



-- 
*UTKARSH SRIVASTAV
CSE-3
B-Tech 3rd Year
@MNNIT ALLAHABAD*

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

[surender sanke]

@nitin
yes i meant the same, if each different character have equal number of
frequency like abcabcabc  a's -3, b's - 3 c's- 3
then resultant string size is 2 else 1

surender

On Sun, Nov 13, 2011 at 12:21 AM, Ankur Garg  wrote:

> @Srinivas
>
> Wat if the string is abc
> then it reduces to cc :) ...So  size 2 can also be there.so u cant say it
> will be 1 "always"
>
>
> On Sun, Nov 13, 2011 at 12:01 AM, Srinivasa Chaitanya T <
> tschaitanya@gmail.com> wrote:
>
>>
>>
>> On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me  wrote:
>>
>>> Given a string consisting of a,b and c's, we can perform the
>>> following
>>> operation:
>>>  Take any two adjacent distinct characters and replace it with the
>>> third character. For example, if 'a' and 'c' are adjacent, they can
>>> replaced with 'b'.
>>> What is the smallest string which can result by applying this
>>> operation repeatedly?
>>>
>>> 1) if the string a..aaa, or bb..bb, etc... string cannot be
>> modified
>> 2) if string starts with ac => this can be reduced to b -> aaac
>> -> aab -> ac -> b
>> 3) So if string not of type (1), then it can be reduced to single
>> character "always" using  method 2
>>e.g:
>>   *aab*cacaab // first reduce aab to b
>>   *bbc*acaab  // reduce bbc to c
>>   *ca*caab
>>   *bc*aab
>>   *aaab*
>>   c
>> .. i guess u got the idea
>>
>>
>>
>>
>>
>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>
>>
>> --
>> T Srinivasa Chaitanya
>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] Amazon Question

[Ankur Garg]

@Srinivas

Wat if the string is abc
then it reduces to cc :) ...So  size 2 can also be there.so u cant say it
will be 1 "always"

On Sun, Nov 13, 2011 at 12:01 AM, Srinivasa Chaitanya T <
tschaitanya@gmail.com> wrote:

>
>
> On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me  wrote:
>
>> Given a string consisting of a,b and c's, we can perform the
>> following
>> operation:
>>  Take any two adjacent distinct characters and replace it with the
>> third character. For example, if 'a' and 'c' are adjacent, they can
>> replaced with 'b'.
>> What is the smallest string which can result by applying this
>> operation repeatedly?
>>
>> 1) if the string a..aaa, or bb..bb, etc... string cannot be
> modified
> 2) if string starts with ac => this can be reduced to b -> aaac ->
> aab -> ac -> b
> 3) So if string not of type (1), then it can be reduced to single
> character "always" using  method 2
>e.g:
>   *aab*cacaab // first reduce aab to b
>   *bbc*acaab  // reduce bbc to c
>   *ca*caab
>   *bc*aab
>   *aaab*
>   c
> .. i guess u got the idea
>
>
>
>
>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> T Srinivasa Chaitanya
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[Srinivasa Chaitanya T]

On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me  wrote:

> Given a string consisting of a,b and c's, we can perform the
> following
> operation:
>  Take any two adjacent distinct characters and replace it with the
> third character. For example, if 'a' and 'c' are adjacent, they can
> replaced with 'b'.
> What is the smallest string which can result by applying this
> operation repeatedly?
>
> 1) if the string a..aaa, or bb..bb, etc... string cannot be
modified
2) if string starts with ac => this can be reduced to b -> aaac ->
aab -> ac -> b
3) So if string not of type (1), then it can be reduced to single character
"always" using  method 2
   e.g:
  *aab*cacaab // first reduce aab to b
  *bbc*acaab  // reduce bbc to c
  *ca*caab
  *bc*aab
  *aaab*
  c
.. i guess u got the idea





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


-- 
T Srinivasa Chaitanya

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

[Ankur Garg]

Hey I coded it . The answer is either 2 or 1 ..So I guess you guys are rite
:)

Here is the code
void smallestString(string &str){
if(str.empty()) return;
int j=0,i,k=0;
for(i=1;i0)j--;
i=j;
  }
}
}

On Sat, Nov 12, 2011 at 8:19 PM, Nitin Garg wrote:

> If yes, how do you prove it?
>
>
> On Sat, Nov 12, 2011 at 8:18 PM, Nitin Garg wrote:
>
>> I can prove that the size of resulting string will be 1 or 2.
>>
>> @surender -
>> what do you mean by no of distinct characters? they are 3 in this case -
>> a,b and c.
>> Do you mean to say that the no. of times each character appears are equal
>> then the final string is of size 2. and 1 otherwise?
>>
>>
>> On Sat, Nov 12, 2011 at 4:57 PM, surender sanke wrote:
>>
>>> @myself
>>>
>>> if number of distinct characters are equal then its final string size is
>>> 2.
>>> else there are more repeated characters other than distinct characters
>>> then its 1
>>>
>>>  correct me !!!
>>> surender
>>>
>>> On Sat, Nov 12, 2011 at 4:46 PM, surender sanke wrote:
>>>
 All distinct combinations will result in string size of 2 + rest
 repeated characters
 eg
 abcabcabc ->aabbcc->abc->aa or bb or cc

 surender

 On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me wrote:

> Given a string consisting of a,b and c's, we can perform the
> following
> operation:
>  Take any two adjacent distinct characters and replace it with the
> third character. For example, if 'a' and 'c' are adjacent, they can
> replaced with 'b'.
> What is the smallest string which can result by applying this
> operation repeatedly?
>
> --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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.
>>>
>>
>>
>>
>> --
>> Nitin Garg
>>
>> "Personality can open doors, but only Character can keep them open"
>>
>
>
>
> --
> 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] Amazon Question

[Nitin Garg]

If yes, how do you prove it?

On Sat, Nov 12, 2011 at 8:18 PM, Nitin Garg wrote:

> I can prove that the size of resulting string will be 1 or 2.
>
> @surender -
> what do you mean by no of distinct characters? they are 3 in this case -
> a,b and c.
> Do you mean to say that the no. of times each character appears are equal
> then the final string is of size 2. and 1 otherwise?
>
>
> On Sat, Nov 12, 2011 at 4:57 PM, surender sanke wrote:
>
>> @myself
>>
>> if number of distinct characters are equal then its final string size is
>> 2.
>> else there are more repeated characters other than distinct characters
>> then its 1
>>
>>  correct me !!!
>> surender
>>
>> On Sat, Nov 12, 2011 at 4:46 PM, surender sanke wrote:
>>
>>> All distinct combinations will result in string size of 2 + rest
>>> repeated characters
>>> eg
>>> abcabcabc ->aabbcc->abc->aa or bb or cc
>>>
>>> surender
>>>
>>> On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me wrote:
>>>
 Given a string consisting of a,b and c's, we can perform the
 following
 operation:
  Take any two adjacent distinct characters and replace it with the
 third character. For example, if 'a' and 'c' are adjacent, they can
 replaced with 'b'.
 What is the smallest string which can result by applying this
 operation repeatedly?

 --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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.
>>
>
>
>
> --
> Nitin Garg
>
> "Personality can open doors, but only Character can keep them open"
>



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

Re: [algogeeks] Amazon Question

[Ankur Garg]

Did they ask you to code this or just asked logic



On Sat, Nov 12, 2011 at 4:57 PM, surender sanke  wrote:

> @myself
>
> if number of distinct characters are equal then its final string size is 2.
> else there are more repeated characters other than distinct characters
> then its 1
>
> correct me !!!
> surender
>
> On Sat, Nov 12, 2011 at 4:46 PM, surender sanke wrote:
>
>> All distinct combinations will result in string size of 2 + rest repeated
>> characters
>> eg
>> abcabcabc ->aabbcc->abc->aa or bb or cc
>>
>> surender
>>
>> On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me  wrote:
>>
>>> Given a string consisting of a,b and c's, we can perform the
>>> following
>>> operation:
>>>  Take any two adjacent distinct characters and replace it with the
>>> third character. For example, if 'a' and 'c' are adjacent, they can
>>> replaced with 'b'.
>>> What is the smallest string which can result by applying this
>>> operation repeatedly?
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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] Amazon Question

[Nitin Garg]

I can prove that the size of resulting string will be 1 or 2.

@surender -
what do you mean by no of distinct characters? they are 3 in this case -
a,b and c.
Do you mean to say that the no. of times each character appears are equal
then the final string is of size 2. and 1 otherwise?

On Sat, Nov 12, 2011 at 4:57 PM, surender sanke  wrote:

> @myself
>
> if number of distinct characters are equal then its final string size is 2.
> else there are more repeated characters other than distinct characters
> then its 1
>
> correct me !!!
> surender
>
> On Sat, Nov 12, 2011 at 4:46 PM, surender sanke wrote:
>
>> All distinct combinations will result in string size of 2 + rest repeated
>> characters
>> eg
>> abcabcabc ->aabbcc->abc->aa or bb or cc
>>
>> surender
>>
>> On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me  wrote:
>>
>>> Given a string consisting of a,b and c's, we can perform the
>>> following
>>> operation:
>>>  Take any two adjacent distinct characters and replace it with the
>>> third character. For example, if 'a' and 'c' are adjacent, they can
>>> replaced with 'b'.
>>> What is the smallest string which can result by applying this
>>> operation repeatedly?
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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.
>



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

Re: [algogeeks] Amazon Question

[surender sanke]

@myself

if number of distinct characters are equal then its final string size is 2.
else there are more repeated characters other than distinct characters then
its 1

correct me !!!
surender

On Sat, Nov 12, 2011 at 4:46 PM, surender sanke  wrote:

> All distinct combinations will result in string size of 2 + rest repeated
> characters
> eg
> abcabcabc ->aabbcc->abc->aa or bb or cc
>
> surender
>
> On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me  wrote:
>
>> Given a string consisting of a,b and c's, we can perform the
>> following
>> operation:
>>  Take any two adjacent distinct characters and replace it with the
>> third character. For example, if 'a' and 'c' are adjacent, they can
>> replaced with 'b'.
>> What is the smallest string which can result by applying this
>> operation repeatedly?
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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

[surender sanke]

All distinct combinations will result in string size of 2 + rest repeated
characters
eg
abcabcabc ->aabbcc->abc->aa or bb or cc

surender

On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me  wrote:

> Given a string consisting of a,b and c's, we can perform the
> following
> operation:
>  Take any two adjacent distinct characters and replace it with the
> third character. For example, if 'a' and 'c' are adjacent, they can
> replaced with 'b'.
> What is the smallest string which can result by applying this
> operation repeatedly?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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
looks interesting. A few things -

>> To check the particular number square can be written as sum of two
squares or not. If it has any prime factor x such that x % 4 == 1 then only.
 - What would be the complexity of finding prime factors. Did you factor
in it in overall complexity.
 - "if it has any prime factor x such that x % 4 == 1 then only", this
looks interesting. how did you figire this out? Is there a theorem of this
sort?

>> so time complexity will reduce to O(n * (number of side which can be
largest one for any triplet) ).
   unfortunately, in terms of complexity it will still be O(n*n) because
there is no predictive way to find how many elements can be discarded with
above criteria. In fact in the worst case each element may satisfy the prime
factor (with modulo 4 = 1) condition. That said, I agree that it definitely
reduces the average running time.

Thanks,
- Ravindra

On Thu, Oct 20, 2011 at 3:38 PM, anshu mishra wrote:

> @Ravindra
>
> To check the particular number square can be written as sum of two squares
> or not.
>
> If it has any prime factor x such that x % 4 == 1 then only.
>
> Now about time complexity.
>
> suppose u have given array is.
>
> 10 6 13 9 17 4 18 12 1 5.
>
> now u can easily skip the numbers(1, 4, 6, 9, 12, 18);
>
>
> and u have to check only for these numbers(5, 10, 13, 17);
>
> so time complexity will reduce to O(n * (number of side which can be
> largest one for any triplet) ).
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[anshu mishra]

@Ravindra

To check the particular number square can be written as sum of two squares
or not.

If it has any prime factor x such that x % 4 == 1 then only.

Now about time complexity.

suppose u have given array is.

10 6 13 9 17 4 18 12 1 5.

now u can easily skip the numbers(1, 4, 6, 9, 12, 18);


and u have to check only for these numbers(5, 10, 13, 17);

so time complexity will reduce to O(n * (number of side which can be largest
one for any triplet) ).

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

[sravanreddy001]

Sorry.. 
this is good one, 
but works for consecutive numbers only from 1..N

-- 
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/-/07wiKGP2WusJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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 wrote:

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

[anshu mishra]

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

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

[Ankur Garg]

@Shashank ..+1 ..I wud say he must be given a tuning award :D :D  for
solving such eternal conundrum ;)



On Mon, Oct 17, 2011 at 2:37 PM, WgpShashank wrote:

> @wladimir , its PPT (Pythagoras triplets ) but its number theory based
> approach  http://en.wikipedia.org/wiki/Pythagorean_triple might not be
> good idea
>
> Here is approach :
> *
> *
> *Euclid's 
> formula*[1] is
> a fundamental formula for generating Pythagorean triples given an arbitrary
> pair of positive integers *m* and *n* with *m* > *n*. The formula states
> that the integers p=m^2-n^2 , q=2mn r=m^2+n^2  , we have to sort the array
> in non-increasing order  , then for each m>n we have to generate the  all
> such p,q,r in worst case it will also requires O(N^2) such p,q,r for each
> M>N isn't it ? then its not less then O(n^2) ??
> Even with this approach,The triple generated by Euclid's formula is
> primitive if and only if *m* and *n* are coprime and *m*-*n* is odd. If
> both *m* and *n* are odd, then *a*, *b*, and *c* will be even, and so the
> triple will not be primitive; however, dividing *a*, *b*, and *c* by 2
> will yield a primitive triple if *m* and *n* are coprime.
>
> @all other , its similar to 3 sun , can't be done in less then O(N^2) if
> number are not in range , When the integers are in the range [-*u* ... *u*],
> 3SUM can be solved in time O(n + *u* lg *u*) by representing *S* as a bit
> vector and performing a discrete convolution using FFT.
>
> i wondered if any other  algo/code/link you have which works in less then
> O(N^2) , Better if One Explain The Approach or Algorithm , You Might able to
> fill Patent :D
>
> Thanks
> Shashank
> CSE, BIT Mesra
>
> --
> 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/-/JQWWHDKMCiAJ.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[Ankur Garg]

*Turing :P

On Mon, Oct 17, 2011 at 3:51 PM, Ankur Garg  wrote:

> @Shashank ..+1 ..I wud say he must be given a tuning award :D :D  for
> solving such eternal conundrum ;)
>
>
>
> On Mon, Oct 17, 2011 at 2:37 PM, WgpShashank 
> wrote:
>
>> @wladimir , its PPT (Pythagoras triplets ) but its number theory based
>> approach  http://en.wikipedia.org/wiki/Pythagorean_triple might not be
>> good idea
>>
>> Here is approach :
>> *
>> *
>> *Euclid's 
>> formula*[1] is
>> a fundamental formula for generating Pythagorean triples given an arbitrary
>> pair of positive integers *m* and *n* with *m* > *n*. The formula states
>> that the integers p=m^2-n^2 , q=2mn r=m^2+n^2  , we have to sort the array
>> in non-increasing order  , then for each m>n we have to generate the  all
>> such p,q,r in worst case it will also requires O(N^2) such p,q,r for each
>> M>N isn't it ? then its not less then O(n^2) ??
>> Even with this approach,The triple generated by Euclid's formula is
>> primitive if and only if *m* and *n* are coprime and *m*-*n* is odd. If
>> both *m* and *n* are odd, then *a*, *b*, and *c* will be even, and so the
>> triple will not be primitive; however, dividing *a*, *b*, and *c* by 2
>> will yield a primitive triple if *m* and *n* are coprime.
>>
>> @all other , its similar to 3 sun , can't be done in less then O(N^2) if
>> number are not in range , When the integers are in the range [-*u* ... *u
>> *], 3SUM can be solved in time O(n + *u* lg *u*) by representing *S* as a
>> bit vector and performing a discrete convolution using FFT.
>>
>> i wondered if any other  algo/code/link you have which works in less then
>> O(N^2) , Better if One Explain The Approach or Algorithm , You Might able to
>> fill Patent :D
>>
>> Thanks
>> Shashank
>> CSE, BIT Mesra
>>
>> --
>> 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/-/JQWWHDKMCiAJ.
>>
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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

[WgpShashank]

@wladimir , its PPT (Pythagoras triplets ) but its number theory based 
approach  http://en.wikipedia.org/wiki/Pythagorean_triple might not be good 
idea 

Here is approach :
*
*
*Euclid's 
formula*[1] is 
a fundamental formula for generating Pythagorean triples given an arbitrary 
pair of positive integers *m* and *n* with *m* > *n*. The formula states 
that the integers p=m^2-n^2 , q=2mn r=m^2+n^2  , we have to sort the array 
in non-increasing order  , then for each m>n we have to generate the  all 
such p,q,r in worst case it will also requires O(N^2) such p,q,r for each 
M>N isn't it ? then its not less then O(n^2) ??
Even with this approach,The triple generated by Euclid's formula is 
primitive if and only if *m* and *n* are coprime and *m*-*n* is odd. If 
both *m* and *n* are odd, then *a*, *b*, and *c* will be even, and so the 
triple will not be primitive; however, dividing *a*, *b*, and *c* by 2 will 
yield a primitive triple if *m* and *n* are coprime.

@all other , its similar to 3 sun , can't be done in less then O(N^2) if 
number are not in range , When the integers are in the range [-*u* ... *u*], 
3SUM can be solved in time O(n + *u* lg *u*) by representing *S* as a bit 
vector and performing a discrete convolution using FFT. 

i wondered if any other  algo/code/link you have which works in less then 
O(N^2) , Better if One Explain The Approach or Algorithm , You Might able to 
fill Patent :D

Thanks
Shashank 
CSE, BIT Mesra

-- 
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/-/JQWWHDKMCiAJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

[sravanreddy001]

This appears to be n^(3/2) complexity, looking at one of the solutions in 

http://stackoverflow.com/questions/575117/pythagorean-triplets

assuming elements as sorted. (x cannot be greater than sqrt(2z) as x2+y2 = 
z2 --> for the worst value of y2 --> 2x^2 = z2

MaxX = ( 2 * N - 1 ) ** 0.5

for x in 3..MaxX {
  y = x+1
  z = y+1
  m = x*x + y*y
  k = z * z
  while z <= N {
 while k < m {
z = z + 1
k = k + (2*z) - 1
}
if k == m and z <= N then {
// use x, y, z
}
y = y + 1
m = m + (2 * y) - 1
  }
 }

-- 
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/-/UjRPZ8oIbmkJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

[Ashish Goel]

http://stackoverflow.com/questions/575117/pythagorean-triplets

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


On Fri, Oct 14, 2011 at 3:14 PM, Ankur Garg  wrote:

> @Rahul
>
> Pls elaborate with an example ...
>
>
> On Fri, Oct 14, 2011 at 2:35 PM, rahul patil <
> rahul.deshmukhpa...@gmail.com> wrote:
>
>> You can take advantage of a basic property of triagle that
>>
>> sum of largest side of triangle < sum of other two sides,
>>
>> After sorting you could easily deside the range in which possible solution
>> could be found for a chosen hypotenuse
>>
>> On Fri, Oct 14, 2011 at 11:10 AM, ravindra patel <
>> ravindra.it...@gmail.com> wrote:
>>
>>> @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 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  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.
>>>
>>
>>
>>
>> --
>> Regards,
>> Rahul Patil
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] Amazon Question - Find Pythagorean triplet in an unsorted array

[Bittu Sarkar]

@rahul It still will be O(n^2) time complexity

On 14 October 2011 15:14, Ankur Garg  wrote:

> @Rahul
>
> Pls elaborate with an example ...
>
>
> On Fri, Oct 14, 2011 at 2:35 PM, rahul patil <
> rahul.deshmukhpa...@gmail.com> wrote:
>
>> You can take advantage of a basic property of triagle that
>>
>> sum of largest side of triangle < sum of other two sides,
>>
>> After sorting you could easily deside the range in which possible solution
>> could be found for a chosen hypotenuse
>>
>> On Fri, Oct 14, 2011 at 11:10 AM, ravindra patel <
>> ravindra.it...@gmail.com> wrote:
>>
>>> @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 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  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.
>>>
>>
>>
>>
>> --
>> Regards,
>> Rahul Patil
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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.

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

[rahul patil]

suppose sorted array is

1,2,3,5,10,12,13,17,19,25

so if u want to find possible combinations, with 25 as hypotenuse, then only
range 10 ... 19 could have answer

as 19 + 10 > 25

On Fri, Oct 14, 2011 at 3:14 PM, Ankur Garg  wrote:

> @Rahul
>
> Pls elaborate with an example ...
>
>
> On Fri, Oct 14, 2011 at 2:35 PM, rahul patil <
> rahul.deshmukhpa...@gmail.com> wrote:
>
>> You can take advantage of a basic property of triagle that
>>
>> sum of largest side of triangle < sum of other two sides,
>>
>> After sorting you could easily deside the range in which possible solution
>> could be found for a chosen hypotenuse
>>
>> On Fri, Oct 14, 2011 at 11:10 AM, ravindra patel <
>> ravindra.it...@gmail.com> wrote:
>>
>>> @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 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  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.
>>>
>>
>>
>>
>> --
>> Regards,
>> Rahul Patil
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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,
Rahul Patil

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

[Siddharth Pipriya]

using properties of tiangle wont help i guess. the will give the range
of VALUES you want to restrict yourself to. not the range of INDEX's
of the array...

On Fri, Oct 14, 2011 at 3:14 PM, Ankur Garg  wrote:
> @Rahul
> Pls elaborate with an example ...
>
> On Fri, Oct 14, 2011 at 2:35 PM, rahul patil 
> wrote:
>>
>> You can take advantage of a basic property of triagle that
>>
>> sum of largest side of triangle < sum of other two sides,
>>
>> After sorting you could easily deside the range in which possible solution
>> could be found for a chosen hypotenuse
>>
>> On Fri, Oct 14, 2011 at 11:10 AM, ravindra patel
>>  wrote:
>>>
>>> @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 
>>> 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  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.
>>
>>
>>
>> --
>> Regards,
>> Rahul Patil
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] Amazon Question - Find Pythagorean triplet in an unsorted array

[Ankur Garg]

@Rahul

Pls elaborate with an example ...

On Fri, Oct 14, 2011 at 2:35 PM, rahul patil
wrote:

> You can take advantage of a basic property of triagle that
>
> sum of largest side of triangle < sum of other two sides,
>
> After sorting you could easily deside the range in which possible solution
> could be found for a chosen hypotenuse
>
> On Fri, Oct 14, 2011 at 11:10 AM, ravindra patel  > wrote:
>
>> @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 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  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.
>>
>
>
>
> --
> Regards,
> Rahul Patil
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[rahul patil]

You can take advantage of a basic property of triagle that

sum of largest side of triangle < sum of other two sides,

After sorting you could easily deside the range in which possible solution
could be found for a chosen hypotenuse

On Fri, Oct 14, 2011 at 11:10 AM, ravindra patel
wrote:

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



-- 
Regards,
Rahul Patil

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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  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  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] Amazon Question - Find Pythagorean triplet in an unsorted array

[Ankur Garg]

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

On Thu, Oct 13, 2011 at 11:34 PM, rahul  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.

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

[Ankur Garg]

BTW can we solve this by hashing..That is the only feasible solution which
comes to my mind to reduce the time complexity ?

On Thu, Oct 13, 2011 at 11:20 PM, Ankur Garg  wrote:

> Dude this is nothing but 3 sum problem
>
> http://en.wikipedia.org/wiki/3SUM
>
> Ask interviewer to check this link and say he has gone mad!! :P
>
> Regards
> Ankur
>
> On Thu, Oct 13, 2011 at 10:29 PM, ravindra patel  > wrote:
>
>> 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.
>>
>
>

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

[praveen raj]

N2 would me minimum
On 13-Oct-2011 11:08 PM, "ravindra patel"  wrote:

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

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

[Ankur Garg]

Dude this is nothing but 3 sum problem

http://en.wikipedia.org/wiki/3SUM

Ask interviewer to check this link and say he has gone mad!! :P

Regards
Ankur

On Thu, Oct 13, 2011 at 10:29 PM, ravindra patel
wrote:

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

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

[Wladimir Tavares]

I thinking in this property but i dont know how to use :(


Euclid, in his book Elements, demonstrated that there is a infinnity of
suits early Pythagoreans. Moreover, he found a formula that generates all
primitive Pythagorean suits. Given two natural numbers m> n, the suit (a, b,
c), where:

 a = m ^ 2 - n ^ 2,
 b = 2mn,
 c = m ^ 2 + n ^ 2,




Wladimir Araujo Tavares
*Federal University of Ceará 
Homepage  |
Maratona|
*




On Thu, Oct 13, 2011 at 1:59 PM, ravindra patel wrote:

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

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

[Deoki Nandan]

can you tell how to write code to access log file

On 26 September 2011 09:27, teja bala  wrote:

> do dfs traversal along the two log files and maintain a stack in which push
> the element from 1st log file and if matching id in 2 log file is found pop
> it and display it to user
> but dis 'll take extra stack space ,,,
>
> another sol.. maintain a bit array for any of the log file and while doing
> BFS traversal if any nth  common id found set the nth bit in bit array and
> thus retrieving the data where the bit is set
>
>
> On Mon, Sep 26, 2011 at 1:32 AM, khushboo lohia wrote:
>
>> Are the customer id's in 2 files in sorted order ?
>>
>>
>> On Mon, Sep 26, 2011 at 1:29 AM, Ankur Garg  wrote:
>>
>>> You are given 2 log files each having 1 billion entries and each entry
>>> has a unique customer id.You need to print the records in two files which
>>> are common.
>>>
>>>
>>>
>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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.
>



-- 
**With Regards
Deoki Nandan Vishwakarma

*
*

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

[teja bala]

do dfs traversal along the two log files and maintain a stack in which push
the element from 1st log file and if matching id in 2 log file is found pop
it and display it to user
but dis 'll take extra stack space ,,,

another sol.. maintain a bit array for any of the log file and while doing
BFS traversal if any nth  common id found set the nth bit in bit array and
thus retrieving the data where the bit is set

On Mon, Sep 26, 2011 at 1:32 AM, khushboo lohia  wrote:

> Are the customer id's in 2 files in sorted order ?
>
>
> On Mon, Sep 26, 2011 at 1:29 AM, Ankur Garg  wrote:
>
>> You are given 2 log files each having 1 billion entries and each entry has
>> a unique customer id.You need to print the records in two files which are
>> common.
>>
>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] Amazon Question

[khushboo lohia]

Are the customer id's in 2 files in sorted order ?

On Mon, Sep 26, 2011 at 1:29 AM, Ankur Garg  wrote:

> You are given 2 log files each having 1 billion entries and each entry has
> a unique customer id.You need to print the records in two files which are
> common.
>
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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 SDE

[saurabh agrawal]

@yogesh, yes you are right. It is not an array, but an abstraact data type
which supports, insertion with index.


On Tue, Sep 20, 2011 at 5:18 PM, Yogesh Yadav  wrote:

> @saurabh:
>
> i think may be u left some part of question to mention...  the array may be
> a heap array ...
>
> or if the ques is correct then i don't think this sum can be possible in
> O(log n)  for previously existing array...
>
> may be we have to make array from start...then as you mention we can use
> another array s[] as
>
> s[i]=s[i-1]+a[i];
>
> for each addition in a[i] we will add s[i] as above then it can be possible
> in O(1)...
>
> If i am wrong and it can be possible in O(log n) then plz tell
>
> 
>
> On Tue, Sep 20, 2011 at 3:28 PM, saurabh agrawal wrote:
>
>> Design an algorithm to perform operation on an array
>> Add(i,y)-> add value y to i position
>> sum(i) -> sum of first i numbers
>> we can use additional array O(n) and worst case performance should be
>> O(log n) for both operation
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] Amazon question SDE

[Yogesh Yadav]

@saurabh:

i think may be u left some part of question to mention...  the array may be
a heap array ...

or if the ques is correct then i don't think this sum can be possible in
O(log n)  for previously existing array...

may be we have to make array from start...then as you mention we can use
another array s[] as

s[i]=s[i-1]+a[i];

for each addition in a[i] we will add s[i] as above then it can be possible
in O(1)...

If i am wrong and it can be possible in O(log n) then plz tell



On Tue, Sep 20, 2011 at 3:28 PM, saurabh agrawal wrote:

> Design an algorithm to perform operation on an array
> Add(i,y)-> add value y to i position
> sum(i) -> sum of first i numbers
> we can use additional array O(n) and worst case performance should be O(log
> n) for both operation
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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 SDE

[vishnu VR]

This can be done using binary indexed tree.
Thanks and Regards,

Vishnu Vardan Reddy Onteddu
Software Engineer

KeyPoint Technologies India Pvt Ltd.
9Q1A, 9th Floor, Cyber Towers,
HITEC City, Madhapur,
Hyderabad – 500081.
T: +91 40 40337000 Extn 70__
F: +91 40 40337070




www.keypoint-tech.com

Be Impressed
Try it for Yourself

www.adaptxt.com

ENGAGING CAPABILITY

www.adaptxt.com

Registered Address: 123/3RT, SR Nagar, Hyderabad-500038, India.
© KeyPoint Technologies UK. All rights reserved. This email plus any
attachments is strictly private and confidential. Disclosure, copying, or
use,
fully or partially is not permitted. Precautions against known computer
viruses are attempted. We accept no responsibility / liability for damage or

consequences caused by viruses or from unauthorised / unagreed changes. If
received mistakenly, inform sender and destroy this email entirely.




On Tue, Sep 20, 2011 at 3:28 PM, saurabh agrawal wrote:

> Design an algorithm to perform operation on an array
> Add(i,y)-> add value y to i position
> sum(i) -> sum of first i numbers
> we can use additional array O(n) and worst case performance should be O(log
> n) for both operation
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[Jagannath Prasad Das]

@naren:a[i] may exceed array limit.sigsegv error amy result


On Sat, Aug 20, 2011 at 9:08 PM, Naren s  wrote:

>
>
> On Sat, Aug 20, 2011 at 9:07 PM, Naren s  wrote:
>
>> for(i=0 to n)
>> {
>> if(a[abs(a[i])-1]>0)
>> a[abs(a[i])-1] = -a[abs(a[i])-1];
>> else
>> printf("%d",abs(a[i]));
>>
>> }
>>
>> space : o(n)
>> time : o(1)
>>
>>
>>
>> On Fri, Aug 19, 2011 at 12:45 AM, *$*  wrote:
>>
>>> How to find duplicate element (only one element is repeated) from an
>>> array of unsorted positive integers..
>>> time complexity .. O(n)
>>> space .. o(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.
>>>
>>
>>
>>
>> --
>> *Narayanan S,*
>> B.E., C.S.E., (final year),
>> College Of Engineering Guindy,
>> Anna University,
>> Chennai-25.
>>
>>
>
>
> --
> *Narayanan S,*
> B.E., C.S.E., (final year),
> College Of Engineering Guindy,
> Anna University,
> Chennai-25.
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[Naren s]

On Sat, Aug 20, 2011 at 9:07 PM, Naren s  wrote:

> for(i=0 to n)
> {
> if(a[abs(a[i])-1]>0)
> a[abs(a[i])-1] = -a[abs(a[i])-1];
> else
> printf("%d",abs(a[i]));
> }
>
> space : o(n)
> time : o(1)
>
>
>
> On Fri, Aug 19, 2011 at 12:45 AM, *$*  wrote:
>
>> How to find duplicate element (only one element is repeated) from an array
>> of unsorted positive integers..
>> time complexity .. O(n)
>> space .. o(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.
>>
>
>
>
> --
> *Narayanan S,*
> B.E., C.S.E., (final year),
> College Of Engineering Guindy,
> Anna University,
> Chennai-25.
>
>


-- 
*Narayanan S,*
B.E., C.S.E., (final year),
College Of Engineering Guindy,
Anna University,
Chennai-25.

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

[Naren s]

for(i=0 to n)
{
if(a[abs(a[i])-1]>0)
a[abs(a[i])-1] = -a[abs(a[i])-1];
else
printf("%d",a[abs(a[i])]);
}

space : o(n)
time : o(1)


On Fri, Aug 19, 2011 at 12:45 AM, *$*  wrote:

> How to find duplicate element (only one element is repeated) from an array
> of unsorted positive integers..
> time complexity .. O(n)
> space .. o(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.
>



-- 
*Narayanan S,*
B.E., C.S.E., (final year),
College Of Engineering Guindy,
Anna University,
Chennai-25.

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

[hary rathor]

bitset is best . require only 32 time less then require in hash table .

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

[sagar pareek]

Common yaar its very simple
it is good for u to go in deep hence google it or refer a good data
structure book

On Thu, Aug 18, 2011 at 5:36 PM, Ankur Garg  wrote:

> Can u provide a bit detail bro !!
>
>
> On Thu, Aug 18, 2011 at 8:04 AM, sagar pareek wrote:
>
>> Hashing
>> :)
>>
>> On Thu, Aug 18, 2011 at 5:30 PM, Ankur Garg  wrote:
>>
>>> Define a data structure , using extra memory/space , such that :
>>>
>>> Insert(int a)
>>> Delete(int a)
>>> isPresent(int a)
>>> get(int a)
>>>
>>> All above operations on the defined data structure take O(1) , i.e.
>>> constant time.
>>>
>>>
>>> Any suggestions /solutions for this problem
>>>
>>>
>>> Regards
>>>
>>> Ankur
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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
>> SAGAR PAREEK
>> COMPUTER SCIENCE AND ENGINEERING
>> NIT ALLAHABAD
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT ALLAHABAD

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

[Anantha Krishnan]

Refer here .

On Thu, Aug 18, 2011 at 5:36 PM, Ankur Garg  wrote:

> Can u provide a bit detail bro !!
>
>
> On Thu, Aug 18, 2011 at 8:04 AM, sagar pareek wrote:
>
>> Hashing
>> :)
>>
>> On Thu, Aug 18, 2011 at 5:30 PM, Ankur Garg  wrote:
>>
>>> Define a data structure , using extra memory/space , such that :
>>>
>>> Insert(int a)
>>> Delete(int a)
>>> isPresent(int a)
>>> get(int a)
>>>
>>> All above operations on the defined data structure take O(1) , i.e.
>>> constant time.
>>>
>>>
>>> Any suggestions /solutions for this problem
>>>
>>>
>>> Regards
>>>
>>> Ankur
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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
>> SAGAR PAREEK
>> COMPUTER SCIENCE AND ENGINEERING
>> NIT ALLAHABAD
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] Amazon Question

[Anantha Krishnan]

We can use hash to do all the operations in O(1) time.

Thanks & Regards,
Anantha Krishnan

On Thu, Aug 18, 2011 at 5:30 PM, Ankur Garg  wrote:

> Define a data structure , using extra memory/space , such that :
>
> Insert(int a)
> Delete(int a)
> isPresent(int a)
> get(int a)
>
> All above operations on the defined data structure take O(1) , i.e.
> constant time.
>
>
> Any suggestions /solutions for this problem
>
>
> Regards
>
> Ankur
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[Ankur Garg]

Can u provide a bit detail bro !!

On Thu, Aug 18, 2011 at 8:04 AM, sagar pareek  wrote:

> Hashing
> :)
>
> On Thu, Aug 18, 2011 at 5:30 PM, Ankur Garg  wrote:
>
>> Define a data structure , using extra memory/space , such that :
>>
>> Insert(int a)
>> Delete(int a)
>> isPresent(int a)
>> get(int a)
>>
>> All above operations on the defined data structure take O(1) , i.e.
>> constant time.
>>
>>
>> Any suggestions /solutions for this problem
>>
>>
>> Regards
>>
>> Ankur
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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
> SAGAR PAREEK
> COMPUTER SCIENCE AND ENGINEERING
> NIT ALLAHABAD
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[sagar pareek]

Hashing
:)

On Thu, Aug 18, 2011 at 5:30 PM, Ankur Garg  wrote:

> Define a data structure , using extra memory/space , such that :
>
> Insert(int a)
> Delete(int a)
> isPresent(int a)
> get(int a)
>
> All above operations on the defined data structure take O(1) , i.e.
> constant time.
>
>
> Any suggestions /solutions for this problem
>
>
> Regards
>
> Ankur
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT ALLAHABAD

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

[Suganya Palaniappan]

@rajeev : Can u pls explain the second approach...??

On Mon, Aug 15, 2011 at 10:09 PM, sandeep pandey <
sandeep.masum4...@gmail.com> wrote:

> dyamic programming.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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,
Sug@ny@...

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

[sandeep pandey]

dyamic programming.

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

[rajeev bharshetty]

First approach :

 I think you can solve the above problem using Levenshtein Distance (edit
distance which is basically no of operations required to transform word1 to
word2) .
Algo can be found here http://en.wikipedia.org/wiki/Levenshtein_distance

Second approach :

 Store the words in trie data structure and then do a BFS on trie to achieve
the solution.

Hope this helps!!!
On Mon, Aug 15, 2011 at 10:08 PM, priya ramesh <
love.for.programm...@gmail.com> wrote:

> You are given a dictionary of all valid words. You have the following 3
> operations permitted on a word: delete a character, insert a character,
> replace a character. Now given two words - word1 and word2 - find the
> minimum number of steps required to convert word1 to word2. (one operation
> counts as 1 step.)
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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
Rajeev N B 

"*Winners Don't do Different things , they do things Differently"*

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

[programming love]

*Executing code with printf's for each iteration for better understanding.*


#include
main(){

int n, i, j, k, t1=0, t2=0, t3, a[30];
printf("Enter the number of elements\n");
scanf("%d", &n);
for(i=0; i=0;k--){

printf("iteration %d\n", t2);
for(j=k,i=0;(ihttp://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Amazon question.

[ankit sambyal]

1. Square each element of the array and then sort it---O(nlogn)
2. for(i=0;i<(size-3);i++)
{
j=i+1; k=size-1;
while(jhttp://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Amazon Question

[Raman]

Ok I got it..
for 2 processors
1->2 (2 steps) (On any processor)
3  4 (1 step) (parallel)
5 6 (1 step) (parallel)
7 8 (1 step) (parallel)  

total 5 steps

-- 
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/-/mM8V_cnNcXIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

[Raman]

@aditi: How did u do the 4th one??

-- 
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/-/rZ25FTEocVEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

[shady]

doesn't matter if the condition is == 0 or  != 0  answer will always be 3.

On Tue, Aug 9, 2011 at 12:04 AM, aditi garg wrote:

> well since i have told u i dont knw OS too well so i ws nt sure...bt if
> suppose the condition (p1==0) is false thn only  1 child will be created??
>
>
> On Mon, Aug 8, 2011 at 11:56 PM, ankit sambyal wrote:
>
>> @aditi : the ans is 3. Why do u think there is no definite 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.
>>
>
>
>
> --
> Aditi Garg
> Undergraduate Student
> Electronics & Communication Divison
> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
> Sector 3, Dwarka
> New Delhi
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[aditi garg]

@sagar: Thanx a lot

On Tue, Aug 9, 2011 at 12:15 AM, sagar pareek  wrote:

> *
> void main() {
>
> int p1= fork();
>
> if (p1 == 0) {
>
>  int p2 = fork();
>
>  if (p2 != 0) {
>
>   fork();
>
>  }
>
> }
>
> }
>
> for confirmation just make a diagram
>
>
> M
>   /  \
>  /\
> M  C1 > fork() 1st
> M>0   and  C1==0
>   /  \
> / \
>   /\
>  C1C2   --> fork()
> 2nd   C1>0   and  C2==0
> /  \
>C1   C3   ---> fork()
> 3rd
> *
>
>
> On Tue, Aug 9, 2011 at 12:04 AM, aditi garg wrote:
>
>> well since i have told u i dont knw OS too well so i ws nt sure...bt if
>> suppose the condition (p1==0) is false thn only  1 child will be created??
>>
>>
>> On Mon, Aug 8, 2011 at 11:56 PM, ankit sambyal wrote:
>>
>>> @aditi : the ans is 3. Why do u think there is no definite 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.
>>>
>>
>>
>>
>> --
>> Aditi Garg
>> Undergraduate Student
>> Electronics & Communication Divison
>> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
>> Sector 3, Dwarka
>> New Delhi
>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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
> SAGAR PAREEK
> COMPUTER SCIENCE AND ENGINEERING
> NIT ALLAHABAD
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Aditi Garg
Undergraduate Student
Electronics & Communication Divison
NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
Sector 3, Dwarka
New Delhi

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

[sagar pareek]

*
void main() {

int p1= fork();

if (p1 == 0) {

 int p2 = fork();

 if (p2 != 0) {

  fork();

 }

}

}

for confirmation just make a diagram


M
  /  \
 /\
M  C1 > fork() 1st
M>0   and  C1==0
  /  \
/ \
  /\
 C1C2   --> fork() 2nd
C1>0   and  C2==0
/  \
   C1   C3   ---> fork() 3rd
*

On Tue, Aug 9, 2011 at 12:04 AM, aditi garg wrote:

> well since i have told u i dont knw OS too well so i ws nt sure...bt if
> suppose the condition (p1==0) is false thn only  1 child will be created??
>
>
> On Mon, Aug 8, 2011 at 11:56 PM, ankit sambyal wrote:
>
>> @aditi : the ans is 3. Why do u think there is no definite 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.
>>
>
>
>
> --
> Aditi Garg
> Undergraduate Student
> Electronics & Communication Divison
> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
> Sector 3, Dwarka
> New Delhi
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT ALLAHABAD

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

[aditi garg]

well since i have told u i dont knw OS too well so i ws nt sure...bt if
suppose the condition (p1==0) is false thn only  1 child will be created??


On Mon, Aug 8, 2011 at 11:56 PM, ankit sambyal wrote:

> @aditi : the ans is 3. Why do u think there is no definite 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.
>



-- 
Aditi Garg
Undergraduate Student
Electronics & Communication Divison
NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
Sector 3, Dwarka
New Delhi

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

[ankit sambyal]

@aditi : the ans is 3. Why do u think there is no definite 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.

Re: [algogeeks] amazon question

[aditi garg]

I dnt think thr wud be a definite ans

On Mon, Aug 8, 2011 at 11:26 PM, siddharam suresh
wrote:

> is it 3 ?
> Thank you,
> Siddharam
>
>
>
> On Mon, Aug 8, 2011 at 11:24 PM, rajul jain wrote:
>
>> How many Children process following program produce
>> *
>> void main() {
>>
>> int p1= fork();
>>
>> if (p1 == 0) {
>>
>>  int p2 = fork();
>>
>>  if (p2 != 0) {
>>
>>   fork();
>>
>>  }
>>
>> }
>>
>> }
>>
>>
>> *
>> On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal <
>> kamakshi...@gmail.com> wrote:
>>
>>> what will be the o/p of the following program:
>>>
>>> main()
>>> {
>>> int ret;
>>> ret=fork();
>>> ret=fork();
>>> ret=fork();
>>> ret=fork();
>>>
>>> if(!ret)
>>> printf("one");
>>> else
>>> printf("two");
>>> }
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> --
>>> Regards,
>>> Kamakshi
>>> kamakshi...@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.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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.
>



-- 
Aditi Garg
Undergraduate Student
Electronics & Communication Divison
NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
Sector 3, Dwarka
New Delhi

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

[Kamakshii Aggarwal]

3?

On Mon, Aug 8, 2011 at 11:26 PM, siddharam suresh
wrote:

> is it 3 ?
> Thank you,
> Siddharam
>
>
>
> On Mon, Aug 8, 2011 at 11:24 PM, rajul jain wrote:
>
>> How many Children process following program produce
>> *
>> void main() {
>>
>> int p1= fork();
>>
>> if (p1 == 0) {
>>
>>  int p2 = fork();
>>
>>  if (p2 != 0) {
>>
>>   fork();
>>
>>  }
>>
>> }
>>
>> }
>>
>>
>> *
>> On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal <
>> kamakshi...@gmail.com> wrote:
>>
>>> what will be the o/p of the following program:
>>>
>>> main()
>>> {
>>> int ret;
>>> ret=fork();
>>> ret=fork();
>>> ret=fork();
>>> ret=fork();
>>>
>>> if(!ret)
>>> printf("one");
>>> else
>>> printf("two");
>>> }
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> --
>>> Regards,
>>> Kamakshi
>>> kamakshi...@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.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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,
Kamakshi
kamakshi...@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.

Re: [algogeeks] amazon question

[siddharam suresh]

is it 3 ?
Thank you,
Siddharam


On Mon, Aug 8, 2011 at 11:24 PM, rajul jain  wrote:

> How many Children process following program produce
> *
> void main() {
>
> int p1= fork();
>
> if (p1 == 0) {
>
>  int p2 = fork();
>
>  if (p2 != 0) {
>
>   fork();
>
>  }
>
> }
>
> }
>
>
> *
> On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal  > wrote:
>
>> what will be the o/p of the following program:
>>
>> main()
>> {
>> int ret;
>> ret=fork();
>> ret=fork();
>> ret=fork();
>> ret=fork();
>>
>> if(!ret)
>> printf("one");
>> else
>> printf("two");
>> }
>>
>>
>>
>>
>>
>>
>>
>>
>> --
>> Regards,
>> Kamakshi
>> kamakshi...@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.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[rajul jain]

How many Children process following program produce
*
void main() {

int p1= fork();

if (p1 == 0) {

 int p2 = fork();

 if (p2 != 0) {

  fork();

 }

}

}


*
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
wrote:

> what will be the o/p of the following program:
>
> main()
> {
> int ret;
> ret=fork();
> ret=fork();
> ret=fork();
> ret=fork();
>
> if(!ret)
> printf("one");
> else
> printf("two");
> }
>
>
>
>
>
>
>
>
> --
> Regards,
> Kamakshi
> kamakshi...@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.
>

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

[dilip makwana]

Yes answer to third is 1:1 ...

see this link for it http://www.mytechinterviews.com/boys-and-girls

On 8 August 2011 20:00, Gyanendra Kumar  wrote:

> i think for 3rd it shud be c.)1:1
>
>
> On Mon, Aug 8, 2011 at 7:56 PM, rajeev bharshetty wrote:
>
>> 4) b
>> 3) a
>>
>> Correct me if i am wrong
>>
>>
>> On Mon, Aug 8, 2011 at 7:54 PM, Dipankar Patro wrote:
>>
>>> 1. O(n)
>>>
>>> 2. (b)
>>>
>>>
>>>
>>> On 8 August 2011 19:24, ankit sambyal  wrote:
>>>
 Plz give the answers ...

 1. In a binary max heap containing n numbers, the smallest element can
 be found in time ??


 2. The number of total nodes in a complete balanced binary tree with n
 levels is,
   a)3^n + 1
   b)2^(n+1) - 1
   c) 2^n + 1
   d) none of above

 3. In a country where everyone wants a boy, each family continues
 having babies till they have a boy. After some time, what is the proportion
 of boys to girls in the country? (Assuming probability of having a boy or a
 girl is the same)
   a) 1:2
   b) 2:1
   c)1:1
   d)1:4


 4. A parallel program consists of 8 tasks – T1 through T8. Each task
 requires one time step to be executed on a single processor. Let X -> Y
 denote the fact that task X must be executed before task Y is executed.
 Suppose only the tasks X, Y are to be executed. On any multiprocessor
 machine it would require at least 2 time steps since in the first step X
 could be executed, and Y could be executed in the next time step (since it
 requires X to complete first). Now, suppose the following dependencies 
 exist
 between the tasks T1 – T8:

 T1 -> T2

 T2 -> T3

 T3 -> T6

 T2 -> T4

 T4 -> T7

 T2 -> T5

 T5 -> T8

 What is the minimum number of time steps required to execute these 8
 tasks on a 2 processor machine and a 4 processor machine?


 a)4 & 2

 b)5 & 2

 c)5 & 4

 d)6 & 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.

>>>
>>>
>>>
>>> --
>>>
>>> ___
>>>
>>> Please do not print this e-mail until urgent requirement. Go Green!!
>>> Save Papers <=> Save Trees
>>>
>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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
>> Rajeev N B 
>>
>> "*Winners Don't do Different things , they do things Differently"*
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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.
>



-- 
*Dilip Makwana*
VJTI
BTech Computers Engineering
2009-2013

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

[aditi garg]

2.b
3.c
4.c

On Mon, Aug 8, 2011 at 8:12 PM, sagar pareek  wrote:

> 1. O(n)
> 2. b
> 4  c
>
> On Mon, Aug 8, 2011 at 8:08 PM, programming love <
> love.for.programm...@gmail.com> wrote:
>
>> 1. O(n)
>> 2.b
>> 4.c
>>
>>
>> On Mon, Aug 8, 2011 at 7:24 PM, ankit sambyal wrote:
>>
>>> Plz give the answers ...
>>>
>>> 1. In a binary max heap containing n numbers, the smallest element can
>>> be found in time ??
>>>
>>>
>>> 2. The number of total nodes in a complete balanced binary tree with n
>>> levels is,
>>>   a)3^n + 1
>>>   b)2^(n+1) - 1
>>>   c) 2^n + 1
>>>   d) none of above
>>>
>>> 3. In a country where everyone wants a boy, each family continues having
>>> babies till they have a boy. After some time, what is the proportion of boys
>>> to girls in the country? (Assuming probability of having a boy or a girl is
>>> the same)
>>>   a) 1:2
>>>   b) 2:1
>>>   c)1:1
>>>   d)1:4
>>>
>>>
>>> 4. A parallel program consists of 8 tasks – T1 through T8. Each task
>>> requires one time step to be executed on a single processor. Let X -> Y
>>> denote the fact that task X must be executed before task Y is executed.
>>> Suppose only the tasks X, Y are to be executed. On any multiprocessor
>>> machine it would require at least 2 time steps since in the first step X
>>> could be executed, and Y could be executed in the next time step (since it
>>> requires X to complete first). Now, suppose the following dependencies exist
>>> between the tasks T1 – T8:
>>>
>>> T1 -> T2
>>>
>>> T2 -> T3
>>>
>>> T3 -> T6
>>>
>>> T2 -> T4
>>>
>>> T4 -> T7
>>>
>>> T2 -> T5
>>>
>>> T5 -> T8
>>>
>>> What is the minimum number of time steps required to execute these 8
>>> tasks on a 2 processor machine and a 4 processor machine?
>>>
>>>
>>> a)4 & 2
>>>
>>> b)5 & 2
>>>
>>> c)5 & 4
>>>
>>> d)6 & 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.
>>
>
>
>
> --
> **Regards
> SAGAR PAREEK
> COMPUTER SCIENCE AND ENGINEERING
> NIT ALLAHABAD
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Aditi Garg
Undergraduate Student
Electronics & Communication Divison
NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
Sector 3, Dwarka
New Delhi

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

[Brijesh Upadhyay]

Yeah.. 3rd answer is 1:1 , for reference 
http://discuss.fogcreek.com/techInterview/default.asp?cmd=show&ixPost=150

-- 
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/-/jd2b6mmXq0IJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

[Pradeep Mishra]

i think for 3rd answer should be 1:1 correct me if m wrong.

On Mon, Aug 8, 2011 at 7:42 AM, sagar pareek  wrote:

> 1. O(n)
> 2. b
> 4  c
>
> On Mon, Aug 8, 2011 at 8:08 PM, programming love <
> love.for.programm...@gmail.com> wrote:
>
>> 1. O(n)
>> 2.b
>> 4.c
>>
>>
>> On Mon, Aug 8, 2011 at 7:24 PM, ankit sambyal wrote:
>>
>>> Plz give the answers ...
>>>
>>> 1. In a binary max heap containing n numbers, the smallest element can
>>> be found in time ??
>>>
>>>
>>> 2. The number of total nodes in a complete balanced binary tree with n
>>> levels is,
>>>   a)3^n + 1
>>>   b)2^(n+1) - 1
>>>   c) 2^n + 1
>>>   d) none of above
>>>
>>> 3. In a country where everyone wants a boy, each family continues having
>>> babies till they have a boy. After some time, what is the proportion of boys
>>> to girls in the country? (Assuming probability of having a boy or a girl is
>>> the same)
>>>   a) 1:2
>>>   b) 2:1
>>>   c)1:1
>>>   d)1:4
>>>
>>>
>>> 4. A parallel program consists of 8 tasks – T1 through T8. Each task
>>> requires one time step to be executed on a single processor. Let X -> Y
>>> denote the fact that task X must be executed before task Y is executed.
>>> Suppose only the tasks X, Y are to be executed. On any multiprocessor
>>> machine it would require at least 2 time steps since in the first step X
>>> could be executed, and Y could be executed in the next time step (since it
>>> requires X to complete first). Now, suppose the following dependencies exist
>>> between the tasks T1 – T8:
>>>
>>> T1 -> T2
>>>
>>> T2 -> T3
>>>
>>> T3 -> T6
>>>
>>> T2 -> T4
>>>
>>> T4 -> T7
>>>
>>> T2 -> T5
>>>
>>> T5 -> T8
>>>
>>> What is the minimum number of time steps required to execute these 8
>>> tasks on a 2 processor machine and a 4 processor machine?
>>>
>>>
>>> a)4 & 2
>>>
>>> b)5 & 2
>>>
>>> c)5 & 4
>>>
>>> d)6 & 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.
>>
>
>
>
> --
> **Regards
> SAGAR PAREEK
> COMPUTER SCIENCE AND ENGINEERING
> NIT ALLAHABAD
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Pradeep Kumar Mishra
IIIT Allahabad
B. Tech 2nd Year ( IT )
prad...@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.

Re: [algogeeks] Amazon Question

[sagar pareek]

1. O(n)
2. b
4  c

On Mon, Aug 8, 2011 at 8:08 PM, programming love <
love.for.programm...@gmail.com> wrote:

> 1. O(n)
> 2.b
> 4.c
>
>
> On Mon, Aug 8, 2011 at 7:24 PM, ankit sambyal wrote:
>
>> Plz give the answers ...
>>
>> 1. In a binary max heap containing n numbers, the smallest element can be
>> found in time ??
>>
>>
>> 2. The number of total nodes in a complete balanced binary tree with n
>> levels is,
>>   a)3^n + 1
>>   b)2^(n+1) - 1
>>   c) 2^n + 1
>>   d) none of above
>>
>> 3. In a country where everyone wants a boy, each family continues having
>> babies till they have a boy. After some time, what is the proportion of boys
>> to girls in the country? (Assuming probability of having a boy or a girl is
>> the same)
>>   a) 1:2
>>   b) 2:1
>>   c)1:1
>>   d)1:4
>>
>>
>> 4. A parallel program consists of 8 tasks – T1 through T8. Each task
>> requires one time step to be executed on a single processor. Let X -> Y
>> denote the fact that task X must be executed before task Y is executed.
>> Suppose only the tasks X, Y are to be executed. On any multiprocessor
>> machine it would require at least 2 time steps since in the first step X
>> could be executed, and Y could be executed in the next time step (since it
>> requires X to complete first). Now, suppose the following dependencies exist
>> between the tasks T1 – T8:
>>
>> T1 -> T2
>>
>> T2 -> T3
>>
>> T3 -> T6
>>
>> T2 -> T4
>>
>> T4 -> T7
>>
>> T2 -> T5
>>
>> T5 -> T8
>>
>> What is the minimum number of time steps required to execute these 8 tasks
>> on a 2 processor machine and a 4 processor machine?
>>
>>
>> a)4 & 2
>>
>> b)5 & 2
>>
>> c)5 & 4
>>
>> d)6 & 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.
>



-- 
**Regards
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT ALLAHABAD

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

[programming love]

1. O(n)
2.b
4.c

On Mon, Aug 8, 2011 at 7:24 PM, ankit sambyal wrote:

> Plz give the answers ...
>
> 1. In a binary max heap containing n numbers, the smallest element can be
> found in time ??
>
>
> 2. The number of total nodes in a complete balanced binary tree with n
> levels is,
>   a)3^n + 1
>   b)2^(n+1) - 1
>   c) 2^n + 1
>   d) none of above
>
> 3. In a country where everyone wants a boy, each family continues having
> babies till they have a boy. After some time, what is the proportion of boys
> to girls in the country? (Assuming probability of having a boy or a girl is
> the same)
>   a) 1:2
>   b) 2:1
>   c)1:1
>   d)1:4
>
>
> 4. A parallel program consists of 8 tasks – T1 through T8. Each task
> requires one time step to be executed on a single processor. Let X -> Y
> denote the fact that task X must be executed before task Y is executed.
> Suppose only the tasks X, Y are to be executed. On any multiprocessor
> machine it would require at least 2 time steps since in the first step X
> could be executed, and Y could be executed in the next time step (since it
> requires X to complete first). Now, suppose the following dependencies exist
> between the tasks T1 – T8:
>
> T1 -> T2
>
> T2 -> T3
>
> T3 -> T6
>
> T2 -> T4
>
> T4 -> T7
>
> T2 -> T5
>
> T5 -> T8
>
> What is the minimum number of time steps required to execute these 8 tasks
> on a 2 processor machine and a 4 processor machine?
>
>
> a)4 & 2
>
> b)5 & 2
>
> c)5 & 4
>
> d)6 & 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

[Gyanendra Kumar]

i think for 3rd it shud be c.)1:1

On Mon, Aug 8, 2011 at 7:56 PM, rajeev bharshetty wrote:

> 4) b
> 3) a
>
> Correct me if i am wrong
>
>
> On Mon, Aug 8, 2011 at 7:54 PM, Dipankar Patro wrote:
>
>> 1. O(n)
>>
>> 2. (b)
>>
>>
>>
>> On 8 August 2011 19:24, ankit sambyal  wrote:
>>
>>> Plz give the answers ...
>>>
>>> 1. In a binary max heap containing n numbers, the smallest element can
>>> be found in time ??
>>>
>>>
>>> 2. The number of total nodes in a complete balanced binary tree with n
>>> levels is,
>>>   a)3^n + 1
>>>   b)2^(n+1) - 1
>>>   c) 2^n + 1
>>>   d) none of above
>>>
>>> 3. In a country where everyone wants a boy, each family continues having
>>> babies till they have a boy. After some time, what is the proportion of boys
>>> to girls in the country? (Assuming probability of having a boy or a girl is
>>> the same)
>>>   a) 1:2
>>>   b) 2:1
>>>   c)1:1
>>>   d)1:4
>>>
>>>
>>> 4. A parallel program consists of 8 tasks – T1 through T8. Each task
>>> requires one time step to be executed on a single processor. Let X -> Y
>>> denote the fact that task X must be executed before task Y is executed.
>>> Suppose only the tasks X, Y are to be executed. On any multiprocessor
>>> machine it would require at least 2 time steps since in the first step X
>>> could be executed, and Y could be executed in the next time step (since it
>>> requires X to complete first). Now, suppose the following dependencies exist
>>> between the tasks T1 – T8:
>>>
>>> T1 -> T2
>>>
>>> T2 -> T3
>>>
>>> T3 -> T6
>>>
>>> T2 -> T4
>>>
>>> T4 -> T7
>>>
>>> T2 -> T5
>>>
>>> T5 -> T8
>>>
>>> What is the minimum number of time steps required to execute these 8
>>> tasks on a 2 processor machine and a 4 processor machine?
>>>
>>>
>>> a)4 & 2
>>>
>>> b)5 & 2
>>>
>>> c)5 & 4
>>>
>>> d)6 & 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.
>>>
>>
>>
>>
>> --
>>
>> ___
>>
>> Please do not print this e-mail until urgent requirement. Go Green!!
>> Save Papers <=> Save Trees
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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
> Rajeev N B 
>
> "*Winners Don't do Different things , they do things Differently"*
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[rajeev bharshetty]

4) b
3) a

Correct me if i am wrong

On Mon, Aug 8, 2011 at 7:54 PM, Dipankar Patro  wrote:

> 1. O(n)
>
> 2. (b)
>
>
>
> On 8 August 2011 19:24, ankit sambyal  wrote:
>
>> Plz give the answers ...
>>
>> 1. In a binary max heap containing n numbers, the smallest element can be
>> found in time ??
>>
>>
>> 2. The number of total nodes in a complete balanced binary tree with n
>> levels is,
>>   a)3^n + 1
>>   b)2^(n+1) - 1
>>   c) 2^n + 1
>>   d) none of above
>>
>> 3. In a country where everyone wants a boy, each family continues having
>> babies till they have a boy. After some time, what is the proportion of boys
>> to girls in the country? (Assuming probability of having a boy or a girl is
>> the same)
>>   a) 1:2
>>   b) 2:1
>>   c)1:1
>>   d)1:4
>>
>>
>> 4. A parallel program consists of 8 tasks – T1 through T8. Each task
>> requires one time step to be executed on a single processor. Let X -> Y
>> denote the fact that task X must be executed before task Y is executed.
>> Suppose only the tasks X, Y are to be executed. On any multiprocessor
>> machine it would require at least 2 time steps since in the first step X
>> could be executed, and Y could be executed in the next time step (since it
>> requires X to complete first). Now, suppose the following dependencies exist
>> between the tasks T1 – T8:
>>
>> T1 -> T2
>>
>> T2 -> T3
>>
>> T3 -> T6
>>
>> T2 -> T4
>>
>> T4 -> T7
>>
>> T2 -> T5
>>
>> T5 -> T8
>>
>> What is the minimum number of time steps required to execute these 8 tasks
>> on a 2 processor machine and a 4 processor machine?
>>
>>
>> a)4 & 2
>>
>> b)5 & 2
>>
>> c)5 & 4
>>
>> d)6 & 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.
>>
>
>
>
> --
>
> ___
>
> Please do not print this e-mail until urgent requirement. Go Green!!
> Save Papers <=> Save Trees
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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
Rajeev N B 

"*Winners Don't do Different things , they do things Differently"*

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

[Dipankar Patro]

1. O(n)

2. (b)


On 8 August 2011 19:24, ankit sambyal  wrote:

> Plz give the answers ...
>
> 1. In a binary max heap containing n numbers, the smallest element can be
> found in time ??
>
>
> 2. The number of total nodes in a complete balanced binary tree with n
> levels is,
>   a)3^n + 1
>   b)2^(n+1) - 1
>   c) 2^n + 1
>   d) none of above
>
> 3. In a country where everyone wants a boy, each family continues having
> babies till they have a boy. After some time, what is the proportion of boys
> to girls in the country? (Assuming probability of having a boy or a girl is
> the same)
>   a) 1:2
>   b) 2:1
>   c)1:1
>   d)1:4
>
>
> 4. A parallel program consists of 8 tasks – T1 through T8. Each task
> requires one time step to be executed on a single processor. Let X -> Y
> denote the fact that task X must be executed before task Y is executed.
> Suppose only the tasks X, Y are to be executed. On any multiprocessor
> machine it would require at least 2 time steps since in the first step X
> could be executed, and Y could be executed in the next time step (since it
> requires X to complete first). Now, suppose the following dependencies exist
> between the tasks T1 – T8:
>
> T1 -> T2
>
> T2 -> T3
>
> T3 -> T6
>
> T2 -> T4
>
> T4 -> T7
>
> T2 -> T5
>
> T5 -> T8
>
> What is the minimum number of time steps required to execute these 8 tasks
> on a 2 processor machine and a 4 processor machine?
>
>
> a)4 & 2
>
> b)5 & 2
>
> c)5 & 4
>
> d)6 & 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.
>



-- 
___

Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers <=> Save Trees

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

[Shachindra A C]

8 one's and 8 two's. The order in which they get printed might vary.

On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
wrote:

> what will be the o/p of the following program:
>
> main()
> {
> int ret;
> ret=fork();
> ret=fork();
> ret=fork();
> ret=fork();
>
> if(!ret)
> printf("one");
> else
> printf("two");
> }
>
>
>
>
>
>
>
>
> --
> Regards,
> Kamakshi
> kamakshi...@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.
>



-- 
Regards,
Shachindra A 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] Amazon Question

[Arun Vishwanathan]

hmm the problem is we need O(1) spacehaving that count wont make it
O(1).

i had an approach in mind of O(n) time and O(1) space..problem is i havent
tested/debugged the code but it is O(1) space i guess and O(n) time.


if total number of zeros(M) and 1s(N) are same print the whole array
else

the logic i used is something like this...
1)traverse the array from 0 to n
2)2 pointers , one pointing to the first 0 and other pointing to the first 1
in the array
3)i and j are 2 variables to keep count of 0 and 1 that we have seen so far
as we keep traversing
4) 2 more varibales are used to maintain count of left over 0s and 1s from
our current position( we know the total number of zeros and ones in O(n))
5)if at any point i is equal to j and either left over 0s or 1s is 0 then
print array from lesser of pointer index(lesser means one of the pointers is
behind the other) till current index we are looking at
the prtining from lesser pointer index till current index is if only none of
the pointers have been changed in the process in between

6) in case i or j becomes greater than N or M repsectively

i do some steps with pointer updation...i am just posting the codemaybe
u can check and see if it is logically ok..it hasnt been tested

M is number of zerso in array
N is number of ones in array
ptri=pointer to array
ptrj=pointer to array
 i and j hold count of 0 and 1 respectively as i move along array

M is number of zeros N is number of ones in the array ..u can find this in
O(n)..if they are equal print whole array

else


chnagei=0;
changej=0;
ptri=null
ptrj=null;
done0=0;
done1=0;
savestart=null
saveend=Null;


for(int index=0;indexN)
   {
   ptri=ptri+(N-i)
changei=1;
i=i-(N-i);
   if(j!=0 && i>N-j)
{
j=0;
  N--;

  }
}


  if(j>M)
  {
  ptrj=ptrj+(M-j);
changej=1;
j=j-(M-j);
   if(i!=0 && j>M-i)
 {
   i=0;
   M--;

 }
  }




}

print from save start to save end..that is answer

On Fri, Aug 5, 2011 at 1:09 PM, surender sanke  wrote:

> Hi,
>
> for 1 do +1
> for 0 do -1
> maintain count at every index of array
> eg:  100110
> array   X 1 0  0  0  0  0  0  1  1  0
> count   0 1 0 -1 -2 -3 -4 -5 -4 -3 -4
> index  -1 0 1  2  3  4  5  6  7  8  9
>
> find count with same value having max index difference.
> -3 is count at index 4 and 8
> max difference is 8-4 = 4
> -4 is count at index 5 and 9
> max difference is 9-5 = 4
> to reduce traverse time after count calculation
> take a map>;
> i - first index of array having same count,
> j - last index of array having same count
> as and when u encounter count create map value with i
> else if already exist update j, and update max with MAX(j-i,max)
>
> Surender
>
>   On Fri, Aug 5, 2011 at 2:25 PM, Arun Vishwanathan <
> aaron.nar...@gmail.com> wrote:
>
>>
>> by the way doesnt it look like an O(n^2) algo?
>>
>> On Fri, Aug 5, 2011 at 10:53 AM, Arun Vishwanathan <
>> aaron.nar...@gmail.com> wrote:
>>
>>>
>>> would u mind giving a short explanation of yr code too if possible?
>>>
>>>
>>> On Thu, Aug 4, 2011 at 5:38 PM, Apoorve Mohan wrote:
>>>
 I think this should worktell me if this works...

 void longest_0_1_substring(char *str)
 {
 int size=0,count=0,max=0,pos=0,prev=0,prev_pos=0,ptr=0,i=0,j=0;

 while(*str++)
 size++;
 str -= (size + 1);

 while(i>>> {
 for(j=i;(j < size) && (str[j]==str[j+1]);++j)
 count++;
 count++;
 if(ptr > 1)
 {
 if(count >= prev)
 {
 if(prev > max)
 {
 max = prev;
 pos = prev_pos;
 }
 }
 else
 {
 if(count > max)
 {
 max = count;
 pos = i - prev;
 }
 }
 }
 prev = count;
 prev_pos = i;
 i += count;
 ++ptr;
 count = 0;
 }

 printf("substring starts at position %d and is of size %d
 .",pos,max);



 }

 On Thu, Aug 4, 2011 at 6:25 PM, himanshu kansal <
 himanshukansal...@gmail.com> wrote:

> okie...can someone do it in O(n) space...bt time shld be linear
> only
>
>
> On Thu, Aug 4, 2011 at 2:13 AM, Prakash D wrote:
>
>> O(1) space is t hard  for this task
>>
>>
>> On Thu, Aug 4, 2011 at 12:55 AM, payel roy wrote:
>>
>>> Is there any solution for the above?
>>>
>>>
>>> On 3 August 2011 21:09, coder coder wrote:
>>>
 ya amazon will be visiting our campus within few days

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

Re: [algogeeks] Amazon Question

[surender sanke]

Hi,

for 1 do +1
for 0 do -1
maintain count at every index of array
eg:  100110
array   X 1 0  0  0  0  0  0  1  1  0
count   0 1 0 -1 -2 -3 -4 -5 -4 -3 -4
index  -1 0 1  2  3  4  5  6  7  8  9

find count with same value having max index difference.
-3 is count at index 4 and 8
max difference is 8-4 = 4
-4 is count at index 5 and 9
max difference is 9-5 = 4
to reduce traverse time after count calculation
take a map>;
i - first index of array having same count,
j - last index of array having same count
as and when u encounter count create map value with i
else if already exist update j, and update max with MAX(j-i,max)

Surender

On Fri, Aug 5, 2011 at 2:25 PM, Arun Vishwanathan wrote:

>
> by the way doesnt it look like an O(n^2) algo?
>
> On Fri, Aug 5, 2011 at 10:53 AM, Arun Vishwanathan  > wrote:
>
>>
>> would u mind giving a short explanation of yr code too if possible?
>>
>>
>> On Thu, Aug 4, 2011 at 5:38 PM, Apoorve Mohan wrote:
>>
>>> I think this should worktell me if this works...
>>>
>>> void longest_0_1_substring(char *str)
>>> {
>>> int size=0,count=0,max=0,pos=0,prev=0,prev_pos=0,ptr=0,i=0,j=0;
>>>
>>> while(*str++)
>>> size++;
>>> str -= (size + 1);
>>>
>>> while(i>> {
>>> for(j=i;(j < size) && (str[j]==str[j+1]);++j)
>>> count++;
>>> count++;
>>> if(ptr > 1)
>>> {
>>> if(count >= prev)
>>> {
>>> if(prev > max)
>>> {
>>> max = prev;
>>> pos = prev_pos;
>>> }
>>> }
>>> else
>>> {
>>> if(count > max)
>>> {
>>> max = count;
>>> pos = i - prev;
>>> }
>>> }
>>> }
>>> prev = count;
>>> prev_pos = i;
>>> i += count;
>>> ++ptr;
>>> count = 0;
>>> }
>>>
>>> printf("substring starts at position %d and is of size %d
>>> .",pos,max);
>>>
>>>
>>>
>>> }
>>>
>>> On Thu, Aug 4, 2011 at 6:25 PM, himanshu kansal <
>>> himanshukansal...@gmail.com> wrote:
>>>
 okie...can someone do it in O(n) space...bt time shld be linear only



 On Thu, Aug 4, 2011 at 2:13 AM, Prakash D  wrote:

> O(1) space is t hard  for this task
>
>
> On Thu, Aug 4, 2011 at 12:55 AM, payel roy wrote:
>
>> Is there any solution for the above?
>>
>>
>> On 3 August 2011 21:09, coder coder wrote:
>>
>>> ya amazon will be visiting our campus within few days
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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.
>



 --

   Regards
 Himanshu Kansal
   Msc Comp. sc.
 (University of Delhi)


 --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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
>>>
>>> Apoorve Mohan
>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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 thi

Re: [algogeeks] Amazon Question

[Arun Vishwanathan]

by the way doesnt it look like an O(n^2) algo?
On Fri, Aug 5, 2011 at 10:53 AM, Arun Vishwanathan
wrote:

>
> would u mind giving a short explanation of yr code too if possible?
>
>
> On Thu, Aug 4, 2011 at 5:38 PM, Apoorve Mohan wrote:
>
>> I think this should worktell me if this works...
>>
>> void longest_0_1_substring(char *str)
>> {
>> int size=0,count=0,max=0,pos=0,prev=0,prev_pos=0,ptr=0,i=0,j=0;
>>
>> while(*str++)
>> size++;
>> str -= (size + 1);
>>
>> while(i> {
>> for(j=i;(j < size) && (str[j]==str[j+1]);++j)
>> count++;
>> count++;
>> if(ptr > 1)
>> {
>> if(count >= prev)
>> {
>> if(prev > max)
>> {
>> max = prev;
>> pos = prev_pos;
>> }
>> }
>> else
>> {
>> if(count > max)
>> {
>> max = count;
>> pos = i - prev;
>> }
>> }
>> }
>> prev = count;
>> prev_pos = i;
>> i += count;
>> ++ptr;
>> count = 0;
>> }
>>
>> printf("substring starts at position %d and is of size %d .",pos,max);
>>
>>
>>
>>
>> }
>>
>> On Thu, Aug 4, 2011 at 6:25 PM, himanshu kansal <
>> himanshukansal...@gmail.com> wrote:
>>
>>> okie...can someone do it in O(n) space...bt time shld be linear only
>>>
>>>
>>> On Thu, Aug 4, 2011 at 2:13 AM, Prakash D  wrote:
>>>
 O(1) space is t hard  for this task


 On Thu, Aug 4, 2011 at 12:55 AM, payel roy wrote:

> Is there any solution for the above?
>
>
> On 3 August 2011 21:09, coder coder wrote:
>
>> ya amazon will be visiting our campus within few days
>>
>> --
>> You received this message because you are subscribed to the Google
>> Groups "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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.

>>>
>>>
>>>
>>> --
>>>
>>>   Regards
>>> Himanshu Kansal
>>>   Msc Comp. sc.
>>> (University of Delhi)
>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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
>>
>> Apoorve Mohan
>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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

[Arun Vishwanathan]

would u mind giving a short explanation of yr code too if possible?


On Thu, Aug 4, 2011 at 5:38 PM, Apoorve Mohan wrote:

> I think this should worktell me if this works...
>
> void longest_0_1_substring(char *str)
> {
> int size=0,count=0,max=0,pos=0,prev=0,prev_pos=0,ptr=0,i=0,j=0;
>
> while(*str++)
> size++;
> str -= (size + 1);
>
> while(i {
> for(j=i;(j < size) && (str[j]==str[j+1]);++j)
> count++;
> count++;
> if(ptr > 1)
> {
> if(count >= prev)
> {
> if(prev > max)
> {
> max = prev;
> pos = prev_pos;
> }
> }
> else
> {
> if(count > max)
> {
> max = count;
> pos = i - prev;
> }
> }
> }
> prev = count;
> prev_pos = i;
> i += count;
> ++ptr;
> count = 0;
> }
>
> printf("substring starts at position %d and is of size %d .",pos,max);
>
>
>
> }
>
> On Thu, Aug 4, 2011 at 6:25 PM, himanshu kansal <
> himanshukansal...@gmail.com> wrote:
>
>> okie...can someone do it in O(n) space...bt time shld be linear only
>>
>>
>> On Thu, Aug 4, 2011 at 2:13 AM, Prakash D  wrote:
>>
>>> O(1) space is t hard  for this task
>>>
>>>
>>> On Thu, Aug 4, 2011 at 12:55 AM, payel roy  wrote:
>>>
 Is there any solution for the above?


 On 3 August 2011 21:09, coder coder wrote:

> ya amazon will be visiting our campus within few days
>
> --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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.
>>>
>>
>>
>>
>> --
>>
>>   Regards
>> Himanshu Kansal
>>   Msc Comp. sc.
>> (University of Delhi)
>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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
>
> Apoorve Mohan
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[Apoorve Mohan]

I think this should worktell me if this works...

void longest_0_1_substring(char *str)
{
int size=0,count=0,max=0,pos=0,prev=0,prev_pos=0,ptr=0,i=0,j=0;

while(*str++)
size++;
str -= (size + 1);

while(i 1)
{
if(count >= prev)
{
if(prev > max)
{
max = prev;
pos = prev_pos;
}
}
else
{
if(count > max)
{
max = count;
pos = i - prev;
}
}
}
prev = count;
prev_pos = i;
i += count;
++ptr;
count = 0;
}

printf("substring starts at position %d and is of size %d .",pos,max);


}

On Thu, Aug 4, 2011 at 6:25 PM, himanshu kansal  wrote:

> okie...can someone do it in O(n) space...bt time shld be linear only
>
>
> On Thu, Aug 4, 2011 at 2:13 AM, Prakash D  wrote:
>
>> O(1) space is t hard  for this task
>>
>>
>> On Thu, Aug 4, 2011 at 12:55 AM, payel roy  wrote:
>>
>>> Is there any solution for the above?
>>>
>>>
>>> On 3 August 2011 21:09, coder coder  wrote:
>>>
 ya amazon will be visiting our campus within few days

  --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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.
>>
>
>
>
> --
>
>   Regards
> Himanshu Kansal
>   Msc Comp. sc.
> (University of Delhi)
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

Apoorve Mohan

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

[himanshu kansal]

okie...can someone do it in O(n) space...bt time shld be linear only

On Thu, Aug 4, 2011 at 2:13 AM, Prakash D  wrote:

> O(1) space is t hard  for this task
>
>
> On Thu, Aug 4, 2011 at 12:55 AM, payel roy  wrote:
>
>> Is there any solution for the above?
>>
>>
>> On 3 August 2011 21:09, coder coder  wrote:
>>
>>> ya amazon will be visiting our campus within few days
>>>
>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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.
>



-- 

  Regards
Himanshu Kansal
  Msc Comp. sc.
(University of Delhi)

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

[Prakash D]

O(1) space is t hard  for this task

On Thu, Aug 4, 2011 at 12:55 AM, payel roy  wrote:

> Is there any solution for the above?
>
>
> On 3 August 2011 21:09, coder coder  wrote:
>
>> ya amazon will be visiting our campus within few days
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] Amazon Question

[payel roy]

Is there any solution for the above?

On 3 August 2011 21:09, coder coder  wrote:

> ya amazon will be visiting our campus within few days
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[coder coder]

ya amazon will be visiting our campus within few days

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

[Kunal Patil]

Sort both the lists...
(Keep track of their original indices as we need to return to original list)

Modify the merge process of merge_sort:

// Assume size of list1 is m and that of list2 is n

curr_list1=0;curr_list2=0;curr_output=0;

while( curr_list1 < m && curr_list2 < n )
{
  If (list1[curr_list1] == list2[curr_list2] )
  {
 int temp = list1[curr_list1];
 output[curr_output++] = temp;

 //These while loops to ignore duplicates
 while( curr_list1 < m && list1[curr_list1] == temp )
 curr_list1++;

 while( curr_list2 < n && list2[curr_list2] == temp )
 curr_list2++;
  }

 else if( list1[curr_list1] < list2[curr_list2] )
  {
  curr_list1++;
  }

 else
  {
  curr_list2++;
  }
}

//Now output contains intersection of both the lists.
//Revert back to original lists.

TC: O(mlogm) + O(nlogn) + O(min (m,n) ) + O(m) + O(n)  = O(mlogm + nlogn)
SC: O(m+n) (To maintain associative array / copy of original lists) +
   O(min (m,n)) (To create output list) = O( m+n )

Correct me if I am wrong anywhere in the analysis.


On Wed, Aug 3, 2011 at 4:31 PM, ankit sambyal wrote:

> Given two lists write a function which returns a list which is the
> intersection of the two lists.the original lists should remain same.
> (Intersection - if first list is say,1,20 3,45 and second list is 3,24
> ,45,90,68 then intersection should be 3,45 )
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[Nitin Nizhawan]

EDIT:
why not first sort the lists first?  (we can create copy if we do not want
to modify original list) it will give O(nLogn) solution

-Nitin
On Wed, Aug 3, 2011 at 4:59 PM, Nitin Nizhawan wrote:

> why not first sort the lists first?  (we could if we do not want to modify
> original list) it will give O(nLogn) solution
>
> -Nitin
>
> On Wed, Aug 3, 2011 at 4:44 PM, veera reddy wrote:
>
>> sry... misunderstood the question
>>
>>
>> On Wed, Aug 3, 2011 at 4:43 PM, veera reddy wrote:
>>
>>> there is o(m+n) solution .
>>> http://geeksforgeeks.org/?p=2405 in this link see method no 4
>>>
>>>
>>> On Wed, Aug 3, 2011 at 4:41 PM, ankit sambyal wrote:
>>>
 ya, I also can't think anything better than O(m*n)

  --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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 ,
>>> P  Veera Reddy Devagiri
>>> Senior Under Graduate
>>> Computer Science and Engineering
>>> IIIT Hyderabad
>>> Mobile no-+91-9492024783
>>>
>>
>>
>>
>> --
>> Regards ,
>> P  Veera Reddy Devagiri
>> Senior Under Graduate
>> Computer Science and Engineering
>> IIIT Hyderabad
>> Mobile no-+91-9492024783
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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

[Nitin Nizhawan]

why not first sort the lists first?  (we could if we do not want to modify
original list) it will give O(nLogn) solution

-Nitin
On Wed, Aug 3, 2011 at 4:44 PM, veera reddy  wrote:

> sry... misunderstood the question
>
>
> On Wed, Aug 3, 2011 at 4:43 PM, veera reddy wrote:
>
>> there is o(m+n) solution .
>> http://geeksforgeeks.org/?p=2405 in this link see method no 4
>>
>>
>> On Wed, Aug 3, 2011 at 4:41 PM, ankit sambyal wrote:
>>
>>> ya, I also can't think anything better than O(m*n)
>>>
>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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 ,
>> P  Veera Reddy Devagiri
>> Senior Under Graduate
>> Computer Science and Engineering
>> IIIT Hyderabad
>> Mobile no-+91-9492024783
>>
>
>
>
> --
> Regards ,
> P  Veera Reddy Devagiri
> Senior Under Graduate
> Computer Science and Engineering
> IIIT Hyderabad
> Mobile no-+91-9492024783
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[veera reddy]

sry... misunderstood the question

On Wed, Aug 3, 2011 at 4:43 PM, veera reddy  wrote:

> there is o(m+n) solution .
> http://geeksforgeeks.org/?p=2405 in this link see method no 4
>
>
> On Wed, Aug 3, 2011 at 4:41 PM, ankit sambyal wrote:
>
>> ya, I also can't think anything better than O(m*n)
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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 ,
> P  Veera Reddy Devagiri
> Senior Under Graduate
> Computer Science and Engineering
> IIIT Hyderabad
> Mobile no-+91-9492024783
>



-- 
Regards ,
P  Veera Reddy Devagiri
Senior Under Graduate
Computer Science and Engineering
IIIT Hyderabad
Mobile no-+91-9492024783

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

[veera reddy]

there is o(m+n) solution .
http://geeksforgeeks.org/?p=2405 in this link see method no 4

On Wed, Aug 3, 2011 at 4:41 PM, ankit sambyal wrote:

> ya, I also can't think anything better than O(m*n)
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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 ,
P  Veera Reddy Devagiri
Senior Under Graduate
Computer Science and Engineering
IIIT Hyderabad
Mobile no-+91-9492024783

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

[ankit sambyal]

ya, I also can't think anything better than O(m*n)

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

[Prakash D]

someone post all the questions asked by amazon pls.. it'll be useful

On Wed, Aug 3, 2011 at 3:43 PM, Arun Vishwanathan wrote:

> it cud also be 0011
>
>
> On Wed, Aug 3, 2011 at 6:54 AM, payel roy  wrote:
>
>> It is contiguous ...the answer will be 0110.
>>
>>
>> On 2 August 2011 20:59, ankit sambyal  wrote:
>>
>>> @payel : Is it sub-sequence or sub-array ??  A sub-sequence may not be
>>> continuous but a sub-array must be continuous. eg : What wud be the answer
>>> for-  100110 ??
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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] Amazon Question

[UMESH KUMAR]

Order would  be O(m*n)...

On Wed, Aug 3, 2011 at 4:01 AM, ankit sambyal wrote:

> Given two lists write a function which returns a list which is the
> intersection of the two lists.the original lists should remain same.
> (Intersection - if first list is say,1,20 3,45 and second list is 3,24
> ,45,90,68 then intersection should be 3,45 )
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[Arun Vishwanathan]

it cud also be 0011

On Wed, Aug 3, 2011 at 6:54 AM, payel roy  wrote:

> It is contiguous ...the answer will be 0110.
>
>
> On 2 August 2011 20:59, ankit sambyal  wrote:
>
>> @payel : Is it sub-sequence or sub-array ??  A sub-sequence may not be
>> continuous but a sub-array must be continuous. eg : What wud be the answer
>> for-  100110 ??
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] Amazon Question

[payel roy]

It is contiguous ...the answer will be 0110.

On 2 August 2011 20:59, ankit sambyal  wrote:

> @payel : Is it sub-sequence or sub-array ??  A sub-sequence may not be
> continuous but a sub-array must be continuous. eg : What wud be the answer
> for-  100110 ??
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[ankit sambyal]

@payel : Is it sub-sequence or sub-array ??  A sub-sequence may not be
continuous but a sub-array must be continuous. eg : What wud be the answer
for-  100110 ??

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