## Microsoft Interview Question for SDE-2s

Country: India

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

``````#include <iostream>
#include <unordered_set>
#include <vector>
#include <functional>

using namespace std;

bool find_square_in_table(const vector<pair<int, int>>& points) {
// hash function for set of coordindates
auto pair_hash = [](const pair<int, int>& p) {
return hash<decltype(p.first)>()(p.first) * 9315 + hash<decltype(p.second)>()(p.second);
};

// build hash table with all coordinates
unordered_set<pair<int, int>, decltype(pair_hash)> ht(10, pair_hash);
for (const auto& point : points) {
ht.emplace(point);
}

// buid pairs and look for points forming a square
for (int i = 0; i < points.size() - 1; ++i) {
for (int j = i + 1; j < points.size(); ++j) {
int dx = points[i].first - points[j].first;
int dy = points[i].second - points[j].second;
int ij[] = { i, j };
for (int s = -1; s < 2; s += 2) {
bool found = true;
for (int idx : ij) {
pair<int, int> ptf = pair<int, int>(points[idx].first + s * dy, points[idx].second - s * dx);
found &= ht.find(ptf) != ht.end();
}
if (found) {
return true;
}
}
}
}
return false;
}

int main()
{
cout << find_square_in_table({ {5, 5}, {10, 5}, {10, 10}, {5, 10} }) << endl; // true
cout << find_square_in_table({ { 5, 5 },{ 10, 5 },{ 10, 10 },{ 5, 11 } }) << endl; // false
cout << find_square_in_table({ { 14, 5 }, {2, 9}, { 7, 3 },{ 12, 12 },{ 5, 10 },{3, 9} }) << endl; // true: (7,3),(5,10),(12,12),(14,5)
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static void Main(string[] args)
{
List<Coordinate> coordinates = new List<Coordinate>();

FindASquare(coordinates);

}

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>();

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);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Find distance any point p1 from the rest, two should be d and the other one should be sqrt(2)*d. Let this pt be p4. Now repeat the same for p4 as well. It should give d for p2 and p3 and aqrt(2) *d for p1.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.