ezra.epstein
BAN USERThis is quite clever and is elegant in its simplicity and robustness: it can handle not just two lists as inputs, but arbitrarily many.
The caveat may be for larger lists. Since it makes an additional copy of the inputs and then performs a preliminary sort, there's additional memory overhead and the performance is constrained by the sorting step which is generally limited to O(n log(n)). For smaller datasets this is not a problem.
Making use of the fact that the inputs are sorted, we can achieve O(n) performance since we can traverse the inputs in-order and do a single pass and also perform a O(n) comparisons (with a slightly larger coefficient). Again, this would only matter for larger inputs.
Also, while this can be done with arbitrarily many input lists, so long as all are sorted, there's more effort involved in doing the comparisons and internal "bookkeeping" so, to keep it simple, I opted for the two-list input as stated. Finally, the problem doesn't explicitly state it, but I assume that each individual input list does not contain any overlapping intervals - that is, each list's intervals are already disjoint and we're merging to create a single list with any cross-list overlapping ranges merged, but no need to merge ranges within a single list. (We could add a pre-processing step to handle the case of overlapping intervals in the inputs.)
In Java this is:
package com.ezraepstein.careercup.fb;
import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
import java.util.StringJoiner;
public class MergeIntervals {
private static boolean isInRangeInclusive(int[] r, int x) {
return r[0] <= x && x<= r[1];
}
/**
* Extends the range (r) based on the ranges in the takeFrom list.
* @param r the current range
* @param takeFrom sorted list of ranges to examine
* @param idx current index into the list of ranges being examined
* @return the new index value.
*/
private static int coalesceIntervals(int[] r, List<int[]> takeFrom, int idx) {
while (idx < takeFrom.size() && isInRangeInclusive(r, takeFrom.get(idx)[0])) {
r[1] = Math.max(r[1], takeFrom.get(idx)[1]);
++idx;
}
return idx;
}
/**
* Merge two lists of ordered (sorted) disjoint ranges to create a single such list.
* <p>
* The input lists must be sorted ascending with only disjoint ranges. This function does not
* check and so no guarantees are made if invalid data are provided.
* </p>
*
* @param lh the first input list (aka, the "left-hand" list to be merged)
* @param rh the secong input list (aka, the "right-hand" one)
* @return the combined list of contiguous ranges.
*/
public static List<int[]> mergeIntervals(final List<int[]> lh, List<int[]> rh) {
List<int[]> result = new ArrayList<int[]>(Math.max(32, lh.size()));
int i = 0, j = 0; // indices into lh and rh, respectively
int[] r; // the current range, will be assigned in the loop
// move along both lists, taking from whichever has the smaller starting range at the current indices.
while (i<lh.size() && j<rh.size()) {
if (lh.get(i)[0] <= rh.get(j)[0]) {
r = lh.get(i++);
j = coalesceIntervals(r, rh, j);
} else {
r = rh.get(j++);
i = coalesceIntervals(r, lh, j);
}
result.add(r);
}
// may have only finished taking items from one list, so check that and copy as needed
if (i < lh.size()) {
result.addAll(lh.subList(i, lh.size()));
} else if (j < rh.size()) {
result.addAll(rh.subList(j, rh.size()));
}
return result;
}
static String intListArrayAsString(List<int[]> l) {
final StringJoiner sj = new StringJoiner(", ");
l.forEach(x -> sj.add(Arrays.toString(x)));
return sj.toString();
}
}
tested via:
package com.ezraepstein.careercup.fb;
import org.junit.Test;
import java.util.Arrays;
import java.util.List;
public class MergeIntervalsTest {
@Test
public void coalesceIntervals() {
List<int[]> lh = Arrays.asList(new int[]{1,2}, new int[]{3,9});
List<int[]> rh = Arrays.asList(new int[]{4,5}, new int[]{8,10}, new int[]{11, 12});
System.out.println("List 1: " + MergeIntervals.intListArrayAsString(lh));
System.out.println("List 2: " + MergeIntervals.intListArrayAsString(rh));
final List<int[]> result = MergeIntervals.mergeIntervals(lh, rh);
System.out.println("O/P: " + MergeIntervals.intListArrayAsString(result));
}
}
with output:
List 1: [1, 2], [3, 9]
List 2: [4, 5], [8, 10], [11, 12]
O/P: [1, 2], [3, 10], [11, 12]
Process finished with exit code 0
In Java rather than Python, a simple impl is :
package com.ezraepstein.careercup;
import java.io.InputStream;
import java.util.*;
public class Main implements Runnable {
private static String[] reverseStringArray(final String[] a) {
final int l = a.length;
String tmp;
for (int i=0; i<(l>>1); ++i) {
tmp = a[l-1-i];
a[l-1-i] = a[i];
a[i] = tmp;
}
return a;
}
static class Path implements Comparable<Path>{
final String[] stops;
final Integer distance;
String getOrigin() {
return stops[0];
}
String getDestination() {
return stops[stops.length - 1];
}
Path(Integer distance, String... stops) {
if (distance == null || distance < 0) {
throw new IllegalArgumentException("distance must not be null or negative");
}
this.distance = distance;
this.stops = (stops.length < 2 || stops[0].compareTo(stops[stops.length-1]) <= 0) ? stops : reverseStringArray(stops);
if (getOrigin() == null || getDestination() == null || getOrigin().equals(getDestination())) {
throw new IllegalArgumentException("origin and destination must be non-null and distinct");
}
}
Path(final String origin, final String destination, final Integer distance) {
this(distance, origin, destination);
}
static Path makePath(Path s1, Path s2) {
final int dist = s1.distance + s2.distance;
if (s1.getOrigin().equals(s2.getOrigin())) {
return new Path(dist, s1.getDestination(), s1.getOrigin(), s2.getDestination());
} else if (s1.getOrigin().equals(s2.getDestination())) {
return new Path(dist, s1.getDestination(), s1.getOrigin(), s2.getOrigin());
} else if (s1.getDestination().equals(s2.getOrigin())) {
return new Path(dist, s1.getOrigin(), s1.getDestination(), s2.getDestination());
} else if (s1.getDestination().equals(s2.getDestination())) {
return new Path(dist, s1.getOrigin(), s1.getDestination(), s2.getOrigin());
} else {
return null;
}
}
@Override
public String toString() {
final StringJoiner sj = new StringJoiner(":", "", "")
.add(distance.toString());
for (String s : stops) {
sj.add(s);
}
return sj.toString();
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
final Path path = (Path) o;
return Arrays.equals(stops, path.stops) &&
Objects.equals(distance, path.distance);
}
@Override
public int hashCode() {
return Objects.hash(stops, distance);
}
@Override
public int compareTo(Path o) {
return o.distance.compareTo(distance); // longest first
}
}
private final Scanner scanner;
private final Map<String, TreeSet<Path>> segmentMap;
private Path longestPath = null;
private Path readLine() {
return new Path(scanner.next().trim().toUpperCase(), scanner.next().trim().toUpperCase(), scanner.nextInt());
}
private void addSegmentForLocation(final Path s, final String location) {
TreeSet<Path> result;
if (!segmentMap.containsKey(location)) {
result = new TreeSet<>();
segmentMap.put(location, result);
} else {
result = segmentMap.get(location);
}
result.add(s);
}
private Path longestForSegmentAndLocation(final Path s, final boolean origin) {
Path p = null;
final TreeSet<Path> fromLoc = segmentMap.get((origin ? s.getOrigin() : s.getDestination()));
if (fromLoc != null) {
long d = s.distance;
final Iterator<Path> itr = fromLoc.iterator();
// given our sorting, the first item is the longest
Path s2 = itr.next();
if (s2.equals(s)) {
// handle edge case where Path s is already in the map.
s2 = itr.next();
}
if (longestPath == null || (d+s2.distance > longestPath.distance)) {
// origin sorts before destination, so construct the path accordingly to keep lexicographic ordering
p = Path.makePath(s, s2);
}
}
return p;
}
private void computeLongestPath(final Path s, final boolean origin) {
final Path p = longestForSegmentAndLocation(s, origin);
if (longestPath == null || (p != null && p.distance > longestPath.distance)) {
longestPath = p;
}
}
private void addSegment(final Path s) {
if (!segmentMap.isEmpty()) {
computeLongestPath(s, true);
computeLongestPath(s, false);
}
addSegmentForLocation(s, s.getOrigin());
addSegmentForLocation(s, s.getDestination());
}
@Override
public void run() {
for (;;) {
addSegment(readLine());
if (longestPath != null) {
System.out.println(longestPath);
}
}
}
private Main(final InputStream ins) {
this.scanner = new Scanner(ins).useDelimiter("[:\\n]");
this.segmentMap = new HashMap<>();
}
public static void main(String[] args) {
new Main(System.in).run();
}
}
The assignments to the local variable "r" should be via copy to avoid modifying the inputs:
- ezra.epstein November 13, 2018