Directi Interview Question
Developer Program Engineers Software Engineer / DevelopersCountry: India
Interview Type: Written Test
If you are refering to the one that sorts intervals, order O(n log n) is not better than O(n) like this one.
thanks for the code. But I didnt get why we need 2 arrays of 600 count, we can just work with one array of 360 count? For example create the array of size 360, mark the temp array 1 for arrival -1 for departure and 0 if there is both at the same min. track the max sum in the next scan.
1. Sort arrival and departure times in increasing order.
2. Starting from the first element in the sorted array add 1 when an arrival time is encountered, subtract 1 when a departure time is encountered. By this way find the max. number of people that are at the party at the same time which gives the min. number of glasses needed.
Time complexity of 2nd step is linear. 1st step depends on the sort algo chosen.
This is just a problem to find the max overlap of segments.
The first reply does not work because it assume everyone come/leave at int hour.
A quick solution is,
1. sort all coming time with leaving time
2. Scan the sorted list, if it is coming, +1, if it is leaving, -1. And record the max number.
That is the answer.
Time Complexity: O(2Nlog(2N))
Space Complexity: O(2N) + sorting space
in this question, it seems safe to assume the time is given by the minute, otherwise the intervals would be defined in a different way
This question is ambiguous because if guest 1 enters at the same time as guest 2 exits, will we still need 2 cups or just 1? So just to be safe, let's assume exits occur after entries, even if they occur at the same time.
My approach is to first multiply all the entry & exit times by 2. Furthermore, add 1 to all the exit times. That way we can enforce the "exit should occur after entry" condition above. It will also allow us to tell whether a given time refers to an entry or exit by looking at its oddity. So now we just need to put all the entry & exit times in an array, sort them, and keep track of the guests at each event.
// assuming the input array is {entry, exit, entry, exit...}
static int maxGuests(int[] arr) {
int len = arr.length;
int times[] = new int[len];
for(int i=0; i<len; i++) {
times[i] = 2*arr[i] + (i%2 == 0 ? 0 : 1);
}
Arrays.sort(times);
int maxGuests = 0;
for(int time : times) {
if(time%2 == 0) {
guests++;
maxGuests = Math.max(maxGuests, guests);
} else {
guests--;
}
}
return maxGuests;
}
struct ArrDep
{
int arrival, Dep;
bool bInParty( int time) { return ( time > arrival && time < Dep);
};
ArrDep guest[10];
guest[0] = { 1800, 1900};
guest[1] = { 2100, 2200};
...
guest[9] = { 2000, 2020};
int MaxGlass = 0;
for ( int i = 1800; i < 2359 ; i++)
{
int Glass = 0;
for ( int g = 0 ; g < 10 ; g++)
{ if ( guest[g].bInParty( I))
Glass++;
}
MaxGlass = MaxGlass < Glass ? Glass : MaxGlass;
}
I don't think it is the most efficient method but works.
Sort the guest list by out time
Maintain another list of sorted out times.
Maintain a variable min outtime. Initially it will be set to some Max Val.
i = 0;
j = 0;
minouttime = 10000;
array list [ ]; //sorted by outtime;
array Guests[]; //sorted by outtime;
while(i < no:of guests)
{
if (Guest[i].intime < minoutime)
{
count++;
minouttime = list[j];
}
else
{
j++;
}
}
There are only 6h = 360 minutes to consider. We can just mark the arrivals and departures in 2 arrays. Checking how many glasses are needed during arrivals and releasing glasses in departures.
The time complexity is O(N) for marking the arrivals and departures.
- Miguel Oliveira September 18, 2013