I don't quite understand how am I going to implement and solve this problem:
Consider an array data of n numerical values in sorted order and a list of numerical target values (target values are not necessarily sorted). Your goal is to compute the smallest range of array indices that contains all of the target values. If a target value is smaller than data[0], the range should start with -1. If a target value is larger than data[n - 1], the range should end with n.
For example, given the array [ 5 8 10 13 15 20 22 26] and the target values (8, 2, 9, 17), the range is -1 to 5.
Devise an efficient algorithm that solves this problem and implement it in
public static <T extends Comparable<? super T>> Interval findInterval(T[] sortedData, List<T> targetValues)
Where
Interval
is a class that provides two public methodsgetLower()
andgetUpper()
to return the lower and upper values of anInterval
object. Implement theInterval
class.
I understand the algorithm of the problem. However, I'm confused how I am going to to implement it. Like what would the return value be for the Interval findInterval
method?
And "Implement the Interval
class." I don't understand what exactly the getLower()
and getUpper()
methods are supposed to return or what type.
I hope someone can give me an idea how I am going to implement this.
CodePudding user response:
At first glance Interval
should only be a data structure to hold the result of the calculation. Therefore, getLower
& getUpper
will not dynamically perform those calculations.
An example of such data structure may be:
public final class Interval {
private final int lower;
private final int upper;
public Interval(int lower, int upper) {
// Check preconditions, like lower can't be < -1, etc.
this.lower = lower;
this.upper = upper;
}
public int getLower() { return lower; }
public int getUpper() { return upper; }
}
I think the most efficient algorithm would be O(log n m)
assuming n
sorted data and m
target values.
First you must find the lowest & highest values in
tagetValues
. This can be done inO(m)
by keeping alowest
&highest
variables up to date while looping over all the elements.Then you can do 2 subsequent binary searches on
sortedData
to find the lower index from thelowest
and the highest index from thehighest
. This costs2 log n
which simplifies toO(log n)
.
import java.util.List;
import java.util.Arrays;
public class FindInterval {
public static void main(String[] args) {
Integer[] data = new Integer[] {5, 8, 10, 13, 15, 20, 22, 26};
List<Integer> targets = Arrays.asList(8, 2, 9, 17);
Interval interval = findInterval(data, targets);
System.out.println(interval);
}
public static <T extends Comparable<? super T>> Interval findInterval(
T[] sortedData,
List<T> targetValues
) {
if (targetValues.isEmpty()) {
throw new IllegalArgumentException("'targetValues' must not be empty.");
}
List<T> targetBounds = findTargetBounds(targetValues);
int lower = Arrays.binarySearch(sortedData, targetBounds.get(0));
if (lower < 0 && lower != -1) {
lower = Math.abs(lower) - 2;
}
int upper = Arrays.binarySearch(sortedData, targetBounds.get(1));
if (upper < 0) {
upper = Math.abs(upper) - 1;
}
return Interval.of(lower, upper);
}
private static <T extends Comparable<? super T>> List<T> findTargetBounds(List<T> targetValues) {
T lower = targetValues.get(0);
T upper = targetValues.get(0);
for (T value : targetValues) {
if (value.compareTo(lower) == -1) lower = value;
if (value.compareTo(upper) == 1) upper = value;
}
return Arrays.asList(lower, upper);
}
private final static class Interval {
private final int lower;
private final int upper;
private Interval(int lower, int upper) {
// Check preconditions, like lower can't be < -1, etc.
this.lower = lower;
this.upper = upper;
}
public int getLower() { return lower; }
public int getUpper() { return upper; }
@Override
public String toString() {
return "[" lower "," upper "]";
}
public static Interval of(int lower, int upper) {
return new Interval(lower, upper);
}
}
}
CodePudding user response:
From what I can understand, getLower()
is meant to return the lower range, and getUpper()
is meant to return the higher range. So for the example given: getLower() -> -1
and getUpper() -> 5
.
As for returning a class, you can simply do something like this in your method:
public static <T extends Comparable<? super T>>
Interval findInterval(T[] sortedData, List<T> targetValues) {
...
return new Interval(...);
}
Does this answer your question?