Given an array of strings ... find the string which is composed of other strings in the array and is of maximum size. Ex: ["satcatratbat" , "rat", "bat", "cat", "sat", "ratbat", "ratsatcat"]. Output: "satcatratbat"

Source: http://www.quora.com/Shashank-Mani-Narayan/Cracking-The-Code/String-matching-porblem

Maximum Sum Subsequence in an unsorted array of size n

We are given an array A having n integers. What we want to find is a contiguous subseqnence (A[i], A[i+1], …, A[j]) such that the sum of the elements in that subsequence is maximized. (Note that, in general, there may be more than one such optimal subsequence.)

Note that if all elements in A are non-negative, we could directly return the entire array as the required optimal subsequence.

APPROACH 1

A simple brute-force method could be to compute the sums of all possible subseqnences in A. How many subsequences are there? There are  possible subsequences. Computing the sum of a subsequence takes O(n) in the worst-case. Hence, the running time of the algorithm would be .

In C++, we could write the following function to do what was explained above:

// start and end are the starting and ending indices of an optimal subsequence.

void f ( int* A, int n, int &start, int& end)

{

int sum, max = A[0];

for (int i = 0; i < n ; i++)

for (int j = i; j < n; j++)

{

sum = 0;

for (int k = i; k <=j; k++)

sum+= A[k];

if (sum >= max)

{

start = i;

end = j;

max = sum;

}

}

}

————

APPROACH 2:

We can improve the running time to  by being a bit more clever in computing the sums of different subsequences. We observe that the sum of the subsequence A[i ... j+1] = A[j+1] + sum of the subsequence A[i ... j].

In C++, we could write as follows:

void f (int *A, int n, int &start, int &end)

{

int sum, max = A[0];

for (int i = 0; i < n; i++)

{

sum = 0;

for (int j = i; j < n; j++)

{

sum + = A[j];

if (sum >= max)

{

start = i;

end = j;

max = sum;

}

}

}

}

———–

APPROACH 3:

Using dynamic programming, we can solve the problem in linear time.

We consider a linear number of subproblems, each of which can be solved using previously solved subproblems in constant time, this giving a running time of .

Let  denote the sum of a maximum sum contiguous subsequence ending exactly at index .

Thus, we have that:

 (for all )

Also, S[0] = A[0].

——–

Using the above recurrence relation, we can compute the sum of the optimal subsequence for array A, which would just be the maximum over  for .

Since we are required to output the starting and ending indices of an optimal subsequence, we would use another array  where  would store the starting index for a maximum sum contiguous subsequence ending at index i.

In prseducode form, the algorithm would look thus:

Create arrays S and T each of size n.

S[0] = A[0];

T[0] = 0;

max = S[0];

max_start = 0, max_end = 0;

For i going from 1 to n-1:

// We know that S[i] = max { S[i-1] + A[i], A[i] .

If ( S[i-1] > 0)

S[i] = S[i-1] + A[i];

T[i] = T[i-1];

Else

S[i] = A[i];

T[i] = i;

If ( S[i] > max)

max_start = T[i];

max_end = i;

max = S[i];

EndFor.

Output max_start and max_end.

———–

The above algorithm takes  time and  space.

——–

We can however improve upon the space requirements, reducing it to . The key idea is this: for computing S[i] and T[i], all we need are the values of S[i-1] and T[i-1] apart from the given array A. Hence, there is no need to store all  values of the S and T arrays.

We could proceed as follows:

max = A[0];

max_start = 0;

max_end = 0;

S = A[0];

T = 0;

For i going from 1 to n-1:

// S = max { S + A[i], A[i] )

if ( S > 0)

S = S + A[i];

Else

S = A[i];

T = i;

If ( S > max)

max_start = T;

max_end = i;

max = S;

End For.

Output max_end and max_start.

———–

The above algorithm takes  time and  space.

How much tottal water can be stored in buildings

Given array of height 5 1 3 6 1 2 

   |
|..|
|..|   
|.||
|.||.|
||||||

a coordinate a(xa,ya) dominates b(xb,yb) if ( xa>=xb and ya>=yb) how can I find all pairs in a set of coordinates

Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.

Example 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).

Find Maximum length palindrome in a from a ascii text file

You are given a string of ‘n’ characters where n is even. The string only consist of 6 type of characters: (){}[]. The task is to form a well formed expression. A well formed expression consist of proper nesting of braces and their is no priority between the braces like [ > } > ). You can edit any bracket and change it to remaining types for accomplishing the task.

Example A. "(){}" is valid B. "({[]})” is valid C. “((})” is invalid

Problem: You are given a two dimensional bit array(elements are 0 or 1). Find number of islands in this array. One island is defined as all elemnts which are 1, including neighbours(with or without diagonals). Or Array Islands problem.

Write An Efficient Program to Clone a Graph ?

Find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Given Table of Cities , Find Minimum Number of Hopes Required to Fly From One to Other City

There is a very Primitive Database and it has a table say "Travel". The content of table is as follows:

Source | Dest
--------------


Sea | LA
LA | FL
LA | MA
FL | Sea
Sea | FL

The ask is to find out all routes between (Sea) to (FL) with mininum hop.
the Result would be:
1. Sea -> FL
2. Sea -> LA - > FL

You have to write a Middle tier function to achieve above result. You can assume there is DBAPI that return the Destination city if you provide the source city.

Provide an efficient algorithm to solve the question "Can I buy N items?

 A shop sells an item in packets of 6, 9, and 17. A customer can buy any number of packets, but a packet cannot be broken up. Provide an efficient algorithm to solve the question "Can I buy N items?". For example, is it possible to buy 29 items? What about 19? Your algorithm simply needs to return true or false.

Design Data Structure For Students-Courses Realtionship

In a university, students can enroll in different courses. A student may enroll for more than one course. Both students and courses can be identified by IDs given to them. Design a data structure to store students, courses, and the student-course relationships. You can use arrays, lists, stacks, trees, graphs, etc. or come up with your own data structures. Give the running times, in Big O notation, for the following operations for your data structure and justify the answers: a) Return all students in a list. b) Return all courses in a list. c) Return all courses in a list for a given student. d) Return all students in a list for a given course.

Given a list of N line segments on the X axis: (x1[i], x2[i]) where i = 1 to N; And then a list of M queries. Each query inputs one x-coordinate and you need to output the set of all {i} that overlaps this point.

A 7 digit number consists of 7 distinct digits (from 0..9 ofcourse); The product of the first 3 digits = product of central 3 digits = product of last 3 digits; Find the middle digit.

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

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.

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

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

Find the longest arithmetic series that can be formed by choosing a sub-collection (possibly the entire collection)..TC problem

An arithmetic series consists of a sequence of terms such that each term minus its immediate predecessor gives the same result. For example, the sequence 3,7,11,15 is the terms of the arithmetic series 3+7+11+15; each term minus its predecessor equals 4. (Of course there is no requirement on the first term since it has no predecessor.)

Given a collection of integers, we want to find the longest arithmetic series that can be formed by choosing a sub-collection (possibly the entire collection). Create a class ASeries that contains a method longest that is given a int[] values and returns the length of the longest arithmetic series that can be formed from values.

Definition

Class: ASeries
Method: longest
Parameters: int[]
Returns: int
Method signature:int longest(int[] values) (be sure your method is public)

Constraints
- values will contain between 2 and 50 elements inclusive.
- Each element of values will be between -1,000,000 and 1,000,000 inclusive.

Examples
0)



{3,8,4,5,6,2,2}

Returns: 5

No arithmetic series using these values is longer than 2,3,4,5,6.
1)



{-1,-5,1,3}

Returns: 3

-1, 1, 3 is an arithmetic series (so is 3,-1,-5).
2)



{-10,-20,-10,-10}

Returns: 3

-10,-10,-10 is an arithmetic series.

I Took The Problem From My Friend Rizwan's Blog (he is Kind oF Computer Geek) :)
he told that success rate of this problem is about 52% so that makes me crazy to,solve it.

first let me try myself thinking how i can approach