static416
BAN USER- 0of 0 votes
AnswersGiven two stations at random, show all possible routes between those stations (if any)
- static416 in Canada
- Stations links are listed below
- Links between stations are bi-directional
- Routes generated should not have cycles
cambridge<>stansted
stansted<> harlow
harlow<>london
london<>hatfield
hatfield<>peterborough
cambridge<>hatfield
cambridge<>ely
peterborough<>ely
peterborough<>birmingham
birmingham<>manchester
manchester<>glasgow
glasgow<>edinburgh
edinburgh<>newcastle
newcastle<>thirsk
thirsk<>york
york<>manchester
york<>peterborough| Report Duplicate | Flag | PURGE
Software Engineer / Developer Trees and Graphs
Here's my solution.
- Create an Interval class that contains just the limits, and some member functions for finding if a value is in range.
- Add each interval to a collection, and sort that collection by the start value
- Now walk through the collection first by column if possible (crossing intervals with the same value), then by row if possible (moving within an interval by one value)
- When you've walked the required distance, you have the value.
This is far easier on memory because you don't need to have every value in every interval stored individually. You just need the interval limits. Think about if you had two intervals of a million values each, my version would require only 4 values to describe that.
This is far easier computationally than listing all values. It would be O(n + m log m), where 'n' is the number of the steps to the index you want, and 'm' is the number of intervals (this is the time required to sort the intervals).
A further improvement would be to dynamically generate an equation that produced the value based on the bounds of the provided intervals. This seems completely possible, but too complicated for me to figure out.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class OverlapInterval {
public class Interval{
int start;
int end;
public Interval(int start, int end)
{
this.start = start;
this.end = end;
}
public Integer Min()
{
return start;
}
public boolean ValueIsInRange(int value)
{
return (value >= start && value <= end);
}
}
List<Interval> intervals;
public void Add(int start, int end)
{
if (intervals == null)
intervals = new ArrayList<Interval>();
intervals.add(new Interval(start, end));
Collections.sort(intervals, new IntervalListSort());
}
private class IntervalListSort implements Comparator<Interval>
{
@Override
public int compare(Interval first, Interval second) {
return first.Min().compareTo(second.Min());
}
}
public int GetValueAtIndex(int index)
{
int indexOfInterval = 0;
int minValidInterval = 0;
int pathLength = 0;
int targetIndex = index;
int curValue = intervals.get(0).Min();
while (pathLength < targetIndex)
{
// Check if interval above has this value
if ((indexOfInterval < (intervals.size() -1))
&& intervals.get(indexOfInterval + 1).ValueIsInRange(curValue))
{
pathLength++;
indexOfInterval++;
}
// Check if min valid interval has this value
else if (intervals.get(minValidInterval).ValueIsInRange(curValue + 1))
{
pathLength++;
curValue++;
indexOfInterval = minValidInterval;
}
else
{
int i = 0;
curValue++;
// Check if any intervals above have this value, that's the new min interval
for (i = (minValidInterval + 1); i < intervals.size(); i++)
{
if (intervals.get(i).ValueIsInRange(curValue))
{
minValidInterval = i;
pathLength++;
indexOfInterval = minValidInterval;
break;
}
}
// If we exited that loop without finding a new valid interval, there is a gap
if (i == intervals.size())
{
// Increase interval by 1, find it's min value
indexOfInterval++;
curValue = intervals.get(indexOfInterval).Min();
minValidInterval = indexOfInterval;
pathLength++;
}
}
}
return curValue;
}
}
Seems like there has to be a faster way. Building a graph of all dictionary words, which are connected to those that differ by only one letter would take a really long time.
Sure the Dijkstra's algorithm afterwards would be relatively quick, but it would take a long time to build the graph in the first place.
I don't have another proposal, but it seems like there should be a faster solution.
My suggestion was going to be to transverse the graph and maintain a list of nodes that all other nodes can see. That would give you ABC for this example.
That would work in this specific example, but might not satisfy the interviewer based on what they are looking for. My example breaks as soon as the problem set gets larger and you have large groups that are nonetheless not visible to every other node.
My solution was:
1. Use Dijkstra's algorithm to find the shortest route and store that route in a map
2. For each route found, recursively remove one link in that route from the graph, and find the next shortest route and add that to the map.
With the dataset provided, this implementation works well. However, finding "all possible routes" in a graph is a bad idea, as it becomes very computationally expensive as the number of nodes and interconnectivity increase.
But now that I think about it, DFS with backtracking may have been conceptually simpler. Though I'm not sure it would have been faster.
Problem is that you don't check if the IP portions are valid. So if the last three digits were 258, you'd accept that, and it wouldn't be valid IP.
- static416 August 17, 2014That said, that's a relatively easy check to add to your code. Before going into the next nested loop, check that the value is <= 255 and doesn't have leading zeros.