CareerCup

This can be done using a 2-D segment tree.
The first segment tree will be for representing the range on the x-axis.
Now, for each node(range) in this segment tree, there will be a segment tree representing the y-ranges.
So, lets say we get a query xi,yi to xf,yf(representing diagonal points of the rectangle). , we first travel in the first segment tree for the range xi to xf. Then for that node, we take we search for the range yi to yf in the corresponding tree for xi to xf.

Time complexity- for building the tree= (xrange*yrange), for each query= (log(xrange)*log(yrange))

space complexity= xrange*yrange. (since we store a segment tree in an array. In this case 2-D array. ) Each node in the array for first segment tree will contain pointer to the array for this 2-D array.

yaa, I agree.. but we normally call that tree an augmented quad tree , the same can be extended to any dimensions eg- 3d is oct tree ..
It has support for some queries on range and some update on range or points.

Another data structure that facilitates similar problems is Bit indexed tree for n-dimensions which facilitates cumulative range query for some sort of problems.

But for this problem a

I am taking a very object oriented approach to this.
Let's say we have a quad tree in which each node has the max value for the range it covers as well as having 4 optional child nodes.
Externally to the node we must keep the size of the grid call this size
So the quad trees data structure looks like this:

class Quad_Tree
{
	// Lots of public and private functions and the Quad_Tree_Node class 
	………………
	………………
	Private:
	Quad_Tree_Node root;
	int x_max;
	int y_max; 
};

//The  Quad_Tree_Node class looks like this 

class Quad_Tree_Node
{
	Quad_Tree_Node *children[4]; 
	int max_value 
}

We also have a class box and Four_Box_Set to encapsulate nasty things that the interviewer is not interested in and will trip you up on the interview. These things will also trip you up in real life I would argue and I would hope that a reasonably smart optimizer would eliminate the over head for in most modern systems.

Box consists of 4 numbers defining a region (x_max, x_min, y_max, y_min) and it has a few set computations functions to compute intersection and tell you if 2 boxes intersect.
Four_Box_Set consists of 4 boxes arranged in 2 rows of 2 but you can index then with a single index. It is just a 1D array of 4 boxes but they share some common limits. Four_Box_Set lets you intersect 1 box with a Four_Box_Set to get another Four_Box_Set. Sometimes some of the boxes may end up with size of 0. We can also take a Box and divide it into 4 equal boxes in a Four_Box_Set.

If you have all these classes in place or can convince your interviewer that they exist with a wave of a hand you are left with 2 simple functions to find the max.
First you need a recursive function by which to search the nodes. This should be a node member. And you need a little function to call this giving it its initial size.

Things would be a lot simpler if the quad tree represents a region that is square and is of a size that is a power of 2. The quad tree get max function can take its internal x_max and y_max and computes such a box: size = 2^ ceiling(log2(max(x_max, y_max))); We might be able to live with a different sized box but we can consider this as a refinement.

The quad tree class gets a function like this:

int get_max(box b)
{
    int size = 2^ ceiling(log2(max(x_max, y_max)));  
    Box r(size,size);
    return root->get_max(b,r);
}//---------------------------------------------------------------------------------------------------------

int  Quad_Tree::node::get_max(box b, box r)
{
    if(b == r) return max_value;  // we are done the box we are looking for matches the node 

    Four_Box_Set children = r.break_in_4(); // computes an array of the 4 domains of the children
    Four_Box_Set sub_sets = children.get_intersections_with(b); // compute the region within the child       
                                                                                                                        // we are interested in 
    int max_out = 0;       // yes you could optimize this loop it a bit if you wanted to 
                                          // and did not trust the optimizer 
    for(i = 0; i < 4; i++)
    {
        If(child_node[i] != NULL)
        {
            	int temp = child_node[i]->get_max(sub_sets[i], children[i]);
	max_out = max(max_out, temp);
        }
    }
    return max_out;
}//---------------------------------------------------------------------------------------------------------

To really improve performance you need to rethink this a bit to take cash coherency into account. Low branching trees are going to get a lot of cash misses so you might want to consider something more complex but you would probably need to experiment and tune it for a particular architecture. Yuck!

2D segment tree

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

void init(int A[][6],int B[][13],int xbegin,int xend,int ybegin,int yend,int xnode,int ynode)
{
if (xbegin>xend || ybegin>yend) return;
if (xbegin==xend && ybegin==yend) {B[xnode][ynode]=A[xbegin][ybegin];return;}
int xmid=(xbegin+xend)/2;
int ymid=(ybegin+yend)/2;

init(A,B,xbegin,xmid,ybegin,ymid,xnode*2+1,ynode*2+1);
init(A,B,xbegin,xmid,ymid+1,yend,xnode*2+1,ynode*2+2);
init(A,B,xmid+1,xend,ybegin,ymid,xnode*2+2,ynode*2+1);
init(A,B,xmid+1,xend,ymid+1,yend,xnode*2+2,ynode*2+2);

int m1=max(B[xnode*2+1][ynode*2+1],B[xnode*2+1][ynode*2+2]);
int m2=max(B[xnode*2+2][ynode*2+2],B[xnode*2+2][ynode*2+1]);
B[xnode][ynode]=max(m1,m2);
}

int query(int A[][6],int B[][13],int xbegin,int xend,int ybegin,int yend,int qxb,int qxe,int qyb,int qye,int xnode,int ynode)
{
if (qxb<=xbegin && qxe>=xend && qyb<=ybegin && qye>=yend) return B[xnode][ynode];
if (qxb>xend || qxe<xbegin || qyb>yend || qye<ybegin) return -1;
int xmid=(xbegin+xend)/2;
int ymid=(ybegin+yend)/2;
int l1=query(A,B,xbegin,xmid,ybegin,ymid,qxb,qxe,qyb,qye,xnode*2+1,ynode*2+1);
int l2=query(A,B,xbegin,xmid,ymid+1,yend,qxb,qxe,qyb,qye,xnode*2+1,ynode*2+2);
int l3=query(A,B,xmid+1,xend,ybegin,ymid,qxb,qxe,qyb,qye,xnode*2+2,ynode*2+1);
int l4=query(A,B,xmid+1,xend,ymid+1,yend,qxb,qxe,qyb,qye,xnode*2+2,ynode*2+2);
return max(max(l1,l2),max(l3,l4));
}

int main()
{
int A[6][6]={
{1,2,3,4,5,6},
{11,12,13,14,15,16},
{21,22,23,24,25,26},
{31,32,33,34,35,36},
{41,42,43,44,45,46},
{51,52,53,54,55,56}};
int l=2*pow(2,log(6)/log(2))+1;
cout<<l<<endl;
int B[13][13]={0};
init(A,B,0,5,0,5,0,0);
cout<<query(A,B,0,5,0,5,1,3,1,3,0,0)<<endl;
return 0;

}