ronnie
BAN USER- 0of 0 votes
AnswersThere is a bucket N which contains n nuts of different
- ronnie in India for Video processing capabilities
sizes and bucket M of m bolts. Also there is a compare function which will take one bolt and a nut as input and return -1,0,1, respectively if nut size greater, equal, or lesser than bolt. Write an algorithm to find matching nits and bolts. Initially he gave sizes for nuts and bolts instead of compare function so i made use of hash map and solved it. So after that he gave this function and asked if there is a better soution than O(mn) ?| Report Duplicate | Flag | PURGE
Cisco Systems SDE-2 Algorithm
1. Compile without -DOPTIMIZE
2. For an matrix of 150*150 it took an average of 46 searches to find element by using the above method.
ie searched each of m[i][j] element for 150*150 elements and it took an average of 46 comparisons.
Whereas if you use traverse from top right to bottom left it took an average of 149 comparisons. ( see traverse function above )
For 1024 * 1024 matrix it takes an average of 72 searches only !!
//// Split the matrix into 4 rectangles along the diagonals and recursively search through /// left bottom and right top
#include<iostream>
#include<cstdlib>
#include<algorithm>
#define p(x) std::cout<< #x" : " << x << "\n"
int count,tra;
class Coordinate
{
public:
int x;
int y;
Coordinate( int X=0, int Y=0):x(X),y(Y){}
Coordinate operator+(int add){ x += add; y += add ; return *this; }
Coordinate operator-(int add){ x -= add; y -= add ; return *this; }
///void operator=(Coordinate& c) {this->x = c.x ; this->y = c.y }
bool isBefore(Coordinate& p) { return (this->x <= p.x && this->y <= y );}
void setToAverage( Coordinate& b, Coordinate& e) { this->x = (b.x+e.x)/2 ; this->y = (b.y+e.y)/2 ;}
bool inBound(Coordinate& end) { return ( this->x >=0 && this->x <= end.x && this->y >= 0 && this->y <= end.y ); }
bool isValid() { return !(this->x == -1 && this->y == -1 ); }
friend std::ostream& operator << (std::ostream& o, Coordinate& p);
};
Coordinate traverse(int **mat, int ele, Coordinate beg, Coordinate end, Coordinate matEnd)
{
Coordinate start(beg.x,end.y);
///p(start);
while ( start.inBound(matEnd) )
{
if ( mat[start.x][start.y] == ele )
return start;
else if ( ele < mat[start.x][start.y])
start.y -= 1;
else
start.x += 1;
//start = start - 1;
///p(start);
tra++;
}
return Coordinate(-1,-1);
}
std::ostream& operator << (std::ostream& o, Coordinate& p)
{
o << "(x,y) : ( " << p.x << " , " << p.y << ") \n";
return o;
}
Coordinate lookUpElement(int **mat, Coordinate begin, Coordinate end, Coordinate matEnd,int element);
Coordinate binarySearch(int **m, int fixedIndex, int beg, int end, bool isRow, int element);
Coordinate partitionAndSearch(int **mat, Coordinate begin, Coordinate end, Coordinate pivot ,int element, Coordinate matEnd)
{
Coordinate lowerLeftBegin ( pivot.x, begin.y), lowerLeftEnd( end.x, pivot.y-1 );
Coordinate lower = lookUpElement(mat,lowerLeftBegin, lowerLeftEnd, matEnd,element);
p(lowerLeftBegin);
p(lowerLeftEnd);
if ( lower.isValid() )
{
return lower;
}
Coordinate upperRightBegin ( begin.x, pivot.y), upperRightEnd( pivot.x-1, end.y );
p( upperRightBegin );
p( upperRightEnd );
return lookUpElement(mat, upperRightBegin, upperRightEnd , matEnd,element);
}
/*
10 20 30 40 50
100 200 300 400 500
1000 1020 1030 1040 1050
1031 1040 1050 1060 1090
*/
Coordinate lookUpElement(int **mat, Coordinate begin, Coordinate end, Coordinate matEnd,int element)
{
count++;
if ( !begin.inBound(matEnd) || !end.inBound(matEnd) )
{
return Coordinate(-1,-1);
}
else if ( mat[begin.x][begin.y] == element )
{
return begin;
}
else if ( mat[end.x][end.y] == element )
{
return end;
}
else if ( !begin.isBefore(end))
{
return Coordinate(-1,-1);
}
int diagDistance = std::min( abs(begin.x - end.x), abs(begin.y-end.y));
p(diagDistance);
p(begin);
p(end);
#ifndef OPTIMIZE
if ( !diagDistance )
{
bool isRow ( begin.x == end.x );
Coordinate o =binarySearch(mat, isRow ? begin.x : begin.y , isRow ? begin.y : begin.x , isRow ? end.y : end.x, isRow, element );
if ( o.isValid() )
return o;
}
#endif
Coordinate start(begin),p;
Coordinate last(begin.x+diagDistance, begin.y + diagDistance );
while( start.isBefore(last) )
{
p.setToAverage(start,last);
if ( element > mat[p.x][p.y] )
{
start = p + 1;
///p(start);
}
else
{
last = p - 1;
//p(last);
}
count++;
}
//p( start );
return partitionAndSearch(mat,begin,end,start,element,matEnd);
}
Coordinate binarySearch(int **m, int fixedIndex, int beg, int end, bool isRow, int element)
{
count++;
if ( beg > end )
return Coordinate(-1,-1);
int mid = beg + (end-beg)/2;
int chekElement = isRow ? m[fixedIndex][mid] : m[mid][fixedIndex];
if ( chekElement == element )
return ( !isRow ? Coordinate( mid, fixedIndex) : Coordinate(fixedIndex, mid) );
else if ( chekElement > element)
return binarySearch(m, fixedIndex, beg, mid-1, isRow, element);
else
return binarySearch(m,fixedIndex, mid+1, end, isRow, element);
}
/// To search call :
Coordinate res = lookUpElement(m, Coordinate(), Coordinate(N-1,N-1), Coordinate(N-1,N-1), key);
if ( res.isValid() )
{
std::cout << "element found at " << res ;
}
11/23 is the probability of both being black or white. so for 1 white and 1 black its 1 - 11/23 = 12/23
- ronnie July 29, 2013