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.
@Srikant: It's not a rotated sorted array.
- sayannayak July 18, 2013