## Flipkart Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

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

Mark all the points (whether it is a start or end of interval) after that put all those points into a seperate struct array and sort ,
Now iterate the array of sorted struct which contains all the points(with start or end indication), now increase the count when you encounter start, and decrease when you encounter end, keep track of the max count so far

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

it will give max count not the interval

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

yes ,it will give you maximum overlapping interval count.

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

while updating the count keep track of the starting point of the interval also,hence u get the interval

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

It's a classical segment tree question. You can simulate a tree using array and perform the standard segment tree algorithm on it.

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

could u elaborate the algo please

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

This is also a very good solution

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

you basically sort the intervals then merge them will be easy. O(nlogn)

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

can you please elaborate on this.

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

That is the exact solution I came up with. Good!

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

what is ans for
0 5
4 6
4 6
4 6
6 13
and u find ans by usng sortng n then merging

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

Like meow mentioned, you need to find the difference between the intervals and sort them. I have posted my code.

``````//modelled the problem with this class
class Coordinates implements Comparable<Coordinates>
{

private int x;
private int y;
private int freq;

public Coordinates(int x1, int y1)
{
this.x = x1;
this.y = y1;

if(x>y)
freq = x-y;
else
freq = y-x;
}

public int getX() {
return x;
}

public void setX(int x) {
this.x = x;
}

public int getY() {
return y;
}

public void setY(int y) {
this.y = y;
}

public int getFreq() {
return freq;
}

public void setFreq(int freq) {
this.freq = freq;
}

//sorting by ascending
public int compareTo(Coordinates c)
{

return this.freq - c.freq;

}

}

//Tester class
public class Tester {

public static void main (String[] args){

List<Coordinates> o = new ArrayList<Coordinates>();

//sort by difference between intervals
Collections.sort(o);

//retrieve or print the object at index 0
System.out.println(o.get(0).getX()+"::"+o.get(0).getY());
}

}``````

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

I Think The above code doesn't work for (0,5)(2,9)(8,10)(6,9)(11,12)

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

``````public static class Point implements Comparable<Point> {
public int x;
public int y;
public Point(int x , int y){
this.x = x;
this.y = y;
}
@Override
public int compareTo(Point o) {
// TODO Auto-generated method stub
return x - o.x;
}
public String toString(){
return "["+x+","+y+"]";
}
}

public static int getMaxOverlappingIntervals(List<Point> points) {

// sort the points with ascending start order.
Collections.sort(points);

int result = 0;
Point maxPoint = new Point(points.get(0).x,points.get(0).y);
String overlaps = " [" + points.get(0).x + "," + points.get(0).y + "]";

for (int i = 1; i < points.size(); i++) {
if (maxPoint.y > points.get(i).x) { // overlap
maxPoint.y = Math.max(points.get(i).y,maxPoint.y);
overlaps += " [" + points.get(i).x + "," + points.get(i).y + "]";
result++;
} else {
maxPoint.y = points.get(i).y;
maxPoint.x = points.get(i).x;
}
}
if ( result == 0 ){
System.out.println(" overlaps : " + 0);
}else{
result++;
System.out.println(" overlaps : " + overlaps);
}
return result;
}``````

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

I have a solution...
First take an array and initialize all its value to zero...
then for particular interval, increment the array values by one between that interval indices of that array..
for example
(0 5)
increment the values by one between index 0 to index 5.. so we get array=1 array=1....array=1;
then for (2 9) array will be as follows
array=2,array=2,array=2,array=2 array=1...array=1;
as array had a value 1 now it is 2;
for(8 10)
array=2,array=2,array=1;
for(6 9)
array=2,array=2,array=3,array=3;
..after inserting all the values
search the array for the maximum value here it's 3..so the answer will be the corresponding interval...here it is (8 10)..
...the first occurrence of max value will denote the starting time of the maximum overlapping interval...
we can link the interval starting point and end point with corresponding index number...
for array index 0 it will point the interval (0 5)
for array index 2 it will point the interval (2 9)..and so on..

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

It will not work as its answer is [8,10]...while the correct answer should be [2,9]

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

``````void getmax(struct ele a[])
{
int i=0,j=0;
struct temp b[2*N];
for(i=0;i<N;i++)
{
b[j].time = a[i].start;
b[j++].c = 's';
b[j].time = a[i].end;
b[j++].c = 'e';
}
sort(b,0,2*N-1);
int count=0,start=0,max=0;
for(i=0;i<2*N;i++)
{
if(b[i].c == 's')
count++;
if(b[i].c == 'e')
count--;
if(max<count)
{
max = count;
start = b[i].time;
}
}
for(i=0;i<N;i++)
{
if(start>a[i].start && start <a[i].end)
start = a[i].start;
}
i=0;
while(start!=a[i].start)
i++;
printf("Max overlapping interval is (%d,%d) and max overlap is %d\n",a[i].start,a[i].end,max);
}``````

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

is this code work for case
0 5
4 6
4 6
4 6
6 13
6 12
ur code gives 0 5
ans shud be 6 13

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

``````void getmax(struct ele a[])
{
int i=0,j=0;
struct temp b[2*N];
for(i=0;i<N;i++)
{
b[j].time = a[i].start;
b[j++].c = 's';
b[j].time = a[i].end;
b[j++].c = 'e';
}
sort(b,0,2*N-1);
int count=0,start=0,max=0;
for(i=0;i<2*N;i++)
{
if(b[i].c == 's')
count++;
if(b[i].c == 'e')
count--;
if(max<count)
{
max = count;
start = b[i].time;
}
}
int begin=100,end=0;
for(i=0;i<N;i++)
{
if(start>a[i].start && start <a[i].end)
{
if(a[i].start<begin)
{
begin = a[i].start;
end = a[i].end;
}
}
}
printf("Max overlapping interval is (%d,%d) and max overlap is %d\n",begin,end,max);
}``````

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

Is the problem about maximum number of times an interval overlaps or the maximum length it overlaps

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

Its about maximum times an interval overlaps

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

1. while reading the intervals, store the interval start Vs interval end into a hashmap.
i.e map.put(0,5)
map.put(2,9) and so on...
2. simultaneously, sort the numbers present in intervals in an array
i.e 0 , 2 , 5 , 6 , 8 , 9 , 10....
3. iterate over this sorted array and check
i. if arr[i] is a key in above hashmap, interval_end = map.get( arr[i] ) // arr[i] means an interval start
else continue
ii. iterate till interval_end and count the numbers in between arr[i] and interval_end
iii. keep a max variable and a interval_start variable to maintain the interval which has max overlaps

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

``````#include <iostream>
#include <algorithm>
using namespace std;
#define SIZE 4
typedef struct point {
int min;
int max;
}_point;

int compare(const _point x, const _point y) {

return( (x.min < y.min)? 1 : 0);

}

void print(_point * inpt)
{
for(int i = 0; i < 4; i++)
{
cout << endl << inpt[i].min << "\t" << inpt[i].max;

}
}

int maxOverlap(_point* inpt) {

int overlap = {0};

for(int i = 0; i < SIZE; i++) {

for(int j = i+1; j < SIZE ; j++) {

if((inpt[i].max >= inpt[j].min) && (inpt[i].max <= inpt[j].max)) {

overlap[i] = overlap[i] + 1;
overlap[j] = overlap[j] + 1;
}

}
}

int max = overlap;
int index = 0;
for(int k = 1; k < SIZE; k++) {

if(overlap[k] > max) {
max = overlap[k];
index = k;
}
}

return index;
}

int main() {

_point input = {{0,5},{2,9},{8,10},{6,9}};
sort(input,(input+4), compare);
print(input);

int result_index = maxOverlap(input);

cout << "\n max overlap pair is : (" << input[result_index].min << "," << input[result_index].max << ")";

return 0;
}``````

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

``````#include<stdio.h>
void operate(int,int[]);
int maxer(int*,int);
int main()
{
int arr,a,n,i;
printf("Enter the no of intervals \n");
scanf("%d",&n);
printf("Enter interval values??\n");
for(i=1;i<=2*n;i++)
{
scanf("%d",&arr[i]);
}
operate(n,arr);
}
void operate(int n,int a[])
{
int i,j;
static int b;
for(i=1;i<n;i++)
{
//printf("looping 1\n");
for(j=i+1;j<=n;j++)
{
//printf("looping 2\n");
if(a[2*i] <= a[2*j-1])
{

//printf("Inside 1\n");
continue;
}
else if(a[2*i-1] >= a[2*j])
{
//printf("Inside 2\n");
continue;
}
else
{
if(a[2*i-1] <= a[2*j-1])
{
//printf("out here..1\n");
if(a[2*i] <= a[2*j])
{
b[i] = b[i]+a[2*i]-a[2*j-1];
b[j]= b[j]+a[2*i]-a[2*j-1];
}
else
{
b[i]= b[i]+a[2*j]-a[2*j-1];
b[j]=b[j]+a[2*j]-a[2*j-1];
}
}
else
{
if(a[2*i] <= a[2*j])
{
b[i]= b[i]+a[2*i]-a[2*i-1];
b[j]=b[j]+a[2*i]-a[2*i-1];
}
else
{
b[i] = b[i]+a[2*j]-a[2*i-1];
b[j]=b[j]+a[2*j]-a[2*i-1];
}
}
}

}
}
i=1;
while(b[i] == 0)
{
if(i == n+1)
break;
i++;
}
//printf("%d %d %d %d \n",b,b,b,b);
if(i == n+1)
{
printf("No common!!");
}
else
{
int max = maxer(b,n);
printf("the interval is (%d,%d)",a[2*max-1],a[2*max]);
}
}
int maxer(int *p,int n)
{
int max,k=1;
max = p;
for(int i=2;i<=n;i++)
{
if(max < p[i])
{
max =p[i];
k=i;

}
}
return k;
}``````

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

Create hash table
1st go from 0 to 5 add all in hashtable
2nd go from 2 to 9 add to hashtable if does not exists else increment by 1
continue this way for rest for the interval.
Loop through and find the max count this case 8 appears 3 time and 10 appears 3 times

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

I meant 8, 10

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

how does 10 appear 3 times? does'nt the answer should be 8,9?

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.