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 navin.nit...@gmail.com 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.
[algogeeks] Re: MS Q
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.
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
@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 praveen0...@gmail.com 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 atul.87fri...@gmail.comwrote: @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 praveen0...@gmail.comwrote: 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 : 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 praveen0...@gmail.com 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
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 islandsendl;
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 gene.ress...@gmail.com 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 surend...@gmail.com 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 gene.ress...@gmail.com 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 stdio.h
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 ashg...@gmail.com 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 ankurga...@gmail.com
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 ashg...@gmail.com
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
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 gene.ress...@gmail.com 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 stdio.h
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 ashg...@gmail.com 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 ankurga...@gmail.com
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 ashg...@gmail.com
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.
[algogeeks] Re: MS Q
Part of the problem must be rules that specify how 1's can be
connected to form an island.
From the discussion, it looks like the rules are that a 1 must be
connected North, West, East, or South. This is called a 4-connected
grid.
Another possibility would be an 8-connected grid. This is probably
what you have in mind. In this case a 1 can be connected to another 1
North, Northeast, East, Southeast, South, Southwest, West, or
NorthWest. In the code I gave in a previous message, you'd just add 4
more erase() calls for the diagonal corners.
Since the OP never said which rule to use, you are not wrong. You're
just answering a different question than he/she had in mind. This is
a difficulty that often occurs when a question is asked imprecisely.
An excellent lesson to learn for anyone who wants to be a software
engineer...
On Jan 11, 1:28 am, Umer Farooq the.um...@gmail.com 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 yprakash@gmail.com 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 surend...@gmail.comwrote:
@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 gene.ress...@gmail.com 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 stdio.h
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 ashg...@gmail.com 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 ankurga...@gmail.com
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 ashg...@gmail.com
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
[algogeeks] Re: MS Q
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 surend...@gmail.com 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 gene.ress...@gmail.com 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 stdio.h
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 ashg...@gmail.com 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 ankurga...@gmail.com
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 ashg...@gmail.com
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.
[algogeeks] Re: MS Q
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 stdio.h
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 ashg...@gmail.com 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 ankurga...@gmail.com 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 ashg...@gmail.com 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.
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 gene.ress...@gmail.com 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 stdio.h
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 ashg...@gmail.com 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 ankurga...@gmail.com
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 ashg...@gmail.com
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
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 surend...@gmail.com 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 gene.ress...@gmail.com 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 stdio.h
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 ashg...@gmail.com 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 ankurga...@gmail.com
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 ashg...@gmail.com
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
@Umer : it has 1 island ashish made editing mistake before.
On Wed, Jan 11, 2012 at 11:58 AM, Umer Farooq the.um...@gmail.com 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 yprakash@gmail.comwrote:
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 surend...@gmail.comwrote:
@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 gene.ress...@gmail.com 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 stdio.h
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 ashg...@gmail.com 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 ankurga...@gmail.com
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 ashg...@gmail.com
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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: MS Q
@harshal every thing seems to be correct m not sure if things will mess up but can we do it in 1 pass ..?? Shashank CSE,BIT Mesra Cracking The Code shashank7s.blogspot.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: MS Q
@ross i think u mean s[i]==g[b[i]] or s[i]==g[i] then hit++ isn't it u r not using guess at all as u r comparing character with digit correct me if m wrong Shashank CSE,BIT Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: MS Q
An algorithm is:
Have a bit array B of 256/65k size.
If an color 'i' is encountered in the solution, set its B[i]=1;
Traverse the solution array S,
if(S[i]==B[i]) hits++;
else if ( B[S[i]] ) pseudohits++;
On Jun 10, 9:40 am, Harshal hc4...@gmail.com wrote:
#includeiostream
#includestring
using namespace std;
void mastermind(char* guess, char* sol, int *hits, int *pseudohits)
{
int temp[256] = {0};
int len1=strlen(sol);
int len2=strlen(guess);
while(--len1+1)
(guess[len1]==sol[len1]) ? ((*hits)+=1,temp[len1] = 1) : (temp[sol[len1]]
+= 1);
while(--len2+1)
if(temp[len2]!=1 temp[guess[len2]] 0)
(*pseudohits)++, temp[guess[len2]] -= 1;
}
int main()
{
int hits=0,pseudo=0;
mastermind(RGGB,YRGB,hits,pseudo);
couthits pseudo;
}
On Fri, Jun 10, 2011 at 2:31 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote:
Game of master mind: you have four balls, and four different colors, as a
solution. The user tries to guess the solution. If they guess the right
color for the right spot, it counts as a 'hit'. If it's the right color, but
the wrong spot, it counts as a psuedo-hit. For example: if the solution is
'RGGB' and the user guesses 'YRGB' they have 2 hits and one pseudo hit.
Write a program to, given a solution and a guess, calculate the number of
hits and pseudo hits.
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Harshal Choudhary,
III Year B.Tech CSE,
NIT Surathkal, Karnataka, India.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: MS Q
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 ashg...@gmail.com 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.
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 dondod...@gmail.com 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 ashg...@gmail.com 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.
