I just failed my google phone screen. Even after solving 150 neetcode and total of 550 problems on leetcode was not able to solve this one.
inputs:
int n - [0..n-1] digits in the array,
int[]arr1 - [0, 1, 2] len 3 values will be valid and will use the digits in the range of 0 to n-1
int[]arr2 - [2, 3, 1] len 3 values will be valid and will use the digits in the range of 0 to n-1
arr1 and arr2 can contain duplicate values and also all values can be equal. arr1:[0, 1, 2] arr2:[0, 1, 2]
int t - will be used to calculate upper and lower bound for each digit in the array. `0<=t<=n`.Function signature
int solve(int n, int t, int[]arr1, int[]arr2) {
}Return how many distinct combinations (length of 3) we can create. Distinct - order matters [0, 1, 2] [2, 0, 1] is distinct. [0, 1, 2] [0, 1, 2] not distinct
E.x
n = 3
arr1[0, 1, 2]
arr2[2, 0, 1]
t = 1So first we have 2 distinct combinations initial values [0, 1, 2] and [2, 0, 1].
When t = 1 that means arr1[0] + 1 is the upper bound arr1[0] - 1 is the lower bound and it wraps around.
from our example we can create [1, 2, 0], [2, 1, 0] [1, 1, 2] ... for the arr1 and so on.
I really struggled with the idea of t and what does it represent? And interviewer was really helpful and showed creating different combinations using t.
t represents upper = (arr[i] + t)%n lower = (arr[i]-t) + n and bounds are included. So if we use our example: arr1[0]'s upper=1 lower=2(cause of wrapping) and you can use any of 0 1 2 for the first digit and same goes for the other ones as well. Upper and lower naming might be bad cause of wrapping you can just think of it as the range limits for a digit you can use.
I could not solve the problem in the given time and interview ended.
I tried solving it after the interview finished.
Idea was to substract overlapping combinations from maximum combination you can get based on t.
For each digit you can have (1+2L*t) digits to choose from. L-is long in java.
So for single array of length 3 the maximum number of distinct combination is (1 + 2L * t) * (1 + 2L * t) * (1 + 2L * t). Finding this math formula took enough time
Since we have 2 arrays it is 2*(1 + 2L * t) * (1 + 2L * t) * (1 + 2L * t) but when they don't overlap
I guess the whole point of the problem was to counting how many overlaps are there in a given input.
int getOverlaps(int d1, int d2, int t, int n) {
if (d1 == d2) {
return 2 * t + 1;
}
Set<Integer> set = new HashSet<>();
int count = 0;
System.out.println("d1");
for (int i = 0; i <= t; i++) {
int upper = (d1 + i) % n;
int lower = d1 - i;
if (lower < 0) lower += n;
// System.out.println(i + " " + d1 + "->" + lower + " " + upper);
set.add(lower);
set.add(upper);
}
System.out.println("d2");
for (int i = 0; i <= t; i++) {
int upper = (d2 + i) % n;
int lower = d2 - i;
if (lower < 0) lower += n;
// System.out.println(i + " " + d2 + "->" + lower + " " + upper);
if (set.contains(upper)) count++;
if (upper != lower && set.contains(lower)) count++;
}
return count;
}
/**
* how many distinct combinations are there?
*
* @param n digits [0...n-1] can be used in the combinations(arr2, arr1)
* @param arr1 arr1 combination int array of length 3
* @param arr2 arr2 combination int array of length 3
* @param t tolerance
* @return long distinct combination count
*/
long solve(int n, int[] arr1, int[] arr2, int t) {
long max = 2 * (1 + 2L * t) * (1 + 2L * t) * (1 + 2L * t);
long totalOverlaps = 1;
for (int i = 0; i < 3; i++) {
int overlaps = getOverlaps(arr1[i], arr2[i], t, n);
totalOverlaps *= overlaps;
}
return max - totalOverlaps;
}Time: O(2t) Space: O(2t)
How would you approach this problem?