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 ?
Answer

Interview Answer

10 Answers

0

(square root of double) public static double sqroot(double d) { if (d < 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) > epsilon) { if (m*m>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<Double> start, ArrayList<Double> stop) { Collections.sort(start); Collections.sort(stop); int numActive = 0; int numOverlap = 0; while ((start.size() > 0) && (stop.size() > 0)) { if ((start.size() > 0) && (start.get(0).doubleValue() < 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<Integer, Integer> accum = new Hashtable<Integer, Integer>(); verticalSums(accum, bt, 0); print(accum); } public static void verticalSums(Hashtable<Integer, Integer> 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<Integer, Integer> accum) { for (Integer k : accum.keySet()) { System.out.println(k + " " + accum.get(k)); } }

Rahul on May 3, 2013
0

(cost maximization) public ArrayList<Boolean> maxCost(ArrayList<Job> jobs) { return (maxCost(new Solution(jobs))).assignments; } private Solution maxCost(Solution solution) { Solution falseSol = solution.assignNext(false); Solution trueSol = solution.assignNext(true); return (trueSol.cost > falseSol.cost) ? trueSol : falseSol; } public class Solution { public ArrayList<Boolean> assignments; public int cost; public ArrayList<Job> jobs; public Solution(ArrayList<Job> jobs) { assignments = new ArrayList<Boolean>(); this.jobs = jobs; cost = 0; } public Solution assignNext(boolean value) { Solution s = new Solution(jobs); for (Boolean b : assignments) { s.assignments.add(b); } s.cost = cost; s.assignments.add(value); if (value) { cost += jobs.get(s.assignments.size()-1).cost; if (conflict(s)) { cost = 0; } } return s; } private boolean conflict(Solution s) { Job newlyAdded = jobs.get(s.assignments.size()-1); for (int i = 0; i < s.assignments.size()-1; i++) { if (!s.assignments.get(i)) continue; Job alreadyScheduled = jobs.get(i); if ((alreadyScheduled.start < newlyAdded.start) && (newlyAdded.start < alreadyScheduled.stop)) return true; if ((alreadyScheduled.start < newlyAdded.stop) && (newlyAdded.stop < alreadyScheduled.stop)) return true; } return false; } }

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<Interval> intervals = new TreeSet<Interval>(); while (intervalCount > 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 >= intervals.length) { return null; } int maxCost = 0; Interval max = null; for (int i=index; i<intervals.length; i++) { Interval interval = intervals[i]; if (maxInterval == null || interval.startTime >= maxInterval.endTime) { Interval rem = computeMaxCostNonOverlappingSet( intervals, interval, i+1); if (rem == null) { rem = (Interval) interval.clone(); rem.cost = 0; } if (interval.cost + rem.cost > maxCost) { max = new Interval(interval.startTime, rem.endTime, interval.cost + rem.cost); maxCost = max.cost; } } } return max; } static class Interval implements Comparable<Interval>, 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

Add Answers or Comments

To comment on this, Sign In or Sign Up.