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

Convert Binary Tree into Doubly Linked List Such That Each Node of Doubly Linked List Contains The Vertical Sum of Binary Tree . We Can't Modify The Orginal Linked List

P.S. Its Extension of Vertical Sum & BT to DLL Problem . Will Take Some Time to Think About The Solution .
Please Search Previous Threads for above two problems .Although I Will Try to Pust Exact Working Code ASAP i will finish it .

Algorithm to output for a length m of a number stream, the value of the element j appearing in the s

Devise a small memory streaming algorithm to determine if |A| = 1.

For a stream of insertions and deletions, recall that x[j] = #insertions - #deletions of element j.
Given such a stream satisfying x[j] >= 0 for all elements j, let

A = { j : x[j] > 0 }

Determining whether A is empty is easy: just check if the sum of all x[j]'s equals 0 (which is easily doable in a stream).

Problem: devise a small memory streaming algorithm to determine if |A| = 1.

Extensions: What about higher sizes of A? What if the promise is not satisfied and we define A to be the set of j's with x[j] not equal to 0.

Game Of Life

Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly?

Given a list of words wordlist on 1st line (no of words <= 100) and a string qstr of len <= 1 million on 2nd line, print the index at qstr where a continuous substring exists that contains all the given words in wordlist.

Given a string of lowercase characters, reorder them such that the same characters are at least distance d from each other.

Input: { a, b, b }, distance = 2

Output: { b, a, b }

Why 11/11/11 Is Mathematically Amazing

You All Know Some Times Back We Had Data 11/11/11, is a once-in-a-century occurrence, adding to a November has been a very fun month for recreational mathematicians.

Last week, a rare eight-digit palindrome date — 11/02/2011, which reads the same frontward and backward — was found to have other mathematical qualities that made it a once-in-10,000-years date.Aziz Inan, a professor of electrical engineering at the University of Portland, Oregon, crunched the numbers and found that when the date was expressed as a number, 11,022,011, it has very special properties.

"It is the product of 7 squared times 11 cubed times 13 squared. That is impressive because those are three consecutive prime numbers. No other palindrome date up to A.D. 10,000 is like that," Inan said. "Not only that, if you write it out as 72 x 113 x 132, you'll notice that even the superscript power numbers — 232 — are a palindrome."

A once-in-10,000-years date is hard to top, but 11/11/11 is no slouch. Some people believe that the date 11/11/11 is a mystical day of good luck, or that 11/11/11 is a good day to make money. Inan explained that when one looks closely at the date, it too has some interesting mathematical properties.

After today, 11/11/11 will next occur 100 years down the road, on Nov. 11, 2111. Interestingly, in 2111, 11/11/11 will be followed by an eight-digit palindrome day, 11/12/2111, which is quite exciting for palindrome fans like Inan.

If you consider today's date as a number — 111,111 — you can run some additional fun math tricks, Inan explained. 111,111 can be obtained from its largest prime number factor, 37, like so: First, subtract 37 from its reverse (73) and you get 36. (Inan added that 36 is equal to the square of the sum of the digits in 111,111.)

Then, split 36 into three consecutive numbers that add up to 36 (11, 12 and 13). Then, multiply 11, 13, 37 and the reverse of 12 (21). And what comes out? You guessed it: 111,111.

Source www.lifeslittlemysteries.com/

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.

Create Linked List From Leaf of Binary Tree