CareerCup

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

int diameterOfBinaryTree(TreeNode* root) {
        maxDown(root);
        return maxLen;
    }
    
    int maxDown(TreeNode* r) {
        if (!r) return 0;
        int maxL = maxDown(r->left), maxR = maxDown(r->right);
        maxLen = max(maxLen, maxL+maxR);
        return max(maxL, maxR) + 1;
    }
    
    int maxLen = 0;

Solution to 1.2

public static List<int[]> maxOverlap(int[][] intervals) { //input [[start1, end1], [start2, end2]...]
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];
        for(int i=0; i<intervals.length; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }
        Arrays.sort(starts);
        Arrays.sort(ends);

        int rooms = 0;
        int endsItr = 0;
        int mark = 1;
        for(int i=0; i<starts.length; i++) {
            if (starts[i] < ends[endsItr]) {
                rooms++;
                mark = endsItr; //mark where the first max overlap zone appears
            } else {
                endsItr++;
            }
        }
        List<int[]> points = new ArrayList<>(); //result
        while(mark <= ends.length - rooms) {
            if(ends[mark] > starts[mark + rooms - 1]) {
                points.add(new int[]{starts[mark + rooms - 1], ends[mark]});
            }
            mark++;
        }
        //optional: convert non-overlap intervals in 'points' to collection of numbers if necessary
        return points;
    }

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);
	}
}