wingchun0511
BAN USER- 3of 3 votes
AnswersHow to find efficiently the minimum of an array of integers that is the maximum of other arrays?
- wingchun0511 in France
Example:
A = [126, 110, 130]
B = [125]
C = [105, 115]
The minimum element of array A that is the maximum of B and C is 126| Report Duplicate | Flag | PURGE
Java Developer Algorithm Coding Java Online Test
Code is worth thousands of words :)
- wingchun0511 January 31, 2015I think the bug is fixed now :)
- wingchun0511 January 31, 2015I just implemented the solution with Java 8:
/**
* Find element y = min(int[] a) where y >= max(int[] b1, int[] b2,..., int[] bn)
* Elements in arrays are greater or equal to 0
* @return element else -1 if not found
*/
public static int min(final int[] a, final int[]... b) {
final int NOT_FOUND = -1;
if (a == null) throw new NullPointerException("first argument cannot be null");
if (a.length == 0 || b.length == 0) return NOT_FOUND;
int max = NOT_FOUND;
for (int[] c : b) {
int tmp = Arrays.stream(c).max().orElse(NOT_FOUND);
if (max < tmp) max = tmp;
}
if (max == NOT_FOUND) return max;
Arrays.sort(a);
if (max == 0) return a[0];
int min = binarySearch(max, a);
return min;
}
private static int binarySearch(int val, int[] a) {
int lo = 0;
int hi = a.length - 1;
while (lo != hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] <= val) lo = mid + 1;
else hi = mid;
}
return a[lo] >= val ? a[lo] : -1;
}
public static void main(String[] args) {
System.out.println(min(new int[]{126, 110, 130}, new int[]{125}, new int[] {105, 115})); // 126
System.out.println(min(new int[]{126, 110, 130}, new int[]{128}, new int[] {105, 115})); // 130
System.out.println(min(new int[]{125}, new int[]{126, 110, 130}, new int[] {105, 115})); // -1
System.out.println(min(new int[]{80,120,90,126,127,128}, new int[]{125}, new int[] {105, 115})); // 126
}
if A is sorted then:
* Linear Search for element Y in A where A >= X takes linear time
* Binary search for Y in A where A >= X takes logarithmic time
What about:
1) sort A
2) X = max (B, C)
3) binary search of X in A
I understand from your code that n1, n2, n3 are the length of a, b, c.
Forget to mention that all values are greater or equal to zero.
What do mean the return values 0 and 1 in your function? The function should return the value. Examples:
1)
A = [126, 110, 130]
B = [125]
C = [105, 115]
func(A, B, C) returns 126
func(B, A, C) returns -1 // -1 means no minimum element found in B that satisfies the constraints min(B) > max(A, C)
2)
A = [110, 126, 130]
B = [128]
C = [105, 115]
func(A, B, C) returns 130
The function should accept any arbitrary number of arrays as argument, where the first argument is the array that might hold the min value.
It sounds good!, but you need to deal with corner cases:
- wingchun0511 February 01, 2015A = [125]
B = [126, 110, 130]
C = [105, 115]
output: 9223372036854775807 (should be: -1)
A = [126, 110, 125, 130]
B = [125]
C = [105, 115]
output: 126 (should be: 125)