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.