Find all the "maximal independent sets" in a given graph

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

How do you find a shortest connection between two persons on Facebook(if the same exists)? You are provided with an API which returns the list of friends of a particular persons

Given an array of n integers having elements 1-n. By mistake one element repeated twice in the array and one element got missed. Need to find out the missing and repeated element. Time=O(n),space=O(1)

GIven a string "RGBBGBGR". we have to eliminate the couple (two same chars adjacent to each other) recursively. For example RGBBGBGR --> RGGBGR-->RBGRG

Given a number 123456789 and two opearators + and *. You have also given value k , You have to find all the such expressions that evaluates and value is equal to the given value.

Given a number 123456789 and two opearators + and *. You can use this two operators as many times u want. But you cant change the sequence of the number given there. The evaluated value is 2097.
e.g. 1+2+345*6+7+8+9=2097
You have to find all the such expressions that evaluates and value is
equal to the given value. You can use concatenation of numbers like 345 is concatenated there.

e.g. some more example
1+2+345*6+7+8+9 = 2097
12*3*45+6*78+9 = 2097
12*34+5*6*7*8+9 = 2097

Given an image that is represented by Nx1000 matrix of binary numbers. 1 represents black(image ink) and 0 represents white(blank).,Return all the positions of the pixels where you break the page and the number of pages, so that the image can be printed in the minimum number of pages.

Given an image that is represented by Nx1000 matrix of binary numbers. 1 represents black(image ink) and 0 represents white(blank).
The page breaks are applied in two ways:
1.)Find the row with all the white pixels.
(But this selection should be efficient as we want to print in minimum no. of pages.
For example: if we get a white line on 200th row, 600th row and 900th row, we should choose 900th line to break page).
2.) If no such row exists, break on the 1000th line.

Return all the positions of the pixels where you break the page and the number of pages, so that the image can be printed in the minimum number of pages.

Devise an algorithm for maximizing the sum of the randomly selected elements from the k subarrays. Basically means that we will want to split the array in such way such that the sum of all the expected values for the elements selected from each subarray is maximum.

You have an array with *n* elements. The elements are either 0 or 1. You
want to *split the array into kcontiguous subarrays*. The size of each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that
k << n. After you split the array into k subarrays. One element of each
subarray will be randomly selected.

Devise an algorithm for maximizing the sum of the randomly selected
elements from the k subarrays. Basically means that we will want to split
the array in such way such that the sum of all the expected values for the
elements selected from each subarray is maximum.

You can assume that n is a power of 2.

Example:

Array: [0,0,1,1,0,0,1,1,0,1,1,0]
n = 12
k = 3
Size of subarrays can be: 2,3,4,5,6

Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
Expected Value of the sum of the elements randomly selected from the
subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.4333333

Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.83333333


Source -> http://stackoverflow.com/questions/8189334/google-combinatorial-optimization-interview-problm

Given a set of numbers [1-N] . Find the number of subsets such that the sum of numbers in the subset is a prime number.

SMS Problem

1 - NULL, 2 - ABC, 3 - DEF, 4 - GHI, 5 - JKL, 6 - MON, 7 - PQRS, 8 - TUV, 9 - WXYZ, * - <Space>, # - <Break>
We must convert the numbers to text.
Eg
I/P - O/P
22 - B
23 - AD
223 - BD
22#2 - BA (# breaks the cycle)
3#33 - DE
2222 - 2
2222#2 - 2A
22222 - A (cycle must wrap around)
222222 - B