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

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

}``````

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.