Maximum Area Rectangle in Histogram using linear search via stack of incomplete sub problems

We have already discussed lots of solution to solve this here, and using the stack to achieve is one of them.

Problem

Question: Find the maximum rectangle (in terms of area) under a histogram in linear time. I mean the area of largest rectangle that fits entirely in the Histogram.

(Please refer figures before code section for clarity. If I include bar i completely, those figure will tell how much maximum area rectangle I can get.)

Consider the histogram below:

Hieghts = { 6,2,5,4,5,1,6}

Max area of the rectangle:

Max area = 4 * 3 = 12



This problem seems like container-with-most-water problem discussed here. But the difference is that we are not using two "wood boards" to make a bucket, but using several boards with different heights.

Brute force solution

A straightforward answer is to go for each bar in the histogram and find the maximum possible area in histogram for it. Finally find the maximum of these values. This will require O(n^2) time but this will be huge if we have a big histogram with thousands of bars. 




Solution with Stack

Here we will use stack (of-course it rings the bell that recursive solution is also possible).

 Time complexity here will be O(n) as we will see. Though as discussed here, there are many better solutions available.

Here we process the elements from left to right order, and maintain a stack of information about started but yet unfinished histograms.The point of this algorithm is to maintain a stack where higher element is always greater or equal to the lower element. Why do we need to maintain that kind of stack? Because if we have a non-decreasing list, we can easily calculate the maximum area in one scan.

We just need to compare: height[i] * (n – i) for every i. (It will be clear in sometime).
So how do we maintain this stack? If we keep seeing larger element, we just need to push them onto the stack. If we see a smaller (compared to the top element on the stack) element, we need to do two things:

1. Pop the stack until we can maintain the non-decreasing order. Pushing the smaller element for m times, where m = number of popped elements.
2. Keep track of the maximum area that cause by those pop.

For example, we have height = {1,3,5,7,4}.
We push onto the stack for {1,3,5,7} then we see 4. 4 is less than 7, so we need to pop. We stop popping until we see 3. However many times we pop, we push 4 onto the stack. Therefore the resulted stack would be {1,3,4,4,4}. Because of popping 7, we need to remember that the maximum area that contains 7 is 7. The largest area that contains 5, the other element which get popped, is 10. So we take that down. We then finish processing all the elements in the original array and end up with a non-decreasing stack {1,3,4,4,4}. We can compute the largest area of this stack, which is 4*3 = 12. Since 12 is larger than the previous largest, 10, we output 12.

Code in java

public int largestRectangleArea(int[] height) {
    Stack<Integer> stack =
        new Stack<Integer>();
    int max = 0;
    int i = 0;
    while(i < height.length) {
        if(stack.isEmpty() ||
            height[i] >= stack.peek()) {
            stack.push(height[i]);
            i++;
        }
        else {
            int count = 0;
            while(!stack.isEmpty() &&
                stack.peek() > height[i]) {
                count++;
                int top = stack.pop();
                max = Math.max(max, top * count);
            }
            for(int j = 0; j < count + 1; ++j) {
                stack.push(height[i]);
            }
            i++;
        }
    }
     
    int count = 0;
    while(!stack.isEmpty()) {
        count++;
        max = Math.max(max, stack.pop() * count);
    }
    return max;
}

Dry running the code



Sources
http://tech-queries.blogspot.in/2011/03/maximum-area-rectangle-in-histogram.html
http://blog.theliuy.com/largest-rectangle-in-histogram/
http://tianrunhe.wordpress.com/2012/07/26/largest-rectangle-in-histogram/

Read More

Find largest sub-matrix with all 1s (not necessarily square)

In last post, we saw a dynamic programming approach to for finding maximum size square sub-matrix with all 1s. In this post, we will discuss how to find largest all 1s sub-matrix in a binary matrix. The resultant sub-matrix is not necessarily a square sub-matrix.

Example:

1  1  0  0  1  0

0  1  1  1  1  1

1  1  1  1  1  0

0  0  1  1  0  0

Largest all 1s sub-matrix is from (1,1) to (2,4).

1  1  1  1

1  1  1  1

Algorithm: If we draw a histogram of all 1’s cells in above rows (until we find a 0) for a particular row, then maximum all 1s sub-matrix ending in that row will the equal to maximum area rectangle in that histogram. Below is the example for 3rd row in above discussed matrix:

If we calculate this area for all the rows, maximum area will be our answer. We can extend our solution very easily to find start and end co-ordinates.

For above purpose, we need to generate an auxiliary matrix S[][] where each element represents the number of 1s above and including it, up until the first 0. S[][] for above matrix will be as shown below:

1  1  0  0  1  0

0  2  1  1  2  1

1  3  2  2  3  0

0  0  3  3  0  0

Now we can simple call our maximum rectangle in histogram on every row in S[][] and update the maximum area every time.

Also we don’t need any extra space for saving S. We can update original matrix (A) to S and after calculation, we can convert S back to A.

Code: I am not writing the code for largestArea() function. One can find its definition in this post.

#define ROW 10  
    #define COL 10  
      
    int find_max_matrix(int A[ROW][COL])  
    {  
     int i, j;  
     int max, cur_max;  
     cur_max = 0;  
      
     //Calculate Auxilary matrix  
     for (i=1; i<ROW; i++)  
         for(j=0; j<COL; j++)  
         {  
             if(A[i][j] == 1)  
                 A[i][j] = A[i-1][j] + 1;  
         }  
      
     //Calculate maximum area in S for each row  
     for (i=0; i<ROW; i++)  
     {       
         max = largestArea(A[i], COL);  
         if (max > cur_max)  
             cur_max = max;  
     }  
      
     //Regenerate Oriignal matrix  
     for (i=ROW-1; i>0; i--)  
         for(j=0; j<COL; j++)  
         {  
             if(A[i][j])  
                 A[i][j] = A[i][j] - A[i-1][j];  
         }  
      
     return cur_max;  
    }  

Complexity: Lets say that total number of rows and columns in A are m and n respectively and N = m*n

Complexity of calculating S = O(m*n) = O(N)

Complexity of LargestArea() for every row = O(n) since there are n elements in every row. Since we called LargestArea() m times so total complexity of calculating largest area = O(m*n) = O(N)

Complexity of converting S to A = O(m*n) = O(N)

So total time complexity = O(N)

Since we are not using any extra space, so space complexity is O(1).

Note: Above function only returns largest area, which can be very easily modified to get start and row indexes as well.

Read More

Maximum Area Rectangle in Histogram

Question: Find the maximum rectangle (in terms of area) under a histogram in linear time. I mean the area of largest rectangle that fits entirely in the Histogram.

(Please refer figures before code section for clarity. If I include bar i completely, those figure will tell how much maximum area rectangle I can get.)

Consider the histogram below:

Max area of the rectangle:

Max area = 4 * 3 = 12

 

Note that the area of the largest rectangle may exceed the largest 32-bit integer. Due to the large numbers of rectangles, the naive O(n²) solution is too slow. Even though O(n*log(n)) or O(n) is required, there are several kinds of solutions to this problem. In the following, we will identify a histogram with the sequence of the heights of its rectangles.

1. Divide-and-conquer using order-statistic trees.
   Initially, build a binary, node- and leaf-labeled tree that contains the histogram as its frontier, i.e., as its leaves from left to right. Mark each inner node with the minimum of the labels of its subtree. Note that such a tree is most efficiently stored in an array using the heap data structure, where the children of node i are located at positions i*2 and i*2+1, respectively. With such an order-statistic tree, the minimum element in a subhistogram (i.e., a subsegment of the sequence of heights) can be found in O(log(n)) steps by using the additional information in the inner nodes to avoid searching all leaves.
   To calculate the maximum rectangle unter a subhistogram, we thus find the minimum height in that subhistogram, and divide it at just that place into two smaller histograms. The maximum rectangle is either completely in the left part, or completely in the right part, or it contains the rectangle with minimum height. The first two cases are solved recursively, while in the third case we know that the width of the maximum rectangle is the width of the whole subhistogram, since we chose the minimum height. Because every element serves exactly once as a place to divide, and we spend O(log(n)) for every division, the complexity of this algorithm is O(n*log(n)).
2. Linear search using order-statistic trees.
   Initially, construct an order-statistic tree as just described. For every element, we find the largest rectangle that includes that element. The height of the rectangle is, of course, the value of the element. Use the order-statistic tree to efficiently find the nearest elements that have smaller heights, both to the left and to the right. The width, and therefore the area of the rectangle can thus be calculated in O(log(n)) steps, giving a total runtime of O(n*log(n)).
3. Sweeping line maintaining intervals.
   Initially, sort the heights so they can be processed in non-increasing order. We sweep a horizontal line downwards through the histogram, maintaining a list of those intervals, where the line intersects the histogram. Actually, the intervals are maintained in an array with one entry for every element of the histogram in the following manner. At the element corresponding to the left end of an interval we store a pointer to the right end, and vice versa.
   As a new element arrives during the sweeping process, this element forms a new interval, and, if there are adjacent intervals, these can be merged in constant time using our representation. The largest rectangle including this element, just as described in the previous algorithm, is available without further expense, since we can read its width from our representation. Actually, it is not quite the largest rectangle, because there may be further elements with equal heights adjacent to the current interval. Performing the sweep in a non-increasing order, however, guarantees that the largest rectangle will have been considered by the time the last element of a group having equal heights is examined. The complexity is dominated by the sorting phase, thus O(n*log(n)), although a radix sort is possible if the heights are bounded.
4. Linear search using a stack of incomplete subproblems
   We process the elements in left-to-right order and maintain a stack of information about started but yet unfinished subhistograms. Whenever a new element arrives it is subjected to the following rules. If the stack is empty we open a new subproblem by pushing the element onto the stack. Otherwise we compare it to the element on top of the stack. If the new one is greater we again push it. If the new one is equal we skip it. In all these cases, we continue with the next new element.
   If the new one is less, we finish the topmost subproblem by updating the maximum area w.r.t. the element at the top of the stack. Then, we discard the element at the top, and repeat the procedure keeping the current new element. This way, all subproblems are finished until the stack becomes empty, or its top element is less than or equal to the new element, leading to the actions described above. If all elements have been processed, and the stack is not yet empty, we finish the remaining subproblems by updating the maximum area w.r.t. to the elements at the top.
   For the update w.r.t. an element, we find the largest rectangle that includes that element. Observe that an update of the maximum area is carried out for all elements except for those skipped. If an element is skipped, however, it has the same largest rectangle as the element on top of the stack at that time that will be updated later.
   The height of the largest rectangle is, of course, the value of the element. At the time of the update, we know how far the largest rectangle extends to the right of the element, because then, for the first time, a new element with smaller height arrived. The information, how far the largest rectangle extends to the left of the element, is available if we store it on the stack, too.
   We therefore revise the procedure described above. If a new element is pushed immediately, either because the stack is empty or it is greater than the top element of the stack, the largest rectangle containing it extends to the left no farther than the current element. If it is pushed after several elements have been popped off the stack, because it is less than these elements, the largest rectangle containing it extends to the left as far as that of the most recently popped element.
   Every element is pushed and popped at most once and in every step of the procedure at least one element is pushed or popped. Since the amount of work for the decisions and the update is constant, the complexity of the algorithm is O(n) by amortized analysis.
   Solution
5. Recursive search
   For a recursive version of the algorithm just described, see the reference below. Indeed, if the recursion is eliminated the necessary stack is analogous to the explicit stack in the iterative version.
6. Rewrite System
   The problem may be generalized by allowing histograms to be composed of rectangles with varying widths. Then, the stack used in the just described algorithms can be concatenated with the yet unprocessed part of the histogram into one list.
   A three element window is moved over this list, starting at the left end. In every step, different actions are performed according to the relative heights of the three elements under inspection. The actions include updating the maximum, merging two of the three elements by taking the minimum of their heights and the sum of their widths, and sliding the window one element to the left or to the right. Rules are provided that specify the actions for each configuration.
   Actually, the behaviour of the stack-based algorithm is simulated. The correctness of the rewrite system can be shown by proving an invariant about the maximum area of the histogram, observing that every configuration is matched by some rule, and giving a termination proof using a variant expression. Additionally, it can be proved that O(n) rewrite steps (each with a constant amount of work) are performed.

Source - 1 , 2,

Read More

Program to check if two rectangle overlap or itntersect

Input - 2 Rectangles with x and y coordinates.
Output - boolean value which states if they overlap or not 

This is a one of the classic problems in graphics programming and game development. So, let's see how we can solve it.

Most computer (now cellphone) screens have an invisible coordinate system that is used to identify where graphical objects are on the screen. For example, the iPhone coordinate system has the origin at the top-left corner of the screen. As you move down the screen, the y value increases. And, as you move right the x value increases.

Algorithm :

• Two rectangles can overlap if one rectangle has 0,1,2,4 corners inside the other rectangle. The check of above mentioned condition could result is many different combinations. Remember overlapping rectangle cannot have 3 corners inside.
  
• Other way we can say that two rectangle overlap if the region of one rectangle lies inside the other.

• The best way to find is to identify whether an overlapping area is present or not which can be known if the below mentioned all conditions are true.
  
  If we check that( B = Black rectangle, R - Red Rectangle)
  
  
• The left edge of B is to the left of right edge of R.
• The top edge of B is above the R bottom edge.
• The right edge of B is to the right of left edge of R.
• The bottom edge of B is below the R upper edge.

Then we can say that rectangles are overlapping.

Off-course, we discussed the algorithm on matching rectangles, let's now focus on where the rectangles will not intersect.

Consider the following figure:

From those pictures, we can infer that two rectangles are not intersecting each other if they have one of the four conditions:

1. Right edge of blue is closer to the left of the screen than the left edge of red 
2. Bottom edge of blue is further from the bottom of the screen than the top edge of red 
3. Top edge of blue is closer to the bottom of the screen than the bottom edge of red 
4. Left edge of blue is further from the left of the screen than the right edge of red

Consider an example: There are two rectangles as shown in diagram – Black Rectangle (B) and Red rectangle(R).

Conditions to be checked
The left edge of B is to the left of right edge of R. The selected area will be :

The top edge of B is above the R bottom edge. So the selected area will be:

The right edge of B is to the right of left edge of R. The selected area will be:

The bottom edge of B is below the R upper edge. The selected area will be:

Hence all conditions are true we can say that rectangles are overlapping.


Therefore we can see that all the conditions are valid and hence rectangle is overlapping.
 
c++ implementation

#include<iostream>
using namespace std;

struct Point
{
  float x;
  float y;
};

struct Rect
{
  Point topLeft;
  Point bottomRight;
};

bool checkOverlap(Rect rect1, Rect rect2)
{
  if (rect1.topLeft.x >= rect2.bottomRight.x 
      || rect1.bottomRight.x <= rect2.topLeft.x 
      || rect1.topLeft.y <= rect2.bottomRight.y 
      || rect1.bottomRight.y >= rect2.topLeft.y)
    return false;
    
  return true;
}

Java implementation
Here is the java implementation for the code if you want to visualize as well. The logic is only present in checkOverlap() method, rest is used to display the GUI and check.

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;



public class RectangleOverlap extends JPanel{

 int r1x1,r1x2,r2x1,r2x2 ;
 int r1y1,r1y2,r2y1,r2y2 ;
 int r1width,r2width ;
 int r1height,r2height ;

 static JButton btn = new JButton("Check");
 public RectangleOverlap(int r1x1,int r1y1,int r1x2,int r1y2,
   int r2x1,int r2y1,int r2x2,int r2y2){

  this.r1x1=r1x1;
  this.r1x2=r1x2;
  this.r1y1=r1y1;
  this.r1y2=r1y2;
  
  this.r2x1=r2x1;
  this.r2x2=r2x2;
  this.r2y1=r2y1;
  this.r2y2=r2y2;

  r1width = Math.abs(r1x1-r1x2);
  r2width = Math.abs(r2x1-r2x2);
  r1height = Math.abs(r1y1-r1y2);
  r2height = Math.abs(r2y1-r2y2);

  addActionListener();
 }



 private void addActionListener() {
  btn.addActionListener(new ActionListener(){

   public void actionPerformed(ActionEvent e) {
    checkOverlap();
   }
  });
 }

 private void checkOverlap() {
  // condition to check whether the rectangles are overlapping or not.s
  boolean isOVerlap= ((r1x2 >= r2x1) &&
    (r1y2 >= r2y1) &&
    (r1x1 <= r2x2) &&
    (r1y1 <= r2y2));

  if(isOVerlap ){
   JOptionPane.showMessageDialog(null, "OVerlap");
  }else{
   JOptionPane.showMessageDialog(null, "No OVerlap");
  }

 }



 @Override

 protected void paintComponent(Graphics g) {
  g.drawRect(r1x1,r1y1 , r1width, r1height);
  g.setColor(new Color(123,232,122));
  g.drawRect(r2x1, r2y1, r2width,r2height);

 }



 public static void main(String args[]){
  JFrame frame = new JFrame();
  frame.setSize(500,500);

  // input to check overlap condition.

  // the order followed as : enter coordinate for 1st rectangle as
  // lower limit and upper limit to rectangles          

  frame.getContentPane().add(new RectangleOverlap(20,30,120,130,10,50,160,120),
    BorderLayout.CENTER);
  frame.getContentPane().add(btn,BorderLayout.SOUTH);
  frame.addWindowListener(new WindowAdapter(){
   @Override

   public void windowClosing(WindowEvent e) {
    System.exit(0);
   }

  });

  frame.setVisible(true);

 }

}

Sources:
http://codesam.blogspot.com/2011/02/check-if-two-rectangles-intersect.html
http://tech-read.com/2009/02/06/program-to-check-rectangle-overlapping/

Read More

Aptitude Quesions and answers

1.One of the following is my secret word:AIM  DUE  MOD  OAT  TIE.With the list in front of you, if I were to tell you any one of my secret word, then you would be able to tell me the number of vowels in my secret word.Which is my secret word?
Ans.TIE

2.In the following figure:A  B  C
                                              D
                                              E   F  G
                                                       H
                                                       I
Each of the digits 1, 2, 3, 4, 5, 6, 7, 8, and 9 is:
a)Represented by a different letter in the figure above.
b)Positioned in the figure above so that each of A + B + C,C + D +E,E + F + G, and G + H + I is equal to 13.
Which digit does E represent?

Ans.E is 4
3.One of Mr. Horton,his wife,their son,and Mr. Horton's mother is a doctor and another is a lawyer.
a)If the doctor is younger than the lawyer, then the doctor and the lawyer are not blood relatives.
b)If the doctor is a woman, then the doctor and the lawyer are blood relatives.
c)If the lawyer is a man, then the doctor is a man.
Whose occupation you know?

Ans.Mr. Horton:he is the doctor.
4.Here is a picture of two cubes:
                                               

         
  a)The two cubes are exactly alike.
  b)The hidden faces indicated by the dots have the same alphabet on them.
Which alphabet-q, r, w, or k is on the faces indicated by the dots?

Ans.q


5.In the following figure:
                                    A              D
                                    B      G     E
                                    C             F
Each of the seven digits from 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 is:
  a)Represented by a different letter in the figure above.
  b)Positioned in the figure above so that A*B*C,B*G*E, and D*E*F are equal.
Which digit does G represent?

Ans.G represents the digit 2.
6.Mr. and Mrs. Aye and Mr. and Mrs. Bee competed in a chess tournament.Of the three games played:
  a)In only the first game werethe two players married to each other.
  b)The men won two games and the women won one game.
  c)The Ayes won more games than the Bees.
  d)Anyone who lost game did not play the subsequent game.
Who did not lose a game?

Ans.Mrs.Bee did not lose a game.
7.Three piles of chips--pile I consists one chip, pile II consists of chips, and pile III consists of three chips--are to be used in game played by Anita and Brinda.The game requires:
  a)That each player in turn take only one chip or all chips from just one pile.
  b)That the player who has to take the last chip loses.
  c)That Anita now have her turn.
From which pile should Anita draw in order to win?

Ans.Pile II

8.Of Abdul, Binoy, and Chandini:
  a)Each member belongs to the Tee family whose members always tell the truth or to the El family whose members        always lie.
  b)Abdul says ''Either I belong or Binoy belongs to a different family from the other two."
     Whose family do you name of?

Ans.Binoy's family--El.

9.In a class composed of x girls and y boys what part of the class is composed of girls

A.y/(x + y)
B.x/xy
C.x/(x + y)
D.y/xy

Ans.C


10.What is the maximum number of half-pint bottles of cream that can be filled with a 4-gallon can of cream(2 pt.=1 qt. and 4 qt.=1 gal)

A.16
B.24
C.30
D.64

Ans.D


11.If the operation,^ is defined by the equation x ^ y = 2x + y,what is the value of a in 2 ^ a = a ^ 3

A.0
B.1
C.-1
D.4

Ans.B


12.A coffee shop blends 2 kinds of coffee,putting in 2 parts of a 33p. a gm. grade to 1 part of a 24p. a gm.If the mixture is changed to 1 part of the 33p. a gm. to 2 parts of the less expensive grade,how much will the shop save in blending 100 gms.

A.Rs.90
B.Rs.1.00
C.Rs.3.00
D.Rs.8.00

Ans.C


13.There are 200 questions on a 3 hr examination.Among these questions are 50 mathematics problems.It is suggested that twice as much time be spent on each maths problem as for each other question.How many minutes should be spent on mathematics problems

A.36
B.72
C.60
D.100

Ans.B






14.In a group of 15,7 have studied Latin, 8 have studied Greek, and 3 have not studied either.How many of these studied both Latin and Greek

A.0
B.3
C.4
D.5

Ans.B


15.If 13 = 13w/(1-w) ,then (2w)² =

A.1/4
B.1/2
C.1
D.2

Ans.C


16. If a and b are positive integers and (a-b)/3.5 = 4/7, then
(A) b < a
(B) b > a
(C) b = a
(D) b >= a
Ans. A


17. In june a baseball team that played 60 games had won 30% of its game played. After a phenomenal winning streak this team raised its average to 50% .How many games must the team have won in a row to attain this average?
A. 12
B. 20
C. 24
D. 30
Ans. C


18. M men agree to purchase a gift for Rs. D. If three men drop out how much more will each have to contribute towards the purchase of the gift/
A. D/(M-3)
B. MD/3
C. M/(D-3)
D. 3D/(M²-3M)
Ans. D


19. A company contracts to paint 3 houses. Mr.Brown can paint a house in 6 days while Mr.Black would take 8 days and Mr.Blue 12 days. After 8 days Mr.Brown goes on vacation and Mr. Black begins to work for a period of 6 days. How many days will it take Mr.Blue to complete the contract?
A. 7
B. 8
C. 11
D. 12

Ans.C

20. 2 hours after a freight train leaves Delhi a passenger train leaves the same station travelling in the same direction at an average speed of 16 km/hr. After travelling 4 hrs the passenger train overtakes the freight train. The average speed of the freight train was?
A. 30
B. 40
C.58
D. 60
Ans. B

21. If 9x-3y=12 and 3x-5y=7 then 6x-2y = ?
A.-5
B. 4
C. 2
D. 8
Ans. D
22. There are 5 red shoes, 4 green shoes. If one draw randomly a shoe what is the probability of getting a red shoe

Ans 5c₁/ 9c₁


23. What is the selling price of a car? If the cost of the car is Rs.60 and a  profit of 10% over selling price is earned

Ans: Rs 66/-




24. 1/3 of girls , 1/2 of boys go to canteen .What factor and total number of classmates go to canteen.

Ans: Cannot be determined.


25. The price of a product is reduced by 30% . By what percentage should it be increased to make it 100%

Ans: 42.857%


26. There is a square of side 6cm . A circle is inscribed inside the square. Find the ratio of the area of circle to square.
Ans. 11/14
27. There are two candles of equal lengths and of different thickness. The thicker one lasts of six hours. The thinner 2 hours less than the thicker one. Ramesh lights the two candles at the same time. When he went to bed he saw the thicker one is twice the length of the thinner one. How long ago did Ramesh light the two candles .

Ans: 3 hours.
28. If M/N = 6/5,then 3M+2N = ?
29. If p/q = 5/4 , then 2p+q= ?
30. If PQRST is a parallelogram what it the ratio of triangle PQS & parallelogram PQRST .
Ans: 1:2
31. The cost of an item is Rs 12.60. If the profit is 10% over selling price what is the selling price ?
Ans: Rs 13.86/-
32. There are 6 red shoes & 4 green shoes . If two of red shoes are drawn what is the probability of getting red shoes
Ans: 6c₂/10c₂
33. To 15 lts of water containing 20% alcohol, we add 5 lts of pure water. What is % alcohol.
Ans : 15%
34. A worker is paid Rs.20/- for a full days work. He works 1,1/3,2/3,1/8.3/4 days in a week. What is the total amount paid for that worker ?
Ans : 57.50
35. If the value of x lies between 0 & 1 which of the following is the largest?
(a) x
(b) x²
(c) -x
(d) 1/x

Ans : (d)
 36. If the total distance of a journey is 120 km .If one goes by 60 kmph and comes back at 40kmph what is the average speed during the journey? 
Ans: 48kmph
37. A school has 30% students from Maharashtra .Out of these 20% are Bombey students. Find the total percentage of Bombay?
Ans:  6%
38. An equilateral triangle of sides 3 inch each is given. How many equilateral triangles of side 1 inch can be formed from it?
Ans: 9
39. If A/B = 3/5,then 15A = ?
Ans : 9B
40. Each side of a rectangle is increased by 100% .By what percentage does the area increase?
Ans : 300%
41. Perimeter of the back wheel = 9 feet, front wheel = 7 feet on a certain distance, the front wheel gets 10 revolutions more than the back wheel .What is the distance?
Ans : 315 feet.
42. Perimeter of front wheel =30, back wheel = 20. If front wheel revolves 240 times. How many revolutions will the back wheel take?
Ans: 360 times
43. 20% of a 6 litre solution and 60% of 4 litre solution are mixed. What percentage of the mixture of solution
Ans: 36%
44City A's population is 68000, decreasing at a rate of 80 people per year. City B having population 42000 is increasing at a rate of 120 people per year. In how many years both the cities will have same population?
Ans: 130 years
45Two cars are 15 kms apart. One is turning at a speed of 50kmph and the other at 40kmph . How much time will it take for the two cars to meet?
Ans: 3/2 hours
46A person wants to buy 3 paise and 5 paise stamps costing exactly one rupee. If he buys which of the following number of stamps he won't able to buy 3 paise stamps.
Ans: 9
47There are 12 boys and 15 girls, How many different dancing groups can be formed with 2 boys and 3 girls.
48Which of the following fractions is less than 1/3
(a) 22/62
(b) 15/46
(c) 2/3
(d) 1
Ans: (b)
49There are two circles, one circle is inscribed and another circle is circumscribed over a square. What is the ratio of area of inner to outer circle?
Ans: 1 : 2
50Three types of tea the a,b,c costs Rs. 95/kg,100/kg and70/kg respectively.
     How many kgs of each should be blended to produce 100 kg of mixture worth Rs.90/kg,
     given that the quntities of band c are equal
a)70,15,15
b)50,25,25
c)60,20,20
d)40,30,30
Ans. (b)
51. in a class, except 18 all are above 50 years.
    15 are below 50 years of age. How many people are there
(a) 30
(b) 33
(c) 36
(d) none of these.
Ans. (d)
52. If a boat is moving in upstream with velocity of 14 km/hr and goes downstream with a velocity of 40 km/hr, then what is the speed of the stream ?

(a) 13 km/hr
(b) 26 km/hr
(c) 34 km/hr
(d) none of these
Ans. A
53. Find the value of ( 0.75 * 0.75 * 0.75 - 0.001 ) / ( 0.75 * 0.75 - 0.075 + 0.01)

(a) 0.845
(b) 1.908
(c) 2.312
(d) 0.001
Ans. A
54. A can have a piece of work done in 8 days, B can work three times faster than the A, C can work five times faster than A. How many days will they take to do the work together ?

(a) 3 days
(b) 8/9 days
(c) 4 days
(d) can't say
Ans. B
55. A car travels a certain distance taking 7 hrs in forward journey, during the return journey increased speed 12km/hr takes the times 5 hrs.What is the distance travelled

(a) 210 kms
(b) 30 kms
(c) 20 kms
(c) none of these
Ans. B
56. Instead of multiplying a number by 7, the number is divided by 7. What is the percentage of error obtained ?
57.  Find (7x + 4y ) / (x-2y) if x/2y = 3/2 ?

(a) 6
(b) 8
(c) 7
(d) data insufficient
Ans. C
58. A man buys 12 lts of liquid which contains 20% of the liquid and the rest is water. He then mixes it with 10 lts of another mixture with 30% of liquid.What is the % of water in the new mixture?
59. If a man buys 1 lt of milk for Rs.12 and mixes it with 20% water and sells it for Rs.15, then what is the percentage of gain?
60. Pipe A can fill a tank in 30 mins and Pipe B can fill it in 28 mins.If 3/4th of the tank is filled by Pipe B alone and both are opened, how much time is required by both the pipes to fill the tank completely ?
61. If on an item a company gives 25% discount, they earn 25% profit. If they now give 10% discount then what is the profit percentage.
(a) 40%
(b) 55%
(c) 35%
(d) 30%
Ans. D
62. A certain number of men can finish a piece of work in 10 days. If however there were 10 men less it will take 10 days more for the work to be finished. How many men were there originally?

(a) 110 men
(b) 130 men
(c) 100 men
(d) none of these
Ans. A
63. In simple interest what sum amounts of Rs.1120/- in 4 years and Rs.1200/- in 5 years ?
(a) Rs. 500
(b) Rs. 600
(c) Rs. 800
(d) Rs. 900
Ans. C
64. If a sum of money compound annually amounts of thrice itself in 3 years. In how many years
will it become 9 times itself.

(a) 6
(b) 8
(c) 10
(d) 12
Ans A
65. Two trains move in the same direction at 50 kmph and 32 kmph respectively. A man in the slower train
observes the 15 seconds elapse before the faster train completely passes by him.
What is the length of faster train ?

(a) 100m
(b) 75m
(c) 120m
(d) 50m
Ans B
66. How many mashes are there in 1 squrare meter of wire gauge if each mesh
is 8mm long and 5mm wide ?

(a) 2500
(b) 25000
(c) 250
(d) 250000
Ans B
67. x% of y is y% of ?
(a) x/y
(b) 2y
(c) x
(d) can't be determined
Ans. C
68. The price of sugar increases by 20%, by what % should a housewife reduce the consumption of sugar so that expenditure on sugar can be same as before ?
(a) 15%
(b) 16.66%
(c) 12%
(d) 9%
Ans B
69. A man spends half of his salary on household expenses, 1/4th for rent, 1/5th for travel expenses, the man deposits the rest in a bank. If his monthly deposits in the bank amount 50, what is his monthly salary ?
(a) Rs.500
(b) Rs.1500
(c) Rs.1000
(d) Rs. 900
Ans C
70. The population of a city increases @ 4% p.a. There is an additional annual increase of 4% of the population due to the influx of job seekers, find the % increase in population after 2 years ?
71. The ratio of the number of boys and girls in a school is 3:2 Out of these 10% the boys and 25% of girls are scholarship holders. % of students who are not scholarship holders.?
72. 15 men take 21 days of 8 hrs. each to do a piece of work. How many days of 6 hrs. each would it take for 21 women if 3 women do as much work as 2 men?
(a) 30
(b) 20
(c) 19
(d) 29
Ans. A
73. A cylinder is 6 cms in diameter and 6 cms in height. If spheres of the same size are made from the material obtained, what is the diameter of each sphere?
(a) 5 cms
(b) 2 cms
(c) 3 cms
(d) 4 cms
Ans C
74. A rectangular plank (2)^1/2 meters wide can be placed so that it is on either side of the diagonal of a square shown below.(Figure is not available)What is the area of the plank?
Ans :7*(2)^1/2
75. The difference b/w the compound interest payble half yearly and the simple interest on a
certain sum lent out at 10% p.a for 1 year is Rs 25. What is the sum?
(a) Rs. 15000
(b) Rs. 12000
(c) Rs. 10000
(d) none of these
Ans C
76. What is the smallest number by which 2880 must be divided in order to make it into a
perfect square ?

(a) 3
(b) 4
(c) 5
(d) 6
Ans. C
77. A father is 30 years older than his son however he will be only thrice as old as the son after 5 years
what is father's present age ?

(a) 40 yrs
(b) 30 yrs
(c) 50 yrs
(d) none of these
Ans. A
78. An article sold at a profit of 20% if both the cost price and selling price would be Rs.20/- the profit would be 10% more. What is the cost price of that article?
29. If an item costs Rs.3 in '99 and Rs.203 in '00.What is the % increase in price?

(a) 200/3 %
(b) 200/6 %
(c) 100%
(d) none of these
Ans. A
80. 5 men or 8 women do equal amount of work in a day. a job requires 3 men and 5 women to finish the job in 10 days how many woman are required to finish the job in 14 days.

a) 10
b) 7
c) 6
d) 12
Ans 7
81. A simple interest amount of rs 5000 for six month is rs 200. what is the anual rate of interest?

a) 10%
b) 6%
c) 8%
d) 9%
Ans 8%
82. In objective test a correct ans score 4 marks and on a wrong ans 2 marks are ---. a student score 480 marks from       150 question. how many ans were correct?
a) 120
b) 130
c) 110
d) 150
Ans130.
83. An artical sold at amount of 50% the net sale price is rs 425 .what is the list price of the artical?

a) 500
b) 488
c) 480
d) 510
Ans 500
84. A man leaves office daily at 7pm  A driver with car comes from his home to pick him from office and bring back home 
     One day he gets free at 5:30 and instead of waiting for driver he starts walking towards home.
     In the way he meets the car and returns home on car  He reaches home 20 minutes earlier than usual.
     In how much time does the man reach home usually??
Ans. 1hr 20min
85. A works thrice as much as B. If A takes 60 days less than B to do a work then find the number of days it would take to       complete the work if both work together?
Ans. 22½days
86. How many 1's are there in the binary form of  8*1024 + 3*64 + 3
Ans. 4
87. In a digital circuit which was to implement (A B) + (A)XOR(B), the designer implements (A B) (A)XOR(B) 
    What is the probability of error in it ?
88. A boy has Rs 2. He wins or loses Re 1 at a time  If he wins he gets Re 1 and if he loses the game he loses Re 1.
     He can loose only 5 times. He is out of the game if he earns Rs 5.
     Find the number of ways in which this is possible?
Ans. 16
89. If there are 1024*1280 pixels on a screen and each pixel can have around 16 million colors
     Find the memory required for this?
Ans. 4MB
90. On a particular day A and B decide that they would either speak the truth or will lie.
     C asks A whether he is speaking truth or lying?
     He answers and B listens to what he said. C then asks B what A has said  B says "A says that he is a liar"
     What is B speaking ?
(a) Truth
(b) Lie
(c) Truth when A lies
(d) Cannot be determined
Ans. (b)
91. What is the angle between the two hands of a clock when time is 8:30
Ans. 75(approx)
92. A student is ranked 13th from right and 8th from left. How many students are there in totality ?
93. A man walks east and turns right and then from there to his left and then 45degrees to
  his right.In which direction did he go

Ans. North west
94. A student gets 70% in one subject, 80% in the other. To get an overall of 75% how much should get in third subject.
95. A man shows his friend a woman sitting in a park and says that she the daughter of my  grandmother's only son.
    What is the relation between the two

Ans. Daughter

96.  How many squares with sides 1/2 inch long are needed to cover a rectangle that is 4 ft long and 6 ft wide
(a) 24
(b) 96
(c) 3456
(d) 13824
(e) 14266
97. If a=2/3b , b=2/3c, and c=2/3d what part of d is b/
(a) 8/27
(b) 4/9
(c) 2/3
(d) 75%
(e) 4/3
Ans. (b)
2598Successive discounts of 20% and 15% are equal to a single discount of
(a) 30%
(b) 32%
(c) 34%
(d) 35%
(e) 36
Ans. (b)
99. The petrol tank of an automobile can hold g liters.If a liters was removed when the tank was full, what part of the full tank was removed?
(a)g-a
(b)g/a
(c) a/g
(d) (g-a)/a
(e) (g-a)/g
Ans. (c)

100. If x/y=4 and y is not '0' what % of x is 2x-y

(a)150%
(b)175%
(c)200%
(d)250%

Ans. (b)

Read More

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.

Read More