Interview Question
Jr. Software EngineersTeam: Python development
Country: United States
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();
}
}
Observations:
- Transit Station Memory Needs
-- For every transit station, we need to remember only top two items (because of two tickets)
-- Ex: For NYC, NYC-HAWAI, NYC-SEATTLE are top two and rest such as NYC-LA, NYC-CHI can be forgotten with NYC as transit station. However, we should not forget the same with NYC station as start/end station
- We can't forget anything other than transit related stuff. Otherwise, issues would occur. For example, in the given input example;
let's say fifth row input is CHI:WA is 8192, then longest route is 8911:NYC:CHI:WA
At this row, can we forget NYC:SEATTLE?
let's say sixth row input is SEATTLE:WA is 9100, then longest route is 11558:NYC:SEATTLE:WA which requires NYC:SEATTLE to be remembered
Algorithm:
- Route is of type (String Station1, String Station2, int Distance)
- There is a NONE(String.EMPTY, String.EMPTY, 0) route to indicate no route
- Longest Route is of type (String startStation, String transitStation, String endStation, int totalDistance)
Initialized as (String.EMPTY, String.EMPTY, String.EMPTY, 0)
- Hash Table with Key as Transit Station, Value as Pair<Route, Route>
Where, Pair contains two stations with longest distance from this station
If there is only one route, other route would be NONE route
- For every input received,
Create a record
Add record to Hash Table twice - with key as station1 and station2
If hash already has an entry for a station, update the value (pair of routes) appropriately such that top two routes are retained
- Get entries from hash using two stations of input route
We will get four routes at the max
Compute longest two-ticket distance using these four routes
If newly computed longest route is longer than stored longest route
{ update stored longest route }
Print stored longest route
I realize this says Python, but did this in Java for kicks.,
- e2 November 11, 2018