Microsoft Interview Question
Country: United States
This seems correct.
Distance between two points P1(x,y), P2(x,y)
D(P1,P2) = SQRT( Sqr(P1.x-P2.x) + Sqr(P1.y-P2.y))
Above condition will be true in case of rhombus & parallelogram also. You need to check with pythogorus theorem also.
import math
def calculate_distance(p1, p2):
return math.sqrt( (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]) )
def square_rectangle(p1, p2, p3, p4):
distances = []
distances.append(calculate_distance(p1,p2))
distances.append(calculate_distance(p1,p3))
distances.append(calculate_distance(p1,p4))
distances.append(calculate_distance(p2,p3))
distances.append(calculate_distance(p2,p4))
distances.append(calculate_distance(p3,p4))
distances.sort()
if distances[0] == distances[1] and distances[1] == distances[2] and distances[2] == distances[3] and distances[3] != distances[4] and distances[4] == distances[5]:
return "square"
elif distances[0] == distances[1] and distances[1] != distances[2] and distances[2] == distances[3] and distances[3] != distances[4] and distances[4] == distances[5]:
return "rectangle"
else:
return "nothing"
print square_rectangle( [0,1], [1,0], [1,1], [0,0] )
print square_rectangle( [1,1], [1,0], [1,1], [0,0] )
print square_rectangle( [2,1], [2,0], [0,1], [0,0] )
I would suppose the four points was given by their coordinates like (x,y)
solution would be first pick up one point, mark it with start_point, then compare it with the rest 3, check if there 1 point has the same x with start_point, mark it as horizontal_point, calculate their distance as width, then check the rest 2 points to see there is 1 point has the same y, mark it as vertical_point, calculate their distance as height, if the remaining last point has the same x with vertical_point and same y with horizontal point, it is a rectangle and if with==height it is a square.
#include <list>
#include <math.h>
struct Point
{
int x = 0;
int y = 0;
};
enum class RectType
{
Square,
Rectangle,
NotRect
};
RectType checkRect(Point* p1, Point* p2, Point* p3, Point* p4)
{
std::list<Point*> cache;
Point* start_p = p1;
cache.push_back(p2);
cache.push_back(p3);
cache.push_back(p4);
Point* horizontal_p = nullptr;
std::list<Point*>::iterator it = cache.begin();
while(it != cache.end())
{
if ((*it)->x == start_p->x)
{
horizontal_p = (*it);
cache.erase(it++);
break;
}
it++;
}
if (!horizontal_p)
return RectType::NotRect;
int width = abs(horizontal_p->y - start_p->y);
Point* vertical_p = nullptr;
std::list<Point*>::iterator it = cache.begin();
while (it != cache.end())
{
if ((*it)->y == start_p->y)
{
vertical_p = (*it);
cache.erase(it++);
break;
}
it++;
}
if (!vertical_p)
return RectType::NotRect;
int height = abs(vertical_p->x - vertical_p->x);
if ((*cache.begin())->x == vertical_p->x && (*cache.begin())->y == horizontal_p->y)
{
if (height == width)
return RectType::Square;
return RectType::Rectangle;
}
return RectType::NotRect;
}
sg,
did you ask the interviewer about the following assumptions
1) Are the points in the input provided in a particular order (e.g. clockwise, anti-clockwise, no particular order )
2) Is the Square or Rectangle, parallel to the axis
that was technical screening question. so no interviewer present while I was working on it.
Wow... it seems people really like to find complicated solutions for very simple problems.
The simplest approach is to check whether the angle abc is right (dot product of vector (a-b) and (c-b) ), compute d' from those three (d' = (a-b)+(c-b)) and if it d' doesn't match d then answer is "none of those".
sauare vs. rectangle can be checked by |a-b|=|c-b|.
If input points are in arbitrary order (not sorted cw or ccw) then run this algorithm for both abcd and bacd.
Note: this will work in 3d as well
actually
suppose p1,p2,p3,p4 are the points,
name the points in clockwise direction,
then join p1 and p2,p3 and p4 ,
now check whether p1p2 and p3p4 are parallel then it is a square or rectangle
if they are not parallel the it is none of the above,
for checking between square or rectangle join p2and p3,
now if p1p2 and p2p3 are equal then it is square or if not equal then its rectangle.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication5
{
public class Custmer
{
public int CustId { get; set; }
public int Amount { get; set; }
public string CustName { get; set; }
}
class Program
{
public static string Message1 = "This is for targeting 25% customer who spend most";
public static string Message2 = "This is for targeting 25% customer who spend least";
public static string Message3 = "Target the rest of the customer";
static void Main(string[] args)
{
List<Custmer> lstCust = new List<Custmer>();
lstCust.Add(new Custmer { CustId = 100, Amount = 100, CustName = "Shoeb" });
lstCust.Add(new Custmer { CustId = 101, Amount = 200, CustName = "Amin" });
lstCust.Add(new Custmer { CustId = 102, Amount = 300, CustName = "Ahad" });
lstCust.Add(new Custmer { CustId = 103, Amount = 400, CustName = "Zakir" });
lstCust.Add(new Custmer { CustId = 104, Amount = 500, CustName = "Munawer" });
lstCust.Add(new Custmer { CustId = 105, Amount = 600, CustName = "Anjum" });
lstCust.Add(new Custmer { CustId = 106, Amount = 700, CustName = "Najeeb" });
lstCust.Add(new Custmer { CustId = 107, Amount = 800, CustName = "Aslam" });
lstCust.Add(new Custmer { CustId = 108, Amount = 900, CustName = "Shakeb" });
lstCust.Add(new Custmer { CustId = 109, Amount = 1000, CustName = "Asim" });
Dictionary<int, string> lstCustResult = new Dictionary<int, string>();
int CustCount = lstCust.Count();
List<Custmer> lstCustMost = new List<Custmer>();
List<Custmer> lstCustLeast = new List<Custmer>();
List<Custmer> lstCustRemaing = new List<Custmer>();
int Max25 = (CustCount * 25) / 100;
int Min = Max25;
int Reminaing = CustCount - (Max25 + Min);
lstCustMost = lstCust.OrderByDescending(x => x.Amount).Take(Max25).ToList();
lstCustLeast = lstCust.OrderBy(x => x.Amount).Take(Max25).ToList();
DisplayListElement(lstCustMost, Message1);
DisplayListElement(lstCustLeast, Message2);
lstCustMost.AddRange(lstCustLeast);
var resultRemaiing = lstCust.Except(lstCustMost).ToList();
DisplayListElement(resultRemaiing,Message3);
Console.ReadLine();
}
public static void DisplayListElement(List<Custmer> lst, string Message)
{
foreach (Custmer Cust in lst)
{
SendMessage(Cust.CustName, Cust.Amount, Message);
}
}
public static void SendMessage(string CustName,int Amount, string Message)
{
Console.WriteLine(string.Format("CustomerName={0}, you'r amount is ={1} and your message={2}", CustName, Amount, Message));
}
}
}
1) Let P1,P2,P3,P4 be the points
- june.pravin August 30, 20152) Find all possible distances between them. There will be six.
3) Sort these distances. Let them be D1,D2,D3,D4,D5,D6
4) If the first 4 and last 2 are equal, its a square
5) If the first 2, second 2 and last 2 are equal, its a rectangle
6) If not, its neither