Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Code you requested:
public static boolean isEquals(List<Rectangle> one, List<Rectangle> two) {
if (one.size() != two.size() || !one.getClass().equals(two.getClass()))
return false;
Comparator<Rectangle> comparator = new Comparator<Rectangle>() {
@Override
public int compare(Rectangle o1, Rectangle o2) {
double[] points1 = new double[]{o1.getMinX(), o1.getMinY(), o1.getMaxX(), o1.getMaxY()};
double[] points2 = new double[]{o2.getMinX(), o2.getMinY(), o2.getMaxX(), o2.getMaxY()};
for (int i = 0; i < points1.length; i++) {
if (points1[i] < points2[i])
return -1;
else if (points1[i] > points2[i])
return 1;
}
return 0;
}
};
Collections.sort(one, comparator);
Collections.sort(two, comparator);
return one.equals(two);
}
assume rectangles are stored as (x,y) where x and y are two length and width of a rectangle.
A wild guess: calculate (x/y+y/x) as the unique attribute for each triangle. Then sort two list.
We can compare them after the sort by simply traverse through two lists.
time: O(nlogn)
space: O(ListA.lenth + ListB.length)
My algo based on the assumption that (x/y+y/x) is always different for different rectangles and all x and y are integers.
I think none of the above idea could work perfectly cover every possible edge condition.
Let me clarify this a little bit: The key problem is how we could find some presentation of a rectangle in a unique way. In other words, if the two rectangles are equal, the presentation are the same. It is a bijection relation ship.
Step1: A rectangle could be represented in multiple ways, a intuitive way is by its left upper point and its lower right point. Say A(1,1) B(2,2). These two points are enough to represent this rectangle.
Step2: Serialize this information. Although there definitely mathmatical way to represent it, I came up a more intuitive ways which is directly insert them into a String. (e.g 1,1,2,2).
Then we write comparator on this String.
I'm not sure why there is so much confusion around this, the approach doing sorting is 100% correct.
Here is another solution without sorting that takes O(n) time and O(n) space.
I didn't consider the spatial location of the rectangles because the problem statement does not say so. It just says a list of rectangles. And a rectangle is just an object with a width and a height.
But the solution can be easily modified to include a location in a 2 dimensional space.
public class DetermineIfTwoListsOfRectanglesAreEqual
{
private static class Rectangle
{
private Rectangle(int width, int height)
{
this.width = width;
this.height = height;
}
private int width;
private int height;
public String toString()
{
return String.format("{w: %d, h: %d}", width, height);
}
}
public static class Solution
{
private Map<String, Integer> indexRectangles(List<Rectangle> list)
{
Map<String, Integer> index = new HashMap<>();
for(Rectangle rectangle : list)
{
String key = rectangle.width + "-" + rectangle.height;
if(!index.containsKey(key))
{
index.put(key, 0);
}
index.put(key, index.get(key) + 1);
}
return index;
}
boolean areListsOfRectanglesEquivalent(List<Rectangle> list1, List<Rectangle> list2)
{
if(list1.size() != list2.size())
{
return false;
}
Map<String, Integer> index1 = indexRectangles(list1);
Map<String, Integer> index2 = indexRectangles(list2);
if(index1.size() != index2.size())
{
return false;
}
for(String key : index1.keySet())
{
if(!index1.get(key).equals(index2.get(key))) // if index2 does not contain the key, get() will return null and the values won't be equal
{
return false;
}
}
return true;
}
}
}
Imagine a rectangle represented as a ordered pair of 2 points. One on the upper left and the other on the lower right. Define a weak ordering comparator function first on the point (check if p1.x < p2.x and then p1.y < p2.y), then on the rectangle overall.
- Hingle McCringleBerry October 21, 2013Now you can sort the two lists and check if they are the same.
Complexity O(n log n).
(Based on the assumption from the second part of your question, that is there is some well defined ordering on the rectangles : That is rectangles that start on a smaller x coordinate is "smaller")