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

- Anonymous April 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

it will give max count not the interval

- Nitin April 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

yes ,it will give you maximum overlapping interval count.

- Anonymous April 15, 2014 | Flag
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

- Anonymous April 15, 2014 | Flag
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.

- ravio April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

could u elaborate the algo please

- sunny April 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is also a very good solution

- huh June 07, 2014 | Flag
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)

- meow April 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you please elaborate on this.

- Nitin April 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- huh June 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- tushar aggarwal July 29, 2014 | Flag
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){
		
		//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());
	}

}

- faizals April 15, 2014 | Flag Reply
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)

- Aditya Kasturi April 15, 2014 | Flag Reply
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;
	}

- codedore April 15, 2014 | Flag Reply
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[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..

- debdas April 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Nitin April 20, 2014 | Flag
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);
}

- Anonymous April 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- tushar aggarwal July 29, 2014 | Flag
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);
}

- Nitin April 20, 2014 | Flag Reply
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

- Srikanth April 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its about maximum times an interval overlaps

- Nitin April 23, 2014 | Flag
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

- Krishna June 04, 2014 | Flag Reply
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[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;
}

- Brajesh Kumar August 28, 2014 | Flag Reply
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[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;
}

- Yagyesh Tripathi November 29, 2014 | Flag Reply
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
so answer is 8,3

- Anonymous April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I meant 8, 10

- Anonymous April 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aka April 13, 2014 | Flag


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