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

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.