## Accenture Interview Question for Software Engineer Interns

Country: United States
Interview Type: Written Test

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

``````import java.util.Scanner;

public class Main {

/*
* Input: n and m
*        then nxm matrix.
*
* ex: 3 4
*     1 2 2 2
*     2 2 2 1
*     1 2 2 2
* */

private int n;
private int m;
private int[][] grid;
private int[][] needsProcessing;

int[] upperLeftmostPoint;
int[] lowerRightmostPoint;

public void init(){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();

while(n <= 0 || m <= 0) {
System.out.println("Insert valid n and m values");
n = sc.nextInt();
m = sc.nextInt();
}
grid = new int[n][m];
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
grid[i][j] = sc.nextInt();
}
}
sc.close();

/* process method will determine which cells do not need processing
* in order to prevent repeating some operations and we will use needsProcessing for that.
* */
needsProcessing = new int[n][m];
for(int i = 0 ; i < n ; i ++){
for(int j = 0; j < m ; j ++){
needsProcessing[i][j] = 0;
}
}

/*Initially we assume cell at (0,0) as a submatrix is the result.*/
upperLeftmostPoint = new int[2];
lowerRightmostPoint = new int[2];
upperLeftmostPoint[0] = 0;
upperLeftmostPoint[1] = 0;
lowerRightmostPoint[0] = 0;
lowerRightmostPoint[1] = 0;
}

public void print(){
System.out.println("Upper leftmost:   ( " + (upperLeftmostPoint[0] + 1) + " , " + (upperLeftmostPoint[1] + 1) + " )");
System.out.println("Bottom rightmost: ( " + (lowerRightmostPoint[0] + 1) + " , " + (lowerRightmostPoint[1] + 1) + " )");

for(int i = upperLeftmostPoint[0] ; i <= lowerRightmostPoint[0] ; i ++){
for(int j = upperLeftmostPoint[1] ; j <= lowerRightmostPoint[1] ; j ++){
System.out.print(grid[i][j] + " ");
}
System.out.println();
}
}

/*
* We iterate through each cell in the matrix.
* First, k is computed. If current cell's value is x, then k is the count of continuous
* x's below the current cell including x.
* Then we hold the "horizontals" array of k elements. Each of them represents the number of continous x's
* rightwards.
* ex: In matrix
*      2 2 1
*      2 2 2
*      2 1 1
*      1 2 2
*      2 3 1
*  If current cell is the first cell which has the value 2. Then k is 3 and
*  horizontals array is {2, 3, 1}.
*
*  Then we compute the biggest submatrix assuming upper leftmost cell is the current cell
*  using horizontals array. For example, here in the same example we first look at the
*  horizontals[0]. Take 2 2 as the biggest sub matrix so far. Then look at the second element
*  of the horizontals. We see that 2 2 is bigger and so on.
*                                  2 2
*  After processing the current cell at the end we compare what we found with the current cell to
*  maxSoFar. Then we update the needed parameters. Also in order to prevent repeating we use needsProcessing
*  matrix. We do that by checking the minimum values. If horizontal[minValueIndexSoFar] >= horizontal[y] then we won't need to
*  process grid[i + y][j] because grid[i][j] will have done the needed operations and process method will repeat some operations
*  while processing grid[i+y][j].
* */

public void process(){
int maxSoFar = (upperLeftmostPoint[0] - upperLeftmostPoint[1] + 1)*(lowerRightmostPoint[0] - lowerRightmostPoint[1] + 1);
for(int i = 0 ; i < n ; i ++){
for(int j = 0; j < m ; j ++) {
if (needsProcessing[i][j] == 0){
int k = 0;
while (k + i < n && grid[i][j] == grid[k + i][j]) k++;

int[] horizontals = new int[k];

for (int s = 0; s < k; s++) {
int t = 0;
while (t + j < m && grid[i + s][j] == grid[i + s][t + j]) t++;
horizontals[s] = t;
}

int minValueIndexSoFar = 0;
int maxOfCurrentSoFar = horizontals[0];
int maxAreaLowerRightmostIndexY = 0;
for (int s = 0; s < k; s++) {
if (horizontals[minValueIndexSoFar] >= horizontals[s]) {
minValueIndexSoFar = s;
/*This means processing grid[i+s][j] is not necessary.*/
needsProcessing[i+s][j] = 1;
}
if (maxOfCurrentSoFar < (s + 1) * horizontals[minValueIndexSoFar]) {
maxOfCurrentSoFar = (s + 1) * horizontals[minValueIndexSoFar];
maxAreaLowerRightmostIndexY = s;
}
}
if (maxOfCurrentSoFar > maxSoFar) {
maxSoFar = maxOfCurrentSoFar;
upperLeftmostPoint[0] = i;
upperLeftmostPoint[1] = j;
lowerRightmostPoint[0] = i + maxAreaLowerRightmostIndexY;
lowerRightmostPoint[1] = j + maxOfCurrentSoFar / (maxAreaLowerRightmostIndexY + 1) - 1;
}
}
}
}
}

public void run(){
init();
process();
print();
}

public static void main(String[] args) {
new Main().run();
}
}``````

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