Flipkart Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
It's a classical segment tree question. You can simulate a tree using array and perform the standard segment tree algorithm on it.
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){
//add given objects
List<Coordinates> o = new ArrayList<Coordinates>();
o.add(new Coordinates(0, 5));
o.add(new Coordinates(2, 9));
o.add(new Coordinates(8, 10));
o.add(new Coordinates(6, 9));
//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());
}
}
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;
}
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[0]=1 array[1]=1....array[5]=1;
then for (2 9) array will be as follows
array[2]=2,array[3]=2,array[4]=2,array[5]=2 array[6]=1...array[9]=1;
as array[2] had a value 1 now it is 2;
for(8 10)
array[8]=2,array[9]=2,array[10]=1;
for(6 9)
array[6]=2,array[7]=2,array[8]=3,array[9]=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..
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);
}
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);
}
Is the problem about maximum number of times an interval overlaps or the maximum length it overlaps
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
#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[4] = {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[0];
int index = 0;
for(int k = 1; k < SIZE; k++) {
if(overlap[k] > max) {
max = overlap[k];
index = k;
}
}
return index;
}
int main() {
// your code goes here
_point input[4] = {{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;
}
#include<stdio.h>
void operate(int,int[]);
int maxer(int*,int);
int main()
{
int arr[100],a[100],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[10];
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[1],b[2],b[3],b[4]);
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[1];
for(int i=2;i<=n;i++)
{
if(max < p[i])
{
max =p[i];
k=i;
}
}
return k;
}
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
so answer is 8,3
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 ,
- Anonymous April 14, 2014Now 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