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

Painter Partition Problem

You have to paint N boards of length {A0, A1, A2 … AN-1}. There are K painters available and you are also given how much time a painter takes to paint 1 unit of board. You have to get this job done as soon as possible under the constraints that any painter will only paint continuous sections of board, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

Find The Number of Unique Path in Maze Where Robot is Sitting at Top-Left Corner & Can Move According to Given Constraints

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid . marked ‘end' in the diagram below.How many possible unique paths are there?

I posted the solution with post because i was aware of such problem earlier :)

Basic Solution,Approach,Algoriothms Using BackTracing

Start form top left corner (say we are at position 1,1 in starting deonted by row=r,column=c (e.g. r=1, c=1 initially) & then will will keep moving untill reach when r=m and c=n e.g. bottom-left corner) writing code for this is simple.

int backtrack(int r, int c, int m, int n) {
if (r == m && c == n)
return 1;
if (r > m || c > n)
return 0;

return backtrack(r+1, c, m, n) + backtrack(r, c+1, m, n);
}

but as normal backtracking problems it inovolves repeated calculations
so is very inefficient in the sense that it recalculates the same solutio n over patah again & again. so we need to use a dynamic programming (DP) technique called memoization akso called top down approach.

const int M_MAX = 10;
const int N_MAX = 10;

int backtrack(int r, int c, int m, int n, int mat[][N_MAX+2]) {
if (r == m && c == n)
return 1;
if (r > m || c > n)
return 0;

if (mat[r+1][c] == -1)
mat[r+1][c] = backtrack(r+1, c, m, n, mat);
if (mat[r][c+1] == -1)
mat[r][c+1] = backtrack(r, c+1, m, n, mat);

return mat[r+1][c] + mat[r][c+1];
}

int bt(int m, int n) {
int mat[M_MAX][N_MAX];
memset(mat, -1, sizeof(mat));
return backtrack(1, 1, m, n, mat);
}

Time Complexity O(M+N)
Space Complexity O(M*N)



Bottom-Up Dynamic Programming More Efficient

As we know The total unique paths at above matrix (r,c) is equal to the sum of total unique paths from matrix to the right (r,c+1) and the matrix below (r+1,c).

(For clarity, we will solve this part assuming an X*Y Matrix)
Each path has (X-1)+(Y-1) steps. Imagine the following paths:

X X Y Y X (move right -> right -> down -> down -> right)
X Y X Y X (move right -> down -> right -> down -> right)
...& so on

Each path can be fully represented by the moves at which we move
right. That is, if I were to ask you which path you took, you could
simply say “I moved right on step 3 and 4.”
Since you must always move right X-1 times, and you have X-1 + Y-1
total steps, you have to pick X-1 times to move right out of X-1+Y-1
choices. Thus, there are C(X-1, X-1+Y-1) paths (e.g., X-1+Y-1 choose
X-1):

(X-1 + Y-1)! / ((X-1)! * (Y-1)!)..

const int M_MAX = 100;
const int N_MAX = 100;

int dp(int m, int n) {
int mat[M_MAX][N_MAX] = {0};
mat[m][n+1] = 1;

for (int r = m; r >= 1; r--)
for (int c = n; c >= 1; c--)
mat[r][c] = mat[r+1][c] + mat[r][c+1];

return mat[1][1];
}

Lets Assume you have M×N sample matrix or grid. so it doen't matter how you traverse the grids, you always traverse a total of M steps. To be more exact, you always have to choose M-N steps to the right (R) and N steps to the bottom (B). Therefore, the problem can be transformed to a question of how many ways can you choose M-N R‘s and N B‘s in these M+N-2 steps. The answer is C(M,N) (or C(M,M-N)). Therefore, the general solution for a m x n grid is C(m+n-2, m-1) & this is our answer.

Time Complexity O(M*N)
Space Complexity O(M*N)


Follow Up: Using Above We Have Only Calculated the number of paths can we print those path as well if yes what will be time complexity.

Avid TV Watcher

Here is a TV avid person. He wants to spend his max time on TV. There are N channels with different program of different length and diff times. WAP so that the person can spend his max time watching TV.Precondition: If that person watches a program, he watches it completely.

Ex:
Channel1:
prog1 – 8:00- 8:30
prog2: 9:00 – 10:00
prog3: 10:15 – 12:00

channel2:
prg1 – 8:15 – 10:00
prg2: 10:30 – 12:00

So in this case max time will be if he watches:

ch2/prg1 + ch1/prg3

Design an algorithm to find the maximum number of apples you can collect ?

As This is Season of Compnies Visiting Collages & my mailbox is full of problems :D Here is Another One

A table composed of N*M cells,each having a certain quantity of apples, is given. you start from the upper-left corner. At each step you can go down or right one cell.Design an algorithm to find the maximum number of apples you can collect ,if you are moving from upper-left corner to bottom-right corner

Yuckdonald's is considering opening a series of restaurants along Quaint Valley Highway (QVH).Give an efficient algorithm to compute the maximum expected total profit subject to the given constraints.

A Reader send me this interestinmg problem some times back & he also confirmed that recently google asked it :)

Yuckdonald's is considering opening a series of restaurants along Quaint Valley Highway (QVH).The n possible locations are along a straight line, and the distances of these locations from the start of QVH are, in miles and in increasing order,m1;m2; : : : ;mn.

The constraints are as follows:

1)At each location,Yuckdonald's may open at most one restaurant. The expected profi t from opening a restaurant at location i is pi, where
pi > 0 and i = 1; 2; : : : ; n.

2)Any two restaurants should be at least k miles apart, where k is a
positive integer.

Give an efficient algorithm to compute the maximum expected total
profit subject to the given constraints.

More Info About The Problem can be found here
http://www.cs.grinnell.edu/~coahranm/csc301/f2007/hw/a8.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf
http://users.eecs.northwestern.edu/~dda902/336/hw6-sol.pdf
https://groups.google.com/forum/#!topic/algogeeks/JUpjPTR494Y
http://www.solvemyproblem.net/Webed/forum/thread.asp?tid=1213

Write an algorithm that loots the maximum amount of money from row of houses.efficiently

There is a row of houses in which each house contains some amount of money.
Write an algorithm that loots the maximum amount of money from these houses.
The only restriction is that you cannot loot two houses that are directly
next to each other.

Device an algorithm that will find a circle that contains n points inside Circle ..Another Excellent Problem From Google :)

ohh Anonymous Readers are keep sending me the problems .but instead of deleting the mails from i really used to enjoy the problems because of quality of problem asked :)

Given 2*n + 3 points in 2d space, with no 3 points collinear and no 4 points lying on a circle, device an algorithm that will find a circle that contains n points inside it, n outside it and 3 on it.

House painting Problem

There are a row of houses, each house can be painted with three colors red, blue and green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. You have to paint the houses with minimum cost. How would you do it?

Note: Painting house-1 with red costs different from painting house-2 with red. The costs are different for each house and each color.