Sunday, November 20, 2011

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.

Saturday, November 19, 2011

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 }

Thursday, November 17, 2011

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/

Tuesday, November 15, 2011

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