Engaged Employer

## Interview Question

Interview Menlo Park, CA

# Given a set of n jobs with [start time, end time, cost

] find a subset so that no 2 jobs overlap and the cost is maximum ?

0

(square root of double) public static double sqroot(double d) { if (d &lt; 0) return -1.0; double epsilon = 0.0001; double s = 0.0; double f = Math.max(d, 1.0); double m = (s + f) / 2; while (Math.abs(m*m-d) &gt; epsilon) { if (m*m&gt;d) { f = m; } else { s = m; } m = (s + f) / 2; } return m; }

Rahul on May 2, 2013
0

(overlapping intervals) public static int numOverlaps(ArrayList&lt;Double&gt; start, ArrayList&lt;Double&gt; stop) { Collections.sort(start); Collections.sort(stop); int numActive = 0; int numOverlap = 0; while ((start.size() &gt; 0) && (stop.size() &gt; 0)) { if ((start.size() &gt; 0) && (start.get(0).doubleValue() &lt; stop.get(0).doubleValue())) { start.remove(0); numOverlap += numActive; numActive++; } else { stop.remove(0); numActive--; } } return numOverlap; }

Rahul on May 2, 2013
0

(root to leaf) public static void allPaths(Node n) { allPaths(n, ""); } public static void allPaths(Node n, String history) { if (null == n) return; history = history + n.val; allPaths(n.left, history); allPaths(n.right, history); if ((null == n.left) && (null == n.right)) { System.out.println(history); } }

Rahul on May 3, 2013
0

(vertical level) public static void verticalSums(BT bt) { Hashtable&lt;Integer, Integer&gt; accum = new Hashtable&lt;Integer, Integer&gt;(); verticalSums(accum, bt, 0); print(accum); } public static void verticalSums(Hashtable&lt;Integer, Integer&gt; accum, BT bt, int level) { if (null == bt) return; int val = 0; if (accum.contains(level)) { val = accum.get(level); } val += bt.val; verticalSums(accum, bt.left, level-1); verticalSums(accum, bt.right, level+1); } public static void print(Hashtable&lt;Integer, Integer&gt; accum) { for (Integer k : accum.keySet()) { System.out.println(k + " " + accum.get(k)); } }

Rahul on May 3, 2013
0

Rahul on May 3, 2013
0

total data = 1 trillion * 10 words * 6 bytes / word = 60TB = one small NetApp box index by hashed userid ; will distribute traffic effectively across servers ; cache active users recent messages in memory

Rahul on May 3, 2013
1

Cannot use Netapp box. From what I read in FB engg blog, they have all the info in main memory of server. total data = 1 trillion * 10 words * 6 bytes / word = 60TB + 1TB for Indexes. considering servers have 64 GB ram. 61 GB usable to store index, 1000 servers.

fb_wannabe on Jan 4, 2014
0

Why 1TB for the index? If we have 10^12 messages and we want to index them shouldn't we have 64 bits hashes * 10^12 messages? How you calculated the memory size of the index?

Michele on Jan 29, 2014
0

Sort the end time, then use Stack. O(n)

Josh on Nov 13, 2014
0

import java.util.Scanner; import java.util.SortedSet; import java.util.TreeSet; public class NonOverlappingJobs { public static void main(String[] args) throws CloneNotSupportedException { final Scanner in = new Scanner(System.in); while (true) { System.out.println("Enter total intervals : "); int intervalCount = in.nextInt(); final SortedSet&lt;Interval&gt; intervals = new TreeSet&lt;Interval&gt;(); while (intervalCount &gt; 0) { final int startTime = in.nextInt(); final int endTime = in.nextInt(); final int cost = in.nextInt(); final Interval interval = new Interval(startTime, endTime, cost); intervals.add(interval); intervalCount--; } System.out.println("Input " + intervals); System.out .println(computeMaxCostNonOverlappingSet(intervals.toArray(new Interval[0]), null, 0)); } } private static Interval computeMaxCostNonOverlappingSet( Interval[] intervals, Interval maxInterval, int index) throws CloneNotSupportedException { if (index &gt;= intervals.length) { return null; } int maxCost = 0; Interval max = null; for (int i=index; i&lt;intervals.length; i++) { Interval interval = intervals[i]; if (maxInterval == null || interval.startTime &gt;= maxInterval.endTime) { Interval rem = computeMaxCostNonOverlappingSet( intervals, interval, i+1); if (rem == null) { rem = (Interval) interval.clone(); rem.cost = 0; } if (interval.cost + rem.cost &gt; maxCost) { max = new Interval(interval.startTime, rem.endTime, interval.cost + rem.cost); maxCost = max.cost; } } } return max; } static class Interval implements Comparable&lt;Interval&gt;, Cloneable { public Integer startTime; public Integer endTime; public Integer cost; public Interval(Integer startTime, Integer endTime, Integer cost) { this.startTime = startTime; this.endTime = endTime; this.cost = cost; } @Override protected Object clone() throws CloneNotSupportedException { Interval clone = new Interval(startTime, endTime, cost); return clone; } @Override public int compareTo(Interval o) { if (o == null) { return 1; } int result = startTime.compareTo(o.startTime); if (result == 0) { result = endTime.compareTo(o.endTime); if (result == 0) { result = cost.compareTo(cost); } } return result; } @Override public String toString() { return "{" + startTime + "," + endTime + "," + cost + "}"; } } }

Ker on Feb 23, 2015