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.