Re: [algogeeks] Re: MS Q
anybody have informaton regarding questions asked in written and interview of capillary technology for developer post please share at bhardwaj.ankit...@gmail.com thanks in advance. On 5/22/12, Navin.nitjsr wrote: > If the matrix is 4-connected, we can use the same matrix. > now we have to find the total number of connected components of a graph. > consider > 1 1 1 0 0 1 1 0 1 > 0 1 1 1 0 0 1 0 0 > 1 1 0 1 0 1 1 1 0 > 0 0 0 0 0 0 0 0 1 > we can use bfs/dfs to mark the nodes as visited and thus total connected > components can be counted. > > > On Tuesday, 10 January 2012 07:09:46 UTC+5:30, ashgoel 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 >> >> Best Regards >> Ashish Goel >> "Think positive and find fuel in failure" >> >> > > -- > 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/-/JiDXnyVHn4YJ. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from 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
@praveen : little more clarity required in your algoare you calling it recursively or moving row by row. On Tue, Jan 24, 2012 at 5:59 PM, praveen raj wrote: > Idea: > 1)Take count =0; > 2) make Outer loop ...and search for 1's . > 3) Start ...searching for 1 consecutively... > and make it ..0 untill all consecutive 1's becomes 0.. > and then count++ > 4) go to 1) untill all 1's finished.. > > count will give the total number of islands... > > > PRAVEEN RAJ > DELHI COLLEGE OF ENGINEERING > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from 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
name it. PRAVEEN RAJ DELHI COLLEGE OF ENGINEERING On Wed, Jan 25, 2012 at 12:45 AM, atul anand wrote: > @Praveen : i have doubt in your algo...it seem it may fail for some > cases... > > On Tue, Jan 24, 2012 at 5:59 PM, praveen raj wrote: > >> Idea: >> 1)Take count =0; >> 2) make Outer loop ...and search for 1's . >> 3) Start ...searching for 1 consecutively... >> and make it ..0 untill all consecutive 1's becomes 0.. >> and then count++ >> 4) go to 1) untill all 1's finished.. >> >> count will give the total number of islands... >> >> >> PRAVEEN RAJ >> DELHI COLLEGE OF ENGINEERING >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from 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: MS Q
@Praveen : i have doubt in your algo...it seem it may fail for some cases... On Tue, Jan 24, 2012 at 5:59 PM, praveen raj wrote: > Idea: > 1)Take count =0; > 2) make Outer loop ...and search for 1's . > 3) Start ...searching for 1 consecutively... > and make it ..0 untill all consecutive 1's becomes 0.. > and then count++ > 4) go to 1) untill all 1's finished.. > > count will give the total number of islands... > > > PRAVEEN RAJ > DELHI COLLEGE OF ENGINEERING > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from 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
Idea: 1)Take count =0; 2) make Outer loop ...and search for 1's . 3) Start ...searching for 1 consecutively... and make it ..0 untill all consecutive 1's becomes 0.. and then count++ 4) go to 1) untill all 1's finished.. count will give the total number of islands... PRAVEEN RAJ DELHI COLLEGE OF ENGINEERING -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 : 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] Re: MS Q
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
Re: [algogeeks] Re: MS Q
this is the solution that i was referring to in the link i provided.
On the same lines there is another problem of rat in a maze .
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
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 you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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 : it has 1 island ashish made editing mistake before.
On Wed, Jan 11, 2012 at 11:58 AM, Umer Farooq wrote:
> I still don't get how are they two islands. As long as I have understood,
> diagonals abridge the two islands into one. In this case, these two islands
> are connected so they form one single island?
>
> 1 1 0 0
> 1 1 0 0
> 0 0 1 1
>
> This can be either one single island. Or they are three island if a change
> in direction makes a whole new island.
>
> Can anyone please clear me the problem?
>
>
> On Wed, Jan 11, 2012 at 10:24 AM, prakash y wrote:
>
>> I think atul/Ramakanth's approach will work fine, if we include one more
>> condition
>>
>> for each arr[i][j]
>> if(arr[i][j]==1)
>> {
>> if (arr[i-1][j]==0 && arr[i][j-1]==0 && arr[i-1][j-1]==0)
>> count++;
>>
>> else if (arr[i-1][j]==1 && arr[i][j-1]==1 && arr[i-1][j-1]==0)
>> count--;
>> }
>>
>> On Wed, Jan 11, 2012 at 8:10 AM, 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 you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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.
>>
>
>
>
> --
> Umer
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://gro
Re: [algogeeks] Re: MS Q
I still don't get how are they two islands. As long as I have understood,
diagonals abridge the two islands into one. In this case, these two islands
are connected so they form one single island?
1 1 0 0
1 1 0 0
0 0 1 1
This can be either one single island. Or they are three island if a change
in direction makes a whole new island.
Can anyone please clear me the problem?
On Wed, Jan 11, 2012 at 10:24 AM, prakash y wrote:
> I think atul/Ramakanth's approach will work fine, if we include one more
> condition
>
> for each arr[i][j]
> if(arr[i][j]==1)
> {
> if (arr[i-1][j]==0 && arr[i][j-1]==0 && arr[i-1][j-1]==0)
> count++;
>
> else if (arr[i-1][j]==1 && arr[i][j-1]==1 && arr[i-1][j-1]==0)
> count--;
> }
>
> On Wed, Jan 11, 2012 at 8:10 AM, 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 you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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.
>
--
Umer
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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
I think atul/Ramakanth's approach will work fine, if we include one more
condition
for each arr[i][j]
if(arr[i][j]==1)
{
if (arr[i-1][j]==0 && arr[i][j-1]==0 && arr[i-1][j-1]==0)
count++;
else if (arr[i-1][j]==1 && arr[i][j-1]==1 && arr[i-1][j-1]==0)
count--;
}
On Wed, Jan 11, 2012 at 8:10 AM, 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 you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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
@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 you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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
while all this is fine, the basic test case that each point on the circle is at a distance of r from the centre becomes first functional test case. what would be non-functional test cases eg. to check on different dpi/screen sizes etc Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Fri, Jun 3, 2011 at 2:57 AM, Don wrote: > Are we drawing a circle on the screen? > > In addition to Harshal's suggestions, try putting the center off the > screen, but have part of the circle on the screen: > > x=-10 > y=-20 > r=100 > > Don > > On Jun 2, 9:19 am, Ashish Goel wrote: > > Given a function to draw a circle with input paramters as co-ordinates of > > centre of the circle and r is the radius of the circle. > > How will you test this function, what will be additional non-functional > > test cases > > > > 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.
