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.

You are given a String number containing the digits of a phone number.Divide the number into groups such that the quality is maximized.Design an efficient algorithm to return the solution that maximizes the quality.

You are given a String number containing the digits of a phone number
(the number of digits, n, can be any positive integer) . To help you memorize the number, you want to divide it into groups of contiguous digits. Each group must contain exactly 2 or 3 digits. There are three kinds of groups:
• Excellent: A group that contains only the same digits. For example, 000 or 77.
• Good: A group of 3 digits, 2 of which are the same. For example, 030, 229 or 166.
• Usual: A group in which all the digits are distinct. For example, 123 or 90.
The quality of a group assignment is defined as 2 × (number of excellent groups) + (number of good groups)
Divide the number into groups such that the quality is maximized.
Design an efficient algorithm to return the solution that maximizes the quality.

Determine whether the Singly Linked List loops back or ends at a null location in time proportional to the length of the list

You are having a pointer to the head of singly linked list. The list either terminates at null pointer or it loops back to some previous location(not necessarily to the head of the list). You have to determine whether the list loops back or ends at a null location in time proportional to the length of the list. You can use at most a constant amount of extra storage.

Design a Data Structure of size O(n) (e.g. of Given Tree Size n) so that you can answer any such query in O(log n) time.

Given a rooted tree of size n . You receive a series of online queries : "Give nearest common ancestor of u,v " . Your objective is to preprocess the tree in O(n) time to get a data structure of size O(n) so that you can answer any such query in O(log n) time.