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

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.

Given that you Can store integers in strings. Right an increment function in C that will increment a given integer by one

A Reader send me mail to solve this probloem :) will tryy to do it asap :)

Given two BST. Find maximum common BST. What Will Be Time Complexity can we do it in O(N) (TC for Checking Largest Commom BST) . What Will be Time Complexity if It will be the Binary Tree . Write an Efficient Algorithm

You have a list of jobs that need to be scheduled. For each job, you know when it should start and when it should end. You need to come up with an algorithm to schedule the maximum number of jobs possible."

Find The Maximum Sum in Triangle From Top to Bottom (Euler Problem) . Don't Forget to Check the Code for Triangle Which has 100s of Base :)

An Anonymous reader sent me the problem & ii posted it here
ohh but i forgot that Problem is already solved & posted few months back . so i am not giving to d same again excpet providing the link

Problem Discription

Given a triangle like the following
3
4 6
1 5 0 1.
How many nodes would you have, for 20 rows? 2. How to find the largest sum from the top of the triangle to the one of the nodes at the bottom. In other words, if you consider it as a tree, find the max sum of all paths from root to the leaf.

Thinking Process & Approach Here

This involves maths stuff rather then considering tree (it wont work check below link for detail ) or applying computer science & problem is already famous (Euler problem ) as we have to find the maximum sum in triangle we have given a big triangle which has many small triangle only thing u need to know a triangle has 3 vertexes so that you can approach :)

and a detailed description,explaination & solution you can find here

http://shashank7s.blogspot.com/2011/04/project-euler-problem-67-finding.html

let me know if i missed something or any other approach to solve it

one think that would recommands to geeks try out the recursive solution for the same problem :)

Given a positive integer n, find the minimum number of steps that takes n to 1 eg: 1.)For n = 1 , output: 0 2.) For n = 4 , output: 2 ( 4 /2 = 2 /2 = 1 ) 3.) For n = 7 , output: 3 ( 7 -1 = 6 /3 = 2 /2 = 1 )

On a positive integer, you can perform any one of the following 3 steps. 1.) Subtract 1 from it. ( n = n - 1 )  , 2.) If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2  )  , 3.) If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3  ). Using These Conditions Solve Above Question Efficiently ?

Approach / Idea: One can think of greedily choosing the step, which makes n as low as possible and conitnue the same, till it reaches  1. If you observe carefully, the greedy strategy doesn't work here. Eg: Given n = 10 , Greedy --> 10 /2 = 5  -1 = 4  /2 = 2  /2 = 1  ( 4 steps ). But the optimal way is --> 10  -1 = 9  /3 = 3  /3 = 1 ( 3 steps ). So, we need to try out all possible steps we can make for each possible value of n we encounter and choose the minimum of these possibilities.

It all starts with recursion :).  F(n) =   1 + min{  F(n-1) ,  F(n/2)  ,  F(n/3)  }  if (n>1) , else 0  ( i.e., F(1) = 0 ) . Now that we have our recurrence equation, we can right way start coding the recursion. Wait.., does it have over-lapping subproblems ?  YES. Is the optimal solution to a given input depends on the optimal solution of its subproblems ? Yes... Bingo ! its DP :) So, we just store the solutions  to the subproblems we solve and use them later on, as in memoization.. or we start from bottom and move up till the given n, as in dp. As its the very first problem we are looking at here, lets see both the codes.

Memoization

[code]

int memo[n+1]; // we will initialize the elements to -1 ( -1 means, not solved it yet )

int getMinSteps ( int n )

{

if ( n == 1 )  return 0;  // base case

if( memo[n] != -1 ) return memo[n];  // we have solved it already :)

int r = 1 + getMinSteps( n - 1 );  // '-1' step .  'r' will contain the optimal answer finally

if( n%2 == 0 )   r  =  min( r , 1 + getMinSteps( n / 2 ) ) ;  //  '/2' step

if( n%3 == 0 )   r  =  min( r , 1 + getMinSteps( n / 3 ) ) ;  //  '/3' step

memo[n] = r ;  // save the result. If you forget this step, then its same as plain recursion.

return r;

}

[/code]

Bottom-Up DP

[code]

int getMinSteps ( int n )

{

int dp[n+1] , i;

dp[1] = 0;  // trivial case

for( i = 2 ; i < = n ; i ++ )

{

dp[i] = 1 + dp[i-1];

if(i%2==0) dp[i] = min( dp[i] , 1+ dp[i/2] );

if(i%3==0) dp[i] = min( dp[i] , 1+ dp[i/3] );

}

return dp[n];

}

Source:http://www.codechef.com/wiki/tutorial-dynamic-programming#Identifying_the_State

Unable to Post The Discription of Problems since last 3 days ..M Not Feeling Good .does anyone know whats the probelm .please comment if you know ?

Unable to Post The Discription of Problems since last 3 days ..M Not Feeling Good .does anyone know whats the probelm .please comment if you know ?

Given n distinct elements, how many Young tableaus can you make?

Given n distinct elements, how many Young tableaus can you make?

You have a set of ants moving on an horizontal segment of length n. Each ant can randomly move either right or left. When an ant takes a direction, she stays in that direction until she either drops out of the segment or it bumps with another ant. In this case, the ant changes her direction. Can you formalize the system and describe what will happen after t iterations?

Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted.

Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted.

There is an array consisting of postive and negative integers. find the subarray whose sum is 0.

Circus Problem

find the atleast one row which neither contain the maximum or the minimum element among all the elements present

Given 2D array is given of order N x N . And it is
filled with distinct elements . Now you have to find the atleast one
row which neither contain the maximum or the minimum element among all
the elements present . The runtime complexity should be less than
O(N^2) .

Naive Solution Will Gothrough All The Row & Coulumn & keep track of min , max .finally return the row that doesn't contain the max or min can't we do better ?

So Mathematically Lets Consider a Set S consisting of any three rows R1, R2, and R3, and compute the min and max of the elements in these rows.

Since all elements are distinct, at most one the three rows
will contain minimum (say R1), and at most one row will
contain maximum (say R2). This means R3 contains neither
max, nor min..

formaly We do not need to look at other rows, as inclusion of other
rows in S, will not make R3 contain max or min.

Correctness of Algorithm: Why We are processing only three row its not making things clear ? How we can sure that from N*N matrix ,if max/min won't be in out of any row from 3 row then it won't contains the max/min from N rows ? e.g. Why it will work that a row that does not contains min/max in N*N matrix will definatly be from one of the threes rows only ?

Things That Strikes In Mind is that as we need to find only 1 min & 1 max (tottal two objects) what can be the possibilities ? hey we wants to extract only two objects out of n*n objects ? what don't pprocess only n+1 rows so that if we are able to cover the all test cases , can be sure that it will satisfy the N*N as well ?

so basically our task reduce to iterate over three rows only & Find the minimum and maximum element from the elements By reading 3 rows.so 2 cases possible.

1. Min and Max element belong to 1 row
2. Min and Max belong to 2 rows

As Said Above using Set.

In both the cases we can get the row which do not contain minnimum and
maximum element from the 3 rows read. If that row does not contain
minimum and maximum element from 3 rows, it won't contain maximum and
minimum element from N rows

lets write 6*6 matrix , try to change the position of min/max , try to test it different test cases , you will find our algorithm will work &b thats work efficiently :)

Time Compelxity O(M^2) where M=3 , differ from N
its Important Questuion & All Things that we have done so far.
we are process only 3*3 sub-matrix . so lest say we have given matrix of size N*N . lets define M=3 & N=k+M where K is N-3 or N-M as i have assigned M to value 3 . so tottal time compexlity will be O(M*M) where M=3 Which is Obviously Much less then N*N isn't it . lets say N=1 million then N^2 will be 1 trillion but m^2 willl be 9 only isn't it its awesome reduction in time compelxity :)


writing the code is not big task for this only designing efficient algo matters.

Correct me if any issue with Time Complexity :)

Find the number of ways of writing a number as the sum of positive integers?

Above is Also called the Partition Function P of n, it is denoted by P(n).

For example,5 can be written as.

5
4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1


The partitions of 4 are listed below:

1. 4
2. 3 + 1
3. 2 + 2
4. 2 + 1 + 1
5. 1 + 1 + 1 + 1

The partitions of 8 are listed below:

1. 8
2. 7 + 1
3. 6 + 2
4. 6 + 1 + 1
5. 5 + 3
6. 5 + 2 + 1
7. 5 + 1 + 1 + 1
8. 4 + 4
9. 4 + 3 + 1
10. 4 + 2 + 2
11. 4 + 2 + 1 + 1
12. 4 + 1 + 1 + 1 + 1
13. 3 + 3 + 2
14. 3 + 3 + 1 + 1
15. 3 + 2 + 2 + 1
16. 3 + 2 + 1 + 1 + 1
17. 3 + 1 + 1 + 1 + 1 + 1
18. 2 + 2 + 2 + 2
19. 2 + 2 + 2 + 1 + 1
20. 2 + 2 + 1 + 1 + 1 + 1
21. 2 + 1 + 1 + 1 + 1 + 1 + 1
22. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Approach

One way of getting a handle on the partition function involves an intermediate function p(k, n), which represents the number of partitions of n using only natural numbers at least as large as k. For any given value of k, partitions counted by p(k, n) fit into exactly one of the following categories:

1. smallest addend is k
2. smallest addend is strictly greater than k.

The number of partitions meeting the first condition is p(k, n − k). To see this, imagine a list of all the partitions of the number n − k into numbers of size at least k, then imagine appending "+ k" to each partition in the list. Now what is it a list of? As a side note, one can use this to define a sort of recursion relation for the partition function in term of the intermediate function, namely

1+ sum(P(k,n-k)=P(n)
for i=1 to floor n/2
where |_n_| is the floor function.

The number of partitions meeting the second condition is p(k + 1, n) since a
partition into parts of at least k that contains no parts of exactly k must have all parts at least k + 1.

Since the two conditions are mutually exclusive, the number of partitions meeting either condition is p(k + 1, n) + p(k, n − k). The recursively defined function is thus:

* p(k, n) = 0 if k > n

* p(k, n) = 1 if k = n

* p(k, n) = p(k+1, n) + p(k, n − k) otherwise.

Got The Hint of DP using matrix of P[n,n] :)

Euler invented a generating function which gives rise to a recurrence equation in P(n),

Design a function getBits that gives x bits from a given position p of a given number n.

Approach

So we need mask for any bit set (10010011 etc). you want to generate a "mask" that pulls only the bits you want to see. So 10010011 or 0x03, I'm interested in xxxxx011. What is the mask that will extract that set ? 00000111 Now I want to be sizeof int independent, I'll let the machine do the work i.e. start with 0 for a byte machine it's 0x00 for a word machine it's 0x0000 etc. 64 bit machine would represent by 64 bits or 0x0000000000000000

Algorithm

Now apply "not" (~0) and get 11111111
shift right (<<) by n and get 11111000 and "not" that and get 00000111 it can be written as ~( ~ 0 << x )........(1) Okay we got our mask. 1. Now, we push the bits we want out of the number into the lowest order bits so we shift binary n by p+1-x ------(2) e.g. n >> p+1-x because so it's just a clever way to get n 1-bits in the least significant part of the number.

The "x bit" you describe has shifted the given number n right far enough so that the least significant x bits are the ones you want

take the and operation of above two you will that the number represented by that x bits or we can also return the bits if save that in to string or array

so we have to finally return ( ( n >> p+1-x ) & ~( ~ 0 << x )) so Here is Working Code for the same #include

unsigned int getbits(unsigned int x, int p, int n)
{
return (x >> (p + 1 - n)) & ~(~0 << n);
}
int main(void) {
int x = 182, p = 2, n = 5;
int z = getbits(x, p, n);
printf("getbits(%u (%x), %d, %d) = %u (%X)\n", x, x, p, n, z, z);
//% u for unsigned & %x for hexadecimal numbers


return 0;
}

Time Complexity O(1)
Space Complexity O(1)
Run Here https://ideone.com/eglaQ

Given 3 input strings S1, S2, S3 for example take s1 = "hard" s2 = "work", s3 = "success" assign numeric values (0-9) to each of the characters in these strings such that equation s1 + s2 = s3 holds true. Constraints are that all occurrence of a letter should be assigned the same digit. Return -1 if not possible.

Find The Cubical in 3d Matrix of m*n*o Efficiently !!!!

Given a 3D matrix of m*n*o dimension and there lies a cubicle in each cell of the matrix. Assume K cubicle are occupied(you know the coordinates of occupied cubicles) and remaining are vacant. You have to arrange a meeting. So find a cubicle such that the sum of the distances traveled by all the persons should be minimum. A Person can't move diagonally, they can only parallel to axes...

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles: Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram. This question is the last question from 2003/2004 ACM International Collegiate Programming Contest, Univ. of Ulm Local Contest. It's one of the 2 hard ones in this question set

k distinct integers [0, N) Select a random no [0,N) which is not in this k distinct list. Example: [4, 6, 9] Choose a random no between 0 - 9 which is not 4, or 6, or 9. Valid output: 2 Invalid output: 6

k distinct integers [0, N) Select a random no [0,N) which is not in this k distinct list. Example: [4, 6, 9] Choose a random no between 0 - 9 which is not 4, or 6, or 9. Valid output: 2 Invalid output: 6

You're given a string, and you want to split it into as few strings as possible such that each string is a palindrome.

A Good Discussion I Found here on The Same


https://groups.google.com/forum/#!topic/algogeeks/hUh_jRv8Ij8
https://groups.google.com/forum/#!topic/algogeeks/EQZFLZ4P3IA

How to generate random integer between A and B, using an unbiased coin. For ex. If A = 3 and B = 6 then your algorithm should generate 3, 4, 5, 6 with equal probabilities.

My Design Problem - 1 , A Man & Party Puzzle!!!! Tough One

A Man is Going to Party on Infinite length Road,So It Clear That You Don't know the starting point , ending point or length of the road he can start from any point in infinite length road & went to party & then came out from party,but her forgot where he parked the Car, Write an Efficient Algorithm that can solve his problem to find out the Car. Explain What data Structures You Will Use ?

Implement 3 Stack Using Single Array Efficiently

Approach 1:(Naive)
Divide the array in three equal parts and allow the individual stack to grow in that limited space (note: “[“ means inclusive, while “(“ means exclusive of the end point).
»»for stack 1, we will use [0, n/3)
»»for stack 2, we will use [n/3, 2n/3)
»»for stack 3, we will use [2n/3, n)

This solution is based on the assumption that we do not have any extra information about the usage of space by individual stacks and that we can’t either modify or use any extra space. With these constraints, we are left with no other choice but to divide equally.
int stackSize = 300;
int[] buffer = new int [stackSize * 3];
int[] stackPointer = {0, 0, 0}; // stack pointers to track top elem

void push(int stackNum, int value) {
/* Find the index of the top element in the array + 1, and
* increment the stack pointer */
int index = stackNum * stackSize + stackPointer[stackNum] + 1;
stackPointer[stackNum]++;
buffer[index] = value;
}

int pop(int stackNum) {
int index = stackNum * stackSize + stackPointer[stackNum];
stackPointer[stackNum]--;
int value = buffer[index];
buffer[index]=0;
return value;
}

int peek(int stackNum) {
int index = stackNum * stackSize + stackPointer[stackNum];
return buffer[index];
}

boolean isEmpty(int stackNum) {
return stackPointer[stackNum] == stackNum*stackSize;
}

Approach 2:

In this approach, any stack can grow as long as there is any free space in the array.

We sequentially allocate space to the stacks and we link new blocks to the previous block. This means any new element in a stack keeps a pointer to the previous top element of that particular stack.
In this implementation, we face a problem of unused space. For example, if a stack deletes some of its elements, the deleted elements may not necessarily appear at the end of the array.
So, in that case, we would not be able to use those newly freed spaces.
To overcome this deficiency, we can maintain a free list and the whole array space would be given initially to the free list. For every insertion, we would delete an entry from the free list. In case of deletion, we would simply add the index of the free cell to the free list.
In this implementation we would be able to have flexibility in terms of variable pace utilization
but we would need to increase the space complexity.
int stackSize = 300;
int indexUsed = 0;
int[] stackPointer = {-1,-1,-1};
StackNode[] buffer = new StackNode[stackSize * 3];
void push(int stackNum, int value) {
int lastIndex = stackPointer[stackNum];
stackPointer[stackNum] = indexUsed;
indexUsed++;
buffer[stackPointer[stackNum]]=new StackNode(lastIndex,value);


}
int pop(int stackNum)
{
int value = buffer[stackPointer[stackNum]].value;
int lastIndex = stackPointer[stackNum];
stackPointer[stackNum] = buffer[stackPointer[stackNum]].previous;
buffer[lastIndex] = null;
indexUsed--;
return value;
}
int peek(int stack) { return buffer[stackPointer[stack]].value; }
boolean isEmpty(int stackNum) { return stackPointer[stackNum] == -1; }

class StackNode
{
public int previous;
public int value;
public StackNode(int p, int v)
{
value = v;
previous = p;
}

}

Taken from Cracking The Code By Gayle Laakmann Mcdowell !!!

How to Count Number of Set Bits e.g. Number of 1's efficiently ?

This Question is asked in almost all core s/w companies & most of we know logarithmic solution of this problem but there exist a constant time solution using bit manipulations stuck !!!!:) See 2nd Method to solve the same problem in O(1)

1st Brian Kernighan’s Algorithm:
Subtraction of 1 from a number toggles all the bits (from right to left) till the rightmost set bit(including the righmost set bit). So if we subtract a number by 1 and do bitwise & with itself (n & (n-1)), we unset the righmost set bit. If we do n & (n-1) in a loop and count the no of times loop executes we get the set bit count.
Beauty of the this solution is number of times it loops is equal to the number of set bits in a given integer.

1 Initialize count: = 0
2 If integer n is not zero
(a) Do bitwise & with (n-1) and assign the value back to n
n: = n&(n-1)
(b) Increment count by 1
(c) go to step 2
3 Else return count

#include

/* Function to get no of set bits in binary
representation of passed binary no. */
int countSetBits(int n)
{
unsigned int count = 0;
while (n)
{
n &= (n-1) ;
count++;
}
return count;
}

/* Program to test function countSetBits */
int main()
{
int i = 16;
printf("%d", countSetBits(i));
getchar();
return 0;
}

Time Complexity O(logn)
Space Complexity O(1)
Run Here https://ideone.com/2y2KJ

2nd Method is Most Efficient One !!!!!!

Assuming that the integer is 32 bits, this is pretty good:

x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);

where
0x55555555 = 01010101 01010101 01010101 01010101
0x33333333 = 00110011 00110011 00110011 00110011
0x0F0F0F0F = 00001111 00001111 00001111 00001111
0x00FF00FF = 00000000 11111111 00000000 11111111
0x0000FFFF = 00000000 00000000 11111111 11111111


Notice that the hex constants are respectively alternate bits,
alternate pairs of bits, alternate groups of four bits, alternate
bytes, and the low-order half of the int.

The first statement determines the number of one-bits in each pair of
bits. The second statement adds adjacent pairs of bits to get the
number of bits in each group of four bits. Then these are added to get
the number of bits in each byte, short int, and finally in the whole
int.

but it works at low level ??

Suppose that the first four bits of x from the left are abcd. Lets separate the bits into pairs with a comma: ab,cd. The first four bits of the hex constant0x55... are 0101, or separated into pairs: 01,01. The logical product of x with this constant is 0b,0d. The first four bits of x>>1 are 0abc, or separated into pairs are 0a,bc. The logical product of this with the constant is 0a,0c. The sum 0b,0d + 0a,0c is a+b,c+d, where a+b = 00, 01, or 10, and b+c = 00, 01, or 10. Thus we have replaced each pair of bits in x with the sum of the two bits originally in the pair.

The next statement uses the constant 0x333.... The first four bits of this are 0011, split into pairs as 00,11. The logical product of the first four bits of x with this constant gives 00,c+d. Furthermore (a+b,c+d)>>2 = 00,a+b. Then 00,c+d + 00,a+b gives the four-bit quantity a+b+c+d, i.e., the number of one bits set in the first four bits of the original x.

The next statements continue to double the number of bits included in each sum.
& so on

#include
using namespace std;

int main()
{
int x=0x00000016;
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);

cout<> 2) & 0x33333333);

cout<> 4) & 0x0F0F0F0F);

cout<> 8) & 0x00FF00FF);

cout<> 16) & 0x0000FFFF);

cout< return 0;

}

Time Complexity O(1)
Space Complexity O(1)
Run Here https://ideone.com/uDKGK
More Info http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

You are provided with a bit generator which generates 1 and 0 with equal probabilities i.e. (1/2). You are required to design a function which generates numbers form 1-1000 with equal probabilities i.e. (1/1000).

Given two sorted arrays a[]={1,3,77,78,90} and b[]={2,5,79,81}. Merge these two arrays, no extra spaces are allowed. Output has to be a[]={1,2,3,5,77} and b[]={78,79,81,90}.

Data Structure Used: Array

Algorithm: Question is really tricky if we don't think smartly !!!! :)
use two pointer & points l to 1st & r to 2nd array
if elementb in 1st is smaller trhen 2nd arraye elemnt at index i then increment 1st pointer
else
swap element at index i in both array &b incerment 1st pointer & sort 2nd
array its not necessary only if we need sorted output in each array

Solution:

size of a=m size of b =n
a[]={1,3,77,78,90} and b[]={2,5,79,81}
l r


while(l<=m && r<=n)
{
if(b[r] {
swap(a[l],b[r]);
l++;
sort(b[]);
}
elseif(a[l] l++;



}

Time Complexity O(mlogm) sorting to 2nd array
Space Complexity O(1)

Given a word, convert it into a palindrome with minimum addition of letters to it. letters can be added anywhere in the word. for eg if yahoo is given result shud be yahoohay.

e.g

ABBA : 0 (already a palindrome)
ABB: 1
FAE: 2
FOO: 1


Simple Algorithm Will be

You need to find the longest palindrome at the end of the string. An algorithm to see if a string is a palindrome can be created by simply running one pointer from the start of the string and one from the end, checking that the characters they refer to are identical, until they meet in the middle. Something like:

function isPalindrome(s):
i1 = 0
i2 = s.length() - 1
while i2 > i1:
if s.char_at(i1) not equal to s.char_at(i2):
return false
increment i1
decrement i2
return true

Try that with the full string. If that doesn't work, save the first character on a stack then see if the remaining characters form a palindrome. If that doesn't work, save the second character as well and check again from the third character onwards.

Eventually you'll end up with a series of saved characters and the remaining string which is a palindrome.

Best case is if the original string was a palindrome in which case the stack will be empty. Worst case is one character left (a one-character string is automatically a palindrome) and all the others on the stack.

The number of characters you need to add to the end of the original string is the number of characters on the stack.

To actually make the palindrome, pop the characters off the stack one-by-one and put them at the start and the end of the palindromic string.

Examples:

String Palindrome Stack Notes
------ ---------- ----- -----
ABBA Y - no characters needed.

String Palindrome Stack Notes
------ ---------- ----- -----
ABB N -
BB Y A one character needed.
ABBA Y - start popping, finished.

String Palindrome Stack Notes
------ ---------- ----- -----
FAE N -
AE N F
E Y AF two characters needed.
AEA Y F start popping.
FAEAF Y - finished.

String Palindrome Stack Notes
------ ---------- ----- -----
FOO N -
OO Y F one character needed.
FOOF Y - start popping, finished.

String Palindrome Stack Notes
------ ---------- ----- -----
HAVANNA N -
AVANNA N H
VANNA N AH
ANNA Y VAH three characters needed.
VANNAV Y AH start popping.
AVANNAVA Y H
HAVANNAVAH Y - finished.

Within a 2D space, there is a batch of points(no duplicate) in the region (0,0),(0,1),(1,0),(1,1), try to find a line which can divide the region to 2 parts with half points in each .the input will be an array of points and the length of the array. struct point{ int x; int y; }; input : struct point * points, int length

Within a 2D space, there is a batch of points(no duplicate) in the region (0,0),(0,1),(1,0),(1,1), try to find a line which can divide the region to 2 parts with half points in each .the input will be an array of points and the length of the array. struct point{ int x; int y; }; input : struct point * points, int length

Design a data structure that can be used instead of an array and avoids the "high-cost" (i.e. O(n)) of initializing the array. the data structure ought to holds n items and supports the following operations in O(1) time: * Init – Initializes the data structure to empty. * Set(i, x) – Sets item x at index i in the data structure. * Get(i) – Gets the item stored in index i (or 'empty' if nothing is there). Remark: the data structure should use O(n) space.

Design a data structure that can be used instead of an array and avoids the "high-cost" (i.e. O(n)) of initializing the array. the data structure ought to holds n items and supports the following operations in O(1) time: * Init – Initializes the data structure to empty. * Set(i, x) – Sets item x at index i in the data structure. * Get(i) – Gets the item stored in index i (or 'empty' if nothing is there). Remark: the data structure should use O(n) space.

You have to write a function checkRegex() which takes two strings as input, one string represents a regex expression and other is an input string to match with the regex expression passed as the other parameter. Return true if it matches, else false.

I found this question on one of the forum

Regex may contain characters ‘a-z’, ‘.’ and ‘*’ where ‘.’ matches any character and ‘*’ means 0 or more occurrences of the previous character preceding it.

Examples:
1) a*b matches b,ab,aab
2) a.b matches aab, abb, acb,…, azb
3) .* matches all the valid strings formed by using the lowercase letters


Status: Solved

Algorithm:Recursion



Time Complexity O(2^n)
Space Complexity O(1)

Given a php source file which contains a few classes defined in it. ,print the class hierarchy in the given desired format.

In PHP, there is concept of single class inheritance i.e. a new class can extend an existing class. You are given a php source file which contains a few classes defined in it. You have to print the class hierarchy in the given desired format.
For example, classes in php source file are A, B extending A, C extending B, D extending A, E.
The output should look like:

A
B
C
D
E

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters fo

Find the length of the longest no-repeated substring e.g. string without repeating characters. For example, the longest substring without repeating letters

ExampleString s="abcabcbbba" Answer will be "abc" of length 3

Algorithm:

Assuming string has small letter only temp array is of length 26.

Take an temp boolean array to set/reset character is present or not

while iterating through whole string using temp array If character value is already set or true then reset values from current index to previous starting index.and update max-length of non-repeated sub-string.e.g.When you have found a repeated character (let’s say at index j), it means that the current sub-string (excluding the repeated character of course) is a potential maximum, so update the maximum if necessary. It also means that the repeated character must have appeared before at an index i, where i  is less than j.

Since you know that all sub-strings that start before or at index i would be less than your current maximum, you can safely start to look for the next sub-string with head which starts exactly at index i+1.

As we are using two indexes which iterates through string two times e.g. O(2m) where m is length of string  and overall time complexity O(m) .

Lets have a look at Code

int lengthOfLongestSubstring(string s) 
{

  int m= s.length();

  int i = 0, j = 0;

  int maxLen = 0;

 boolean temp[]=new boolean[256];

  while (j < m) {

    if (temp[s[j]]) {

      maxLen = max(maxLen, j-i);

      while (s[i] != s[j])
      {

        temp[s[i]] = false;

        i++;

      }

      i++;

      j++;

    } else  
    {

      temp[s[j]] = true;

      j++;

    }

  }

  maxLen = max(maxLen, m-i);

  return maxLen;

}

Time Complexity O(M)  M is Length of String

Design an algorithm and write code to serialize and deserialize a binary tree.

Writing the tree to a file is called ‘serialization’ and reading back from the file to reconstruct the exact same binary tree is ‘de-serialization’.

First, we are able to save the binary tree to a file and restore it at a later time. We are also able to transmit the binary tree representation via network and load it into another computer. Without doubt, serialization/deserialization of a binary tree is important and an algorithm to represent a binary tree in a compact way is very desirable.

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be “resurrected” later in the same or another computer environment.

The pre-order traversal code below does all the job to serialize a binary tree, believe it or not!
Source :http://www.brilliantsheep.com/serializing-and-deserializing-a-binary-tree-in-java Time Complexity O(N)
Space Complexity O(N) to Store BST in File

Describe an algorithm to save a Binary Search Tree (BST) to a file in terms of run-time and disk space complexity. You must be able to restore to the exact original BST using the saved format.

Question need to be understand clearly .We Have to Transfer the Whole BST/BT across the network this is where he asked to implement the serialization on Tree & the transfer to another host on recipient side we use deserialization . to implement serialization on tree we need to save it in file & restoring the exact tree on receiving side .important question arises that which traversal we have to use here pre,in or post ?? only one is best are u able to think of it ???

let me explain lets we have tree is
_30_
/ \
20 40
/ / \
10 35 50

In-order traversal
If we do an in-order traversal, we will output 10 20 30 35 40 50. There is no way of telling how the original BST structure looks like, as the following unbalanced BST is one of the possible BST sets from the output 10 20 30 35 40 50.

_50
/
40
/
35
/
30
/
20
/
10

Post-order traversal:
If we do a post-order traversal, we will output the leaf nodes before its parent node. Specifically, we will output 10 20 35 50 40 30 using post-order traversal. Imagine we’re reading the nodes to construct the tree back. See the problem that we are reading the leaf nodes before its parent? There’s too much trouble to create the child nodes before its parent. Remember that the BST insertion algorithm works by traversing the tree from the root to the correct leaf to insert.

Pre-order traversal:
Pre-order traversal is the perfect algorithm for making a copy of a BST. The output of a pre-order traversal of the BST above is 30 20 10 40 35 50. Please note the following important observation:
A node’s parent is always output before itself.

Therefore, when we read the BST back from the file, we are always able to create the parent node before creating its child nodes. The code for writing a BST to a file is exactly the same as pre-order traversal.

Ps: we can solve this problem with any traversal if we need to given an array to store in array instead of file isn't it think ?? why

on receiving side Reading a BST from a file:
The question now is, how would you reconstruct a BST back from the file? Assume that we have the following pre-order traversal output of the BST earlier: 30 20 10 40 35 50.
so answer is
When we encounter a new node to insert, we should always place it into the first empty space which it will fit using a pre-order traversal. How do we determine the first empty space which a node will fit in? We can use the ordinary BST insertion algorithm, but the run-time complexity will be O(n lg n), since inserting a node takes O(lg n) time. Not efficient enough! so we need some more efficient algorithm
yes we can do it using what we used to solve "Determine if a Binary Tree is a Binary Search Tree (BST)?"

so what will be the efficent algo then here it is
We use the same idea here. We pass the valid range of the values from the parent node to its child nodes. When we are about to insert a node, we will check if the insert value is in the valid range. If it is, this is the right space to insert. If it is not, we will try the next empty space. Reconstructing the whole BST from a file will take only O(n) time.

void readBSTHelper(int min, int max, int &insertVal,
BinaryTree *&p, ifstream &fin) {
if (insertVal > min && insertVal < max) { int val = insertVal; p = new BinaryTree(val); if (fin >> insertVal) {
readBSTHelper(min, val, insertVal, p->left, fin);
readBSTHelper(val, max, insertVal, p->right, fin);
}
}
}

void readBST(BinaryTree *&root, ifstream &fin) {
int val;
fin >> val;
readBSTHelper(INT_MIN, INT_MAX, val, root, fin);
}

Time Complexity O(N)
Space Complexity O(1)