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

Interview Answer

10 Answers

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
1

(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.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 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);
                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= 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

Add Answers or Comments

To comment on this, Sign In or Sign Up.