## Adobe Interview Question for Software Engineer / Developers

• 0

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

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

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

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

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

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

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

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

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

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);
}
}
}
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;
Position p3 = new Position(p1.row,p2.col);
Position p4 = new Position(p2.row,p1.col);
}
}
}
}
}
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

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.

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.

### 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.