Microsoft Interview Question
SDE-2sCountry: India
static void Main(string[] args)
{
List<Coordinate> coordinates = new List<Coordinate>();
coordinates.Add(new Coordinate(7, 2));
coordinates.Add(new Coordinate(5, 2));
coordinates.Add(new Coordinate(2, 2));
coordinates.Add(new Coordinate(2, 4));
coordinates.Add(new Coordinate(5, 5));
coordinates.Add(new Coordinate(2, 5));
FindASquare(coordinates);
Console.ReadKey();
}
private static void FindASquare(List<Coordinate> coordinates)
{
foreach(Coordinate currentCoordinate in coordinates)
{
// Check for 90 degree Check
var yAxisNeighbours = coordinates.Where(co => co.X == currentCoordinate.X).ToList<Coordinate>();
var xAxisNeighbours = coordinates.Where(co => co.Y == currentCoordinate.Y).ToList<Coordinate>();
if (xAxisNeighbours.Count < 2 || yAxisNeighbours.Count < 2)
{
Console.WriteLine(currentCoordinate.ToString() + " Fails 90 degree check.");
continue;
}
foreach(Coordinate xAxisNeighbour in xAxisNeighbours)
{
if (xAxisNeighbour.Equals(currentCoordinate))
continue;
int squraLenght = xAxisNeighbour.X - currentCoordinate.X;
squraLenght = squraLenght > 0 ? squraLenght : squraLenght * (-1);
List <Coordinate> thirdCoordinates = new List<Coordinate>();
thirdCoordinates.Add(new Coordinate(currentCoordinate.X, currentCoordinate.Y + squraLenght));
thirdCoordinates.Add(new Coordinate(currentCoordinate.X, currentCoordinate.Y - squraLenght));
foreach(Coordinate thirdCoordinate in thirdCoordinates)
{
if (!thirdCoordinate.InList(coordinates))
continue;
Coordinate fourCoordinates = new Coordinate(xAxisNeighbour.X,thirdCoordinate.Y);
if (!fourCoordinates.InList(coordinates))
continue;
Console.WriteLine("Following coordinates are make an square: " + currentCoordinate.ToString() + xAxisNeighbour.ToString() + thirdCoordinate.ToString() + fourCoordinates.ToString());
return;
}
}
}
}
}
public class Coordinate
{
public int X;
public int Y;
public Coordinate(int x, int y)
{
this.X = x;
this.Y = y;
}
public override bool Equals(Object obj)
{
if (obj == null)
return false;
Coordinate coordindate = obj as Coordinate;
if ((Object)coordindate == null)
return false;
return (this.X == coordindate.X) && (this.Y == coordindate.Y);
}
public bool InList(List<Coordinate> coordinates)
{
return coordinates.Any(co => co.X == this.X && co.Y == this.Y);
}
public override string ToString()
{
return String.Format("({0},{1})", this.X, this.Y);
}
}
template <class T>
static std::ostream& operator << (std::ostream& stream, const std::pair<T, T>& pt){
return stream << "(" << pt.first << ", " << pt.second << ")";
}
template <class T>
class Square
{
public:
// costruct by a diagonal A-C; A, B, C, D clokwise
Square(const std::pair<T, T>& a, const std::pair<T, T>& c):
ptA(a),
ptB((a.first + a.second + c.first - c.second) / 2, (a.second + c.first + c.second - a.first) / 2),
ptC(c),
ptD((a.first - a.second + c.first + c.second) / 2, (a.first + a.second - c.first + c.second) / 2)
{}
const std::pair<T, T> ptA, ptB, ptC, ptD;
void print() const{
std::cout << "square: " << ptA << "," << ptB << "," << ptC << "," << ptD << "\n";
}
};
template <class T>
static void findSquaerInVector(const std::vector<std::pair<T, T> >& vec)
{
auto pair_hash = [](const pair<T, T>& p) {
return hash<decltype(p.first)>()(p.first) * 9315 + hash<decltype(p.second)>()(p.second);
};
std::unordered_set <std::pair<T, T>, decltype(pair_hash) > ptHash (10, pair_hash);
for (const auto& pt : vec){
ptHash.insert(pt);
}
for (int i = 0; i < vec.size(); ++i)
{
for (int j = i + 1; j < vec.size(); ++j)
{
Square<T> sq(vec[i], vec[j]);
// check for corresponding diagonal
if (ptHash.find(sq.ptB) != ptHash.end()
&& ptHash.find(sq.ptD) != ptHash.end())
{
sq.print();
return;
}
}
}
}
Assumptions:
- coorinate is with integers
- no overflow can occure due to range of values
Implementation:
- for each pair of points a,b find a' and b' such that a,b,b',a' forms a square
a' and b' are defined if a and b are defined (two options, a' and b' or a'' and b'')
dx = ax - bx
dy = ay - by
a'x = ax - dy, b'x = bx - dy
a'y = ay + dx, b'y = by + dx
a''x = ax + dy, b''x = bx + dy
a''y = ay - dx, b''y = by - dx
find a' and b' or a'' and b'' in array
the find can be done in O(1) by using a hashtable
- overall time complexity O(n^2), and O(n) space
if working with floating point, this won't work as straight forward, but you can actually do
almost the same, just instead of using the hashtable to find the point pairs, use the
hashtable as a spatial store dividing the space into small squares, then you put the
points into all the 8 squares and the one it lies on (etc. etc.)
find the 9 squares around a point and check against all points found within this squares.
If you divide space small enough, you might even get away by just checking if there is
point in the square... but get the error discussion right.
- Chris July 28, 2017