Finding largest rectangular area without trees
In an interview I was asked a question very similar to this or this.
In my version there is a rectangular piece of land with trees on it. We know the coordinates of the land and the location of the trees on the land. Goal is to find the largest contiguous rectangular area within our land that doesn't contain any trees.
Solving these problems require you to develop the properties of the problem that then you can base an algorithm on for which there is no time. My response in the interview was what I consider brute force method of trying to take a square and see how big it can grow. Then try to find the largest one.
But thinking about the problem more I said what if I had a land and one tree. Then I get essentially 4 areas. Now if I have two trees, I should be able to take the areas from the first tree and check to see if the 2nd tree would influence them. If the 2nd tree is inside an area, then it would give me potentially 4 areas to work with. That is the one area is replaced with up to 4 (removing the original one). If there are no tree in the area then the area is unaffected by the 2nd tree. So now I can try the 3rd, 4th... tree. Each time check the effect of the tree on the land. At the end the one with the largest area is my answer. This solution doesn't care about the size of the land, just the number of trees.
Here is what I wrote in Haskell that I think solves the problem. The implementation takes advantage of foldM library to do most of the work. In foldM signature, "a" is my land, "b" is the tree, and "ma" is List of a which is a list of land pieces. Any feedback is appreciated.
In my version there is a rectangular piece of land with trees on it. We know the coordinates of the land and the location of the trees on the land. Goal is to find the largest contiguous rectangular area within our land that doesn't contain any trees.
Solving these problems require you to develop the properties of the problem that then you can base an algorithm on for which there is no time. My response in the interview was what I consider brute force method of trying to take a square and see how big it can grow. Then try to find the largest one.
But thinking about the problem more I said what if I had a land and one tree. Then I get essentially 4 areas. Now if I have two trees, I should be able to take the areas from the first tree and check to see if the 2nd tree would influence them. If the 2nd tree is inside an area, then it would give me potentially 4 areas to work with. That is the one area is replaced with up to 4 (removing the original one). If there are no tree in the area then the area is unaffected by the 2nd tree. So now I can try the 3rd, 4th... tree. Each time check the effect of the tree on the land. At the end the one with the largest area is my answer. This solution doesn't care about the size of the land, just the number of trees.
Here is what I wrote in Haskell that I think solves the problem. The implementation takes advantage of foldM library to do most of the work. In foldM signature, "a" is my land, "b" is the tree, and "ma" is List of a which is a list of land pieces. Any feedback is appreciated.