Coupon Dunia Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




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

Solution:
1) Sort the intervals by END times into a collection S.
2) Remove the first (earliest end time) interval from S -> you will go to that party (count++).
3) Delete all the intervals at the head of S that intersect with the one chosen in 2) as you cannot go to these parties.
4) Go back to 2) in a looping fashion.

Why is this the correct algorithm?

Assume you have a bunch of parties to go to, we are going to prove that we should FIRST pick the one with the earliest end time.

Assume otherwise (for proof by contradiction) that it's advantageous to pick another party... fill in the details.

- RecruitingForSandvineCanada August 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you please provide working code for the same. I am unable to code it.

- dk August 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you please provide working code. I am unable to follow your algo.

- ritwik_pandey August 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can do this by sorting by start-times as well:

var times = [[1,4],[1,9],[2,8],[3,7],[5,6],[8,10]];

function maxMeetings(arr) {
	arr = arr.sort(function(a, b) { return (a[0]-b[0]); });
    
    var results   = [];
    var prevStart = arr[0][0];
    var prevEnd   = arr[0][1];
    
    for(var i=1; i<arr.length; i++) {
    	var currStart = arr[i][0];
        var currEnd   = arr[i][1];
        
        // trick is to maximize the # of meetings so '<'
        if(currStart < prevEnd) {
        	prevEnd = Math.min(prevEnd, currEnd);
        } else {
        	results.push([prevStart, prevEnd]);
            prevStart = currStart;
            prevEnd   = currEnd;
        }
    }
    results.push([prevStart, prevEnd]);
    return results;
}

console.log(JSON.stringify(maxMeetings(times)));

- Aslam October 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can do this by sorting by start-times as well :

var times = [[1,4],[1,9],[2,8],[3,7],[5,6],[8,10]];

function maxMeetings(arr) {
	arr = arr.sort(function(a, b) { return (a[0]-b[0]); });
    
    var results   = [];
    var prevStart = arr[0][0];
    var prevEnd   = arr[0][1];
    
    for(var i=1; i<arr.length; i++) {
    	var currStart = arr[i][0];
        var currEnd   = arr[i][1];
        
        // trick is to maximize the # of meetings so '<'
        if(currStart < prevEnd) {
        	prevEnd = Math.min(prevEnd, currEnd);
        } else {
        	results.push([prevStart, prevEnd]);
            prevStart = currStart;
            prevEnd   = currEnd;
        }
    }
    results.push([prevStart, prevEnd]);
    return results;
}

console.log(JSON.stringify(maxMeetings(times)));

- aforaslam October 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Using Dynamic Programming, because there are 24 hours per day, set the DP size to 25

int maxParties(vector<pair<int, int>> v)
{
    unordered_map<int,vector<int>> record;

    for(int i=0; i<v.size(); i++)
    {
       record[v[i].second].push_back(v[i].first);
    }

    vector<int> DP(25, 0);
    for(int i=1; i<=24; i++)
    {
       DP[i]= DP[i-1];
       if (!record[i].empty())
       {
          for(int j=0; j<record[i].size(); j++)
          DP[i]= max(DP[i], DP[record[i][j]]+1);
       }
    }

    return DP.back();
}

And the output is 3

- soneyoung August 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this solution[ O(n) ] is better than greedy approach [O(log n)] (because of sorting) mentioned above but has a disadvantage as it uses extra space..but greedy solution's time complexity can be improved to O(n) by using count or radix sort ..Another point to note is that extra space used in greedy solution is O(1) because of count sort but in second case it is O(n).

- 007mayankpaneri October 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Build a graph with each nodes referring to a party. The node can points to n number of next nodes (parties). The path with more nodes is the answer for this problem.

Will post the code soon

- vsalaksh August 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

int main() {
int size,in_start = 0,in_end=0,count=0;
scanf("%d",&size);
int start[size],end[size],i=0;
for(i=0;i<size;++i){
scanf("%d%d",&start[i],&end[i]);
}
in_start = start[0];
in_end = end[0];
for(i=1;i<size;++i){
if(start[i] > in_end)
{
count++;
in_start = start[i];
in_end = end[i];
}
else if(start[i] == in_start && end[i] < in_end){
in_start = start[i];
in_end = end[i];
i=1;
count = 0;
}
}
printf("%d",count+1);
return 0;
}

- nathan August 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Average O(n log n) runtime complexity using O(n) memory though most of that is taken by the storage of the incoming values. The actual algorithm itself would take O(1) memory.

class Event implements Comparable{
    int start;
    int end;
    
    Event(int start, int end){
        this.start = start;
        this.end = end;
    }

    public int compare(Event e){
        return e.end - this.end;
    }
}

public static int getMaxParties(Event[] parties){
    Arrays.sort(parties);
    int count = 0;
    int currentEnd = -1;
    for(Event party : parties){
        if(party.start >= currentEnd){
            count++;
            currentEnd = party.end;
        }
    }
    return count;
}

- zortlord August 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

would it make any difference if I first sort the list based on starting time and then on end time if start time is same. then taking the first activity always.
something like this.
int count=0;
int end=arr[1].endt;
for(i=2;i<=n;i++)
{
if(arr[i].start>=end)
{
count++;
end=arr[i].endt;
}
}
return count+1;


will it give correct result? because i gave him this solution and he said that's wrong. I couldn't figured out the test case.
please help

- ritwik_pandey August 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@ritwik_pandey:

Here's the test case that would show you why sorting on the start fails:
1 24
2 3
3 4
4 5
etc

- zortlord August 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@zortlord
thank you so much. I understood where I was wrong.

- ritwik_pandey August 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The greedy approach by @ RecruitingForSandvineCanada and the DP approach of soneyoung are both correct, I think the DP approach based on time for this specific problem is a very clever answer.

But in general, if your intervals wouldn't be time intervals, you could also solve it using another DP approach in O(nlogn). This DP approach will be more useful when there is a benefit for choosing each interval.

Anyway, here's my code, which is a Dynamic Programming approach for this problem in general. (you could easily add benefits of each interval to the code)

//finding maximum number of non-overlaping intervals
//also could be solve Greedily

//Mehrdad AP

#include <iostream>
#include <algorithm>
#include <vector> 
#include <stdio.h>

using namespace std;


bool cmpBasedEnd(const pair<int,int> &x,const pair<int,int>& y)
{
	if (x.second!=y.second) 
		return x.second < y.second;
	else
		return x.first < y.first;
}

int maximumNonOverlapIntervals(vector< pair<int,int> > intervals)
{

	int N=intervals.size();

	//sorting array based on end of intervals
	sort(intervals.begin(),intervals.end(),cmpBasedEnd);
	
	vector<int> dp(N,0);

	for (int i=0;i<N;i++){
		
		int j= upper_bound(intervals.begin(),intervals.begin()+i,make_pair(100000,intervals[i].first),cmpBasedEnd) - intervals.begin();
		j--;//index of nearest interval(party) which could be the previous party before i-th party

		dp[i]=1;
		if (j>=0 && intervals[j].second<=intervals[i].first)
			dp[i]+=dp[j];

		if (i>0)
			dp[i] = max ( dp[i] , dp[i-1]);

	}

	return dp[N-1];
}

int main()
{
	int N;
	cin >> N;

	vector< pair<int,int> > V(N);
	for (int i=0;i<N;i++)
		cin >> V[i].first >> V[i].second ;

	cout << maximumNonOverlapIntervals(V) << endl;

	return 0;
}

- MehrdadAP August 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Party():
   def __init__(self, startTime, endTime):
      self.start=startTime
      self.end=endTime

def numParties(partyList):
   partyList=sorted(partyList, cmp=lambda x, y: x.end-y.end)
   print(map(str, partyList))
   numParties=0
   while len(partyList)>0:
     partyList=filter(lambda x : x.start>=partyList[0].end, partyList[1:])
     numParties+=1
   return numParties

- Anonymous August 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Put all slots in min priority queue (using start time): NlogN

- Remove min slot from priority queue in a variable 'tempSlot

Iterate through priority queue: removing the minimum slot at a time
- If the start time of removed slot is greater than end time of 'tempSlot' then increase the counter by one and save removed slot as tempSlot.. Otherwise put the combined slot of tempSlot and removed Slot as temp Slot.

Second step is also NlogN.

Code:

public static int freeSlots(Slot[] slots) {
    int freeSlots = 0;
    MinPQ<Slot> pq = new MinPQ<Slot>();
    for (Slot slot : slots) {
      pq.insert(slot);
    }
    Slot tempSlot = pq.delMin();
    while (!pq.isEmpty()) {
      Slot tempSlot2 = pq.delMin();
      if (tempSlot2.start > tempSlot.end) {
        freeSlots = freeSlots + 1;
        tempSlot = tempSlot2;
      } else {
        tempSlot = tempSlot.combine(tempSlot2);
      }
    }
    return freeSlots;
  }

  static class Slot implements Comparable<Slot> {
    double start;
    double end;

    Slot(double start, double end) {
      this.start = start;
      this.end = end;
    }

    Slot combine(Slot slot1) {
      return new Slot(Math.min(start, slot1.start), Math.max(end, slot1.end));
    }

    @Override
    public int compareTo(Slot slot1) {
      if (start < slot1.start) {
        return -1;
      }
      if (start > slot1.start) {
        return 1;
      }
      return 0;
    }

  }

  public static void main(String[] args) {
    Slot[] lines = { new Slot(1, 9), new Slot(11, 12), new Slot(1, 4), new Slot(2, 8),
        new Slot(5, 6), new Slot(3, 7), new Slot(9.5, 10) };
    System.out.println(freeSlots(lines));
  }

- Kumar August 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<utility>
#include<algorithm>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
pair<int,int> p[100001];
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int a,b;
cin>>a>>b;
p[i].first=a;
p[i].second=b;
}
sort(p,p+n);

int ans=0;
int max=p[0].second;
for(int i=0;i<n-1;i++)
{
if(p[i].second<p[i+1].first || max<p[i+1].first)
{
max=p[i+1].second;
ans++;
}
}
cout<<ans+1<<endl;
}
}

- vineet.sharma September 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<utility>
#include<algorithm>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		pair<int,int> p[100001];
		int n;
		cin>>n;
		for(int i=0;i<n;i++)
		{
			int a,b;
			cin>>a>>b;
			p[i].first=a;
			p[i].second=b;
		}
		sort(p,p+n);
		
		int ans=0;		
		int max=p[0].second;
		for(int i=0;i<n-1;i++)
		{
			if(p[i].second<p[i+1].first || max<p[i+1].first)
			{
				max=p[i+1].second;
				ans++;
			}
		}
		cout<<ans+1<<endl;
	}

}

- vineet.sharma September 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<utility>
#include<algorithm>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		pair<int,int> p[100001];
		int n;
		cin>>n;
		for(int i=0;i<n;i++)
		{
			int a,b;
			cin>>a>>b;
			p[i].first=a;
			p[i].second=b;
		}
		sort(p,p+n);
		
		int ans=0;		
		int max=p[0].second;
		for(int i=0;i<n-1;i++)
		{
			if(p[i].second<p[i+1].first || max<p[i+1].first)
			{
				max=p[i+1].second;
				ans++;
			}
		}
		cout<<ans+1<<endl;
	}
}

- vineet.sharma September 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<utility>
#include<algorithm>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		pair<int,int> p[100001];
		int n;
		cin>>n;
		for(int i=0;i<n;i++)
		{
			int a,b;
			cin>>a>>b;
			p[i].first=a;
			p[i].second=b;
		}
		sort(p,p+n);
		
		int ans=0;		
		int max=p[0].second;
		for(int i=0;i<n-1;i++)
		{
			if(p[i].second<p[i+1].first || max<p[i+1].first)
			{
				max=p[i+1].second;
				ans++;
			}
		}
		cout<<ans+1<<endl;
	}
}

- vineet.sharma September 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- vineet September 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sjdbkjsbd

- vineet September 26, 2015 | Flag Reply


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