Given an array A[] and a integer num. Find four no.s in the array whose sum is equal to given num.

Algorithm :

Naive Algorithm Will O(N^4) Use Four Loop & keep Checking for all four elements.its so Naive ,easily understood-able..

Algorithm:
Little Efficient O(N^3).
Sort the input array. O(nlogn)
Then take 4 pointers p1,p2,p3,p4 where
0<=p1<=n-3               1st loop
p1+1<=p2<=n-2       1st inner loop                                                    

in loop set p3=p1+ & p4=n-1
( e.g. Take 3 Pointer Pointing to three successive indexes from starting  & 4th Pointer pointing to n-1th position. )
Now use same algo we used to check for two elements in sorted array whose sum equals to given element or not 3rd Inner Loop

Most Efficient O(N^2)

Algorithm:
Create an array of all possible PAIR sums..that would be done in O(n^2)
Sort the Above array of size n^2 that can be done in.O(n^2log(n)) .
Then Search this array for two pairs..that sum to the required value..this can be done by maintaining two pointer One at the starting index..and other at the highest index..and moving them accordingly..(if sum of pair exceeds given value..move up highest value pointer..else move down..lowest value pointer) .it Will take O(n)

Total Time Complexity Will be O(n^2logn) +O(nlogn) +O(n)=O(n^2logn).
Space Complexity O(N^2).

find the minimum number of platforms so that all the buses can be placed as per their schedule.

At a bus-station, you have time-table for buses arrival and departure. You need to find the minimum number of platforms so that all the buses can be placed as per their schedule.


Example

Bus         Arrival         Departure 
BusA        0900 hrs        0930 hrs
BusB        0915 hrs        1300 hrs
BusC        1030 hrs        1100 hrs
BusD        1045 hrs        1145 hrs

Algorithm

Its simple dynamic programming question that calculate the 

number of buses at station at any time(when a bus comes or 

leaves). Maximum number in that pool will be nothing but 

the maximum number of buses at the bus-station at any time

,which is same as max number of platforms required.

So first sort
all the arrival(A) and departure(D) time in an int array. 

Please save the corresponding arrival or departure in the 

array also.Either you can use a particular bit for this 

purpose or make a structure. After sorting our array will

look like this: 

0900    0915    1930    1030    1045    1100    1145    1300
A       A       D       A       A       D       D       D

Now modify the array as put 1 where you see A and -1 where you see D.
So new array will be like this:
1              1            -1              1               1            -1            -1              -1


And finally make a cumulative array out of this:
1            2              1               2                3            2               1                0


Your solution will be the maximum value in this array. Here it is 3.


I think that code for this will not be complex so I am skipping that part.
The complexity of this solution depends on the complexity of sorting.


Also we don not need to create a cumulative array or an array with 1 and -1;
you just need a counter (cnt) initialized at '0'. Whenever, you find an 'A' in
arrival-departure array, increment cnt by 1. Compare it with maximum value (max);
if it is greater than max, make max equal to cnt. If you get a 'D' in arrival-departure
array, decrement cnt by 1. At the end, return 'max'.

Time Compelxity O(nlogn)

Space Complexity O(1) 

find at what time the maximum number of people will be in the party .

Found This Question on One of the Forum :D & posting here as thought it  seems to be something interesting :) There is a list containing the checkin and checkout time of every person in a party . The checkin time is in ascending order while the checkout is random .

Eg:

                       Check_in                Check_out

Person 1             8.00                          9.00

Person 2             8.15                          8.30

Person 3             8.30                          9.20

and so on ...Now , give an optimized solution to find at what time the maximum number of people will be in the party . 

Algorithm

It has the same Algorithm  That  We have been used to solve Bus-Station Problem :)

Time Compelxity O(nlogn)

Space Complexity O(1) 

Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen.

Basic Idea is run around random number generator & we need to take care of that so before moving forward we need to understand how random number generation works 

lets say you wants to generate random number between i to j e.g. [ i,j ). One standard pattern for accomplishing this is:

   (int)(Math.random() * ((Max - Min) 

This returns a value in the range [0,Max-Min).

Now you need to shift this range up to the range that you are targeting. You do this by adding the Min value.

     Min + (int)(Math.random() * ((Max - Min)

But, this is still doesn't include Max and you are getting a double value. In order to get the Max value included, you need to add 1 to your range parameter (Max - Min) and then truncate the decimal part by casting to an int. This is accomplished via:
And there you have it. A random integer value in the range [Min,Max], or per the example [5,10]:

Min + (int)(Math.random() * ((Max - Min) + 1)) 

The java Math library function Math.random() generates a double value in the range [0,1). Notice this range does not include the 1.

In order to get a specific range of values first you need to multiply by the magnitude of the range of values you want covered.
For example if you want [5,10] you need cover 5 integer values so you use
You now will get a value in the range [Min,Max). Following our example, that means [5,10):
Math.random() * ( Max - Min )
Math.random() * 5 This would return a value in the range [0,5)
Min + (Math.random() * (Max - Min))
5 + (Math.random() * (10 - 5))
Min + (int)(Math.random() * ((Max - Min) + 1))
5 + (int)(Math.random() * ((10 - 5) + 1))

Algorithm:
 
Our first instinct on this problem might be to randomly pick elements 
from the array and put them into our new subset array. But then, what 
if we pick the same element twice? Ideally, we’d want to somehow “shrink” 
the array to no longer contain that element. Shrinking is expensive though
because of all the shifting required.
 
Instead of shrinking / shifting, we can swap the element with an element 
at the beginning of the array and then “remember” that the array now only 
includes elements j and greater. That is, when we pick subset[0] to be 
array[k], we replace array[k] with the first element in the array. When 
we pick subset[1], we consider array[0] to be “dead” and we pick a random
element y between 1 and array.size(). We then set subset[1] equal to 
array[y], and set array[y] equal to array[1]. Elements 0 and 1 are
Solution:
 
class Uniform_RandomNumberGenerator
{
 /* Random number between lower and higher, inclusive */
  public static int rand(int lower, int higher)
 {
     return lower + (int)(Math.random() * (higher - lower + 1));
 }

 /* pick M elements from original array. Clone original array so that
 * we don’t destroy the input. */

 public static int[] pickMRandomly(int[] original, int m)
{
 int[] subset = new int[m];
 int[] array = original.clone();
  for (int j = 0; j < m; j++)
  {
   int index = rand(j, array.length - 1);
   subset[j] = array[index];
   array[index] = array[j]; // array[j] is now “dead”
  }
   return subset;
}

public static void main(String a[])

{  int ar[]=new int[]{2,5,3,1,4};
   int br[]=new int[5];
   br=pickMRandomly(ar,5);//n-1
      System.out.println();
   for(int i=0;i<br.length;i++)
   System.out.print(br[i] + " " );
}

}
Time Complexity: O(N)
Space Complexity: O(N)
Run Here https://ideone.com/RcBmx 
 

Write a method to shuffle a deck of cards. It must be a perfect shuffle - in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect.

Basic Idea is run around random number generator & we need to take care of that so before moving forward we need to understand how random number generation works 

lets say you wants to generate random number between i to j e.g.
[ i,j ) excluding upper limit. One standard pattern for accomplishing this is:

Min + (int)(Math.random() * ((Max - Min) + 1))

The java Math library function Math.random() generates a double value in the range [0,1). Notice this range does not include the 1.


In order to get a specific range of values first you need to multiply by the magnitude of the range of values you want covered.

Math.random() * ( Max - Min )

This returns a value in the range [0,Max-Min).


For example if you want [5,10] you need cover 5 integer values so you use

Math.random() * 5 This would return a value in the range [0,5)

Now you need to shift this range up to the range that you are targeting. You do this by adding the Min value.

Min + (Math.random() * (Max - Min))

You now will get a value in the range [Min,Max). Following our example, that means [5,10):

5 + (Math.random() * (10 - 5))

But, this is still doesn't include Max and you are getting a double value.
In order to get the Max value included, you need to add 1 to your range parameter (Max - Min) and then truncate the decimal part by casting to an int. This is accomplished via:

Min + (int)(Math.random() * ((Max - Min) + 1))

And there you have it. A random integer value in the range [Min,Max],
or per the example [5,10]:

5 + (int)(Math.random() * ((10 - 5) + 1))

Algorithm:

This is a very well known algorithm known as Knuth-Shuffle. If you aren’t one

of the lucky few to have already know this algorithm, read on.Let’s start 

with a brute force approach: we could randomly selecting items and put them 

into a new array. We must make sure that we don’t pick the same item twice 

though by somehow marking the node as dead.
 

Array: [1] [2] [3] [4] [5]
Randomly select 4: [4] [?] [?] [?] [?]
Mark element as dead: [1] [2] [3] [X] [5]
 

The tricky part is, how do we mark [4] as dead such that we prevent that 

element from being picked again? One way to do it is to swap the now-dead [4]

with the first element in the array:
 

Array: [1] [2] [3] [4] [5]
Randomly select 4: [4] [?] [?] [?] [?]
Swap dead element: [X] [2] [3] [1] [5]
 

Array: [X] [2] [3] [1] [5]
Randomly select 3: [4] [3] [?] [?] [?]
Swap dead element: [X] [X] [2] [1] [5]
 

By doing it this way, it’s much easier for the algorithm to "know" that the 

first k elements are dead than that the third, fourth, nineth, etc elements 

are dead. We can also optimize this by merging the shuffled array and the 

original array.
 

Randomly select 4: [4] [2] [3] [1] [5]
Randomly select 3: [4] [3] [2] [1] [5]

Working Solution: Its Totally Worthy & Pure Shuffle Used in Our Music Player

class random
{
 
public static void shuffleArray(int[] cards) 
{
 int temp, index;int ar[]=new int[cards.length];
 int count=0;
 for (int i = 0; i < cards.length; i++)
 {
 index = (int) (Math.random() * (cards.length - i)) + i; 
//generate random index between i to n here we don't need to add 1 in last 
//to range as array indexes start at 0 if we add 1 to cards.length-i then 
//we might get index > n-1 which throws array out of index bound exception
 ar[count++]=index;
 temp = cards[i];
 cards[i] = cards[index];
 cards[index] = temp;
 }
  
 for(int i=0;i<ar.length;i++)
   System.out.print(ar[i] + " ");
}
 
public static void main(String a[])
 
{  int ar[]=new int[]{1,2,3,4,5};
    shuffleArray(ar);
      System.out.println();
   for(int i=0;i<ar.length;i++)
   System.out.print(ar[i] + " " );
}
 
}
 

Time Complexity: O(N)

Space Complexity: O(1)

Run Here https://ideone.com/UTk9V 

               https://ideone.com/B0YEn - Read from Consol  

Write a method to count the number of 2s between 0 and n.

#include <stdio.h>
#include <string.h>
#define NUMBER 1
main ()
{
/*This program calculates the number of 2's present in the number x*/

int arr[]={221};
int i=0,count=0;

for(i=0;i<NUMBER;i++)
{
while(arr[i]>0)
{
int rem,quo;
rem=arr[i]%10;
quo=arr[i]/10;
printf("rem= %d and quo=%d \n ", rem,quo);
if(rem==2&&quo==2)
{
count=count+2;

printf("Number is : %d\n",arr[i]);
arr[i]=arr[i]/10;

}
else if(rem==2)
{
count++;
printf("Number is : %d\n",arr[i]);
}
else if(quo==2)
{
count++;
printf("Number is : %d\n",arr[i]);
arr[i]=arr[i]/10;
}
arr[i]=arr[i]/10;
}
}
printf("THe number of 2's are : %d\n",count);
printf("\n\n\n");
}

Run Here http://ideone.com/JUnXva

Design an algorithm that takes strings S and r and returns if r matches s. (Assume r is a well-formed regular expression.)

Before starting solving we need to think about some test cases  like .,*,?,^,$  e.g about a regular expression grammar.

A regular expression is a sequence of characters that defines a set of
matching strings.For this problem , we define a simple subset of a full
regular expression Language.

Alphabetical and numerical characters match themselves. 

 1.For example aW9 will match that string of 3 letters wherever it appears.

The meta-characters ". and $ stand for the beginning and end of the
string. For example, .....aW9 matches aW9 only at the start of a string
aW9$ matches aW9 only at the end of a string, and ^aW9$ matches a string only if it is exactly equal to aW9.

2.The metacharacter . matches any single character. For example,

a.9 matches a89 and xyaW9123 but not aw89.

3.The metacharacter * specifies a repetition of the single previous

period or a literal character. For example，a. *9 matches aw89.
By definition, regular expression r matches string s if s contains a
substring starting at any position matching r. For example, aW9 and a. 9
match string xyaW9123 but .....aW9 does not.

Algorithm:

The key to solving this problem is using recursion effectively.
If the regular expression r starts with "', then s must match the remainder of r; otherwise, s must match r at some position.

Call the function that checks whether a string S matches r from
the beginning matchHere. This function has to check several cases

(1.) Iength-O regular expressions which match everything, 

(2.) a regular expression starting with a *match, 

(3.) the regular expression $，and 

(4.) a regular expression starting with an alphanumeric character or dot.
Of these, (1.) and (3.) are base cases, (4.) is a check followed by a call
to matchHere, and (3.) requires a new matchStar function.

More Info http://swtch.com/~rsc/regexp/regexp1.html

Given a BST and a number, Find the closest node to that number in the BST. Give an algorithm for that. Let there be binary search tree having nodes with values 12,34,64,23,64,25,76,6 and the number given is 28, then the answer would be 25 as it is the closest node.

We Have to Solve It Efficiently O(Logn) is Desired :)

Given a BST and a number, Find the closest node to that number in the BST. Give an algorithm for that. Let there be binary search tree having nodes with values 12,34,64,23,64,25,76,6 and the number given is 28, then the answer would be 25 as it is the closest node.

Given a BST and a number, Find the closest node to that number in the BST. Give an algorithm for that. Let there be binary search tree having nodes with values 12,34,64,23,64,25,76,6 and the number given is 28, then the answer would be 25 as it is the closest node.

Given a class Card{int value, int suit, Color color}, Write a method Card[] GetUniqueElements(Card[] cards) which gives all the unique Card Objects .

For Example  (1,1,R), (1,2,G), (1,1,R), (2,2,R), (2,2,B) where parameters are ( card value, card suit, card color) respectively where R=1 & G=2 &B=3 (card color) etc.

Answer should be (1,1,R),(1,1,R), (2,2,R), (2,2,B)

Write a function to find the longest common prefix string amongst an array of strings

Simple Algorithm Will Go Like This:

Algorithm:Longest Common Prefix ( LCP)

1.Take a String From Array Whose length is Minimum else

  you might get exception if tries to access array element

  outside range.why this will work because if there exist 

  a common prefix then it will be the desired answer .

 Example like in case of "shash" ,"shank","shashank" LCP will be "sha"

 for this string "ab", "abc", "def" ,"defgh", "sha" LCP will be NULL

2.Keep Comparing reamining string character by character with 1st selected string  if mismatch occurs at any position i then append 1st string to output string.

Working Code

String findLongPrefix(String [] str) 

{
                StringBuilder strBuilder = new StringBuilder();
                
                char [] firstStr = str[0].toCharArray();
                for(int i=0; i< str[0].length(); i++ ) {
                        boolean found = true;
                        for(String str: str) {
                                if(str.charAt(i) != firstStr[i]) {
                                        found = false;
                                        break;
                                } 
                        }
                        
                        if(found) {
                                strBuilder.append(firstStr[i]);
                        } else 
                                break;
                        
                }
                
                return strBuilder.toString();
        }

Time Complexity O(N*M-1)=O( Where N is Length of 1st Smallest String 

and M is Number of remaining string in string array so it will run

upto length of array-1

Space Complexity O(1)

Write a function int interval_unfold_count(int n); that returns the length of the shortest sequence of operations resulting in either L or R being equal to N.

Two integer variables L and R are initially equal to 0 and 1 respectively (i.e. L = 0 and R = 1).
The values of these variables can be manipulated using the following operations: operation 'L' is the assignment L = 2*L-R, operation 'R' is the assignment R = 2*R-L.
Given an integer N we want to find what is the shortest sequence of such operations necessary to make either L or R equal to N. For example, given N = 21, the following sequence of operations:
(initially L = 0, R = 1),
L = 2*L-R (makes L = -1, R = 1),
L = 2*L-R (makes L = -3, R = 1),
R = 2*R-L (makes L = -3, R = 5),
L = 2*L-R (makes L = -11, R = 5),
R = 2*R-L (makes L = -11, R = 21)
makes one of the variables (namely R) equal to N (i.e. after the last operation N = R = 21). This sequence consists of 5 operations and there is no shorter sequence that would make either L or R equal 21.
Write a function int interval_unfold_count(int n);
that returns the length of the shortest sequence of operations resulting in either L or R being equal to N. For example, given N = 21 the function should return 5.

A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. o Delection of the smallest element o Insertion of an element if it is not already present in the set

Which of the following data structures can be used for this purpose?
(a) A heap can be used but not a balanced binary search tree
(b) A balanced binary search tree can be used but not a heap
(c) Both balanced binary search tree and heap can be used
(d) Neither balanced binary search tree nor heap can be used

A self-balancing balancing binary search tree(Its *BST not BT )* containing 
n items allows the lookup, insertion, and removal of an item in O(log n) 
worst-case time. Since it’s a BST, we can easily find out minimum element 

in O(nlogn). please note that if it would have been simple BST not Balnced

BST then our complexity to lookup will changes to O(n) in worst case when

tree is skewed but as question say balanced BST (check out AVL/RB Tree) they 
gureentte that look-up will O(logn) only why its true & will work you need 
to go through tree rotation (thats used to make tree balanced & reduce 
height ).

Since Heap is a balanced binary tree (or almost complete binary tree but not 
balanced BST ), insertion complexity for heap is O(logn). Also complexity to 
get minimum in a min heap is O(logn) because removal of root node causes a 
call to Heapify (after removing the first element from the array) to maintain

the heap tree property. But a heap cannot be used for the above purpose as 

the question says – insert an element if it is not already present because of 

this constraint we can't use min-heap as well . For a heap, we cannot find out

in O(logn) if an element is present or not as its balanced Binary Tree(BT) , 

we have to search all the elements e.g.in both  left & right sub-tree up-to 
leaf so in worst case it will take O(n) time to search an element weather 
ist present or not , then its present leave it  else insert as a last node & 
call heapify (take O(logn)) so tottal time complexity will be O(n)+ O(logn) 
=O(n) 

      search+heapify =O(search) 

so why correct answer is only Balanced Binary Search Tree 

Given an unsorted array of size n. Array elements are in range from 1 to n. One number from set {1, 2, …n} is missing .Find the missing elements ?

Given a string, find the length of the longest substring without repeating characters.

 For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 * 99. Find the largest palindrome made from the product of two 3-digit numbers.

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 * 99. Find the largest palindrome made from the product of two 3-digit numbers.

Count the number of islands in an ocean where ocean is represented as a grid. Cells, having a part of any island, are marked as 'x' otherwise 'o'.

Design an algorithm to perform operation on an array Add(i,y)-> add value y to i position sum(i) -> sum of first i numbers we can use additional array O(n) and worst case performance should be O(log n) for both operation

Design an algorithm to perform operation on an array
Add(i,y)-> add value y to i position
sum(i) -> sum of first i numbers
we can use additional array O(n) and worst case performance should be O(log n) for both operation

Practice Problem For Binary Index Tree :

http://problemclassifier.appspot.com/index.jsp?search=BIT&usr=
http://problemclassifier.appspot.com/index.jsp?search=tree&usr=

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.

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.

Give a data-structure which will guarantee O(log n) time per operation.

Complete binary tree as an efficient data-structure

You are given an array of size n(n being a power of two). All the entries of the array are initialized to zero. You have to perform a sequence of the following online operations :

* (i) Add(i,x) which adds x to the entry A[i].
* (ii) Report sum(i,j) = sum of the entries in the array from indices i to j for any 0 < i < j <= n.

It can be seen easily that we can perform the first operation in O(1) time whereas the second operation may cost O(n) in worst case. Your objective is to perform these operations efficiently. Give a data-structure which will guarantee O(log n) time per operation. (The title of the problem is a hint).

Merge the two Binary Search Trees in time O(log m + log n)

You are given two height balanced binary search trees T and T', storing m and n elements respectively. Every element of tree T is smaller than every element of tree T'. Every node u also stores height of the subtree rooted at it. Using this extra information how can you merge the two trees in time O(log m + log n) (preserving both the height balance and the order)?

Determine whether the kth largest element of the heap is greater than x or not.

Consider a binary heap containing n numbers (the root stores the greatest number). You are given a positive integer k < n and a number x . You have to determine whether the kth largest element of the heap is greater than x or not. Your algorithm must take O(k) time. You may use O(k) extra storage.

Searching for a friend

You are standing at a crossing from where there emerge four roads extending to infinity. Your friend is somewhere on one of the four roads. You do not know on which road he is and how far he is from you. You have to walk to your friend and the total distance traveled by you must be at most a constant times the actual distance of your friend from you. In terminology of algorithms, you should traverse O(d) distance, where d is the distance of your friend from you.

Searching For Celebrity

Celebrity is a person whom everybody knows but he knows nobody. You have gone to a party. There are total n persons in the party. Your job is to find the celebrity in the party. You can ask questions of the form Does Mr. X know Mr. Y ?. You will get a binary answer for each such question asked. Find the celebrity by asking only O(n) questions.

You are given n real numbers in an array. A number in the array is called a decimal dominant if it occurs more than n/10 times in the array. Give an O(n) time algorithm to determine if the given array has a decimal dominant.

Generating lexial predecessor of a k-subset of set of n elements

Given a file containing 4,300,000,000 integers, how can you find one that appears at least twice

A Theoritical Approach From Programming Pearls

Binary search find an element that occurs at least twice by recursively searching the subinterval that contains more than half of the integers. My original solution did not guarantee that the number of integers is halved in each iteration, so the worst case run time of its log2 n passes was proportional to n·log n. Jim Saxe reduced that to linear time by observing that the search can avoid carrying too many duplicates.

When his search knows that a duplicate must be in a current range of m integers, it will only store m+1 integers on its current work tape;

If more integers would have gone on the tape, his program discards them. Although his method frequently ignores input variables, its strategy is conservative enough to ensure that it finds at least one duplicate.

The algorithm that Bentley is talking about works by repeatedly halving
the candidate range in which the duplicate element must lie. Initially
this range is 0..2^32-1. On each pass it throws away the half of the
range that contains fewer data values and it also throws away the data
lying in that half. Eventually the range decreases to a single value,
which must be a duplicate because the remaining data has at least two
elements. The problem that Bentley notes is that the data may still
have 4 billion elements at this stage! The final improvement he
mentions is that you can throw away data _inside_ the candidate range
as long as you keep enough data around to ensure that at least one
duplicate occurs in it. This is equal to the size of the current
candidate range plus 1!


Another Similer Approach I Found

Create a bit array of length 2^32 bits (initialize to zero), that would be about 512MB and will fit into RAM on any modern machine.

Start reading the file, int by int, check bit with the same index as the value of the int, if the bit is set you have found a duplicate, if it is zero, set to one and proceed with the next int from the file.

The trick is to find a suitable data structure and algorithm. In this case everything fits into RAM with a suitable data structure and a simple and efficient algorithm can be used.
If the numbers are int64 you need to find a suitable sorting strategy or make multiple passes, depending on how much additional storage you have available.

The Pigeonhole Principle -- If you have N pigeons in M pigeonholes, and N>M, there are at least 2 pigeons in a hole. The set of 32-bit integers are our 2^32 pigeonholes, the 4.3 billion numbers in our file are the pigeons. Since 4.3x10^9 > 2^32, we know there are duplicates.

You can apply this principle to test if a duplicate we're looking for is in a subset of the numbers at the cost of reading the whole file, without loading more than a little at a time into RAM-- just count the number of times you see a number in your test range, and compare to the total number of integers in that range. For example, to check for a duplicate between 1,000,000 and 2,000,000 inclusive:

int pigeons = 0;
int pigeonholes = 2000000 - 1000000 + 1; // include both fenceposts
for (each number N in file) {
if ( N >= 1000000 && N <= 2000000 ) { pigeons++ } } if (pigeons > pigeonholes) {
// one of the duplicates is between 1,000,000 and 2,000,000
// try again with a narrower range
}

Picking how big of range(s) to check vs. how many times you want to read 16GB of data is up to you :)

As far as a general algorithm category goes, this is a combinatorics (math about counting) problem.

Given an array[] of integers (+ive , -ive, 0) find the subarray which gives the largest product.

Data Structure Used: Array

Algorithm & Expliantion

Lets us take an array = { 2,-25,4,5,-3,-5}

We take 3 variables P , N , Val

P=1 , N=0 , Val=0

first value is 2 , A[0] which is +ve . So we multiply both P & N with A[0] .
P=2 , N=0

now V[1] = -25 -ve .

We multiply P with -V[1] & N with -V[1] .

P=50
N=0

As V[1] is -ve we swap P & N .
P=0 , N=50

if V[i] == 0
We initialise P=1 , N=0

if( P < 1 ) /* analogous to kadane's algo's if( sumSoFar < 0 ) */ { P=1; N=0; } at every step val = max( val , P ) We proceed in the same fashion till the end . What we are trying to do is to maintain max Positive product so far & max -ve product so far . Hence when we encounter a -ve value we multiply both with - V[i] & then swap as -ve * -ve = +ve -ve * +ve = -ve Working Code #include

int swap(int *a,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}

int main()
{
int a[]={6,-1,2,-33,4,15,-7,28,-9,-10};
int maxp=1,maxn=0;
int i=0;
for(i=0;i<10;i++) { if(a[i]>0)
{
maxp*=a[i];
maxn*=a[i];
}
else
{
maxp*=-a[i];
maxn*=-a[i];
swap(&maxp,&maxn);
}


}

printf("%d",maxp);
}

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

Design An Algorithm to Exhibit Did You Mean Feature of Google Search Engine

When people search at Google, they often type two words without space. For example, instead of typing "binary tree", someone can type "binarytree". Given an input, what is a good way of finding if it is a combination of two valid words e.g. In Directly You have Add Space between two such or if are using some data structure , whene words would have been inserted , you would have mainted a boolen varible to defined the end of word (eod)


An Exanmple Will be Let's say you have a phrase without any spaces - eg. "thisisawesome". Given a dictionary, how would you add spaces in this string?

When people search at Google, they often type two words without space. For example, instead of typing "binary tree", someone can type "binarytree". Given an input, what is a good way of finding if it is a combination of two valid words e.g. In Directly You have Add Space between two such or if are using some data structure , where words would have been inserted , you would have maintained a boolean variable to defined the end of word (eod)
An Example Will be Let's say you have a phrase without any spaces - eg. "thisisawesome". Given a dictionary, how would you add spaces in this string?

        Trie trie = new Trie();
        trie.insert("i");
        trie.insert("this");
        trie.insert("saw");
        trie.insert("is");
        trie.insert("a");
        trie.insert("some");
        trie.insert("awesome");

        String inputString = "thisisawesome";
        String outputString = "";
      
        int left = 0;
        int right = 1;

        while ( right <= inputString.length()) 

        {
            {
                String str = inputString.substring(left,right);
                boolean found = trie.containsKey(str);
                if ( found) 

                {
                    outputString += str;
                    outputString += " ";
                    left += str.length();
                    right = left + 1;
                }

                 else

                 {
                    right++;
                }
            }
        }
      
   

Another Good Working Code  You Can Refer Avinash Solution


Time Complexity O(K) k is length of input string