Design an algorithm such that maximum number of jobs can be performed in that given time interval.

You are given N jobs with their start and end time mentioned.These jobs may have their timings overlapped.You have to suggest an algorithm such that maximum number of jobs can be performed in that given time interval.

Given a set of n jobs j1, j2, · · · , jn, find a set of compatible jobs with the

maximum weight.
• Each job ji starts at sji and and finishes at fji .
• Each job ji has weight (value) vji .
• Two jobs are compatible if their intervals do not overlap.
In other words, we are trying to find a set of jobs ji1 , ji2 , · · · , jik such that the following is maximized:

sum(vjix) for each x=1 to k

The dynamic programming paradigm gives us two options when examining
each job. The optimal solution either contains the job, or it doesn’t. As
an example, if the optimal solution contains j1, then we pick j1 and find the
optimal solution for jobs compatible with j1. If the optimal solution does
not contain j1, then we find the optimal solution for j2, j3, · · · , jn. (This assumes that the jobs are arranged in order of their finish time, such that fj1
Once we select a job to be a part of the optimal solution, we exclude a
host of other jobs that are incompatible with the selection. To assist in our
definition of an optimal solution, we define jip to be the largest index job,
ip < i, that is compatible with ji. In other words, jip is the job for which
sji − fjip is minimized.

We can then let OPT(i) be the set containing the optimal solution for
jobs j1, j2, · · · , ji. It is defined as follows for each ji:

• Case 1: OPT selects ji
– We cannot select jobs jip+1, · · · , ji−1, so we exclude them from
consideration.
– We recurse and find the optimal solution for jobs j1, j2, · · · , jip by
setting OPT(i) = vji + OPT(ip).

• Case 2: OPT does not select ji
– We recurse and find the optimal solution for jobs j1, j2, · · · , ji−1
by setting OPT(i) = OPT(i − 1).

Since we don’t know which case will return the optimal solution, we must
try both. Once we have calculated both possibilities, we pick the case which
returns the larger set. Now we can create a more compact definition, together
with a simple implementation:

OPT(i) = max{vji + OPT(ip),OPT(i − 1)} | i 1
= 0 | otherwise

The recursive algorithm looks like

COMPUTE_OPT(i):
if i == 0:
return 0
return max {
COMPUTE_OPT(i - 1),
v[j(i)] + COMPUTE_OPT(p(i))
}

The problem with the algorithm as it stands is that a lot of computation is
repeated. This is visualized by looking at the recursive tree structure:

-COMPUTE_OPT(5)
-COMPUTE_OPT(3)
-COMPUTE_OPT(1)
-COMPUTE_OPT(2)
-COMPUTE_OPT(0)
-COMPUTE_OPT(1)
-COMPUTE_OPT(4)
-COMPUTE_OPT(2)
-COMPUTE_OPT(0)
-COMPUTE_OPT(1)
-COMPUTE_OPT(3)
-COMPUTE_OPT(1)
-COMPUTE_OPT(2)
-COMPUTE_OPT(0)
-COMPUTE_OPT(1)

It is easy to see that for even a small set of jobs, the amount of repeated
computation is huge. To avoid this, we introduce memoization, which stores
the values for OPT(i) in a global array as they are calculated. If the value is
needed later, it is simply retrieved from the array, pruning the recursive tree
such that each descent only happens once. The following revised algorithm
implements memoization:
M_COMPUTE_OPT(i):
if M[i] != null:
return M[i]
if i == 0:
M[0] = 0
else:
M[i] = max {
M_COMPUTE_OPT(i - 1),
v[j(i)] + M_COMPUTE_OPT(p(i))
}
return M[i]

This memoized version saves valuable computational resources, but each
recursive call adds overhead. The algorithm runs in O(n) time, but its recursive
nature makes it bulky.

We can eliminate the overhead of recursion by constructing an iterative (nonrecursive)
algorithm that builds a bottom-up list of the values.
M[0] = 0
for i = 1 to n:
M[i] = max {
M(i - 1),
v[j(i)] + M(p(i))
}
This is obviously linear, and without the added computational weight of
a recursive algorithm. To reconstruct the solution, we simply run backwards
through the array (take M[n] and compare to M[n-1], etc.).
PRINT_SOLUTION(i):
if i == 0:
return
if v[j(i)] + M[p(i)] == M[i]:
print j(i)
PRINT_SOLUTION(p(i))
else:
PRINT_SOLUTION(i - 1)

Time Complexity O(N)
Space Compleixty O(N)


Resources
http://en.wikipedia.org/wiki/Interval_scheduling
http://pages.cs.wisc.edu/~shuchi/courses/787-F09/scribe-notes/lec3.pdf
http://www.cs.cornell.edu/courses/cs482/2007sp/dynamic.pdf
http://www.cs.uiuc.edu/class/sp08/cs473/Lectures/lec10.pdf
http://www.cs.sfu.ca/~ssa121/personal/spring08/705/dp.pdf
http://www.cs.uiowa.edu/~hzhang/c31/6-dynamic.pdf
classes.soe.ucsc.edu/.../06dynamic-programming-weighted-interv-sched.ppt
http://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/06dynamic-programming.pdf
http://www.cse.psu.edu/~asmith/courses/cse565/F08/www/lec-notes/CSE565-F08-Lec-17.pdf

Fill the rectangle with squares

Given a rectangle with known width and height, design an algorithm to fill the rectangle using n squares(n is integer given) and make sure in the result the wasting area is minimized. Length of square doesn't have to be integer.
i.e, given width=3,height=2,n=5, one solution is that rectangle can be filled with five 1x1 squares and the wasting area is 1. Another solution could be filled with five 0.9x0.9 squares, but the wasting area is more than first solution.

Given two arrays of numbers, find if each of the two arrays have the same set of ntegers ? Suggest an algo which can run faster than NlogN without extra space?

Design a data structure that offers the following operations in O(1) time: e.g. in contant time * insert * remove * contains * get random element (one of Only those elemnt currently present in data structure

we have to think of all possible DS that can do some of the operation in desired complexity then we can come up with some combinations of Data structure so that we can get what question is asking for :)

So its clear O(1) lookup implies a hashed data structure.

By comparison:

* O(1) insert/delete with O(N) lookup implies a linked list.
* O(1) insert, O(N) delete, and O(N) lookup implies an array-backed list
* O(logN) insert/delete/lookup implies a tree(BST) or heap.

we basically need to find out some kind of combinations from above DS .

First I thought About Doubly Linked List instead of Array but soon realized that we won't get desired complexity isn't it ? even we can achieve some of operation in O(1) but how u will make sure all will be done in O(1) ??

so lets Consider a data structure composed of a hashtable H and an array A. The hashtable keys are the elements in the data structure, and the values are their positions in the array.

here can be possible way to achieve the desired time complexity

1. insert(value): append the value to array and let i be it's index in A. Set H[value]=i.

2. remove(value): We are going to replace the cell that contains value in A with the last element in A. let d be the last element in the array A at index m. let i be H[value], the index in the array of the value to be removed. Set A[i]=d, H[d]=i, decrease the size of the array by one, and remove value from H.

3. contains(value): return H.contains(value) no doubt in this :)

4. getRandomElement(): let r=random(current size of A). return A[r].
e.g. index=random()%size of current array will generate index in range & then we can return element at given index . this will make sure that this function will generate the random number from  present elements of data structure only.

Time Complexity Will be O(1)
Space Complexity O(N) , N is size of hashtable

Design a data structure that offers the following operations in O(1) time: * insert * remove * contains * get random element (one of Only those elemnt currently present in data structures)

design the algorithm which computs the placements of 21 triomino that cover 8*8 chess board

Here is Another One :)

A triomino is formed by joining three unit-sized squares in m L-shape.
Amutiled chessboard(henceforth 8 x 8M board) is made up of 64 unitsized
squares arranged in an 8 × 8 square minus the topleft square. design the algorithm which computs the placements of 21 triomino that cover 8*8 chess board.

Design a program that takes an Image and a collection of m x m-sized tiles and produce a mosaic from the tiles that resembles the image.

Friend of Mine Who Appeared For Google sometimes back Told Me about this intersteting Problem:) I did some lazyness to post the question here . Are you guys are able to think about approach ? I Not Going to do no More Spoon Feeding Here :) so Try It Out

Hint :) There is Interesteing Math Behind It. Are You able to Think out the cloest point k-dimensional ? if you are able to come up with approach & complexity analysis thats enough to Crack Google

Joseph Perumtation Problem

“n” people are seated around in a circle. At each step, the “m”th person is eliminated from the circle. The next iteration continues from the person next to the eliminated person. In the end, there will be only one person remaining. Given “n” and “m”, write a program to find out the person who will be remaining at the end

Given a list of Tagalog words as a String[], return the same list in Tagalog alphabetical order

A Reader send me this problem . Thanks to Him for this intersteing Problem. so i am going to posting here.

In the first half of the 20th century, around the time that Tagalog became the national language of the Philippines, a standardized alphabet was introduced to be used in Tagalog school books (since then, the national language has changed to a hybrid "Pilipino" language, as Tagalog is only one of several major languages spoken in the Philippines).

Tagalog's 20-letter alphabet is as follows:

a b k d e g h i l m n ng o p r s t u w y

Note that not all letters used in English are present, 'k' is the third letter, and 'ng' is a single letter that comes between 'n' and 'o'.

You are compiling a Tagalog dictionary, and for people to be able to find words in it, the words need to be sorted in alphabetical order with reference to the Tagalog alphabet. Given a list of Tagalog words as a String[], return the same list in Tagalog alphabetical order

1)


{"ang","ano","anim","alak","alam","alab"}

Returns: {"alab", "alak", "alam", "anim", "ano", "ang" }

A few "A" words that are alphabetically close together.
2)


{"siya","niya","kaniya","ikaw","ito","iyon"}

Returns: {"kaniya", "ikaw", "ito", "iyon", "niya", "siya" }

Common Tagalog pronouns.
3)


{"kaba","baka","naba","ngipin","nipin"}

Returns: {"baka", "kaba", "naba", "nipin", "ngipin" }

Find three numbers in an array which forms a maximum product (for signed integers)

Naive Solution Requires sorting the input data & then finding product of 3 largest from the last isn't it can't we do it linear time :0

Data Structure Used: Array

Algorithm:
The solution involves in finding three maximum and two minimum numbers. If the minimum numbers are negatives and if their product is greater than the two maximum number's product, then they have to considered for maximum product.

so let l1,l2,l3 are the three maximum number & s1,s2 are the minimum numbers
Our Solution will be maxproduct=max( l1*s1*s2,l1*l2*l2)

#include <iostream>
using namespace std;
 
#define MAX 10
 
int* MaxProduct(const int input[], const int size)
{
 int* output = new int[3];
 int negative = 0;
 for(int i = 0; i < 3; i++)
 {
  output[i] = -999999;
 }
 int min[2] = {0,0};
 
 for(int i=0;i<size;i++)
 {
  // find two smallest negative numbers
  if(input[i] <= 0)
  {
   if(input[i] < min[0])
   {
    min[1] = min[0];
    min[0] = input[i];
   }
   else if(input[i] < min[1])
   {
    min[1] = input[i];
   }
   negative++;
  }
 
  // find three largest positive numbers
  if(input[i] > output[0])
  {
   output[2] = output[1];
   output[1] = output[0];
   output[0] = input[i];
  }
  else if(input[i] > output[1])
  {
   output[2] = output[1];
   output[1] = input[i];
  }
  else if(input[i] > output[2])
  {
   output[2] = input[i];
  }
 }
 
 if(size != negative)
 {
  if((min[0] * min[1]) > (output[0] * output[1]) ||  

(min[0] * min[1]) > (output[1] * output[2]))
  {
   output[1] = min[0];
   output[2] = min[1];
  }
 }
 
 return output;
}
 
int main()
{ 

const int input[MAX]={-6,-1,-2,-33,-4,-15,-7,-28,-9,-10};
 int* result = 0;
 result = MaxProduct(input,MAX);
 
 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result[i] << endl;
 }
 

const int input1[MAX] = {0,-1,-2,-33,4,15,-7,-28,-9,-10};
 int* result1 = 0;
 result1 = MaxProduct(input1,MAX);
 
 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result1[i] << endl;
 }
 
 const int input2[MAX] = {0,-1,-2,-33,-4,-15,-7,-28,-9 

,-10};
 int* result2 = 0;
 result2 = MaxProduct(input2,MAX);
 
 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result2[i] << endl;
 }
 
 const int input3[MAX] = {6,1,2,33,4,15,7,28,9,10};
 int* result3 = 0;
 result3 = MaxProduct(input3,MAX);
 
 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result3[i] << endl;
 }
 
 return 0;
}

Time Complexity O(N) As we Done only Single Pass Over Array
Space Complexity O(1)
Run Here https://ideone.com/4zhiE