teja.sbt
BAN USER- 0of 0 votes
AnswersDesign an algorithm to find the least common ancestor of two nodes in a Binary tree(Note: Its not a binary search Tree)
Node Structure is given as
- teja.sbt in United States for KindleClass Node{ int data; Node leftchild; Node Rightchild; }
| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test Algorithm - 0of 0 votes
AnswersThe programming problem is:
- teja.sbt in United States for Speech Recognition
Each turn of a simulation, car A has a 10% chance of moving 5 feet forward, and a 90% chance of staying still. Similarly, each turn of the simulation car B has a 60% chance of moving 1 feet forward, and a 40% chance of staying still. A race consists of however many turns in the simulation it takes to travel 100ft. Write a simulation to run such a race, and run it 100 times. Count how many times car A wins and how many times car B wins. Do the results match up with what you would expect from a mathematical analysis of the problem?| Report Duplicate | Flag | PURGE
Raytheon Software Engineer / Developer Math & Computation
import java.util.Random;
public class CarRace {
public void raceCars(){
int carA=0;
int carB=0;
int carAchance=0;
int carBchance=0;
Random rand = new Random();
for(int i=0;i<100;i++){
carA = 0;
carB = 0;
while(carA !=100 && carB!=100) {
if(rand.nextInt(100) < 10){
carA=carA+5;
}
if(rand.nextInt(100) < 60){
carB=carB+1;
}
}
if(carA == 100){
carAchance++;
}
if(carB == 100){
carBchance++;
}
if(carA>carB){
System.out.print("car A won \n");
}
else if(carA<carB){
System.out.print("car B won \n");
}
else if(carA == carB){
System.out.print("Both won equal number of times ");
}
}
}
public static void main(String args[]){
CarRace race = new CarRace();
race.raceCars();
}
}
My friend came up with this brilliant answer. He said :
- teja.sbt November 23, 20121. List the pre and post order traversal of the tree.
(Now observe that the common parent of the two nodes will occur before both the nodes and after both the nodes in the pre and post order traversal listing respectively.)
2. In a pre-order traversal list place all the nodes occurring before n1 and n2 in a hash map h1
Preorder traversal P1: [....] n1....n2......
3. Now traverse the nodes which occur after both the Nodes n1 and n2. -
Postorder Traversal P2: ....n2....n1[....]
4. Return the first node which maps to the hash map h1 in the list P2