Facebook Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
For the maximum overlapping problem, the following solution creates a sorted list of 'events' where each event is the start or the end of an interval. Think of it as a timeline of events.
Now, is a simple case of traversing the list and keep track of overlaps.
public static void solve(int[][] intervals) {
List<Event> events = getSortedEvents(intervals);
int max = 0;
int overlap = 0;
int bestPoint = 0;
for(Event event : events) {
if ("Entry".equals(event.getType()))
overlap++;
else
overlap--;
if (overlap > max) {
max = overlap;
bestPoint = event.getTime();
}
}
System.out.println(max + " " + bestPoint);
}
private static List<Event> getSortedEvents(int[][] intervals) {
List<Event> events = new ArrayList<Event>();
for(int i=0; i < intervals.length; i++) {
events.add(new Event(intervals[i][0], "Entry"));
events.add(new Event(intervals[i][1], "Exit"));
}
return events
.stream()
.sorted(Comparator.comparing(Event::getTime).thenComparing(Event::getType))
.collect(Collectors.toList());
}
private static class Event {
private int time;
private String type;
Event(int time, String type) {
this.time = time;
this.type = type;
}
int getTime() { return time; }
String getType() { return type; }
}
For diameter:
class Main {
public static void main(String[] args) {
Node root = new Node(1);
Node l1 = new Node(2);
Node r1 = new Node(3);
Node l2 = new Node(4);
Node r2 = new Node(5);
Node l3 = new Node(6);
Node l4 = new Node(7);
Node l5 = new Node(8);
root.left=l1;
root.right=r1;
l1.left=l2;
l1.right=r2;
l2.left=l3;
r1.left=l4;
l3.right=l5;
System.out.println("ans: "+finddia(root));
}
public static int finddia(Node n){
int leftmax = maxheight(n.left);
int rightmax = maxheight(n.right);
return leftmax+rightmax+1;
}
public static int maxheight(Node n){
if(n==null)return 0;
int max = Math.max(maxheight(n.left),maxheight(n.right));
return max+1;
}
}
class Node {
int data;
Node left,right;
public Node(int d){
data=d;
}
}
1.2 Consider the input as arrival and departure time of guests and we have to find at which time there were max number of guests
public class PointOfMaxOverlapOfInterval {
public static void findMaxOverlapInterval(int[][] arr){
int[] entry = new int[arr.length];
int[] exits = new int[arr.length];
for(int i=0;i<=arr.length-1;i++){
entry[i] = arr[i][0];
exits[i] = arr[i][1];
}
Arrays.sort(entry);
Arrays.sort(exits);
//use merge of MergeSort
int i=0; // arrival
int j=0; // exits
int maxGuests=0; // max guests at a single time
int maxGuestsTime=0; // point in time with max no of guests i.e overlap
int totalGuestsSoFar=0; // running record of total guests present at any point
while(i<=entry.length-1 && j<=exits.length-1){
if(entry[i] <= exits[j]){ // guest entry less than equal ( if one enters and one leaves ,
// still we have more overlap at this point
totalGuestsSoFar++;
if(totalGuestsSoFar > maxGuests){
maxGuests=totalGuestsSoFar;
maxGuestsTime=entry[i];
}
i++; // Increment index of arrival
}else{ // guest exit
totalGuestsSoFar--;
j++; // Increment index of exists
}
}
System.out.println("maxGuests="+maxGuests+" maxGuestsTime="+maxGuestsTime);
}
public static void main(String[] args) {
int[][] arr = { {1,4}, {2,5} , {9,12} , {5,9} , {5,12},{4,12} };
findMaxOverlapInterval(arr);
}
}
Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
ONE TO ONE real-time coaching offers
SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Candidate's solution to 1.1
Solution to 1.2
- aonecoding July 15, 2017