doomguy
BAN USER- 0of 0 votes
AnswersYou are given a graph and a node in the graph. Group the nodes connected to this node if they are also connected to each other. For example, the graph has nodes 1, 2, 3, 4, 5 where 1 is connected to 2, 3, 4; 2 and 3 are also connected to each other, 4 is just connected to 1 and 5 is a separate node. You are given node 1 as input. Output should be:
- doomguy in United States
2 3
4| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 2 votes
AnswersWrite code to rotate a square matrix:
- doomguy in United States
Input:
1 2 3
4 5 6
7 8 9
Output:
4 1 2
7 5 3
8 9 6| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures
@Igor
I am unable to post a reply for some reason but
Consider the following example: 4 2 5 and 3 are connected to 1. 4 and 2 are also connected to 3 and 6 is just connected to 5. (Diagram may get messed up on posting)
4
|\
6-5-1-3
|/
2
From what I understand with your approach,
when we visit unvisited children of 2, it will only discover 3 and group it with 1. However, we also want 4 to be included as it is also connected to 1 and connected to 3.
Moreover in your approach, it will also end up grouping 6 with 5. But it should not happen as it is not connected to 1.
The correct output for this case should be
2 3 4
5
Whereas (correct me if I am wrong), your approach would give
2 3
4
5 6
Sorry if my simpler example in the question was not making the requirement clear.
#include <stdio.h>
struct node
{
int v;
struct node* left;
struct node* right;
};
void createtree(struct node* root)
{
int x,y;
printf("Enter left child of %d: ",root->v);
scanf("%d",&x);
printf("Enter right child of %d: ",root->v);
scanf("%d",&y);
if(x==-999)root->left=NULL;
else {
root->left=new struct node();
root->left->v=x;
root->left->left=NULL;
root->left->right=NULL;
createtree(root->left);
}
if(y==-999)root->right=NULL;
else {
root->right=new struct node();
root->right->v=y;
root->right->left=NULL;
root->right->right=NULL;
createtree(root->right);
}
}
void display(struct node* root)
{
printf("%d ",root->v);
if(root->left!=NULL)display(root->left);
if(root->right!=NULL)display(root->right);
}
void treereverse(struct node *root)
{
if(root==NULL)return;
struct node *t=root->left;
root->left=root->right;
root->right=t;
treereverse(root->left);
treereverse(root->right);
}
int main()
{
struct node* root,*start;
root=new struct node();
start=root;
int x;
printf("Enter root: ");
scanf("%d",&x);
root->v=x;
root->left=NULL;
root->right=NULL;
createtree(root);
root=start;
printf("Before reversal: \n");
display(root);
root=start;
treereverse(root);
printf("After reversal: \n");
root=start;
display(root);
}
/*The treereverse function simply swaps the left and right child of a node. The results are displayed using pre-order traversal.*/
@Dinesh Pant
- doomguy April 13, 2016Since 2 is connected to 3,5 the output should be:
2 3 5
4
See the more elaborate example I give above as a reply to Igor. It may be more helpful. Also no directed graph.