Given an Array of Interegers , NUmber of Unique Binary Searchj Trees Can be Made from this values are ?

you are building an N node binary search tree with the values 1..N. How many structurally different  binary search trees are there that store those values? Write a recursive function that, given the number of distinct values, computes the number of structurally unique binary search trees that store those values. For example, countTrees(4) should return 14, since there are 14  structurally unique binary search trees that store 1, 2, 3, and 4.

Fix the ClassThatNeedsFixing implementation so that the critical section is protected.

I have two methods of an object, and they each access a critical section of code. I want to restrict access to the section so that in one method, I allow multiple threads to access the critical section. In the other method, I want only one thread to have access. If a caller calls the second method, it should lock out all clients from accessing the critical section in either of the two functions. Here is the basic structure of the class:

class ClassThatNeedsFixing
{
public:
// Will allow many concurrent threads through, unless there is a
// call to the other method.
void AllowMany() {
// Here is the critical section that must be protected
...
}
// Will lock out any client, including callers to the other method.
void AllowOne() {
// Here is the critical section that must be protected
...
}
private:
// Assume there are members here that need protecting
// above.
...
};
In order to solve this problem, you are provided with two classes: Mutex and Semaphore. They have the standard behavior of the concepts that share their class names. Here are the public interfaces for each of these classes:
class Mutex
{
public:
Mutex();
void Acquire();
void Release();
};
class Semaphore
{
public:
// At it's creation, one can specify the count
// of the semaphore.
Semaphore(unsigned int count);
void Acquire();
void Release();
};

Fix the ClassThatNeedsFixing implementation so that the critical section is protected.

Your solution will be graded on flexibility and robustness (i.e., we should be able to re-use your solution in a generic case and it should be exception safe). You are allowed to create as many classes/objects/templates/etc that you need. Feel free to use the STL if necessary. Document your code as you would for real-world maintainability.

Given two strings find the combination of strings which can be interleaved

e.g. i/p: if "AB" and "CD" are two strings
o/p:
ABCD
ACBD
ACDB
ACBD
CABD
CDAB

find the kth largest sum(a+b) possible where a in A, and b in B.

Given 2 Sorted arrays A, B in decreasing order of size m and n respectively and a number k, such that 1 <= k <= m*n. You need to find the kth largest sum(a+b) possible where a in A, and b in B.


Algorithm:
Take 0th index value from 1st array & 1st index value from 2nd array store it in S1
Now 0th index value from 2nd array & 1st index value from 1st array , store in S2
Also stores starting & ending index of each array -take care-off

iniatlize maxsum variable to a[0]+b[0] 
Keep checking until we found kth sum from array a & b where a is from 1st & b is from 
if s1>s2 then increment array b lastindex untill its equal to length of this array  & update maxsum=s1
else then increment array a lastindex until its equal to length of this array
maxsum=s2;

Finally Return maxsum;

2nd array.

#include<stdio.h>

int k_sum(int A[],int B[],int m,int n,int k){
	int indexA = 1;
	int indexB = 1;
	int i,s1,s2,sA=0,sB=0;
	int maxsum = A[0] + B[0];

	for(i=0;i<k-1;i++)
	{
		s1 = A[sA] + B[indexB];
		s2 = A[indexA] + B[sB];

		if(s1 >= s2){
			if(indexB == n-1){
				indexB = sB + 1;
				++sA;
			}
			else{
			++indexB;
			}
			maxsum = s1;
		}
		else{
			if(indexA == m-1){
				indexA = sA + 1;
				++sB;
			}
			else{
			++indexA;
			}
			maxsum = s2;
		}
	}

	return maxsum;
}

int main(){
	int A[5]= {10,9,6,4,3};
	int B[6] = {15,13,12,10,78,5};
	int k=10;
	printf("%d \n",k_sum(A,B,5,6,10));
		return 0;
}

Time Complexity O(K) K=M*N M,N are length of length of array s1,s2

Space Complexity O(1)

https://ideone.com/2IxZX

Run Here https://ideone.com/5Zy8B 

find three numbers a,b and c in an unsorted array of integer such that a^2+b^2=c^2 efficiently

Design an algorithm to find the best times to buy and sell the sock to maximize the benifit

Some times back A guy From Chennai Named praveen send me this interesting problem. but some one recently send me mail for the same to solve it efficiently so thought to posting it.problem is really interesting and if after epending soem time with problem someone can come with efficient solution then its really fun isn't it :) In first look problem is not easy although i am sure most of geeks would already have done the same problem efficiently but in direct way that i will show below how we can transform this probelm into simple array probelm.

Problem Statement

You have an array for which the ith element is the price of a given stock on day i.If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell.
or to maximize the benefit ?

Problem Solving Approach

The very first think that comes to mind is that finding the minimum and maximum value would do, but it does have a hidden restriction, that is:

Contraint: You must buy before you can sell. ohhh No i need some more info or i have to trick :)

Hint: Find i and j that maximizes Aj - Ai, where i <= j. There is an obvious O(N2) solution, Algorithm for this Use two loops. In the outer loop, pick elements one by one and in the inner loop calculate the difference of the picked element with every other element in the array and compare the difference with the maximum difference calculated so far.outer loop will run for the buy price/day & innner loop will run for seling price/day . #include

int MaximumBenefit(int arr[], int arr_size)
{
int max_diff = arr[1] - arr[0];
int buy, sell;
for(buy = 0; buy < arr_size; i++) { for(sell= buy +1; sell< arr_size; j++) { if(arr[sell] - arr[buy] > max_diff)
max_diff = arr[sell] - arr[buy];
}
}
return max_diff;
}

int main()
{
int arr[] = {2, 3, 10, 6, 4, 8, 1};
printf("Maximum difference is %d", MaximumBenefit(arr, 7));
getchar();
return 0;
}

Time Complexity: O(n^2)
Time Complexity: O(1)

Can't we reduce the time compelxity yes in fact we can do better in just
O(N).And ofcourse this the hidden part of problem but this how computer science can applied to real life probelms to slove it efficiently & get maximum benefits isn't it ? Now i can say if you will do some twaek with your mind , you will able to come up with nice O(N) linear tiem solution :) start thinking whats the main think we requirs to solve it ? what we have to maximiz e? whats the contrint ?

Algorithm is simple
In this method, instead of taking difference of the buying price with every other selling price , we take the difference with the minimum element found so far. So we need to keep track of 2 things:
1) Maximum difference found so far (max_diff).
2) Minimum number visited so far (min_element). thats starting such index from oth location that has minimum value

so as said aobve to solve this problem efficiently, you would need to track the minimum value's index. As you traverse, update the minimum value’s index when a new minimum is met. Then, compare the difference of the current element with the minimum value. Save the buy and sell time when the difference exceeds our maximum difference (also update the maximum difference).

int MaximumBenefit(int stocksprice[], int size)
{
int min = 0;
int maxDiff = 0;
int buy=0,sell=0;
for (int i = 0; i < size; i++) { if (stocksprice[i] < stocksprice[min]) min = i; int diff = stocksprice[i] - stocksprice[min]; if (diff > maxDiff)
{
buy = min;
sell = i;
maxDiff = diff;
}
}
return maxDiff;
}


Time Complexity O(N)
Space Complexity O(1)
Run Here https://ideone.com/L1VEf

Coin Denomination Problem

Let us say we have an amount we have to pay someone: say $97. The given currency has notes worth $1, $5, $10 and $50. Now, what is the minimum number of currency notes with which the amount can be made? In this case, its eight: two $1 notes, a $5 note, four $10 notes and a $50 notes - eight in all.

If a computer had to solve the same problem, how would it do it? Let us see below. ‘Denomination’ refers to the list of available currency notes: $1, $5, $10 and $50 in this case - each note is a denomination.

In General

Problem: We are given a set of denominations d1,d2,d3,...,dn in increasing order. (Without loss of generality) we assume also that d1=1 (that is, there is always a $1 note, and that is the first denomination) so that it is always possible to produce all amounts from the given denominations. We are also given an amount of money amt. We must use a minimum number of coins (or currency notes) of the given denominations to produce amt.

Great Info http://www.seeingwithc.org/topic1html.html

You must partition the cities into two subsequences (not necessarily contiguous) such that person A visits all cities in the first subsequence (in order), person B visits all cities in the second subsequence (in order), and such that the sum of the total distances travelled by A and B is minimized.

Two-Person Traversal of a Sequence of Cities. You are given an ordered sequence of n cities, and the distances between every pair of cities. You must partition the cities into two subsequences (not necessarily contiguous) such that person A visits all cities in the first subsequence (in order), person B visits all cities in the second subsequence (in order), and such that the sum of the total distances travelled by A and B is minimized. Assume that person A and person B start initially at the first city in their respective subsequences.

Recursion Relation: We recurse on C(i; j), the minimum distance traveled if person A ends at city
i and person B ends at city j. Assume WLOG i < j. The relation is:
{ to j-1 //end
{ sum d(k, k + 1) if i = 0
{ for (k=1) //start
C(i; j) =
{ min 0
where d(i; j) is the distance between cities i and j.
Running Time: There are n2 entries in C(i; j) and lling in each entry takes O(n) for a total of O(n3).

Refrence http://people.csail.mit.edu/bdean/6.046/dp/
http://courses.csail.mit.edu/6.006/fall10/handouts/dpproblems-sol.pdf

Given a number, come up with all of the possible ways to insert '+' and '-' in that number.

for example given 123, possible answer would be

1+23
1+2+3
1-23
1-2+3
1-2-3
1+2-3
12+3
12-3

Stacking The Box Give an algorithm for creating the highest possible stack of boxes with the constraint that if box bj is stacked on box bi,

You are given a set of boxes b1 to bn. Each box bj has an associated width wj , height hj and depth dj. Give an algorithm for creating the highest possible stack of boxes with the constraint that if box bj is stacked on box bi, the 2D base of bi must be larger in both dimensions than the base of bj . You can of course, rotate the boxes to decide which face is the base, but you can use each box only once.
For example, given two boxes with h1 = 5;w1 = 5; d1 = 1 and h2 = 4;w2 = 5; h2 = 2, you should orient box 1 so that it has a base of 5x5 and a height of 1 and stack box 2 on top of it oriented so that it has a height of 5 for a total stack height of 6.