## lindat

- 2of 2 votes

AnswersGiven a cube made of N x N x N sub-cubes, how many sub-cubes are on the outside of the cube?

- lindat in United States| Report Duplicate | Flag

Zynga Software Development Manager Puzzle

I think it can be done in O(n) time.

Given an arr of len=5 such as {-2, 5, -1, -2, -1}, imagine all the sums you need to calculate organized like this, where each number on lines 1-4 is the sum of the length of numbers on line 0 if you draw a triangle to it. So the -1 on line 4 is a sum of all the numbers on line 0. And the -4 on line 2 is a sum of {-1, -2, -1} and the 4 on line 1 is a sum of {5, -1}

```
0: -2 5 -1 -2 -1
1: 3 4 -3 -3
2: 2 2 -4
3: 0 1
4: -1
```

You can rotate to its side and represent the above in an n x n matrix:

```
0 1 2 3 4
0 -2
1 3 5
2 2 2 -1
3 0 2 0 -2
4 -1 -4 1 -1 -1
```

And the algorithm to populate it and count the number of subarrays is something like

```
int[][] sums = new int[len][len];
int count = 0;
// populate the middle diagonal with arr, and along the way,
// check whether the number is between a and b
for (int i =0; i < len; i++) {
sums[i][i] = arr[i];
if (arr[i] >= a && arr[i] <= b) {
count++;
}
// now populate "lines" 1-4
for (int line=1; i < len; i++) {
int tmp = sums[line-1][line-1] + sums[line][line];
sums[line -1][line] = tmp;
if (tmp >= a && tmp <= b) {
count++;
}
}
System.out.println(count);
```

It takes two unnested for loops, so that's O(n);

This is my first time answering Career Cup. Please be nice:)

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Not quite but you seem to be on the right path. It looks like you tried to account for the 4 remaining sides with 4(n-1), which isn't correct.

- lindat September 29, 2015By the way, what the interviewer also looked for is whether I was able to reduce the equation down to the simplest terms.

Note this interview I had was 2 years ago.