## Coupon Dunia Interview Question for Software Engineer / Developers

• 1
of 1 vote

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.

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

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

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

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

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-b); });

var results   = [];
var prevStart = arr;
var prevEnd   = arr;

for(var i=1; i<arr.length; i++) {
var currStart = arr[i];
var currEnd   = arr[i];

// 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)));``````

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

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-b); });

var results   = [];
var prevStart = arr;
var prevEnd   = arr;

for(var i=1; i<arr.length; i++) {
var currStart = arr[i];
var currEnd   = arr[i];

// 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)));``````

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

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

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).

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

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;
in_end = end;
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;
}

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;
}``````

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

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.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.

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

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

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

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

#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;
}``````

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.end, partyList[1:])
numParties+=1
return numParties``````

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));
}``````

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;
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.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;
}
}

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;
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.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;
}``````

}

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;
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.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;
}
}``````

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;
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.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;
}
}``````

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

test

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

``sjdbkjsbd``

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.