Sort an array of strings so that all the anagrams are next to each other

Write a method to sort an array of strings so that all the anagrams are next to each other.
The basic idea is to implement a normal sorting algorithm where you override the compareTo method to compare the “signature” of each string. In this case, the signature is the alphabetically sorted string.

public class AnagramComparator implements Comparator<String> {
 public String sortChars(String s) {
 char[] content = s.toCharArray();
 Arrays.sort(content);
 return new String(content);
 }

 public int compare(String s1, String s2) {
 return sortChars(s1).compareTo(sortChars(s2));
 }
 }

Now, just sort the arrays, using this compareTo method instead of the usual one.
Arrays.sort(array, new AnagramComparator());

PaintFill function

Implement the “paint fill” function that one might see on many image editing programs. That is, given a screen (represented by a 2-dimensional array of Colors), a point, and a new color, fill in the surrounding area until you hit a border of that color.


First, let’s visualize how this method works. When we call Paint Fill (eg, “click” paint fill in the image editing application) on, say, a green pixel, we want to “bleed” outwards. Pixel by pixel, we expand outwards calling PaintFill on the surrounding pixel. When we hit a pixel that is not green, we stop. Surrounding green pixels may still be painted if they are touched by another Paint Fill operation.
We can implement this algorithm recursively:

enum Color {
 Black, White, Red, Yellow, Green
 }
 boolean PaintFill(Color[][] screen, int x, int y, Color ocolor,
 Color ncolor) {
 if (x < 0 || x >= screen[0].length ||
 y < 0 || y >= screen.length) {
 return false;
 }
 if (screen[y][x] == ocolor) {
 screen[y][x] = ncolor;
 PaintFill(screen, x - 1, y, ocolor, ncolor); // left
 PaintFill(screen, x + 1, y, ocolor, ncolor); // right
 PaintFill(screen, x, y - 1, ocolor, ncolor); // top
 PaintFill(screen, x, y + 1, ocolor, ncolor); // bottom
 }
 return true;
 }

 boolean PaintFill(Color[][] screen, int x, int y, Color ncolor) {
 return PaintFill(screen, x, y, screen[y][x], ncolor);
 }

print all valid combinations of n-pairs of parentheses

Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n-pairs of parentheses.
EXAMPLE:
input: 3 (e.g., 3 pairs of parentheses)
output: ()()(), ()(()), (())(), ((()))

We can solve this problem recursively by recursing through the string. On each iteration, we have the index for a particular character in the string. We need to select either a left or a right paren. When can we use left, and when can we use a right paren?
»»Left: As long as we haven’t used up all the left parentheses, we can always insert a left paren.
»»Right: We can insert a right paren as long as it won’t lead to a syntax error. When will we get a syntax error? We will get a syntax error if there are more right parentheses than left.
So, we simply keep track of the number of left and right parentheses allowed. If there are left parens remaining, we’ll insert a left paren and recurse. If there are more right parens remaining than left (eg, if there are more left parens used), then we’ll insert a right paren and recurse.

public static void printPar(int l, int r, char[] str, int count) {
 if (l < 0 || r < l) return; // invalid state
 if (l == 0 && r == 0) {
 System.out.println(str); // found one, so print it
 } else {
 if (l > 0) { // try a left paren, if there are some available
 str[count] = ‘(‘;
 printPar(l - 1, r, str, count + 1);
 }
 if (r > l) { // try a right paren, if there’s a matching left
 str[count] = ‘)’;
 printPar(l, r - 1, str, count + 1);
 }
 }
 }

 public static void printPar(int count) {
 char[] str = new char[count*2];
 printPar(count, count, str, 0);
 }

A game of Russian roulette

Q : You are tied to your chair and can't get up.Here's a gun. Here's the barrel of the gun, six chambers, all empty. Now watch me as I put two bullets in the gun. See how I put them in two adjacent chambers? I close the barrel and spin it. I put the gun to your head and pull the trigger. Click. You're still alive. Lucky you!  I'm going to pull the trigger one more time. Which would you prefer, that I spin the barrel first, or that I just pull the trigger?


A:There are two bullets in six chambers, or, to put it more optimistically, four empty chambers out of six. Spin
the barrel, and you've got a four-in-six, or two-in-three, chance of survival.For the other option, look at it this way. The four empty chambers are all contiguous. One of them just spared your life. For three of these four empty chambers, the "next" chamber in succession will also be empty. The remaining empty chamber is right before one of the two bullets. That means you have a three-in-four chance of survival when you don't spin.
Three-fourths is better than two-thirds, so you definitely don't want the barrel spun again.

How to check reason for application slowing down?

What will be the three things you will look into when your java system.application goes slow suddenly. Means one day you notice application is running very slow and till yesterday it was fine, so what three things you will see first or debug first.


1. checking logs.
2. checking memory usage and cpu usage, if behave exceptionally.
3. dump thread or think about what is recently config/code change, or what is the possible datasource change
4. low virtual memory

Globe Walker

Question: How many points are there on the globe where, by walking one mile south, then one mile east and then one mile north, you would reach the place where you started?

Answer: The trivial answer to this question is one point, namely, the North Pole. But if you think that answer should suffice, you might want to think again! 

Let’s think this through methodically. If we consider the southern hemisphere, there is a ring near the South Pole that has a circumference of one mile. So what if we were standing at any point one mile north of this ring? If we walked one mile south, we would be on the ring. Then one mile east would bring us back to same point on the ring (since it’s circumference is one mile). One mile north from that point would bring us back to the point were we started from. If we count, there would be an infinite number of points north of this one mile ring.

So what’s our running total of possible points? We have 1 + infinite points. But we’re not done yet!

Consider a ring that is half a mile in circumference near the South Pole. Walking a mile along this ring would cause us to circle twice, but still bring us to back to the point we started from. As a result, starting from a point that is one mile north of a half mile ring would also be valid. Similarly, for any positive integer n, there is a circle with radius

r = 1 / (2 * pi * n)

centered at the South Pole. Walking one mile along these rings would cause us to circle n times and return to the same point as we started. There are infinite possible values for n. Furthermore, there are infinite ways of determining a starting point that is one mile north of these n rings, thus giving us (infinity * infinity) possible points that satisfy the required condition.

So the real answer to this question is 1 + infinity * infinity = infinite possible points!

Crazy Guy on the Airplane

A line of 100 airline passengers is waiting to board a plane. they each hold a ticket to one of the 100 seats on that flight. (for convenience, let’s say that the nth passenger in line has a ticket for the seat number n.)

Unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. all of the other passengers are quite normal, and will go to their proper seat unless it is already occupied. If it is occupied, they will then find a free seat to sit in, at random.

What is the probability that the last (100th) person to board the plane will sit in their proper seat (#100)?

Solution :

For four passengers, the possiblities are:

(x-ing out the ones that are not possible--because a "normal" passenger would sit in their own seat if it is open)

1234

1243 x

1324 x

1342 x

1423 x

1432 x

2134

2143 x

2314 x

2341 x

2413 x

2431 x

3124

3142 x

3214 

3241 x

3412 x

3421 x

4123

4132

4213

4231

4312 x

4321 x

Of the 8 valid possibilities, 1/2 of them have player 4 sitting in the his own seat.

An easier way to think about it:

There are only two (relevant) possible outcomes of a random seat choice:

1) Seat 1  (1/100 chance)

2) Seat 100 (1/100 chance)

3) Some other seat (98/100 chance)

Case 1 - Each other person can sit in their assigned seat, and the last passenger can sit his own. Let's call this a "win"

Case 2 - Each other person can sit in their assigned seat, but the last passenger's seat is taken, and he has to sit in seat 1. Let's call this a "loss"

Case 3 doesn't particularly interest us, because it simply defers the "decision" point to a passenger later, who will make another random choice.

At each point, the chances of randomly choosing seat 1 is the same as randomly choosing seat n, so the chances will always be 1/2, no matter how many seats/passengers we're talking about.

Cars on the Road

if the probability of observing a car in 20 minutes on a highway is 609/625, what is the probability of observing a car in 5 minutes (assuming constant default probability)?


probability of not seeing the car in 20 mins = (probability of not seeing the car in 5 mins)^ 4

as we can assume constant default probability

probability of not seeing tha car in 5 mins = (1 - (609/625))^ (1/4) = 2/5

so probability of seeing the car in 5 mins = 1 - (2/5) = 3/5

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.