## 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.*/

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

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