## sayannayak

BAN USER- 0of 0 votes

AnswersYou are given a sorted array,increasing monotonically and decreasing in the same fashion.

- sayannayak in India for Bangalore

WAP to find the index of an element in this array without calculating the pivot.

Running time should be O(log n).You can assume there ia no duplicate element in this array.

e.g: the array is {1,7,10,12,25,30,27,20)

input: arr[],key=27. output=6

input :arr[],key=0. output=-1| Report Duplicate | Flag | PURGE

Amazon SDE-2 - 0of 0 votes

AnswersGiven one integer n.

- sayannayak in India

You have to find out for any integer n,How many distinguished n*n boolean matrix you can form such that each row and each column contains exactly.ceil(n/2) zeroes.

Follow Up: Write your code if you want to print the matrices as well| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm

```
int DistingusishedTree(int n) {
if(n<1)
return 1;
int sum=0;
for(int i=1;i<=n;i++){
sum+=DistingusishedTree(i-1)*DistingusishedTree(n-i);
}
return sum;
}
```

This is the program to find the different BSTs.

The reason is simple:

suppose n=3;

so we will make each number as root and calculate the different subtrees possible.

for i=1;

left subtree will not contain any node and right subtree will contain 2 nodes i.e 2 & 3

there are two combination possible.

if i=2

left subtree will contain 1 node(1) and right subtree will contain 1 node(3)

if i=3

left subtree will contain 2 nodes(1,2).there are two combinations possible for it.

so required number will be

num(i)= sumation(num(i-1)+num(n-i)) where i=1,2...n

The compact formula for this is num(n)=C(2n,n)-C(2n,2n+1) and known as catalan number

N.B.: This problem can be solved using DP instead of recusion.

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

Open Chat in New Window

@Srikant: It's not a rotated sorted array.

- sayannayak July 18, 2013