## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

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.

Now 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")

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

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

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

can you please explain a little bit more clear? how many rectangles for each list? and if all the rectangle in list a have a same rectangle in list b, is this meaning equal?

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

maybe we can apply radix sort? Sort both list by second point, then by first and compare them.

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

there are n rectangles in one list and m in the other. No idea how to proceed with this. Any suggestions with code?

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

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.

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

Could you please provide some code?

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

I guess we can assume that each rectangle is represented by two points (x1,y1) and (x2,y2). Then, we can calculate the area of each rectangle by (y1-y2)*(x2-x1), and then store them in a HashMap.

Please correct me if I am wrong

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

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.

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

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

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.