Flipkart Interview Question for SDE-2s


Country: India
Interview Type: In-Person




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

Just exploring the idea...
1) Overlapping Intervals: Use Segment Tree or Interval Tree. Tree has to be developed using minimum interval time. It can also detect collisions.

2) Non-Overlapping Intervals: Use a BST with start time of the meeting as the key (end time can is kept as a value). To detect collisions, for an input start time, check if the end time of the floor(start time) node is less than the input start time, and check if the start time of the ceil(start time) node is greater than the input end time.

- PraTrick March 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package tree;

class IntervalNode {

    public int startTime;
    public int endTime;
    public int max;
    public IntervalNode parent;
    public IntervalNode left;
    public IntervalNode right;

    @Override
    public String toString() {
        return "{Start: " + startTime + ", End: " + endTime + ", Max: " + max;
    }
}
public class IntervalTree {

    public static IntervalNode root = null;

    public void addInterval (int startTime, int endTime) {
        if (startTime > endTime)
        {
            System.out.println("Start time can not be greater than End Time");
            return;
        }
        IntervalNode temp = new IntervalNode();
        temp.startTime = startTime;
        temp.endTime = endTime;
        temp.max = endTime;

        if (root == null) {
            // add first node
            temp.parent = null;
            root = temp;
            return;
        }

        IntervalNode currentNode  = root;

        boolean breakloop = true;
        while(breakloop) {
            if (temp.startTime < currentNode.startTime) {
                if (currentNode.left == null) {
                    currentNode.left = temp;
                    temp.parent = currentNode;
                    breakloop = false;
                } else {
                    currentNode = currentNode.left;
                }
            } else {
                if (currentNode.right == null) {
                    currentNode.right = temp;
                    temp.parent = currentNode;
                    breakloop = false;
                } else {
                    currentNode = currentNode.right;
                }
            }
        }

        //Update Max
        while(currentNode != null && currentNode.parent !=null && currentNode.max > currentNode.parent.max) {
            currentNode.parent.max = currentNode.max;
            currentNode = currentNode.parent;
        }

    }

    private static boolean doOverlap(IntervalNode a, IntervalNode b) {
        if (a.startTime <= b.endTime && b.startTime <= a.endTime)
            return true;
        else
            return false;
    }
    public static IntervalNode checkIntervalCollision(int startTime, int endTime, IntervalNode node) {
        if (startTime > endTime)
        {
            System.out.println("Start time can not be greater than End Time");
        }

        // base case, tree is empty
        if (node == null) return null;

        IntervalNode tempNode = new IntervalNode();
        tempNode.startTime = startTime;
        tempNode.endTime = endTime;

        // if given interval overlaps with root
        if (doOverlap(tempNode, node))
        {
            System.out.println("Overlaps with" + node);
            return node;
        }

        if (node.left != null && node.left.max >= tempNode.startTime)
            return checkIntervalCollision(startTime, endTime, node.left);

        // else interval can only overlap with right
        return checkIntervalCollision(startTime, endTime, node.right);
    }

    public void display(IntervalNode intervalNode) {
        if ( intervalNode != null ) {
            System.out.println("{Start: " + intervalNode.startTime + ", END: " + intervalNode.endTime + ", MAX: "+ intervalNode.max + "}");
            display(intervalNode.left);
            display(intervalNode.right);
        }
    }


}

- contact@viveksoni.net November 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More