damian.j9687
BAN USERI'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;
}
}
}
@divm01986 Is it necessary to have the tags set? You already have the tags in the tree.
- damian.j9687 April 17, 2017Also, e.time - interval will not give you the timestamp of the last X seconds if the event is from yesterday. But probably in this kind of problem it is a normal assumption to make that the time of last event processed is the current time.Is it necessary to have the tags set? You already have the tags in the tree.
Also, e.time - interval will not give you the timestamp of the last X seconds if the event is from yesterday. But probably in this kind of problem it is a normal assumption to make that the time of last event processed is the current time.