This is a most unusual paragraph. How quickly can you find out
what is so unusual about it? It looks so ordinary, you'd think
nothing was wrong with it and in fact, nothing is wrong with it.
It is unusual, why? Study it. Think about it and you may find
out. If you work at it for a bit,
it will dawn on you. Try to do it without coaching.
Showing posts with label Puzzle. Show all posts
Showing posts with label Puzzle. Show all posts
January 4, 2011
January 3, 2011
World War - I Puzzle
A grandfather is telling his grandson stories of world war.
He said :
"At the end of World War 1, I was awarded for my bravery
after saving a group of my men"
"We were fighting in northern France and one of our
enemies threw a grenade at us. I managed to pick it up and
throw it away before it exploded. So right after the war
ended, a General gave me a sword, engraved with the words
'Awarded for Bravery and Valor, A True Hero, World War 1'".
"The grandson thinks about the story for a minute and then
says "Grandpa, that story can't be true!"
How did the grandson know?
He said :
"At the end of World War 1, I was awarded for my bravery
after saving a group of my men"
"We were fighting in northern France and one of our
enemies threw a grenade at us. I managed to pick it up and
throw it away before it exploded. So right after the war
ended, a General gave me a sword, engraved with the words
'Awarded for Bravery and Valor, A True Hero, World War 1'".
"The grandson thinks about the story for a minute and then
says "Grandpa, that story can't be true!"
How did the grandson know?
December 26, 2010
Program to Shuffle a pack of card in O(n)
public class Shuffle {
public static void shuff(int[] arr) {
for(int i=0; i
int rand = (int)(Math.random() * arr.length);
int temp = arr[rand];
arr[rand] = arr[i];
arr[i] = temp;
}
for(int i=0; i
System.out.println(" "+arr[i]);
}
}
}
public static void shuff(int[] arr) {
for(int i=0; i
int rand = (int)(Math.random() * arr.length);
int temp = arr[rand];
arr[rand] = arr[i];
arr[i] = temp;
}
for(int i=0; i
System.out.println(" "+arr[i]);
}
}
}
October 28, 2010
Mean - Median - Mode
Mean - Median - Mode are three words which I often confuse.
Mean : Average
- Arithmetic Mean (AM) : (a+b+c+....+n)/n
- 1/n
- Geometric Mean (GM) : (a*b*c*.....*n)
- Harmonic Mean (HM)
AM >= GM >= HM
Median : Middle Value
If we have a set of values, then mean of those can be found by arranging those values in ascending/ descending order and the middle value will be median.
Mode : Most frequently occuring value. Mode may / may not be unique.
July 20, 2010
Java Program without main method
When JVM finds a class, it first executes the static block and then searches for main method.
So, to avoid the JVM from searching for main method, we can execute the required code (iff possible) in static block and then exit .. before the main method is called.
Below is the code :
/**
* @Author : Pragya Rawal
*
*/
public class NoMain {
static {
System.out.println("I am in static block");
System.exit(0);
}
}
Please note that you would not be able to run this program using Eclispe IDE. You will have to run using command line
javac NoMain.java
java NoMain
you would see the output : "I am in static block"
So, to avoid the JVM from searching for main method, we can execute the required code (iff possible) in static block and then exit .. before the main method is called.
Below is the code :
/**
* @Author : Pragya Rawal
*
*/
public class NoMain {
static {
System.out.println("I am in static block");
System.exit(0);
}
}
Please note that you would not be able to run this program using Eclispe IDE. You will have to run using command line
javac NoMain.java
java NoMain
you would see the output : "I am in static block"
June 23, 2010
Inefficient O(n^2) Method of finding Largest Recurring Substring in a string
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* @author Pragya Rawal
*/
public class LargestSubstring {
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter String : ");
try {
String input = br.readLine();
LargestSubstring str = new LargestSubstring();
String largestSubstr = str.getLargestSubstr(input);
if (largestSubstr != null) {
System.out.println("Largest Recurring substring is : "
+ largestSubstr);
}
} catch (IOException e) {
e.printStackTrace();
}
}
public String getLargestSubstr(String input) {
if (null == input || input.length() == 0) {
System.out.println("Invalid / Empty string ...");
return null;
} else {
int length = input.length();
int subStrLen = 0;
String longestSubStr = "";
String currentStr = "";
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
int k = i;
int l = j;
while ((k < length) && (l < length) &&(input.charAt(k) == input.charAt(l)) ) {
currentStr += input.charAt(k);
k++;
l++;
subStrLen++;
}
if (longestSubStr.length() < currentStr.length()) {
longestSubStr = currentStr;
}
currentStr = "";
}
}
return longestSubStr;
}
}
}
import java.io.IOException;
import java.io.InputStreamReader;
/**
* @author Pragya Rawal
*/
public class LargestSubstring {
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter String : ");
try {
String input = br.readLine();
LargestSubstring str = new LargestSubstring();
String largestSubstr = str.getLargestSubstr(input);
if (largestSubstr != null) {
System.out.println("Largest Recurring substring is : "
+ largestSubstr);
}
} catch (IOException e) {
e.printStackTrace();
}
}
public String getLargestSubstr(String input) {
if (null == input || input.length() == 0) {
System.out.println("Invalid / Empty string ...");
return null;
} else {
int length = input.length();
int subStrLen = 0;
String longestSubStr = "";
String currentStr = "";
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
int k = i;
int l = j;
while ((k < length) && (l < length) &&(input.charAt(k) == input.charAt(l)) ) {
currentStr += input.charAt(k);
k++;
l++;
subStrLen++;
}
if (longestSubStr.length() < currentStr.length()) {
longestSubStr = currentStr;
}
currentStr = "";
}
}
return longestSubStr;
}
}
}
June 22, 2010
Program(s) for finding power of a number
First, an interactive solution: (raising a to the power of b)
public double Power(double a, int b) {
if (b<=0) return 0; // we want a positive integer for the exponent
else {
double c=1;
for (int i=0; i
}
return c;
}
}
Very easy and linear. You start from one and go on multiplying c by a so c is respectively 1, a, a^2, a^3, ... a^b.
When done, you return c. This one takes linear time.
Second, a recursive solution:
public double Power(double a, int b) {
if (b<=0) return 0;
else if (b==1) return a;
else {
return a*Power(a,b-1);
}
}
This is also an easy one. What we do here? Simple: we calculate a^b=a * a^(b-1). This is done by the recursion and takes linear time as well.
So, how can we beat these to slugs? We do this way.
Let me give you an example with b being a power of 2 (which is the easiest to understand).
Imagine you have to evaluate a^64. You could think this:
a^64 = c^32 where c=a^2
c^32 = d^16 where d=c^2
d^16 = e^8 where e=d^2
e^8 = f^4 where f=e^2
f^4 = g^2 where g=f^2
g^2 = g*g
This requires 6 operations. Using one of the two previous algorithms takes 64 operations! In fact 6=log64 (log is meant in base 2 obviously).
Now, things are different when b isn't a power of 2, but the algorithm is just a bit more complicated. Let's see an example again. We'll evaluate a^20.
a^20 = c^10 where c=a^2
c^10 = d^5 where d=c^2
d^5 = d * e^2 where e=d^2
e^2 = e*e
This requires 5 operations. Log16=4 and log32=5 so as you can see we have here 5=Ceiling(log20). This happens when b isn't a power of 2, but the cost of the entire algorithm doesn't grow that much and we can still say that it runs in logarithmic time (this is more true when b is a medium-big number).
private double Power(double a, int b) {
if (b<0) {
throw new ApplicationException("B must be a positive integer or zero");
}
if (b==0) return 1;
if (a==0) return 0;
if (b%2==0) {
return Power(a*a, b/2);
} else if (b%2==1) {
return a*Power(a*a,b/2);
}
return 0;
}
Another solution can be :
a^b = 10^(ln[10](a) * b)
Reference : http://www.osix.net/modules/article/?id=696
public double Power(double a, int b) {
if (b<=0) return 0; // we want a positive integer for the exponent
else {
double c=1;
for (int i=0; i
}
return c;
}
}
Very easy and linear. You start from one and go on multiplying c by a so c is respectively 1, a, a^2, a^3, ... a^b.
When done, you return c. This one takes linear time.
Second, a recursive solution:
public double Power(double a, int b) {
if (b<=0) return 0;
else if (b==1) return a;
else {
return a*Power(a,b-1);
}
}
This is also an easy one. What we do here? Simple: we calculate a^b=a * a^(b-1). This is done by the recursion and takes linear time as well.
So, how can we beat these to slugs? We do this way.
Let me give you an example with b being a power of 2 (which is the easiest to understand).
Imagine you have to evaluate a^64. You could think this:
a^64 = c^32 where c=a^2
c^32 = d^16 where d=c^2
d^16 = e^8 where e=d^2
e^8 = f^4 where f=e^2
f^4 = g^2 where g=f^2
g^2 = g*g
This requires 6 operations. Using one of the two previous algorithms takes 64 operations! In fact 6=log64 (log is meant in base 2 obviously).
Now, things are different when b isn't a power of 2, but the algorithm is just a bit more complicated. Let's see an example again. We'll evaluate a^20.
a^20 = c^10 where c=a^2
c^10 = d^5 where d=c^2
d^5 = d * e^2 where e=d^2
e^2 = e*e
This requires 5 operations. Log16=4 and log32=5 so as you can see we have here 5=Ceiling(log20). This happens when b isn't a power of 2, but the cost of the entire algorithm doesn't grow that much and we can still say that it runs in logarithmic time (this is more true when b is a medium-big number).
private double Power(double a, int b) {
if (b<0) {
throw new ApplicationException("B must be a positive integer or zero");
}
if (b==0) return 1;
if (a==0) return 0;
if (b%2==0) {
return Power(a*a, b/2);
} else if (b%2==1) {
return a*Power(a*a,b/2);
}
return 0;
}
Another solution can be :
a^b = 10^(ln[10](a) * b)
Reference : http://www.osix.net/modules/article/?id=696
Clock Angle Problem : Amazon Ques
Clock angle problems relate two different measurements - angles and time. To answer the problem the relationship between the time shown (or an elapsed time) and the position of the hands (as given by an angle) has to be found.
A general approach to such problems is to consider the rate of change of the angle in degrees per minute. The hour hand of a normal 12-hour analogue clock turns 360 degrees in 12 hours. This is equivalent to 360 degrees in 720 minutes or 0.5 degrees per minute. The minute hand turns 360 degrees in 60 minutes or 6 degrees per minute.
Equation for the degrees on the hour hand
(0.5 degrees per minute on the hour hand) * (the time on the hour hand * 60 minutes per hour) + (0.5 degrees per minute on the minute hand) * (the time on the minute hand)
Equation for the degrees on the minute hand
(6 degrees per minute on the minute hand) * (the time on the minute hand)
'Example: The time is 5:24'
The degree on the hour hand is (0.5*5*60)+(0.5*24)=162 degrees
It could be also calculated as
Hour hand angle = total minutes / 2
In this case Hour hand angle = total minutes / 2 = ( (total hours * 60) + (total minutes) ) / 2 = ( (5 * 60) + 24 ) / 2 = 162 degrees
The degrees on the minute hand is 6*24=144 degrees
Minute handl angle = minutes * 6
Equation for the degrees between the hands
The angle between the hands can also be found using the formula cos-1(cos(5.5x)), where x=the number of minutes past noon. This will always give an angle between 0 and 180 degrees.
'Example: The time is 1:35'
1:35 is 1(60)+35=95 minutes past noon.
cos-1(cos(5.5*95))=cos-1(cos(522.5))=cos-1(-.95372)=162.5 degrees between the hands
Angle=mod(60H-11M)/2
where H= hours and M=minutes
When are hour and minute hands of a clock superimposed?
Hour and Minute hands are superimposed only when angle between them are 0. If hour and minute hands are superimposed at time h:m
0.5*60*h + 0.5*m = 6*m
m=(30/5.5)*h
for h varies from 0...11, clock hands are superimposed at 1:05.4545,2:10.90...12:00.
A general approach to such problems is to consider the rate of change of the angle in degrees per minute. The hour hand of a normal 12-hour analogue clock turns 360 degrees in 12 hours. This is equivalent to 360 degrees in 720 minutes or 0.5 degrees per minute. The minute hand turns 360 degrees in 60 minutes or 6 degrees per minute.
Equation for the degrees on the hour hand
(0.5 degrees per minute on the hour hand) * (the time on the hour hand * 60 minutes per hour) + (0.5 degrees per minute on the minute hand) * (the time on the minute hand)
Equation for the degrees on the minute hand
(6 degrees per minute on the minute hand) * (the time on the minute hand)
'Example: The time is 5:24'
The degree on the hour hand is (0.5*5*60)+(0.5*24)=162 degrees
It could be also calculated as
Hour hand angle = total minutes / 2
In this case Hour hand angle = total minutes / 2 = ( (total hours * 60) + (total minutes) ) / 2 = ( (5 * 60) + 24 ) / 2 = 162 degrees
The degrees on the minute hand is 6*24=144 degrees
Minute handl angle = minutes * 6
Equation for the degrees between the hands
The angle between the hands can also be found using the formula cos-1(cos(5.5x)), where x=the number of minutes past noon. This will always give an angle between 0 and 180 degrees.
'Example: The time is 1:35'
1:35 is 1(60)+35=95 minutes past noon.
cos-1(cos(5.5*95))=cos-1(cos(522.5))=cos-1(-.95372)=162.5 degrees between the hands
Angle=mod(60H-11M)/2
where H= hours and M=minutes
When are hour and minute hands of a clock superimposed?
Hour and Minute hands are superimposed only when angle between them are 0. If hour and minute hands are superimposed at time h:m
0.5*60*h + 0.5*m = 6*m
m=(30/5.5)*h
for h varies from 0...11, clock hands are superimposed at 1:05.4545,2:10.90...12:00.
March 26, 2010
Puzzle : The Elder Twin
One day Kerry celebrated her birthday. Two days later her older twin brother, Terry, celebrated his birthday. How come?
Sol : At the time she went into labor, the mother of the twins was traveling by boat. The older twin, Terry, was born first early on March 1st. The boat then crossed the international date line (or anytime zone line) and Kerry, the younger twin, was born on February the 28th. In a leap year the younger twin celebrates her birthday two days before her older brother..
http://www.bellaonline.com/articles/art39652.asp
Sol : At the time she went into labor, the mother of the twins was traveling by boat. The older twin, Terry, was born first early on March 1st. The boat then crossed the international date line (or anytime zone line) and Kerry, the younger twin, was born on February the 28th. In a leap year the younger twin celebrates her birthday two days before her older brother..
http://www.bellaonline.com/articles/art39652.asp
January 8, 2010
Mind Blowing Puzzle
Puzzle : There are 50 1-cent coins on the table. Initially all coins are tails up. Close your eyes, and I will turn over 10 random coins. The task is to divide all the coins into two groups blindly, so that the groups have an equal number of heads up.
Solution : We r sure that there r 10 heads in the group ..
So separate 10 random coins to form a group.. and remaining 40 will be in another group.. So if there are x heads in 10grp there will b 10-x heads in 40grp..
ie, the no of tails in 10grp is equal to the no of heads in 40grp..
So if u flip all the coins in 10grp all the tails will become heads and finally now both groups have same number of heads..
http://geniusbeauty.com/mental-beauty/brain-game-how-to-become-a-psychic/
Solution : We r sure that there r 10 heads in the group ..
So separate 10 random coins to form a group.. and remaining 40 will be in another group.. So if there are x heads in 10grp there will b 10-x heads in 40grp..
ie, the no of tails in 10grp is equal to the no of heads in 40grp..
So if u flip all the coins in 10grp all the tails will become heads and finally now both groups have same number of heads..
http://geniusbeauty.com/mental-beauty/brain-game-how-to-become-a-psychic/
December 28, 2009
ex write a program to reverse 20th bit of a 32 bit int
XOR the given number with a number whose 20th digit is one and all other digits are zero. THis will always work :)
XOR : returns true if both the digits are different , false otherwise :)
http://www.vipan.com/htdocs/bitwisehelp.html
XOR : returns true if both the digits are different , false otherwise :)
http://www.vipan.com/htdocs/bitwisehelp.html
Bitwise operations
Use: Shift left multiplies by 2; shift right divides by 2
y = x << 3; // Assigns 8*x to y.
y = (x << 2) + x; // Assigns 5*x to y.
y = x << 3; // Assigns 8*x to y.
y = (x << 2) + x; // Assigns 5*x to y.
September 14, 2009
Good Questions
Q: Why methods like wait() , notify(), notifyAll() are present in Object class and not in Runnable Interface?
Ans : http://www.coderanch.com/t/234332/Threads-Synchronization/java/why-does-Object-class-have
Puzzles (Probability Questions)
Q: Find the probability of getting a number with 7 between 100 and 999 (both inclusive).
Ans : 252/900
between 100 to 200, there are 19 numbers ..
19*8 = 152
+ 100 numbers in b/w 700 to 799.
Q: What is the number of comparisons in the worst case to merge two sorted lists containing n elements each?
A. 2n
B. 2n-1
C. 2n+1
D. 2n-2
Ans : 2n-1
Cyclomatic complexity (or conditional complexity) is a software metric (measurement). It was developed by Thomas J. McCabe Sr. in 1976 and is used to measure the complexity of a program. It directly measures the number of linearly independent paths through a program's source code. For instance, if the source code contained no decision points such as IF statements or FOR loops, the complexity would be 1, since there is only a single path through the code. If the code had a single IF statement containing a single condition there would be two paths through the code, one path where the IF statement is evaluated as TRUE and one path where the IF statement is evaluated as FALSE.
Mathematically, the cyclomatic complexity of a structured program[note 1] is defined with reference to a directed graph containing the basic blocks of the program, with an edge between two basic blocks if control may pass from the first to the second (the control flow graph of the program). The complexity is then defined as:[2]
M = E - N + 2P
where
M = cyclomatic complexity
E = the number of edges of the graph
N = the number of nodes of the graph
P = the number of connected components.
The same function as above, shown as a strongly-connected control flow graph, for calculation via the alternative method. For this graph, E = 10, N = 8 and P = 1, so the cyclomatic complexity of the program is still 3.
An alternative formulation is to use a graph in which each exit point is connected back to the entry point. In this case, the graph is said to be strongly connected, and the cyclomatic complexity of the program is equal to the cyclomatic number of its graph (also known as the first Betti number), which is defined as:[2]
M = E - N + P
This may be seen as calculating the number of linearly independent cycles that exist in the graph, i.e. those cycles that do not contain other cycles within themselves. Note that because each exit point loops back to the entry point, there is at least one such cycle for each exit point.
For a single program (or subroutine or method), P is always equal to 1. Cyclomatic complexity may, however, be applied to several such programs or subprograms at the same time (e.g., to all of the methods in a class), and in these cases P will be equal to the number of programs in question, as each subprogram will appear as a disconnected subset of the graph.
It can be shown that the cyclomatic complexity of any structured program with only one entrance point and one exit point is equal to the number of decision points (i.e., 'if' statements or conditional loops) contained in that program plus one.[2][3]
Cyclomatic complexity may be extended to a program with multiple exit points; in this case it is equal to:
p - s + 2
where p is the number of decision points in the program, and s is the number of exit points
XOR of two numbers a and b can be found :
a^b or a|b & !(a&b)
Ans : http://www.coderanch.com/t/234332/Threads-Synchronization/java/why-does-Object-class-have
Puzzles (Probability Questions)
Q: Find the probability of getting a number with 7 between 100 and 999 (both inclusive).
Ans : 252/900
between 100 to 200, there are 19 numbers ..
19*8 = 152
+ 100 numbers in b/w 700 to 799.
Q: What is the number of comparisons in the worst case to merge two sorted lists containing n elements each?
A. 2n
B. 2n-1
C. 2n+1
D. 2n-2
Ans : 2n-1
Cyclomatic complexity (or conditional complexity) is a software metric (measurement). It was developed by Thomas J. McCabe Sr. in 1976 and is used to measure the complexity of a program. It directly measures the number of linearly independent paths through a program's source code. For instance, if the source code contained no decision points such as IF statements or FOR loops, the complexity would be 1, since there is only a single path through the code. If the code had a single IF statement containing a single condition there would be two paths through the code, one path where the IF statement is evaluated as TRUE and one path where the IF statement is evaluated as FALSE.
Mathematically, the cyclomatic complexity of a structured program[note 1] is defined with reference to a directed graph containing the basic blocks of the program, with an edge between two basic blocks if control may pass from the first to the second (the control flow graph of the program). The complexity is then defined as:[2]
M = E - N + 2P
where
M = cyclomatic complexity
E = the number of edges of the graph
N = the number of nodes of the graph
P = the number of connected components.
The same function as above, shown as a strongly-connected control flow graph, for calculation via the alternative method. For this graph, E = 10, N = 8 and P = 1, so the cyclomatic complexity of the program is still 3.
An alternative formulation is to use a graph in which each exit point is connected back to the entry point. In this case, the graph is said to be strongly connected, and the cyclomatic complexity of the program is equal to the cyclomatic number of its graph (also known as the first Betti number), which is defined as:[2]
M = E - N + P
This may be seen as calculating the number of linearly independent cycles that exist in the graph, i.e. those cycles that do not contain other cycles within themselves. Note that because each exit point loops back to the entry point, there is at least one such cycle for each exit point.
For a single program (or subroutine or method), P is always equal to 1. Cyclomatic complexity may, however, be applied to several such programs or subprograms at the same time (e.g., to all of the methods in a class), and in these cases P will be equal to the number of programs in question, as each subprogram will appear as a disconnected subset of the graph.
It can be shown that the cyclomatic complexity of any structured program with only one entrance point and one exit point is equal to the number of decision points (i.e., 'if' statements or conditional loops) contained in that program plus one.[2][3]
Cyclomatic complexity may be extended to a program with multiple exit points; in this case it is equal to:
p - s + 2
where p is the number of decision points in the program, and s is the number of exit points
XOR of two numbers a and b can be found :
a^b or a|b & !(a&b)
August 25, 2009
Three ants puzzle
There are three ants at the three corners of a regular
triangle. Each ant starts moving on a straight line toward
another, randomly chosen corner. What is the probability
that none of the ants collide?
2 comments:
Anonymous said...
25%. From the ant's perspective each can go left or right. There are 8 poss combinations - LLL, LLR, LRL, RLL, LRR, RLR, RRL, and RRR. You can also work that out by raising 2 (the number of choices) to the power of 3 (the number of choosers) = 2 x 2 x 2 = 8. In only 2 of these cases (LLL and RRR will there be no collisions, so 2 / 8 = 0.25
Secret Squïrrel
March 9, 2008 6:34 AM
Neeraj said...
There are two directions tomove for each ant
Thus total 2x2x2 =8 movements in different directions
out of these only two result in non - collisions of any of the ant - either all clockwise or all counter clockwise
Thus rest 6 result in at leaat 1 collission.
Thus probablility of non collision = 2/8=1/4=0.25
Reference : http://puzzles4you.blogspot.com/2008/03/three-ants.html
triangle. Each ant starts moving on a straight line toward
another, randomly chosen corner. What is the probability
that none of the ants collide?
2 comments:
Anonymous said...
25%. From the ant's perspective each can go left or right. There are 8 poss combinations - LLL, LLR, LRL, RLL, LRR, RLR, RRL, and RRR. You can also work that out by raising 2 (the number of choices) to the power of 3 (the number of choosers) = 2 x 2 x 2 = 8. In only 2 of these cases (LLL and RRR will there be no collisions, so 2 / 8 = 0.25
Secret Squïrrel
March 9, 2008 6:34 AM
Neeraj said...
There are two directions tomove for each ant
Thus total 2x2x2 =8 movements in different directions
out of these only two result in non - collisions of any of the ant - either all clockwise or all counter clockwise
Thus rest 6 result in at leaat 1 collission.
Thus probablility of non collision = 2/8=1/4=0.25
Reference : http://puzzles4you.blogspot.com/2008/03/three-ants.html
Three ants puzzle
There are three ants at the three corners of a regular
triangle. Each ant starts moving on a straight line toward
another, randomly chosen corner. What is the probability
that none of the ants collide?
25%. From the ant's perspective each can go left or right. There are 8 poss combinations - LLL, LLR, LRL, RLL, LRR, RLR, RRL, and RRR. You can also work that out by raising 2 (the number of choices) to the power of 3 (the number of choosers) = 2 x 2 x 2 = 8. In only 2 of these cases (LLL and RRR will there be no collisions, so 2 / 8 = 0.25
There are two directions to move for each ant
Thus total 2x2x2 =8 movements in different directions
out of these only two result in non - collisions of any of the ant - either all clockwise or all counter clockwise
Thus rest 6 result in at leaat 1 collission.
Thus probablility of non collision = 2/8=1/4=0.25
Reference : http://puzzles4you.blogspot.com/2008/03/three-ants.html
triangle. Each ant starts moving on a straight line toward
another, randomly chosen corner. What is the probability
that none of the ants collide?
25%. From the ant's perspective each can go left or right. There are 8 poss combinations - LLL, LLR, LRL, RLL, LRR, RLR, RRL, and RRR. You can also work that out by raising 2 (the number of choices) to the power of 3 (the number of choosers) = 2 x 2 x 2 = 8. In only 2 of these cases (LLL and RRR will there be no collisions, so 2 / 8 = 0.25
There are two directions to move for each ant
Thus total 2x2x2 =8 movements in different directions
out of these only two result in non - collisions of any of the ant - either all clockwise or all counter clockwise
Thus rest 6 result in at leaat 1 collission.
Thus probablility of non collision = 2/8=1/4=0.25
Reference : http://puzzles4you.blogspot.com/2008/03/three-ants.html
How many such points on the earth
Q Find all the points on the globe from which if you travel 1km south, then 1 km east and then 1 km north; you end up at the same point from which you started.
Hints:
1. There is an infinite amount of such points.
2. The answer is 100% true, no tricks - so don't waste your time searching for any.
Ans : Half the answer is this:
There is some place on the globe, where the perimeter of the earth is exactly 1 km. If you start walking from any point which is 1 km north of that ring, and walk 1 km south, you'll end up on the 1 km perimeter. You'll then go 1 km east which will take you all the way around the globe and then you'll go 1 km north and end up in the starting point.
This is the answer which many people give, but it's not full. It gives us a stip (or a ring) of points with this property, but there is also an infinite amount of such strips (or rings):
The full answer, as given by UnToha, is that the perimeter of the walk around the globe doesn't have to be 1 km. It can be any factor of 1 km so that when walking 1 km east, you'll walk some K times around the globe (where K has to be an integer), thus making several complete trips around the globe. This gives us an infinite amount of rings, each having an infinite amount of points, all of which have this strange property.
reference : http://neworder.box.sk/forum/viewtopic.php?id=40242
Hints:
1. There is an infinite amount of such points.
2. The answer is 100% true, no tricks - so don't waste your time searching for any.
Ans : Half the answer is this:
There is some place on the globe, where the perimeter of the earth is exactly 1 km. If you start walking from any point which is 1 km north of that ring, and walk 1 km south, you'll end up on the 1 km perimeter. You'll then go 1 km east which will take you all the way around the globe and then you'll go 1 km north and end up in the starting point.
This is the answer which many people give, but it's not full. It gives us a stip (or a ring) of points with this property, but there is also an infinite amount of such strips (or rings):
The full answer, as given by UnToha, is that the perimeter of the walk around the globe doesn't have to be 1 km. It can be any factor of 1 km so that when walking 1 km east, you'll walk some K times around the globe (where K has to be an integer), thus making several complete trips around the globe. This gives us an infinite amount of rings, each having an infinite amount of points, all of which have this strange property.
reference : http://neworder.box.sk/forum/viewtopic.php?id=40242
May 27, 2009
program to find permutations
import java.util.ArrayList;
import java.util.List;
public class Permutation {
public static void permuteString(List permutations,
String beginningString, String endingString) {
String output = beginningString + endingString;
if (endingString.length() <= 1) {
permutations.add(output);
} else {
for (int i = 0; i < endingString.length(); i++) {
try {
String newString = endingString.substring(0, i)
+ endingString.substring(i + 1);
permuteString(permutations, beginningString
+ endingString.charAt(i), newString);
} catch (StringIndexOutOfBoundsException exception) {
exception.printStackTrace();
}
}
}
}
public static void main(String[] args) {
List permutations = new ArrayList();
permuteString(permutations, "", "123456789");
for (String string : permutations) {
// System.out.println(output);
int first = Integer.parseInt(string.substring(0, 4));
int second = Integer.parseInt(string.substring(4, 5));
int third = Integer.parseInt(string.substring(5, 9));
if ((first * second) == third) {
System.out.println(string + "-->true");
}
}
}
}
import java.util.List;
public class Permutation {
public static void permuteString(List
String beginningString, String endingString) {
String output = beginningString + endingString;
if (endingString.length() <= 1) {
permutations.add(output);
} else {
for (int i = 0; i < endingString.length(); i++) {
try {
String newString = endingString.substring(0, i)
+ endingString.substring(i + 1);
permuteString(permutations, beginningString
+ endingString.charAt(i), newString);
} catch (StringIndexOutOfBoundsException exception) {
exception.printStackTrace();
}
}
}
}
public static void main(String[] args) {
List
permuteString(permutations, "", "123456789");
for (String string : permutations) {
// System.out.println(output);
int first = Integer.parseInt(string.substring(0, 4));
int second = Integer.parseInt(string.substring(4, 5));
int third = Integer.parseInt(string.substring(5, 9));
if ((first * second) == third) {
System.out.println(string + "-->true");
}
}
}
}
Good Ques n their solutions
Q : reverse a string without using any loops (use recursion)
A : public static String Reverse(String strParam) {
if (strParam.length() == 1) {
return strParam;
} else {
return Reverse(strParam.substring(1)) + strParam.substring(0, 1);
}
}
Q: Write a algorithm to find out the substring in a string and find out the number of occurrences also
A: public static void findSubString(String input, String subStr) {
int occurance = 0;
int inp_len = input.length();
int sub_len = subStr.length();
for (int i = 0; i < inp_len; i++) {
System.out.println("Scanning Character : " + input.charAt(i));
int charsmatched = 0;
if (input.charAt(i) == subStr.charAt(0)) {
charsmatched++;
for (int k = 1; k < sub_len; k++) {
if ((i < (inp_len - sub_len)) && (input.charAt(i + k) == subStr.charAt(k))) {
charsmatched++;
}
if (charsmatched == sub_len) {
occurance++;
System.out.println("Substring found : " + occurance + " times");
}
}
}
}
System.out.println("Total ocurances : " + occurance);
}
Q: 4. Find out the nth number in a fibonnaci series.
A:
public static long fibonacci(int n) {
long sum = 0;
if (n < 0) {
System.out.println("Enter a positive number");
} else if (n == 0) {
sum += 0;
return sum;
} else if (n == 1) {
sum += 1;
} else {
sum = fibonacci(n - 1) + fibonacci(n - 2);
}
return sum;
}
Q: 5. Sentence is given , u have to reverse words
A: public static void rvrsWords(String input) {
System.out.println("Original : " + input);
String output = " ";
if (input != null) {
String[] array = input.split(" ");
int len = array.length;
for (int i = 0; i < (len / 2); i++) {
String temp = array[i];
array[i] = array[len - i - 1];
array[len - i - 1] = temp;
output = " " + array[i];
}
System.out.println("Reversed Array : ");
for (int i = 0; i < (len); i++) {
System.out.println(array[i] + " ");
}
}
}
A 2 : private static String reverseString(String string) {
String reverse="",temp="";
for(int i=0;ichar c= string.charAt(i);
if(c==' ' && temp.length()>0){
reverse = temp + " " + reverse;
temp="";
}else{
temp += c;
}
}
reverse = temp + " " + reverse;
return reverse;
}
Q: Given array A[i] = i+1 for i = 0 to N-1
create array O[i] = product of all elements of array A except A[i] for i = 0 to N-1
eg: for N = 3, O[2] = A[0]*A[1]
O[1] = A[0]*A[2] (we cant multiple with A[1])
public class Product {
public static void main(String[] args) {
int n =5;
int[] a= new int[n] ;
for(int i = 0 ; i < n ; i++) {
a[i] = i+1;
System.out.println(a[i]);
}
Product p = new Product();
p.product(a, 3);
}
public void product(int[] a, int x ) {
int product = 1;
for(int i = 0; i < a.length ; i++) {
if(!(i ==x)) {
product *= a[i];
}
}
System.out.println("Product is : "+ product);
}
}
A : public static String Reverse(String strParam) {
if (strParam.length() == 1) {
return strParam;
} else {
return Reverse(strParam.substring(1)) + strParam.substring(0, 1);
}
}
Q: Write a algorithm to find out the substring in a string and find out the number of occurrences also
A: public static void findSubString(String input, String subStr) {
int occurance = 0;
int inp_len = input.length();
int sub_len = subStr.length();
for (int i = 0; i < inp_len; i++) {
System.out.println("Scanning Character : " + input.charAt(i));
int charsmatched = 0;
if (input.charAt(i) == subStr.charAt(0)) {
charsmatched++;
for (int k = 1; k < sub_len; k++) {
if ((i < (inp_len - sub_len)) && (input.charAt(i + k) == subStr.charAt(k))) {
charsmatched++;
}
if (charsmatched == sub_len) {
occurance++;
System.out.println("Substring found : " + occurance + " times");
}
}
}
}
System.out.println("Total ocurances : " + occurance);
}
Q: 4. Find out the nth number in a fibonnaci series.
A:
public static long fibonacci(int n) {
long sum = 0;
if (n < 0) {
System.out.println("Enter a positive number");
} else if (n == 0) {
sum += 0;
return sum;
} else if (n == 1) {
sum += 1;
} else {
sum = fibonacci(n - 1) + fibonacci(n - 2);
}
return sum;
}
Q: 5. Sentence is given , u have to reverse words
A: public static void rvrsWords(String input) {
System.out.println("Original : " + input);
String output = " ";
if (input != null) {
String[] array = input.split(" ");
int len = array.length;
for (int i = 0; i < (len / 2); i++) {
String temp = array[i];
array[i] = array[len - i - 1];
array[len - i - 1] = temp;
output = " " + array[i];
}
System.out.println("Reversed Array : ");
for (int i = 0; i < (len); i++) {
System.out.println(array[i] + " ");
}
}
}
A 2 : private static String reverseString(String string) {
String reverse="",temp="";
for(int i=0;i
if(c==' ' && temp.length()>0){
reverse = temp + " " + reverse;
temp="";
}else{
temp += c;
}
}
reverse = temp + " " + reverse;
return reverse;
}
Q: Given array A[i] = i+1 for i = 0 to N-1
create array O[i] = product of all elements of array A except A[i] for i = 0 to N-1
eg: for N = 3, O[2] = A[0]*A[1]
O[1] = A[0]*A[2] (we cant multiple with A[1])
public class Product {
public static void main(String[] args) {
int n =5;
int[] a= new int[n] ;
for(int i = 0 ; i < n ; i++) {
a[i] = i+1;
System.out.println(a[i]);
}
Product p = new Product();
p.product(a, 3);
}
public void product(int[] a, int x ) {
int product = 1;
for(int i = 0; i < a.length ; i++) {
if(!(i ==x)) {
product *= a[i];
}
}
System.out.println("Product is : "+ product);
}
}
March 4, 2009
Interview Questions
Q: How many cars are there in the USA?
Sol1: Total number of cars in the USA = (Total number of cars manufactured in the USA + Total number of cars imported in the USA - Total number of cars exported from the USA)
Sol2:
Let
Population = 250 million
People per household = 3
Cars/household = 1
Avg life of car = 10 years
Total cars = ((25 X 10^6) / 3) / 10 - 1
Sol3: aprox population of USA is x ... and approx population of people ownig cars be say 20 percent or 30 percent ... (minus children, old people, so on) so there so I would go with .25x as number of people with cars and that should give me an approx number of so many cars ...
Sol1: Total number of cars in the USA = (Total number of cars manufactured in the USA + Total number of cars imported in the USA - Total number of cars exported from the USA)
Sol2:
Let
Population = 250 million
People per household = 3
Cars/household = 1
Avg life of car = 10 years
Total cars = ((25 X 10^6) / 3) / 10 - 1
Sol3: aprox population of USA is x ... and approx population of people ownig cars be say 20 percent or 30 percent ... (minus children, old people, so on) so there so I would go with .25x as number of people with cars and that should give me an approx number of so many cars ...
March 2, 2009
Icosahedron Coloring Problem
Problem :How many different ways can you color an icosahedron with one of three colors on each face?
Sol :
http://www.mrwright.org
Sol :
As with any mathematical problem, we must understand the problem before we can attempt to solve it. First, an icosahedron is a regular solid consisting of 20 faces, each of which is an equilateral triangle. We wish to color each face of the icosahedron with one of three colors. A sample icosahedron colored red, green, and blue is pictured at right. We will permit any face to be colored any of the three colors, regardless of the colors of adjacent faces.
An initial guess for the number of ways to color the icosahedron might go as follows: we can choose any of three colors for the first face, and no matter which color we choose, we can choose any of three colors for the second face, so there are 3 · 3 = 9 ways to color the first 2 faces. Continuing in this fasion, we see there are 33 ways to color the first three faces, and in general, 3n ways to color the first n faces. Therefore, there are 320 = 3,486,784,401 ways to color the 20 faces of the icosahedron with three colors.
The problem with the above reasoning is that we have overcounted. If we were coloring an oriented icosahedron (one that is fixed in space), then 320 would be the correct answer. However, the question is much more interesting if we allow our icosahedron to be unoriented, that is, the icosahedron may be rotated in space. Each colored icosahedron can be positioned many different ways, so two colored icosahedrons that at first glance appear different may be the same if one can be rotated so that its coloring matches that of the other. The major task in counting the number of colorings, then, is to determine when two colorings are the same. Therefore, we will study some simpler problems to gain intuition before we answer the question, "How many ways can you color an unoriented icosahedron with three colors?"
Basic Combinatorics
First we will count the ways we can arrange n objects in a line. Clearly we can choose any of n distinct objects to go in the first position, and regardless of our choice, we can choose any of n – 1 for the second position. We can choose any of n – 2 for the third position, and so on, until we obtain the formula n(n – 1)(n – 2) ··· (2)(1) = n! ways to arrange n elements in a line.
Now suppose we wanted to arrange n distinct objects in an unoriented circle (that is, a circle that we can rotate). An equivalent question is, "How many different necklaces can we make with n beads of different colors?" Since we can rotate the necklace, we can choose one specific bead and fix it at the top. We can then choose any of n – 1 beads to be positioned to the right of the first bead, and n – 2 beads for the next position, and so on. The number of unique necklaces then becomes 1·(n – 1)(n – 2) ··· (2)(1) = (n – 1)!
The problem becomes more difficult when we have nonunique items to arrange in a circle. Consider the following two orderings of orange and blue dots arranged in a circle. They are different when fixed in space, but as necklaces made from orange and blue beads, they are the same, since we can rotate one to align it with the other. This example forces us to consider the symmetries of elements arranged in a circle.
Answer: 58,130,055
http://www.mrwright.org
Subscribe to:
Posts (Atom)