1.Given a rectangular (cuboidal for the puritans) cake with a rectangular piece removed (any size or orientation), how would you cut the remainder of the cake into two equal halves with one straight cut of a knife ?
The cut (plane) should pass through the center of the two rectangles: the outer cake and the inner hollow area. Since any plane passing through the center of the cuboid will divide the volume in two halves, both the cake and hollow area are divided into two equal halves.
2.Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array if you like.
Many solutions: Bit vector, sorting...
3.How many points are there on the globe where by walking one mile south, one mile east and one mile north you reach the place where you started.
The answer is "many points". The set of such points is given as {North pole, special circle}.
From north pole, walking one mile south followed by one mile east still keeps you one mile south of North pole.
The special circle consists of a set of points defined as follows. Let's say you were to locate a spot near the South Pole where the circular distance "around" the Earth's North-South axis is 1 mile. The path of such a journey would create a circle with a radius of approximately 840.8 feet (because C=2.r.pi). Call this point X. Now consider another point Y one mile north of X. The special circle is the circular path around North-South axis going through Y. If you begin you journey from any point (say Y1) on this special circle, and travel one mile south, you get to a point (say X1) on the circle of point X. Now one mile east will bring you back to X1, because circumference of circle of X is 1 mile. Then one mile North brings you back to Y1.
4.In a X's and 0's game (i.e. TIC TAC TOE) if you write a program for this give a fast way to generate the moves by the computer. I mean this should be the fastest way possible.
The answer is that you need to store all possible configurations of the board and the move that is associated with that. Then it boils down to just accessing the right element and getting the corresponding move for it. Do some analysis and do some more optimization in storage since otherwise it becomes infeasible to get the required storage in a DOS machine.
5.There are 3 ants at 3 corners of a triangle, they randomly start moving towards another corner.. what is the probability that they don't collide.
All three should move in the same direction - clockwise or anticlockwise. Probability is 1/4.
The cut (plane) should pass through the center of the two rectangles: the outer cake and the inner hollow area. Since any plane passing through the center of the cuboid will divide the volume in two halves, both the cake and hollow area are divided into two equal halves.
2.Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array if you like.
Many solutions: Bit vector, sorting...
3.How many points are there on the globe where by walking one mile south, one mile east and one mile north you reach the place where you started.
The answer is "many points". The set of such points is given as {North pole, special circle}.
From north pole, walking one mile south followed by one mile east still keeps you one mile south of North pole.
The special circle consists of a set of points defined as follows. Let's say you were to locate a spot near the South Pole where the circular distance "around" the Earth's North-South axis is 1 mile. The path of such a journey would create a circle with a radius of approximately 840.8 feet (because C=2.r.pi). Call this point X. Now consider another point Y one mile north of X. The special circle is the circular path around North-South axis going through Y. If you begin you journey from any point (say Y1) on this special circle, and travel one mile south, you get to a point (say X1) on the circle of point X. Now one mile east will bring you back to X1, because circumference of circle of X is 1 mile. Then one mile North brings you back to Y1.
4.In a X's and 0's game (i.e. TIC TAC TOE) if you write a program for this give a fast way to generate the moves by the computer. I mean this should be the fastest way possible.
The answer is that you need to store all possible configurations of the board and the move that is associated with that. Then it boils down to just accessing the right element and getting the corresponding move for it. Do some analysis and do some more optimization in storage since otherwise it becomes infeasible to get the required storage in a DOS machine.
5.There are 3 ants at 3 corners of a triangle, they randomly start moving towards another corner.. what is the probability that they don't collide.
All three should move in the same direction - clockwise or anticlockwise. Probability is 1/4.
No comments:
Post a Comment