Interview Question for Dev Leads Dev Leads


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
0
of 0 vote

//Create a edge weighted digraph with negative weights as follows:
//Create vertexes for each segment with negative edge of -1 between joining segments
//Create two additional vertices one called source with edges from the source to all the segments
//Another vertex called sink with edges from all the vertices(excluding the "source" vertex) to the sink
//Apply Shortest path algorithm by Dijkstra from the "source" vertex to "sink" vertex
//Since edges are negative weights, this will give the longest path between vertices
//read the segments from the shortest path excluding the "source" and "sink" vertices
//Time complexity O((|V|+|E|) LOG |V|) Where |V| is the no of segments given and |E| is the number of connecting segments
//If there are no cycles between segements, instead of Dijkstra, you can apply topological sort and time complexity will be O(|V| + |E|)

- naren November 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

(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));
	}
}

- Sunny November 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//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;
}

- Anonymous November 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 , .

- praveenkcs28 November 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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));
	}
}

- Sunny November 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess, we should apply DFS of BFS for every node in the graph and select maximum of maximums + 1. Complexity is O(n^2). May be we can apply some optimizations, but I can't invent any.

- Maxim November 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can simply traverse the Segment Array and store the stretch Count and start Index of the each Stretch(separated by -1) into some Sorted Dictionary and then just Copy the segment elements associated with Maximum stretch from the Dictionary to the new Array?

- wizkid November 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What company was it?

- Zane August 03, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More