Facebook Interview Question: Given a set of n jobs with [s... | Glassdoor

## Interview Question

Software Engineer 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 epsilon)
{
if (m*m>d)
{
f = m;
}
else
{
s = m;
}
m = (s + f) / 2;
}
return m;
}

Rahul on May 2, 2013
2

(overlapping intervals)

public static int numOverlaps(ArrayList start, ArrayList 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 accum = new Hashtable();
verticalSums(accum, bt, 0);
print(accum);
}

public static void verticalSums(Hashtable 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 accum)
{
for (Integer k : accum.keySet())
{
System.out.println(k + " " + accum.get(k));
}
}

Rahul on May 3, 2013
0

(cost maximization)

public ArrayList maxCost(ArrayList 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 assignments;
public int cost;
public ArrayList jobs;

public Solution(ArrayList jobs)
{
assignments = new ArrayList();
this.jobs = jobs;
cost = 0;
}

public Solution assignNext(boolean value)
{
Solution s = new Solution(jobs);
for (Boolean b : assignments)
{
}
s.cost = cost;
if (value)
{
cost += jobs.get(s.assignments.size()-1).cost;
if (conflict(s))
{
cost = 0;
}
}
return s;
}

private boolean conflict(Solution s)
{
for (int i = 0; i < s.assignments.size()-1; i++)
{
if (!s.assignments.get(i)) continue;
}
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 intervals = new TreeSet();

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);
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= 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, 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