## doomguy

- 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

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

Amazon SDE1 Data Structures - 0of 0 votes

AnswersThere are two integer arrays ,each in very large files (size of each is larger than RAM). How would you find the common elements in the arrays in linear time.

- doomguy in United States| Report Duplicate | Flag

Amazon Software Engineer / Developer Data Structures - 0of 0 votes

AnswersFor an array of integers, find if there are 3 numbers that add up to zero. An algorithm of complexity O(n^2) was required.

- doomguy in United States| Report Duplicate | Flag

Amazon Software Engineer / Developer 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.