Why are manhole covers round?

A manhole cover is a removable plate forming the lid over the opening of a manhole, to prevent anyone from falling in and to keep unauthorized persons out.

The question of why manhole covers are typically round, at least in the U.S., was made famous by Microsoft and Google when they began asking it as a job-interview question.Originally meant as a psychological assessment of how one approaches a question with more than one correct answer, the problem has produced a number of alternate explanations, from the pragmatic ("Manhole covers are round because manholes are round.") to the philosophical.

Reasons for the shape include:

• A round manhole cover cannot fall through its circular opening, whereas a square manhole cover may fall in if it were inserted diagonally in the hole. (A Reuleaux triangleor other curve of constant width would also serve this purpose, but round covers are much easier to manufacture. The existence of a "lip" holding up the lid means that the underlying hole is smaller than the cover, so that other shapes might suffice.)
• Round tubes are the strongest and most material-efficient shape against the compression of the earth around them, and so it is natural that the cover of a round tube assume a circular shape.
• Similarly, it is easier to dig a circular hole and thus the cover is also circular.
• The bearing surfaces of manhole frames and covers are machined to assure flatness and prevent them from becoming dislodged by traffic. Round castings are much easier to machine using a lathe.
• Circular covers do not need to be rotated to align them when covering a circular manhole.
• Human beings have a roughly circular cross-section.
• A round manhole cover can be more easily moved by being rolled.
• Most manhole covers are made by a few large companies. A different shape would have to be custom made.

Other manhole shapes can be found, usually squares or rectangles.

Anagrams in a Dictionary

Q)Given a dictionary of words.Returns the set of all words grouped into subsets of words that are all 
anagrams of each other.
Algorithm :
1)Create a hashmap of String and Set (Map<String,set<String>>)
2)Read a word from the dictionary and sort the word.
   i) If the sorted word(key) word is not present in the Map,crate an empty set and add this key to      set.Insert key,list pair into map.
  ii)Else {
        If key is present in the map,get the list and add the key to set.Again put this new key value pair into map.     }

3)Iterate through all keys of map,get the set and print key,values of set.
      
ps:An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once; e.g., orchestra = carthorse, A decimal point = I'm a dot in place.

Street Trees

A group of trees is planted along a straight line.
KOI is planning to plant more trees so that the distance between two adjacent trees is equal for all trees.
For simplicity, each tree can only be planted on an integer coordinate.
For example, if 4 trees were originally planted on coordinates (1,3,7,13), and if KOI plants 3 more trees on coordinates (5,9,11), then the distance between two adjacent trees will equal for all trees.
Your task is to calculate the minimal number of trees that KOI can plant so that the distance between two adjacent trees will equal for all trees.
Input :
The first line is an integer N (3<=N<=100,000), which denotes the number of already planted trees.
The next N lines will have an integer X (1<=X<=1,000,000,000), which denotes the coordinate of each tree.
You can safely assume that the value of X will be unique.
Output :
Output the minimal number of trees that must be planted.
Example :
Input: 
4
1  3  7  13
Output:  3
Solution : Get the difference between alternate numbers into an array.Now find out the gcd of all the numbers.GCD is  the minimum distance between the trees.Start from the starting tree and keep on adding gcd to previous number.
Answer : http://www.ideone.com/Cfyr9

No of words in a language

There is a language with only two elements ie 'a' and 'bc'. How many words can be
made out of it if whose Length is n.

Let N(k) be the number of strings of length k. Since you can
make a string of length k by appending 'a' onto a string of length k-1
or by appending 'bc' onto a string of length k-2, it follows that

N(k) = N(k-1) + N(k-2)

Furthermore, there are no strings of length -1 and only one string of
length 0.

Restaurent problem

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 effi cient algorithm to compute the maximum expected total
pro fit subject to the given
constraints.

http://codepad.org/DDtJ6yBF

Longest Increasing Subsequence

Given a sequence of n real numbers A(1) ... A(n), determine a subsequence (not necessarily contiguous) of maximum length in which the values in the subsequence form a strictly increasing sequence.


http://codepad.org/C3sr0oF3

Ransom Note

Question:given an arbitrary ransom note string and another string containing all the contents of all the magazines, write a function that will return true if the ransom note can be made from the magazines; otherwise, it will return false. Remember, every letter found in the magazine string can only be used once in your ransom note. For example, if the ransom note string was "no scheme" and the magazine string was "programming interviews are weird", you would return false since you can't form the first string by grabbing and rearranging letters from the second string.


Solution is here.