Adobe Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
That seems to fail for:
int[][] arr = { { 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 0 },
{ 1, 1, 1, 1, 0 },
{ 0, 0, 1, 0, 0 } };
and it can be a rectangle, not just a square.
This problem can be easily solved by slightly modifying "Largest Area of Histogram problem".
int main()
{
int a[5][5]={{0,0,0,0,0},{0,1,1,0,0},{0,1,1,0,0},{0,1,1,0,0},{0,1,1,0,0}};
int mRowIndex=-1;
int mColIndex=-1;
int mRow=0,mCol=0,rowC,colC;
int i,j,k,m,n=5;
cout<<"Input Boolean Matrix:\n\n\n";
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cout<<a[i][j]<<" ";
if(a[i][j]==1)
{
rowC=0;
colC=0;
k=i;
m=j;
while(a[k][j]==1 && k<n)
{
k++;
rowC++;
}
while(a[i][m]==1 && m<n)
{
m++;
colC++;
}
if((rowC+colC)>(mRow+mCol))
{
mRow=rowC;
mCol=colC;
mRowIndex=i;
mColIndex=j;
}
}
}
cout<<"\n";
}
cout<<"\n\n\n";
if(mRowIndex >= 0 && mColIndex >= 0)
{
cout<<"Start row index = "<<mRowIndex<<"\n";
cout<<"Start col index = "<<mColIndex<<"\n";
cout<<"Rectangle size = "<<mRow<<" * "<<mCol<<"\n\n\n";
}
return 0;
}
Shouldn't a[k][m] be checked if it is equal to 1 too...otherwise you are just checking the three corners of the rectangle.
package com.tc.graphs;
import java.util.Set;
import java.util.TreeSet;
public class RectangleBorderOnes {
/**
* @param args
*/
Set<Integer> t = new TreeSet<Integer>();
int[][] array = { { 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 0 }, { 1, 1, 1, 1, 0 }, { 0, 0, 1, 0, 0 } };
private void addEdge(int start,int end){
array[start][end] = 1;
}
private int calculate(){
for(int row=0;row<array.length;row++){
for(int colum=0;colum<array[row].length-1;colum++){
//System.out.println(row + "" +colum);
if((array[row][colum]==1)){
for(int columCol=colum+1;columCol<array[row].length;columCol++){
//System.out.println(colum + "" + columCol);
int flag = 0;
for(int i=colum;i<=columCol;i++){
if(array[row][i]==0){
flag=0;
break;
}else {
flag=1;
}
}
if(flag==1){
checkOnes(row,colum,columCol);
}
}
}else{
// break;
}
}
}
Object[] result = t.toArray();
return (Integer)result[result.length - 1];
}
private void checkOnes(int row,int colum,int columCol) {
// TODO Auto-generated method stub
// Now we got the width
int width = columCol - colum + 1;
for(int i = row+1;i<array.length;i++){
int flag = 1;
for(int k = row+1;k<=i;k++){
if(array[k][colum]==0 || array[k][columCol]==0){
flag=0;
}
}
if(flag==1){
int cc=1;
for(int j = colum+1;j<=columCol-1;j++){
if(array[i][j]==0){
cc=0;
}
}
if(cc==1){
//System.out.println("rectangle Completed");
int area = (i-row+1)*(columCol-colum+1);
//System.out.println(area);
t.add(area);
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
RectangleBorderOnes r = new RectangleBorderOnes();
int res = r.calculate();
System.out.println(res);
}
}
package com.practises;
import java.util.ArrayList;
import java.util.List;
class Position{
int row;
int col;
Position(int r, int c){
row=r; col=c;
}
@Override
public boolean equals(Object obj) {
Position p = (Position)obj;
return this.row==p.row || this.col==p.col;
}
@Override
public String toString() {
return "{Point: Row-"+row+" Col-"+col+"}";
}
}
class Rectangle {
int area;
List<Position> positions = new ArrayList<Position>();
@Override
public String toString() {
return "Area::: "+area+" Points:::"+positions;
}
}
public class GetMax1sRectangle {
public static void main(String[] args) {
int[][] twoDArray = {{1,0,0,0,1},
{1,1,1,1,1},
{0,1,1,0,1},
{1,0,1,1,1},
{1,1,1,1,1}};
List<Position> list1Pos=new ArrayList<Position>();
for(int rowIndex=0; rowIndex<twoDArray.length; rowIndex++){
for(int colIndex=0; colIndex<twoDArray[rowIndex].length; colIndex++){
if(twoDArray[rowIndex][colIndex]==1){
Position p = new Position(rowIndex, colIndex);
list1Pos.add(p);
}
}
}
Rectangle rectangle = new Rectangle();
for(int index1=0; index1<list1Pos.size(); index1++){
for(int index2=index1; index2<list1Pos.size(); index2++){
Position p1 = list1Pos.get(index1);
Position p2 = list1Pos.get(index2);
if(!p1.equals(p2)) {
if(twoDArray[p1.row][p2.col]==1 && twoDArray[p2.row][p1.col]==1){
int area = (p2.row-p1.row+1)*(p2.col-p1.col+1);
if(area>rectangle.area){
rectangle.positions.clear();
rectangle.area=area;
rectangle.positions.add(p1);
rectangle.positions.add(p2);
Position p3 = new Position(p1.row,p2.col);
Position p4 = new Position(p2.row,p1.col);
rectangle.positions.add(p3);
rectangle.positions.add(p4);
}
}
}
}
}
System.err.println(rectangle);
}
}
This question was asked in my google interview. I could come up with the worst case complexity solution, but that is O(m^2 * n^2). He asked for a better complexity and I started with making a Point class with x,y coordinates and adding the points with 1 at the position in the ArrayList<ArrayList<Point>> list. Each index in this list denotes a new row. You can ignore the inner lists with size < 1. I messed up when I told the complexity though. He said I need to wrap up and his last question was complexity. The answer is: If there are maximum of k 1s in any row in mXn matrix, then it's (mC1 * kC2 * (m-1)C1 * kC2) which is O(m^2 * k^2). I instead told him its O(k1^4) where k1 is the total number of 1s. :(
package com.algo;
import java.util.Arrays;
public class MaxPerimeter {
public static int findMaxPermiter(boolean[][] rect) {
int row = rect.length;
int col = rect[0].length;
int maxPerimeter = 0;
for(int i=0; i<col; i++) {
int[] boundary = new int[row];
for(int j=i;j<col;j++) {
for(int k=0;k<row;k++) {
if(!rect[k][j] || !rect[k][i])
boundary[k] = 0;
else
boundary[k] += 1;
}
int maxWidth = maxConsecutiveNonZero(boundary, j-i+1);
if(maxWidth != 1 && j-i != 0)
maxPerimeter = Math.max(maxPerimeter, 2 * ((j-i+1) + maxWidth-2));
}
}
return maxPerimeter;
}
private static int maxConsecutiveNonZero(int[] boundary, int target) {
//System.out.println(Arrays.toString(boundary) + " target " + target);
int start = -1;
int end = 0;
int maxWidth = 1;
while(end < boundary.length) {
if(start == -1 && boundary[end] == target)
start = end;
else if(boundary[end] == target) {
maxWidth = Math.max(end - start + 1, maxWidth);
} else if(boundary[end] == 0) {
start = -1;
}
end++;
}
//System.out.println("max width " + maxWidth);
return maxWidth;
}
public static void main(String[] args) {
boolean[][] rectange = { {true, true, true, true},
{false, true, true, false},
{true, true, true, true}
};
int ans = findMaxPermiter(rectange);
System.out.println("Perimeter is: " + ans);
}
}
package com.algo;
import java.util.Arrays;
public class MaxPerimeter {
public static int findMaxPermiter(boolean[][] rect) {
int row = rect.length;
int col = rect[0].length;
int maxPerimeter = 0;
for(int i=0; i<col; i++) {
int[] boundary = new int[row];
for(int j=i;j<col;j++) {
for(int k=0;k<row;k++) {
if(!rect[k][j] || !rect[k][i])
boundary[k] = 0;
else
boundary[k] += 1;
}
int maxWidth = maxConsecutiveNonZero(boundary, j-i+1);
if(maxWidth != 1 && j-i != 0)
maxPerimeter = Math.max(maxPerimeter, 2 * ((j-i+1) + maxWidth-2));
}
}
return maxPerimeter;
}
private static int maxConsecutiveNonZero(int[] boundary, int target) {
//System.out.println(Arrays.toString(boundary) + " target " + target);
int start = -1;
int end = 0;
int maxWidth = 1;
while(end < boundary.length) {
if(start == -1 && boundary[end] == target)
start = end;
else if(boundary[end] == target) {
maxWidth = Math.max(end - start + 1, maxWidth);
} else if(boundary[end] == 0) {
start = -1;
}
end++;
}
//System.out.println("max width " + maxWidth);
return maxWidth;
}
public static void main(String[] args) {
boolean[][] rectange = { {true, true, true, true},
{false, true, true, false},
{true, true, true, true}
};
int ans = findMaxPermiter(rectange);
System.out.println("Perimeter is: " + ans);
}
}
package com.algo;
import java.util.Arrays;
public class MaxPerimeter {
public static int findMaxPermiter(boolean[][] rect) {
int row = rect.length;
int col = rect[0].length;
int maxPerimeter = 0;
for(int i=0; i<col; i++) {
int[] boundary = new int[row];
for(int j=i;j<col;j++) {
for(int k=0;k<row;k++) {
if(!rect[k][j] || !rect[k][i])
boundary[k] = 0;
else
boundary[k] += 1;
}
int maxWidth = maxConsecutiveNonZero(boundary, j-i+1);
if(maxWidth != 1 && j-i != 0)
maxPerimeter = Math.max(maxPerimeter, 2 * ((j-i+1) + maxWidth-2));
}
}
return maxPerimeter;
}
private static int maxConsecutiveNonZero(int[] boundary, int target) {
//System.out.println(Arrays.toString(boundary) + " target " + target);
int start = -1;
int end = 0;
int maxWidth = 1;
while(end < boundary.length) {
if(start == -1 && boundary[end] == target)
start = end;
else if(boundary[end] == target) {
maxWidth = Math.max(end - start + 1, maxWidth);
} else if(boundary[end] == 0) {
start = -1;
}
end++;
}
//System.out.println("max width " + maxWidth);
return maxWidth;
}
public static void main(String[] args) {
boolean[][] rectange = { {true, true, true, true},
{false, true, true, false},
{true, true, true, true}
};
int ans = findMaxPermiter(rectange);
System.out.println("Perimeter is: " + ans);
}
}
One solution is to go through all the points in the matrix and check for each length if rectangle is valid.Here is the code although i feel this solution is lame.
- Daman November 02, 2012:p
public class FindMaxRectangle {
private boolean checkOnes(int[][] arr, int i, int j, int length) {
if (arr[i][j] == 1 && arr[i][j + length] == 1
&& arr[i + length][j] == 1 && arr[i + length][j + length] == 1) {
return true;
}
return false;
}
public void printMaxRectangle(int[][] arr) {
int max = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
for (int length = 0; length < arr.length; length++) {
if (length + i < arr.length && length + j < arr.length) {
boolean test = checkOnes(arr, i, j, length);
if (test == true) {
if (length > max) {
max = length;
}
}
}
}
}
}
System.out.println("max is" + max);
}
public static void main(String args[]) {
int[][] arr = { { 1, 1, 0, 1, 0 }, { 1, 1, 0, 0, 0 },
{ 0, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0 } };
FindMaxRectangle fmr = new FindMaxRectangle();
fmr.printMaxRectangle(arr);
}
}