## Adobe Interview Question for Software Engineer / Developers

• 0
of 0 votes

Country: India
Interview Type: In-Person

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

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.
: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);
}

}

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

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.

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

ya we can then take 2 loops of length row length and column length and keep check on both.Complexity will be worsened to O(n^4)
I dont know if biggest area in histogram could work but O(n^4) is surely not going to impress the interviewer

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

This problem can be easily solved by slightly modifying "Largest Area of Histogram problem".

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

easily? while it looks similar, it's quite different here.

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

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

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

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.

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

Ya..the above solution is incorrect..thanx for pointing out...it only checks 2 sides and 3 vertices of a rectangle..

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

Depth first search

complexity < 4n

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

i think DFS is for to find out max area with all 1's

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

Hi,
Any solution for this one?

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

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

}

}``````

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

Please verify my solution. I could solve it by BruteForce only. Any algorithm can be applied on this? Experts please help

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

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

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

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. :(

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

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

}``````

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

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

}``````

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

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

}``````

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

This works work all test cases.
boundary array keeps count of consecutive 1's and sets it to 0 if start/end boundary element is 0/false.
maxConsecutiveNonZero function returns max consecutive width whose boundary equals target. The target is width of the rectangle.

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