## Flipkart Interview Question

Country: India
Interview Type: Phone Interview

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

Think of it as a room and the intervals are times when a person is in the room. You are looking for time when max number of people are in a room. Note: I am assuming open intervals.

So sort the points, and traverse in ascending order. As an event occurs (person joins, left endpoint or person leaves, right end point), update the counts accordingly.

``````def get_max_overlap(intervals):

endpoints = []
left = None
count = 0
for interval in intervals:
endpoints.append((interval, True, interval))
endpoints.append((interval, False, interval))

endpoints.sort()

count = 0
max_count = 0
cur_intervals = {}
max_intervals = {}
for endpoint in endpoints:
interval = endpoint
is_left = endpoint
if is_left:
count += 1
cur_intervals[interval] = count
if count > max_count:
max_count = count
max_intervals = cur_intervals.copy()
else:
del cur_intervals[interval]
count -= 1

return max_intervals.keys()

def get_intervals(points_list):
intervals = []
left = None
count = 0
for point in points_list:
count += 1
if count % 2 == 0:
intervals.append((left, point))
else:
left = point
return intervals

def print_intervals(msg, intervals, scale = 3):
sorted_intervals = sorted(intervals, key = lambda x: x)
print msg, sorted_intervals

for interval in sorted_intervals:
left = interval
right = interval
left_indent = left*scale -2
if left > 10:
left_indent -= 1
w = (right-left)*scale
print " "*left_indent,left,"-"*w,right

def show_overlaps(points_list):
intervals = get_intervals(points_list)
overlap = get_max_overlap(intervals)
print_intervals("Input", intervals)
print ""
print_intervals("Maximum Overlap", overlap)

def main():
show_overlaps([0,5,2,9,8,10,6,9])
show_overlaps([1,20,2,8,3,15,8,12,14,17,19,20,2,22])

if __name__ == "__main__":
main()``````

``````Input [(0, 5), (2, 9), (6, 9), (8, 10)]
0 --------------- 5
2 --------------------- 9
6 --------- 9
8 ------ 10

Maximum Overlap [(2, 9), (6, 9), (8, 10)]
2 --------------------- 9
6 --------- 9
8 ------ 10

Input [(1, 20), (2, 8), (2, 22), (3, 15), (8, 12), (14, 17), (19, 20)]
1 --------------------------------------------------------- 20
2 ------------------ 8
2 ------------------------------------------------------------ 22
3 ------------------------------------ 15
8 ------------ 12
14 --------- 17
19 --- 20

Maximum Overlap [(1, 20), (2, 8), (2, 22), (3, 15)]
1 --------------------------------------------------------- 20
2 ------------------ 8
2 ------------------------------------------------------------ 22
3 ------------------------------------ 15``````

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

This should be implementable in O(n log n) time, but the cur_intervals.copy() line can make it quadratic (and this was to get the list of intervals, if you just need the count, then there is no issue).

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

The actual code to get the overlaps was easy. Most of the time was spent(wasted?) in trying to pretty print.

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

And pretty printing has a bug if the interval starts with 0.

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

and other places. LOL.

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

This is a really nice piece of code and I agree with your algorithm --- swiping! Thanks for taking effort preparing such a nice program and please ignore those ill jokes.

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

Having said this, I think there is a tiny bug in your code: if there is a end point, say, 9, that is both a left boundary for an interval A and a right boundary for another interval B, A appears ahead of B. Then your algorithm will have this max_intervals++ behavior once 9 as the left boundary of A is scanned; while in fact it is not changed since 9 is also the right boundary of B.

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

Thanks Chih. The joke comments were made by me only (I am the author of the code), so no ill will.

Yes, there seems to be a bug. Thanks for pointing out.

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

can you able to send this code with java to my mail id kotresha888@gmail.com.........

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

This is a problem of finding the number of platform required on a railway station given the train arrival and departure times.

[a1,d1], [a2,d2], [a3,d3]....
create two sorted array - one for arrival and another for departure.

initialize the number of platform required = 0;
i and j the counters for arrival and departure list; initialized to 0;

for all a[i] in the arrival sorted list
{

increment the number of platform required by 1;
if d[j] < a[i] then
{
decrement the number of platform required by 1;
j++;
}
i++;
}

number of platform required is the max_interval;

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

Nice solution man !

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

Simple and efficient solution !!

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

Doesn't [2,9] overlap with [0, 5] and similarly for others?

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

[2,9] overlaps only with [0,5]. we have to find for any single interval what is the maximum number of overlap and 8,10 has the max no. of overlaps

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

why? doesn't 2,9 overlap 8,10 and 6,9 too?

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

I think you can sort the intervals by the right endpoint which will result in
[0, 5]
[2, 9]
[6, 9]
[8, 10] in this case. Now you know that the left endpoint of the rightmost interval will be <= or > to the right endpoint of the previous one. If it's the former, we increment the counter and proceed to the previous interval until we find the interval whose right endpoint is smaller than the left endpoint. If it's the latter case, you exclude that interval and continue the process for the rest of the case. Sorting takes O(nlogn) and takes linear time to search for the maximally overlapping interval.

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

can you explain bit more ....................

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

I think more intuitive way to think about this is you take the minimum left endpoint and the maximum right endpoint. These will be the range of values that you can take on. In this case [0, 10]. Iterate every value from 0 to 10 and mark every value that's the left endpoint of the given interval and while you iterate through the value you encounter left endpoint of another interval then you know there's overlap. For instance,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
L L L L
I marked L for the left end point of every interval. So while we are going through the interval [0, 5] we encounter L for number 2. So you increment the counter for [0, 5]. You repeat the same steps for the rest of the given intervals and take the max of the counters. The interval that has the maximum counter will be the one that overlaps the most.

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

oops formatting messed up the L positions.

``````0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
L      L               L      L``````

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

Still not the right positions for L.

``````0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
L      L               L      L``````

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

The question is unclear. Do we return the interval/count which intersects with most intervals or we are looking for maximum overlap (i.e. a set of intervals which intersect each other).

Basically, if you create a graph of intervals (adjacency determined by interval intersection) are you looking for maximum degree or maximum clique?

The typically asked question is for maximum clique.

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

We have to return only the count

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

It is asking whether you want count of A or count of B. You respond, we want count...

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

if it means the max number in a certain interval, then can be done by sorting on the left point, then binary search the right point in the list, and keep the end position for each interval in an array, so in one pass we'll get the result. time complexity o(nlgn) space o(n)

if it means the interval which overlaps most number of intervals, we need sort twice. one is by the left point, the other on the right point. similar idea, just count twice to get each interval's overlapping number. still nlgn

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

for overlapping mean the element within 1 interval lies in other.then for each interval u can check that the lower bound of other interval is greater than the first interval and upperbound is less than the upper bound of first interval..
complexity 0(n^2).

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

``````public class maxIntervals {
public static boolean findIntervals(int a1, int b1, int a2, int b2) {
if ((b1 < a2) || (a1 > b2))
return false;
return true;
}

public static void main(String[] args) {
maxIntervals ob1 = new maxIntervals();
int size = 4;

// int interval[][] = new int[size][size];
int interval[][] = { { 0, 5 }, { 2, 9 }, { 6, 9 }, { 8, 10 }};
int intervalCount[] = new int[size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {

if (!(i == j)) {
if (findIntervals(interval[i], interval[i],
interval[j], interval[j])) {
int key = 0;
key = intervalCount[i];
key++;
intervalCount[i] = key++;
}
}
}
}
for (int i = 0; i < size; i ++ ) {
System.out.println(intervalCount[i]);
}
}``````

}

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

#include<stdio.h>
int main()
{
int arr={0,5,2,9,8,10,6,9};
int table={0};
int i,sizeArray,max,temp1,temp2;
max=0xFFFF;
sizeArray=sizeof(arr)/sizeof(int);
/* for(i=0;i<sizeArray;i++)
{
if(max<arr[i])
max=arr[i];
}
*/
for(i=0;i<sizeArray;i++)
{
temp1=arr[i];
temp2=arr[++i];
while(temp1<=temp2)
{
table[temp1]=table[temp1]+1;
temp1++;
}
}
printf("Table\n");
for(i=0;i<=10;i++)
printf("%d ",table[i]);
max=table;
for(i=1;i<=10;i++)
{
if(max<table[i])
{
max=table[i];
}
}
printf("\nMax=%d",max);
return 0;
}

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

``````#include<stdio.h>
int main()
{
int arr={0,5,2,9,8,10,6,9};
int table={0};
int i,sizeArray,max,temp1,temp2;
max=0xFFFF;
sizeArray=sizeof(arr)/sizeof(int);
/* for(i=0;i<sizeArray;i++)
{
if(max<arr[i])
max=arr[i];
}
*/
for(i=0;i<sizeArray;i++)
{
temp1=arr[i];
temp2=arr[++i];
while(temp1<=temp2)
{
table[temp1]=table[temp1]+1;
temp1++;
}
}
printf("Table\n");
for(i=0;i<=10;i++)
printf("%d ",table[i]);
max=table;
for(i=1;i<=10;i++)
{
if(max<table[i])
{
max=table[i];
}
}
printf("\nMax=%d",max);
return 0;
}``````

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

I think this can be easier using interval tree.

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

Store input into String array. String[] intervals = { "0-5", "2-9", "8-10", "6-9" };
Here is the code

``````public static void overlapping(String[] intervals) {
boolean[] overlaps = new boolean;

int rangeStart = 0;
int rangeEnd = 0;
List<Integer> ll = new ArrayList<Integer>();
for (String interval : intervals) {
int start = Integer.parseInt(interval.split("-"));
int end = Integer.parseInt(interval.split("-"));
if (rangeEnd != 0) {
}
rangeStart = 0;
rangeEnd = 0;
boolean rangeFlag = false;
for (int i = start; i <= end; i++) {
if (!overlaps[i]) {
overlaps[i] = true;
} else {
if (!rangeFlag) {
rangeStart = i;
rangeFlag = true;
}
rangeEnd++;
}
}
}

System.out.println(ll.size() / 2);
}``````

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.