Directi Interview Question for Developer Program Engineers Software Engineer / Developers


Country: India
Interview Type: Written Test




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

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.

int MinGlasses(int* guest_arrival, int* guest_departure, int n) {
    int arrivals[600], departures[600], i;
    for (i = 0 ; i < 600; i++)
        arrivals[i] = departures[i] = 0;
    for (i = 0 ; i < n ; i++) { // format the time into the interval [0, 559]
        arrivals[guest_arrival[i] - 1800]++;//we could format into an interval
        departures[guest_departure[i] - 1800]++; // [0, 359] to save space
    }
    int res = 0, available_glasses = 0;
    for (i = 0 ; i <= 559; i++) {
        available_glasses += departures[i];
        if (arrivals[i] > available_glasses) {
            res += arrivals[i] - available_glasses;
            available_glasses = 0;
        } else
            available_glasses -= arrivals[i];
    }
    return res;
}

- Miguel Oliveira September 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Better solution (order less than 600) provided below

- Anuj Modi September 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you are refering to the one that sorts intervals, order O(n log n) is not better than O(n) like this one.

- Miguel Oliveira September 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- thebiker925 September 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes, this code was done like this to be easy to understand

- Miguel Oliveira September 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ohh ok, Thanks!

- thebiker925 September 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

- heuristican December 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

one thing is to be taken care, that when sorting is done , if departure time of one person is same as the arrival time of the other person, then departure time should come first, otherwise algo will not give minimum nmber og the glasses...

- jain July 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Jie September 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Miguel Oliveira September 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree.

- Anuj Modi September 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Greedy. Sort increasing order of arrival time , and break tie by increasing order of departure time. Now choose greedily.

- Anonymous December 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Sunny January 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

totally I have 559 hours, So I will take 280 glass wine of the wine glass which that is minimum according to 559, then I'll manage by cleaning.

Theoretically
1hr.=1wine glass
they asked minimum so divide by 2

- NELSON DESAI June 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous September 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous September 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Finally count will give the total no: of glasses required.

- Anonymous September 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Im not getting how ul have taken arrival and departure?? And also in second solution how you assumed only 10 guest when in question they have not mentioned the exact number..Please explain

- Anonymous September 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a=[(int(x),1) for x in raw_input().split(' ')]
b=[(int(x),-1) for x in raw_input().split(' ')]
a.extend(b)
a.sort()
c=0;
m=0
for i in a:
	c+=i[1]
	m=max(m,c);
print m

- harshit.knit November 04, 2014 | 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