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

- Hingle McCringleBerry October 21, 2013 | Flag Reply
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);
	}

- Rich October 27, 2013 | Flag Reply
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?

- wulian1223 October 22, 2013 | Flag Reply
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.

- gstepanov@griddynamics.com October 22, 2013 | Flag Reply
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?

- chandeepsingh85 October 22, 2013 | Flag Reply
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.

- david86391 October 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Could you please provide some code?

- Anonymous October 25, 2013 | Flag Reply
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

- bhavin04890 October 26, 2013 | Flag Reply
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.

- Anonymous November 02, 2013 | Flag Reply
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;
        }
    }    
}

- damian.j9687 April 17, 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