lindat
BAN USER- 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 | PURGE
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:)
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.