Interview Question
Dev Leads Dev LeadsCountry: India
Interview Type: In-Person
(1) Create a hashtable that keeps track of each (ID, NextID) pair.
(2) Identify the set of IDs that represent the heads of each list.
(3) For each ID in (2), recursively traverse the hashtable until you arrive at a negative number.
(4) Return the longest traversal length while iterating in (3).
class LongestStretch {
static class Seg { int ID; int NextID; }
static int longest(Seg[] segments) {
HashSet<Integer> heads = new HashSet<Integer>();
HashSet<Integer> tails = new HashSet<Integer>();
HashMap<Integer, Integer> next = new HashMap<Integer, Integer>();
for(Seg seg : segments) {
next.put(seg.ID, seg.NextID);
heads.add(seg.ID);
tails.add(seg.NextID);
}
heads.removeAll(tails);
int longest = 0;
for(int head : heads) {
int len = 0;
int current = head;
while(current >= 0) {
len++;
current = next.get(current);
}
longest = Math.max(longest, len);
}
return longest;
}
public static void main(String[] args) {
int len = args.length;
Seg[] segments = new Seg[len/2];
for(int i=0; i<len; i+=2) {
Seg seg = new Seg();
seg.ID = Integer.parseInt(args[i]);
seg.NextID = Integer.parseInt(args[i+1]);
segments[i/2] = seg;
}
System.out.println(longest(segments));
}
}
//1. Initialize a map of Seg -> List<Seg>, which keeps track of each segment's longest list. Also initialize a set of visited segments, and a map which maps ID -> Segment
//2. Go through each segment. While the nextID is not -1, grab the segment of the nextId. if the visited set contains that segment then simply
// Add the segment's list to the current segment's list and stop. I've used LinkedList for the List implementation so hopefully this should be a simple pointer operation for the addAll
// If the visited set does not contain the segment then add it to the current segment's list, and update the current segment
//3. Run through the map's entrySet and find the biggest set. Convert to array and return.
public Seg[] longestConnectedSegs(Seg[] segments) {
Map<Integer, Seg> segmentMap = new HashMap<Integer, Seg>()
for (int i = 0; i < segments.length; i++) {
segmentMap.put(segments[i].id, segments[i]);
}
Map<Seg, List<Seg>> connectedMap = new HashMap<Seg, List<Seg>>();
Set<Seg> visitedSet = new HashSet<Seg>();
for (int i = 0; i < segments.length; i++) {
Seg currentSeg = segments[i];
visitedSet.add(currentSeg]);
List<Seg> currentList = new LinkedList<Seg>();
connectedMap.put(currentSeg, currentList);
currentList.add(currentSeg);
while (currentSeg.nextId != -1) {
int nextId = currentSeg.nextId;
Seg nextSegment = segmentMap.get(nextId);
if (visitedSet.contains(nextSegment)) {
currentList.addAll(connectedMap.get(nextSegment);
break;
} else {
currentList.add(nextSegment);
}
currentSeg = nextSegment;
}
}
int maxConnectedSegNum = 0;
List<Seg> maxConnectedSegs = null;
Set<Entry<Seg, List<Seg>>> entrySet = segmentMap.entrySet();
for (Entry<Seg, List<Seg>> entry : entrySet) {
List<Seg> connectedSeg = entry.value();
if (connectedSeg.size() > maxConnectedSegNum) {
maxConnectedSegNum = connectedSeg.size();
maxConnectedSegs = connectedSeg;
}
}
Seg[] maxSegs = new Seg[maxConnectedSegNum];
int i = 0;
for (Seg seg : maxConnectedSegs) {
maxSegs[i++] = seg;
}
return maxSegs;
}
Keep a variable,say lenOfSeq, which will count the length of the longerst sequence found till now. Now , start enumerating the set and analyze each element one by one. It's something similar to DFS , keep on finding the next element for the selected element and increase the count for each element. Now , whatever elements are being covered in this particular , we don't need to analyze them in future because they are alread part of a longer path. So ,we will store these elements in a separate set , say traversedElementSet , .
Okay here's my Java implementation of your idea:
import java.util.*;
class LongestStretch2 {
static class Seg { int ID; int NextID; }
static int longest(Seg[] segments) {
int longest = 0;
HashMap<Integer, Integer> next = new HashMap<Integer, Integer>();
HashMap<Integer, Integer> counts = new HashMap<Integer, Integer>();
for(Seg seg : segments) {
next.put(seg.ID, seg.NextID);
}
for(int id : next.keySet()) {
int len = 1;
int currId = id;
while(true) {
int nextId = next.get(currId);
if(counts.containsKey(nextId)) {
len += counts.get(nextId);
break;
}
if(nextId < 0)
break;
currId = nextId;
len++;
}
counts.put(id, len);
longest = Math.max(longest, len);
}
return longest;
}
public static void main(String[] args) {
int len = args.length;
Seg[] segments = new Seg[len/2];
for(int i=0; i<len; i+=2) {
Seg seg = new Seg();
seg.ID = Integer.parseInt(args[i]);
seg.NextID = Integer.parseInt(args[i+1]);
segments[i/2] = seg;
}
System.out.println(longest(segments));
}
}
- naren November 07, 2014