## Facebook Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

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

``````public class Solution {

public int maxWeight(Interval[] intervals) {

//First calculate all possible subsets
List<List<Interval>> subsets = calculateSubsets(intervals);

//Since they are sorted, find the maximum weight. If intervals
//overlap, do not use the set.
int maxWeight = 0;
for(List<Interal> subset: subsets){
if(subset.size() > 0){
int currWeight = subset.get(0).weight;
int currEnd = subset.get(0).end;
boolean isCandidate = true;

for(int 1 = 0; i < subset.size(); i++){
if(subset.get(i).start < currEnd){
isCandidate = false;
break;
} else {
currWeight += subset.get(i).weight;
currEnd = subset.get(i).end;
}
}

if(isCandidate){
maxWeight = Math.max(currWeight, maxWeight);
}
}
}

return maxWeight;

}

public List<List<Interval>> calculateSubsets(Interval[] intervals){
List<List<Intervals>> subsets = new ArrayList<List<String>>();

Arrays.sort(intervals, new Comparator<Interval>(){
@Override
public int compare(Interval i1, Interval i2){
return i1.end < i2.end;
}
});

for(Interval i: intervals){
List<List<Interval>> temp = new ArrayList<List<String>>();
for(List<Intervals> s: subsets){
ArrayList<Interval> n = new ArrayList<Interval>(s);
}
}

return subsets;
}
}``````

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

Build trees where the heads are the overlapping first N meetings and remove them from the available list, then under each tree add all possible (non-overlapping) subtrees and traverse them all.

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

Other way of doing this is first sort all the meetings by start time. then parse these set of meetings from start forming hour buckets or meeting buckets goal is to find all the set of meetings that are overlapping(since only one of these can be attended). Once we have the set of meeting buckets choose the highest weight meeting from each bucket.

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

List <Meeting> FindFirstAvilMeets (Datetime StartTime, List <Meeting> Meetings)
{
List <Meeting> ret = new List <Meeting> ();
for each(var m in Meetings)
{
if (m.StartTime < StartTime) continue;
bool bIncl = true;
for each(var m2 in Meetings)
{
if (m2.StartTime < StartTime) continue;
if (m is m2) continue;
if (m.startTime >= m2.endTime) {bIncl = false; break; }
}
if (bIncl)
}
return ret;
}

int gMaxWt = 0;
List <Meeting> gMaxWtSol;

void FindMaxWtSolution(int Wt, List<Meeting> Found, List<Meeting> TheRest)
{
if (TheRest.Length == 0)
if (Wt > gMaxWt)
{
gMaxWt = Wt; gMaxWtSol = Found; return;
} else
return;
DateTime StartTime = new DateTime(0);
if (Found.Length > 0) StartTime =Found[Found.Length - 1];
for each(var m in FindFirstAvilMeets(StartTime, TheRest))
{
}
}

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

``````object Solution {

case class Meeting(start: Long, end: Long, weight: Int) extends Ordered[Meeting] {
def isOvelappedBy(meeting: Meeting) = {
val (min, max) = if (this <= meeting) (this, meeting) else (meeting, this)
(min.end > max.start && min.end < max.end) || (min.end >= max.end)
}

override def compare(that: Meeting) = Meeting.ordering.compare(this, that)
}

object Meeting {
def parse(sc: java.util.Scanner) = Meeting(sc.next().toLong, sc.next().toLong, sc.nextInt())

implicit val ordering: Ordering[Meeting] = Ordering.by(_.start)
}

val sc = new java.util.Scanner(System.in)
val n = sc.nextInt
val meetings = collection.mutable.ListBuffer.empty[Meeting]
for (i <- 0 until n) meetings += Meeting.parse(sc)
meetings.toList
}

def schedule(meetings: List[Meeting]): Int = {
val sorted = meetings.sorted

def partitionOverlappings(meeting: Meeting, meetings: List[Meeting]): (List[Meeting], List[Meeting]) = {
(meetings.filter(meeting.isOvelappedBy(_)), meetings.filter(!meeting.isOvelappedBy(_)))
}

def scheduleHelper(meetings: List[Meeting], weight: Int): Int = {
meetings match {
case meeting::rest => {
val (overlappings, notOverlappings) = partitionOverlappings(meeting, meetings)
math.max(
scheduleHelper(notOverlappings, weight + meeting.weight),
overlappings.map(o => scheduleHelper(rest, weight)).max
)
}

case _ => weight
}
}

scheduleHelper(meetings, 0)

}

def main(args: Array[String]) {
println(schedule(meetings))
}
}``````

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

We can sort the meetings by start time, and then, compare situations of taking the particular meeting and skipping it:

``````class Meeting {
public:
int start_;
int end_;
int weight_;
Meeting(int start, int end, int weight)
{
start_ = start;
end_ = end;
weight_ = weight;
}
bool operator < (Meeting const &other) const
{
if (start_ == other.start_) {
return end_ < other.end_;
}
return start_ < other.start_;
}
};

class Result {
public:
int total_weight_;
vector<Meeting> meetings_;
bool valid_;
Result(bool valid)
{
valid_ = valid;
total_weight_ = 0;
}
};

Result OptimalSchedule(vector<Meeting> const &meetings, vector<Result> &memo, int idx = 0)
{
if (idx >= meetings.size() ||
idx < 0)
{
return Result(true);
}

if (idx == 0) {
memo.clear();
memo.resize(meetings.size(), Result(false));
}
if (memo[idx].valid_) {
return memo[idx];
}

int next_idx = idx + 1;
while (next_idx < meetings.size() &&
meetings[next_idx].start_ <= meetings[idx].end_)
{
++next_idx;
}

Result take = OptimalSchedule(meetings, memo, next_idx);
take.total_weight_ += meetings[idx].weight_;
take.meetings_.push_back(meetings[idx]);

Result skip = OptimalSchedule(meetings, memo, idx + 1);

memo[idx] = take.total_weight_ > skip.total_weight_ ? take : skip;
return memo[idx];
}

Result OptimalSchedule(vector<Meeting> &meetings)
{
sort(meetings.begin(), meetings.end());
vector<Result> memo;
return OptimalSchedule(meetings, memo);
}``````

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

``````/*
*Steps:
* 1. Sort the intervals based on start time
* 2. Use dynamic program to calculate weight by including current meeting and skipping current meeting
*   Use max from above two to get weight
*
*/
public class MaximumWeightMeeting {

public static List<Meeting> getMaxWeightMeeting(List<Meeting> list ,int i, int sumOfWeights, List<Meeting> result){
//System.out.println("weight="+sumOfWeights);
if(i >= list.size()){
//return sumOfWeights; // don't return 0. Return what has been calculated yet
List<Meeting> ret = result;
ret.add(new Meeting(0,0,sumOfWeights)); // create dummy meeting with 0 start , end and sumOfWesights as sum
return ret;
}

int nextMeetingIndex = nextPossibleMeeting(list,i);
List<Meeting> newResult = new ArrayList<Meeting>(result); // newresult when we attend current meeting

// Max of (attending current meeting and call for next Possible meeting that can be attended,
// skip currentMeeting and call for next meeting (i+1)
//return Math.max(getMaxWeightMeeting(list,nextMeetingIndex,sumOfWeights+list.get(i).weight, newResult),
//		getMaxWeightMeeting(list, i+1, sumOfWeights, result));

List<Meeting>  result1 =  getMaxWeightMeeting(list,nextMeetingIndex,sumOfWeights+list.get(i).weight, newResult);
List<Meeting>  result2 = getMaxWeightMeeting(list, i+1, sumOfWeights, result);

int sumWeight1 = result1.get(result1.size()-1).weight;
int sumWeight2 = result2.get(result2.size()-1).weight;

if(sumWeight1 > sumWeight2){
return result1;
}else{
return result2;
}
}

public static int nextPossibleMeeting(List<Meeting> list , int k){
for(int i=k+1;i<=list.size()-1;i++){
if(list.get(i).startTime >= list.get(k).endTime){ // find next meeting that can be attended by after kth meeting
return i;
}
}
return Integer.MAX_VALUE; // very last meeting index
}

public static void main(String[] args) {

List<Meeting> list = new ArrayList<Meeting>();

// Sort Meetings by Start time
Collections.sort(list,new MeetingComparator());

for(Meeting m : list){
System.out.println(m.toString());
}

List<Meeting> result = getMaxWeightMeeting(list,0,0 ,new ArrayList<Meeting>());
System.out.println("Max sum of weights = " + result.get(result.size()-1).weight);
System.out.println("Max sum Meeting Intervals : " + result.toString());

}

}

class Meeting{
int startTime;
int endTime;
int weight;

Meeting(int startTime, int endTime, int weight){
this.startTime = startTime;
this.endTime = endTime;
this.weight = weight;
}

public String toString(){
return this.startTime + "," + this.endTime + "," + this.weight;
}
}

class MeetingComparator implements Comparator<Meeting>{
public int compare(Meeting m1, Meeting m2){
// return the one with smaller startTime
return (m1.startTime < m2.startTime)?-1:((m1.startTime > m2.startTime)?1:0);
}
}``````

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

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.

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