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

- Chris July 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

    }

- vishalg9986 July 30, 2017 | Flag Reply
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;
			}
		}
	}

}

- vzyarko August 03, 2017 | Flag Reply
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.

- Sayantan August 18, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More