[algogeeks] Re: Time Complexity Ques

[Gene]

I'm sorry for not being specific.  I meant it doesn't converge for all
roots, e.g. cube root.

On Jan 15, 10:18 pm, Dave  wrote:
> @Gene: Actually, Newton's Method for sqrt(a), where a > 0, also
> sometimes called Heron's Method, converges for every initial guess x_0> 0. 
> This is not true generally for Newton's Method, but it is true
>
> for Newton's Method applied to f(x) = x^2 - a.
>
> Dave
>
> On Jan 15, 5:39 pm, Gene  wrote:
>
>
>
> > To find sqrt(a), this is equivalent to Newton's Method with f(x)=x^2 -
> > a.  Newton is: x_{i+1} = x_i + f'(x_i) / f'(x_i).  So you have x_{i+1}
> > = x_i + (x_i^2 - a) / (2 x_i) = (x + a/x)  / 2, which is just what the
> > Babylonian method says to do.
>
> > Newton's method roughly doubles the number of significant bits in the
> > answer with every iteration _when it converges_.  The problem is that
> > it doesn't converge to every root.  There's a huge literature on this,
> > which I'll let you find yourself.
>
> > On Jan 15, 10:22 pm, Ankur Garg  wrote:
>
> > > Hello
>
> > > I was going through this link
>
> > >http://www.geeksforgeeks.org/archives/3187
>
> > > Wonder what is the time complexity for this..?Can anyone explain >
>
> > > 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.

[algogeeks] Re: Time Complexity Ques

[Gene]

To find sqrt(a), this is equivalent to Newton's Method with

  f(x)=x^2 - a.

Newton is:

  x_{i+1} = x_i + f'(x_i) / f'(x_i).

So you have

  x_{i+1} = x_i + (x_i^2 - a) / (2 x_i) = (x + a/x)  / 2,

which is just what the Babylonian method says to do.

Newton's method roughly doubles the number of significant bits in the
answer with every iteration _when it converges_.  The problem is that
though it works fine for sqrt(), it won't converge for arbitrary f.
There's
a huge literature on this, which I'll let you find yourself.

On Jan 15, 4:22 pm, Ankur Garg  wrote:
> Hello
>
> I was going through this link
>
> http://www.geeksforgeeks.org/archives/3187
>
> Wonder what is the time complexity for this..?Can anyone explain >
>
> 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.

[algogeeks] Re: Time Complexity Ques

[Dave]

@Gene: Actually, Newton's Method for sqrt(a), where a > 0, also
sometimes called Heron's Method, converges for every initial guess x_0
> 0. This is not true generally for Newton's Method, but it is true
for Newton's Method applied to f(x) = x^2 - a.

Dave

On Jan 15, 5:39 pm, Gene  wrote:
> To find sqrt(a), this is equivalent to Newton's Method with f(x)=x^2 -
> a.  Newton is: x_{i+1} = x_i + f'(x_i) / f'(x_i).  So you have x_{i+1}
> = x_i + (x_i^2 - a) / (2 x_i) = (x + a/x)  / 2, which is just what the
> Babylonian method says to do.
>
> Newton's method roughly doubles the number of significant bits in the
> answer with every iteration _when it converges_.  The problem is that
> it doesn't converge to every root.  There's a huge literature on this,
> which I'll let you find yourself.
>
> On Jan 15, 10:22 pm, Ankur Garg  wrote:
>
>
>
> > Hello
>
> > I was going through this link
>
> >http://www.geeksforgeeks.org/archives/3187
>
> > Wonder what is the time complexity for this..?Can anyone explain >
>
> > 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.

[algogeeks] Re: hextoint program MS Q

[Gene]

More detail:  For nearly all compilers, int is 32 bits. So I think you
mean "" should return a negative number.  I just ran the code,
and it does this as expected.

To stop parsing prior to overflow, say something like

int hex_to_int(char *s)
{
  int i = 0;
  while (*s) {
if ('0' <= *s && *s <= '9')
  i = (i << 4) + (*s - '0');
else if ('a' <= *s && *s <= 'f')
  i = (i << 4) + *s + (10 - 'a');
else if ('A' <= *s && *s <= 'F')
  i = (i << 4) + *s + (10 - 'A');
else break;
if (i & 0xf00) break;
s++;
  }
  return i;
}


On Jan 15, 10:01 pm, Gene  wrote:
> And it ought to.  Did you try it?
>
> On Jan 15, 9:55 pm, Ashish Goel  wrote:
>
>
>
> > a 0x should come as a negative number
>
> > Best Regards
> > Ashish Goel
> > "Think positive and find fuel in failure"
> > +919985813081
> > +919966006652
>
> > On Mon, Jan 16, 2012 at 8:19 AM, Gene  wrote:
> > > Okay. Normally you want to use a library that someone else has
> > > tested.  So:
>
> > > sscanf("%x", &i);
>
> > > If you don't have access to any libraries, then:
>
> > > /*
> > >  * Return the integer value of the hex string s. Allowable characters
> > >  * are 0-9, a-f, A-F.  Any other character causes scanning to stop and
> > >  * the hex value of the string up to that character is returned. If
> > > the first
> > >  * character is non-hex, then zero is returned.
> > >  */
> > > int hex_to_int(char *s)
> > > {
> > >  int i = 0;
> > >  while (*s) {
> > >    if ('0' <= *s && *s <= '9')
> > >      i = (i << 4) + (*s - '0');
> > >    else if ('a' <= *s && *s <= 'f')
> > >      i = (i << 4) + *s + (10 - 'a');
> > >    else if ('A' <= *s && *s <= 'F')
> > >      i = (i << 4) + *s + (10 - 'A');
> > >    else break;
> > >    s++;
> > >  }
> > >  return i;
> > > }
>
> > > On Jan 15, 9:16 pm, Ashish Goel  wrote:
> > > > i would assume C or C++
>
> > > > Best Regards
> > > > Ashish Goel
> > > > "Think positive and find fuel in failure"
> > > > +919985813081
> > > > +919966006652
>
> > > > On Mon, Jan 16, 2012 at 7:40 AM, Gene  wrote:
> > > > > Which language?
>
> > > > > On Jan 15, 8:23 pm, Ashish Goel  wrote:
> > > > > > Hi,
>
> > > > > > given a string in hex, convert it into int.
> > > > > > Write test cases for the same.
>
> > > > > > Best Regards
> > > > > > Ashish Goel
> > > > > > "Think positive and find fuel in failure"
> > > > > > +919985813081
> > > > > > +919966006652
>
> > > > > --
> > > > > You received this message because you are subscribed to the Google
> > > Groups
> > > > > "Algorithm Geeks" group.
> > > > > To post to this group, send email to algogeeks@googlegroups.com.
> > > > > To unsubscribe from this group, send email to
> > > > > algogeeks+unsubscr...@googlegroups.com.
> > > > > For more options, visit this group at
> > > > >http://groups.google.com/group/algogeeks?hl=en.
>
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.

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

[algogeeks] Re: hextoint program MS Q

[Gene]

And it ought to.  Did you try it?



On Jan 15, 9:55 pm, Ashish Goel  wrote:
> a 0x should come as a negative number
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
>
> On Mon, Jan 16, 2012 at 8:19 AM, Gene  wrote:
> > Okay. Normally you want to use a library that someone else has
> > tested.  So:
>
> > sscanf("%x", &i);
>
> > If you don't have access to any libraries, then:
>
> > /*
> >  * Return the integer value of the hex string s. Allowable characters
> >  * are 0-9, a-f, A-F.  Any other character causes scanning to stop and
> >  * the hex value of the string up to that character is returned. If
> > the first
> >  * character is non-hex, then zero is returned.
> >  */
> > int hex_to_int(char *s)
> > {
> >  int i = 0;
> >  while (*s) {
> >    if ('0' <= *s && *s <= '9')
> >      i = (i << 4) + (*s - '0');
> >    else if ('a' <= *s && *s <= 'f')
> >      i = (i << 4) + *s + (10 - 'a');
> >    else if ('A' <= *s && *s <= 'F')
> >      i = (i << 4) + *s + (10 - 'A');
> >    else break;
> >    s++;
> >  }
> >  return i;
> > }
>
> > On Jan 15, 9:16 pm, Ashish Goel  wrote:
> > > i would assume C or C++
>
> > > Best Regards
> > > Ashish Goel
> > > "Think positive and find fuel in failure"
> > > +919985813081
> > > +919966006652
>
> > > On Mon, Jan 16, 2012 at 7:40 AM, Gene  wrote:
> > > > Which language?
>
> > > > On Jan 15, 8:23 pm, Ashish Goel  wrote:
> > > > > Hi,
>
> > > > > given a string in hex, convert it into int.
> > > > > Write test cases for the same.
>
> > > > > Best Regards
> > > > > Ashish Goel
> > > > > "Think positive and find fuel in failure"
> > > > > +919985813081
> > > > > +919966006652
>
> > > > --
> > > > You received this message because you are subscribed to the Google
> > Groups
> > > > "Algorithm Geeks" group.
> > > > To post to this group, send email to algogeeks@googlegroups.com.
> > > > To unsubscribe from this group, send email to
> > > > algogeeks+unsubscr...@googlegroups.com.
> > > > For more options, visit this group at
> > > >http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

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

Re: [algogeeks] Re: hextoint program MS Q

[Ashish Goel]

a 0x should come as a negative number

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


On Mon, Jan 16, 2012 at 8:19 AM, Gene  wrote:

> Okay. Normally you want to use a library that someone else has
> tested.  So:
>
> sscanf("%x", &i);
>
> If you don't have access to any libraries, then:
>
> /*
>  * Return the integer value of the hex string s. Allowable characters
>  * are 0-9, a-f, A-F.  Any other character causes scanning to stop and
>  * the hex value of the string up to that character is returned. If
> the first
>  * character is non-hex, then zero is returned.
>  */
> int hex_to_int(char *s)
> {
>  int i = 0;
>  while (*s) {
>if ('0' <= *s && *s <= '9')
>  i = (i << 4) + (*s - '0');
>else if ('a' <= *s && *s <= 'f')
>  i = (i << 4) + *s + (10 - 'a');
>else if ('A' <= *s && *s <= 'F')
>  i = (i << 4) + *s + (10 - 'A');
>else break;
>s++;
>  }
>  return i;
> }
>
> On Jan 15, 9:16 pm, Ashish Goel  wrote:
> > i would assume C or C++
> >
> > Best Regards
> > Ashish Goel
> > "Think positive and find fuel in failure"
> > +919985813081
> > +919966006652
> >
> >
> >
> > On Mon, Jan 16, 2012 at 7:40 AM, Gene  wrote:
> > > Which language?
> >
> > > On Jan 15, 8:23 pm, Ashish Goel  wrote:
> > > > Hi,
> >
> > > > given a string in hex, convert it into int.
> > > > Write test cases for the same.
> >
> > > > Best Regards
> > > > Ashish Goel
> > > > "Think positive and find fuel in failure"
> > > > +919985813081
> > > > +919966006652
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

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

[algogeeks] Re: hextoint program MS Q

[Gene]

Okay. Normally you want to use a library that someone else has
tested.  So:

sscanf("%x", &i);

If you don't have access to any libraries, then:

/*
 * Return the integer value of the hex string s. Allowable characters
 * are 0-9, a-f, A-F.  Any other character causes scanning to stop and
 * the hex value of the string up to that character is returned. If
the first
 * character is non-hex, then zero is returned.
 */
int hex_to_int(char *s)
{
  int i = 0;
  while (*s) {
if ('0' <= *s && *s <= '9')
  i = (i << 4) + (*s - '0');
else if ('a' <= *s && *s <= 'f')
  i = (i << 4) + *s + (10 - 'a');
else if ('A' <= *s && *s <= 'F')
  i = (i << 4) + *s + (10 - 'A');
else break;
s++;
  }
  return i;
}

On Jan 15, 9:16 pm, Ashish Goel  wrote:
> i would assume C or C++
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
>
> On Mon, Jan 16, 2012 at 7:40 AM, Gene  wrote:
> > Which language?
>
> > On Jan 15, 8:23 pm, Ashish Goel  wrote:
> > > Hi,
>
> > > given a string in hex, convert it into int.
> > > Write test cases for the same.
>
> > > Best Regards
> > > Ashish Goel
> > > "Think positive and find fuel in failure"
> > > +919985813081
> > > +919966006652
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

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

Re: [algogeeks] Re: hextoint program MS Q

[Ashish Goel]

i would assume C or C++

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


On Mon, Jan 16, 2012 at 7:40 AM, Gene  wrote:

> Which language?
>
> On Jan 15, 8:23 pm, Ashish Goel  wrote:
> > Hi,
> >
> > given a string in hex, convert it into int.
> > Write test cases for the same.
> >
> > Best Regards
> > Ashish Goel
> > "Think positive and find fuel in failure"
> > +919985813081
> > +919966006652
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

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

[algogeeks] Re: hextoint program MS Q

[Gene]

Which language?

On Jan 15, 8:23 pm, Ashish Goel  wrote:
> Hi,
>
> given a string in hex, convert it into int.
> Write test cases for the same.
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652

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

[algogeeks] Re: Sorting for large data

[Gene]

If the interviewer actually said 10^80 data items, he/she was
expecting you to say it's a silly question.

Do you realize how much 10^80 is?  A terabyte is 10^12 bytes. So we
are talking about 10^68 1 Tb disk drives just to hold 1 byte records.
The number of grains of sand that would make up the volume of the
Earth is only about 10^32.  It's fair to say that at least for a few
decades there won't be enough storage capacity in the world to hold
10^80 data items.

If the interviewer actually said 10^8, we have 100 million records.
This is more reasonable.  The interviewer probably wanted you to ask
how big the records are.  If small, you can do a regular sort in
memory.  If large, you could sort a list of keys or disk offsets.
External sort would start being a valid technique with 10^9 or 10^10
records depending on how much main memory you have available.

As to tools, gnusort does external sort when the data are very big.
At least it did about 10 years ago when I looked at the source code.

On Jan 14, 1:09 pm, Abhishek Goswami  wrote:
> Hi,
> Could any point out me any algorithm and program  if we need to sort to
> large data
> like 10 ^ 80 with memory constraint. Suppose you have minimum memory like 4
> MB.
>
> I am not sure that this algo discussed or not but i was not able to find in
> this group.
>
> Thanks
> Abhishek

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

[algogeeks] rectangle of max sum MS Q

[Ashish Goel]

given a m*n matrix, find the subset rectangle with max sum (any other
rectangle taken would have lesser sum)
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652

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

[algogeeks] hextoint program MS Q

[Ashish Goel]

Hi,

given a string in hex, convert it into int.
Write test cases for the same.


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

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

Re: [algogeeks] Re: Sorting for large data

[Ashish Goel]

@atul, how virtual memory? still swaps right...
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652


On Sun, Jan 15, 2012 at 12:50 PM, atul anand wrote:

> virtual memory

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

[algogeeks] Re: Time Complexity Ques

[Gene]

To find sqrt(a), this is equivalent to Newton's Method with f(x)=x^2 -
a.  Newton is: x_{i+1} = x_i + f'(x_i) / f'(x_i).  So you have x_{i+1}
= x_i + (x_i^2 - a) / (2 x_i) = (x + a/x)  / 2, which is just what the
Babylonian method says to do.

Newton's method roughly doubles the number of significant bits in the
answer with every iteration _when it converges_.  The problem is that
it doesn't converge to every root.  There's a huge literature on this,
which I'll let you find yourself.



On Jan 15, 10:22 pm, Ankur Garg  wrote:
> Hello
>
> I was going through this link
>
> http://www.geeksforgeeks.org/archives/3187
>
> Wonder what is the time complexity for this..?Can anyone explain >
>
> 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.

[algogeeks] Time Complexity Ques

[Ankur Garg]

Hello

I was going through this link

http://www.geeksforgeeks.org/archives/3187

Wonder what is the time complexity for this..?Can anyone explain >

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.

[algogeeks] Need 5 minutes of your time to answer few questions

[Vishal Jain]

Hi,


We are conducting a research study. Your input can help us in making
informed decisions to improve our service. We estimate that it will take
you approximately 5 minutes to complete the survey.


Simply click on the link below, or cut and paste the entire URL into your
browser to access the survey:

https://docs.google.com/spreadsheet/viewform?formkey=dDBUTnZlNEE2NFZMS3pqYkNqaEhwYVE6MQ


We would appreciate your response.
Your input is very important to us and will be kept strictly confidential
(used only for the purposes of research for this project).

PS: Please ignore the mail in case you have got it earlier.

Thanks & Regards
Vishal Jain
MNo: +91-9540611889
Tweet @jainvis

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

Re: [algogeeks] Re: MS Q

[atul anand]

@Umer : will fail for this case :-

0 0 0 0
0 1 0 1
1 1 1 1

island = 1;

it seem your code will print island =1 ;

On Sun, Jan 15, 2012 at 3:45 PM, Umer Farooq  wrote:

> Here is my solution. Please have a look at it. Any kind of positive
> criticism will be highly appreciated.
>
> bool isConnected(int **space, int x, int y)
> {
> if (x == 0 && y == 0)
>  {
> return false;
> }
>  if (y > 0)
> {
> if (space[x][y-1] == 1)
>  return true;
> }
> if (x > 0)
>  {
> if (space[x-1][y] == 1)
> return true;
>  }
> if (x > 0 && y > 0)
> {
>  if (space[x-1][y-1] == 1)
> return true;
> }
>  if ((x-1 >= 0)&&(y+1 < sizeof(space)/sizeof(space[0][0])))
> {
>  if (space[x-1][y+1] == 1)
> return true;
> }
>  return false;
> }
>
> int _tmain(int argc, _TCHAR* argv[])
> {
> int len = 4;
>  int breadth = 4;
> int **space;
> space = new int*[len];
>  for (int i = 0; i < len; i++)
> space[i] = new int[breadth];
>
>  space[0][0] = 1;
> space[0][1] = 1;
> space[0][2] = 0;
>  space[0][3] = 0;
>
> space[1][0] = 1;
> space[1][1] = 1;
>  space[1][2] = 0;
> space[1][3] = 0;
>
> space[2][0] = 0;
>  space[2][1] = 0;
> space[2][2] = 0;
> space[2][3] = 0;
>
> space[3][0] = 0;
> space[3][1] = 0;
> space[3][2] = 1;
>  space[3][3] = 1;
>  int islands = 0;
>  for (int i = 0; i < len; i++)
> {
> for (int j = 0; j < breadth; j++)
>  if (isConnected(space, i, j) == false && space[i][j] == 1)
> islands++;
>  }
>
> cout << islands< int r = 0;
>  cin >> r;
>
> return 0;
> }
>
> The function isConnected tells if an element at x,y on matrix (space) is
> connected to an existing island or is it completely a new island.
> The 2D array used in main function is only a test case. You can replace it
> with anything you want. The nested loop in the main method iterates over
> the whole array and gets the total number of islands that are present.
>
> Anyway, nice question. I liked solving it :)
>
> One more thing. Was it asked in phone interview or on-site interview?
>
> On Wed, Jan 11, 2012 at 6:08 PM, Gene  wrote:
>
>> The OP is not clear on how to handle diagonals. If adjacent 1's on the
>> diagonal are considered connected, then just add 4 more calls to
>> erase().
>>
>> The standard terms are 4-connected and 8-connected.  Both come up when
>> working with grid graphs or pixel matrices.
>>
>>
>> On Jan 10, 9:40 pm, surender sanke  wrote:
>> > @gene
>> > in that case ur erase() should even consider diagonal elements as well,
>> > else there would be 2 islands in example
>> >
>> > surender
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > On Wed, Jan 11, 2012 at 7:19 AM, Gene  wrote:
>> > > Guys,
>> >
>> > > You are making this way too hard.  It's really a graph problem. The
>> > > nodes are the 1's and adjacent 1's are connected by undirected edges.
>> > > You must count components in the graph. So the algorithm is easy:
>> > > Find a component, erase it, repeat.  Count components as you go.
>> > > What's an efficient way to do this with this special kind of graph we
>> > > have?  Just erase components by erasing 1's.
>> >
>> > > So we get:
>> >
>> > > #include 
>> >
>> > > int a[100][100] = {
>> > >  {1, 1, 0, 0},
>> > >  {1, 1, 0, 0},
>> > >  {0, 0, 1, 1},
>> > > };
>> >
>> > > int m = 3, n = 4;
>> >
>> > > // Erase the undirected component rooted at i,j.
>> > > void erase(int i, int j)
>> > > {
>> > >  // If we're off the graph or already erased,
>> > >  // there's nothing to do.
>> > >  if (i < 0 || j < 0 || i >= m || j >= n || !a[i][j])
>> > >return;
>> > >  // Erase!
>> > >  a[i][j] = 0;
>> > >  // Recursively erase the 4 neighbors.
>> > >  erase(i+1, j); erase(i-1, j);
>> > >  erase(i, j+1); erase(i, j-1);
>> > > }
>> >
>> > > void count_islands()
>> > > {
>> > >  int i, j, n_islands = 0;
>> > >  // Search for a component.
>> > >  for (i = 0; i < m; i++) {
>> > >for (j = 0; j < n; j++) {
>> > >  if (a[i][j] == 1) {
>> > >// Found one!  Count and erase.
>> > >n_islands++;
>> > >erase(i, j);
>> > >  }
>> > >}
>> > >  }
>> > >  printf("found %d islands\n", n_islands);
>> > > }
>> >
>> > > int main(void)
>> > > {
>> > >  count_islands();
>> > >  return 0;
>> > > }
>> >
>> > > On Jan 9, 9:06 pm, Ashish Goel  wrote:
>> > > > row, col, diag all
>> >
>> > > > 1-1-1 is a single island :)
>> >
>> > > > 1 1 0 0
>> > > > 1 1 0 0
>> > > > 0 0 1 1
>> >
>> > > > this has only 2 islands
>> >
>> > > > Best Regards
>> > > > Ashish Goel
>> > > > "Think positive and find fuel in failure"
>> > > > +919985813081
>> > > > +919966006652
>> >
>> > > > On Tue, Jan 10, 2012 at 7:29 AM, Ankur Garg 
>> > > wrote:
>> > > > > Can you give an example
>> >
>> > > > > Say  matrix is
>> >
>> > > > > 1 1 0 0
>> > > > > 1 1 0 0
>> > > > > 0 0 1 1
>> >
>> > > > > Has it got 3 islands i.e 1-1 be in same row or they can be column
>> wise
>> > > > > also i.e. 5
>> >
>> > > > > On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel 
>> > > wrote:
>> >
>> > > > >> there is a matrix of 1 and 0
>> > > > >> 1 is a island and 0 is water
>> > > > >> 1-1 together makes one 

Re: [algogeeks] Binary Index Tree

[Amol Sharma]

also try

http://www.spoj.pl/problems/DQUERY/

--


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
 








On Sun, Jan 15, 2012 at 7:11 PM, saurabh singh  wrote:

> search problem japan
> Saurabh Singh
> B.Tech (Computer Science)
> MNNIT
> blog:geekinessthecoolway.blogspot.com
>
>
>
> On Sun, Jan 15, 2012 at 4:23 AM, Mad Coder  wrote:
>
>> Hi all, I was going through Binary Index Tree (BIT) tutorial through
>> topcoder , although the concept is clear to me, I want to do some more
>> practice questions. So it will be helpful if you provide me link of some
>> questions of BIT in spoj.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] Binary Index Tree

[saurabh singh]

search problem japan
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com



On Sun, Jan 15, 2012 at 4:23 AM, Mad Coder  wrote:

> Hi all, I was going through Binary Index Tree (BIT) tutorial through
> topcoder , although the concept is clear to me, I want to do some more
> practice questions. So it will be helpful if you provide me link of some
> questions of BIT in spoj.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] Re: MS Q

[Umer Farooq]

Here is my solution. Please have a look at it. Any kind of positive
criticism will be highly appreciated.

bool isConnected(int **space, int x, int y)
{
if (x == 0 && y == 0)
{
return false;
}
if (y > 0)
{
if (space[x][y-1] == 1)
return true;
}
if (x > 0)
{
if (space[x-1][y] == 1)
return true;
}
if (x > 0 && y > 0)
{
if (space[x-1][y-1] == 1)
return true;
}
if ((x-1 >= 0)&&(y+1 < sizeof(space)/sizeof(space[0][0])))
{
if (space[x-1][y+1] == 1)
return true;
}
return false;
}

int _tmain(int argc, _TCHAR* argv[])
{
int len = 4;
int breadth = 4;
int **space;
space = new int*[len];
for (int i = 0; i < len; i++)
space[i] = new int[breadth];

space[0][0] = 1;
space[0][1] = 1;
space[0][2] = 0;
space[0][3] = 0;

space[1][0] = 1;
space[1][1] = 1;
space[1][2] = 0;
space[1][3] = 0;

space[2][0] = 0;
space[2][1] = 0;
space[2][2] = 0;
space[2][3] = 0;

space[3][0] = 0;
space[3][1] = 0;
space[3][2] = 1;
space[3][3] = 1;
 int islands = 0;
for (int i = 0; i < len; i++)
{
for (int j = 0; j < breadth; j++)
if (isConnected(space, i, j) == false && space[i][j] == 1)
islands++;
}

cout << islands<> r;

return 0;
}

The function isConnected tells if an element at x,y on matrix (space) is
connected to an existing island or is it completely a new island.
The 2D array used in main function is only a test case. You can replace it
with anything you want. The nested loop in the main method iterates over
the whole array and gets the total number of islands that are present.

Anyway, nice question. I liked solving it :)

One more thing. Was it asked in phone interview or on-site interview?

On Wed, Jan 11, 2012 at 6:08 PM, Gene  wrote:

> The OP is not clear on how to handle diagonals. If adjacent 1's on the
> diagonal are considered connected, then just add 4 more calls to
> erase().
>
> The standard terms are 4-connected and 8-connected.  Both come up when
> working with grid graphs or pixel matrices.
>
>
> On Jan 10, 9:40 pm, surender sanke  wrote:
> > @gene
> > in that case ur erase() should even consider diagonal elements as well,
> > else there would be 2 islands in example
> >
> > surender
> >
> >
> >
> >
> >
> >
> >
> > On Wed, Jan 11, 2012 at 7:19 AM, Gene  wrote:
> > > Guys,
> >
> > > You are making this way too hard.  It's really a graph problem. The
> > > nodes are the 1's and adjacent 1's are connected by undirected edges.
> > > You must count components in the graph. So the algorithm is easy:
> > > Find a component, erase it, repeat.  Count components as you go.
> > > What's an efficient way to do this with this special kind of graph we
> > > have?  Just erase components by erasing 1's.
> >
> > > So we get:
> >
> > > #include 
> >
> > > int a[100][100] = {
> > >  {1, 1, 0, 0},
> > >  {1, 1, 0, 0},
> > >  {0, 0, 1, 1},
> > > };
> >
> > > int m = 3, n = 4;
> >
> > > // Erase the undirected component rooted at i,j.
> > > void erase(int i, int j)
> > > {
> > >  // If we're off the graph or already erased,
> > >  // there's nothing to do.
> > >  if (i < 0 || j < 0 || i >= m || j >= n || !a[i][j])
> > >return;
> > >  // Erase!
> > >  a[i][j] = 0;
> > >  // Recursively erase the 4 neighbors.
> > >  erase(i+1, j); erase(i-1, j);
> > >  erase(i, j+1); erase(i, j-1);
> > > }
> >
> > > void count_islands()
> > > {
> > >  int i, j, n_islands = 0;
> > >  // Search for a component.
> > >  for (i = 0; i < m; i++) {
> > >for (j = 0; j < n; j++) {
> > >  if (a[i][j] == 1) {
> > >// Found one!  Count and erase.
> > >n_islands++;
> > >erase(i, j);
> > >  }
> > >}
> > >  }
> > >  printf("found %d islands\n", n_islands);
> > > }
> >
> > > int main(void)
> > > {
> > >  count_islands();
> > >  return 0;
> > > }
> >
> > > On Jan 9, 9:06 pm, Ashish Goel  wrote:
> > > > row, col, diag all
> >
> > > > 1-1-1 is a single island :)
> >
> > > > 1 1 0 0
> > > > 1 1 0 0
> > > > 0 0 1 1
> >
> > > > this has only 2 islands
> >
> > > > Best Regards
> > > > Ashish Goel
> > > > "Think positive and find fuel in failure"
> > > > +919985813081
> > > > +919966006652
> >
> > > > On Tue, Jan 10, 2012 at 7:29 AM, Ankur Garg 
> > > wrote:
> > > > > Can you give an example
> >
> > > > > Say  matrix is
> >
> > > > > 1 1 0 0
> > > > > 1 1 0 0
> > > > > 0 0 1 1
> >
> > > > > Has it got 3 islands i.e 1-1 be in same row or they can be column
> wise
> > > > > also i.e. 5
> >
> > > > > On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel 
> > > wrote:
> >
> > > > >> there is a matrix of 1 and 0
> > > > >> 1 is a island and 0 is water
> > > > >> 1-1 together makes one island
> > > > >> calculate total no of islands
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from 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