## explorer.bit

BAN USERAn honest Person.

- 0of 0 votes

AnswersThere are 3 person in a forest, when they slept at night someone from outside colored their faces black(all three). Now when they wake up in the morning all three started laughing at each other thinking that the other two persons have black faces.

- explorer.bit in India

But after some time they realized that their own faces are also black and then they stop laughing at each other.

Here, you have to give a valid LOGICAL REASON that how they realized that their own faces are also black, i.e. all three faces are black.

.

.

To mention here, these are not logical reasons... e.g.

1. They are looking on faces of each other so the other person will realize that his face is also black.

2. One will look into others eyes(eyes as mirror) hence he can find that his face is black.

3. He will use water to see his face if something wrong, hence he will find that his face is black.

4. They will tell each other that your face is black. ..... e.t.c

.

.

ALL THE BEST to all for this question.| Report Duplicate | Flag | PURGE

Sapient Corporation Associate Brain Teasers - 0of 0 votes

AnswersYou are given an array which contains coin denominations. e.g. d = {1,2,3,5,8,12,15,21,37,56}. Each of these denominations are in infinite numbers. Write a program to produce the minimum number of coins(with denomination) which sum up to a given value. e.g. 189

- explorer.bit in India

output: 3(56)+1(23) = 4

you may produce output as 56->56->56->23| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer - 0of 0 votes

AnswersYou are given 2 fair dices, whose all 6 faces are blank. You have to fill these faces with 0-9(you can repeat some digits, as there are 12 faces) such that, you should be able to produce all the dates of an English month.

- explorer.bit in India

e.g. you should be able to show 01 02 ....09 10.....30 31| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Brain Teasers

Actually what I think about this question is that, you can't use extra space O(n).

- explorer.bit November 16, 2012Yeah, you got it. Tell me how did you get to solution? It would be pretty interesting how u solved it.

- explorer.bit November 16, 2012When two people are laughing...the reason may be that they have their faces black but they don't know that, and they are laughing on each other not on you ... so this is not a logic to get the conclusion that your face is black :)

...

Also to mention, you can't feel that paint(No itching or any other hint)

Actually, what I understood was that you can only go right or below.....So, if it is not that, then it wont work.

- explorer.bit November 14, 2012Yeah, actually the solution is to repeat 0,1,2 in both the dices and distribute 3,4,5,6,7,8 in the remaining faces of the dices with any combination. You just have to invert '6' for showing '9'.

- explorer.bit November 14, 2012Please try to understand that it is not about outcome of throwing two dices....It's just about you should be able to show all the valid dates(01-31) ,..... so (0,0) doen't make sense, coz no one will ask you to show 00 or 85 or 92 etc.

- explorer.bit November 14, 2012I was also not able to do it at first, but Hiring manager gave this hint and within 5 seconds I got that hint. So it is just tricky, try to get it. Else I'll tell the solution.

- explorer.bit November 14, 2012This was a hint Lightyear ... I am not asking you, but, I am giving hint that you should reuse one or more numbers. Get this hint and you are done :)

- explorer.bit November 14, 2012You always have to show both the dices .... like I have shown in question.

- explorer.bit November 14, 2012Can you reuse any number?? :)

- explorer.bit November 14, 2012Actually ... The question says, only to check if two trees are similar.......So we should only check the structure of the tree.

If you'll check for the values also, that means they are copy of each other, which is not required.

You can make one auxiliary matrix for the minimum difficulty as ...

mat[][] dif[][]

7 9 2 11 ----> 7 16 9 18

13 23 1 3 ----> 20 39 10 13

14 11 20 6 ----> 21 27 29 19

22 44 3 15 ----> 29 60 12 27

You can take this matrix as Matrix of pointers to nodes with structure ...

struct node{ int data; node parent};

First, Dynamically provide the required space for dif[][];

Now for making the above matrix do following ...

void PrintPath(int mat[][4],node *diff[][4]) //m*n*n

{

dif[0][0]->data = mat[0][0];

dif[0][0]->parent = NULL;

for(int i=0;i<m;i++)

{

for(int j=0;j<n;j++)

{

node *temp;

if(i==0 || j==0) temp = dif[0][0]

else temp = FindMinimum(dif,i,j); //It returns the pointer to node with minimum value/data in jth column and ith row with in range of row(0,i) and column(0,j) in O(m+n) time complexity

dif[i][j]->data = temp->data + mat[i][j];

diff[i][j]->parent = temp;

}

}

temp = dif[m-1][n-1];

while(temp!=NULL)

{

cout<<temp->data;

temp = temp->parent;

}

} // Function ends Here

node *FindMinimum(node *dif[][4],int m,int n) //O(m+n)

{

node *min = dif[0][n];

for(int i=0;i<=m;i++)

if(min->data > dif[i][j]->data) min = dif[i][j];

for(int j=0;j<=n;j++)

if(min->data > dif[i][j]->data) min = dif[i][j];

return min;

}

Total Time Complexity O(m*n*(m+n))

Space Complexity O(m*n)

bool ISSimilar(node *a, node *b)

{

if(a==NULL && b==NULL) return true;

else if(a==NULL || b==NULL) return false;

else return (ISSimilar(a->left, b->left) && ISSimilar(a->right, b->right));

}

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

Open Chat in New Window

dff

- explorer.bit January 21, 2013