Google Interview Question
Developer Program EngineersYou're right. If there is same time for in and out, then the order of updating MAX is important. E.g. If we see multiple IN's and OUT's at one same time, then 1) update MAX, 2) decrease counter by OUT's, 3) increase counter by IN's, 4) update MAX again.
This is also the approach I took. I define a class that contains the time as well as a boolean indicating entry/exit. I throw them into a heap (PriorityQueue in Java) and start popping them. For each event, I first set the current time to the time of this event. Then I increment or decrement the count depending on whether it's an entry or exit. I also keep track of the max guests (and the time at which that occurs).
The only confusing part is why in the example the answer is t=5, because at that time there's also 1 exit event. But you can handle that easily in the compareTo method used for sorting.
class Event implements Comparable<Event> {
int time;
boolean entry;
public Event(int _time, boolean _entry) {
time = _time;
entry = _entry;
}
public int compareTo(Event e) {
if(time < e.time)
return -1;
else if(time > e.time)
return 1;
else if(entry)
return -1;
else if (e.entry)
return 1;
else return 0;
}
}
class MostGuests {
static int timeMax(int[] arr) {
boolean entry = true;
PriorityQueue<Event> heap = new PriorityQueue<Event>();
for(int t : arr) {
heap.add(new Event(t, entry));
entry = !entry;
}
int maxGuests = 0;
int timeMax = 0;
int guests = 0;
int time = 0;
while(!heap.isEmpty()) {
Event e = heap.poll();
time = e.time;
if(e.entry) {
guests++;
if(guests > maxGuests) {
maxGuests = guests;
timeMax = time;
}
} else {
guests--;
}
}
return timeMax;
}
}
I wrote this naive solution. Comments are welcome.
1) Have an integer array of size 24 initialize to 0. lets call it t.
2) for each pair of start and end times, increment the t array corresponding indices from start to end
3) Finally check for the maximum in the t array and return corresponding index.
int getmax(const vector<pair<int,int> >& vp){
vector<int> t(24,0);
pair<int, int> p;
for(unsigned int i=0;i<vp.size();i++){
p = vp[i];
for(int j = p.first;j<=p.second;j++){
t[j]++;
}
}
int currmax = -1;
for(int i=0;i<24;i++){
if(t[i] > currmax){
currmax = i;
}
}
return currmax;
}
it was not 1-24 range of numbers. tht would be so easy.say the time limit is 10000..
there is some DP approach of O(n) tht dont require extra space but i was not able to recall tht at that time :(
i am looking for that one
On top of my mind, It seems problem of identifying max-clique in graph?
consider each person as node in graph, draw edge if two person overlaps in time inclusive of arrival and departure - O(n^2)
find max-clique, O(??) nodes in max clique will be present at party.
Regarding above solution if max(depart time) > 2^n, it will O(2^n) solution.
This problem is similar to problem BYTESE2 on spoj.Here is the Acc. O(NlogN) solution:
#include<iostream>
using namespace std ;
#define MAXN 105
int n,a[MAXN],b[MAXN] ;
main()
{
int i,j,runs ;
scanf("%d",&runs) ;
while(runs--)
{
scanf("%d",&n) ;
for(i=0;i<n;i++) scanf("%d%d",&a[i],&b[i]) ;
sort(a,a+n) ;
sort(b,b+n) ;
int cur = 0,p1 = 0,p2 = 0,ret = 0 ;
while(p1 < n && p2 < n)
{
if(a[p1] <= b[p2]) cur ++,p1 ++ ;
else cur --,p2 ++ ;
ret >?= cur ;
}
printf("%d\n",ret) ;
}
}
we can have a hashtable and enter the time as a key and value as num of persons. For each entry and exit time modify the value for each same time. return the key having maximum num of people as value.
I guess the problem would be more interesting if the interval of time where most people were present in the party was asked...
Though the solution would be not very involved, it'd using Interval trees; mapping each interval in the tree and increasing counts on the intervals already visited. At the end, traverse the entire tree to find the max count interval node.
This data structure could be tweaked to find solution to stated problem as well..
I first think of a naive approach.
Let's say there are m time slots and n guests. The input will be a list of entry in form of [x, y], where 0 <= x <= y <= m. The input is not sorted in any favor.
We create an array of size m. Initialize each element to be value 0. Then scan the input; for each input [x, y], perform the following:
for i in [x...m) array[x]++
for j in [y...m) array[y]--
Finally, output the index of the largest element in the array.
The code works below (Java):
// Assume we have the following data type
public class Entry {
public int enterTime;
public exitTime;
}
public int maxGuest(Entry[] entries, int m) {
int[] table = new int[m];
for (Entry e : entries) {
for (int i = e.enterTime; i < m; i++) table[i]++;
for (int i = e.exitTime; i < m; i++) table[i]--;
}
int max = 0;
for (int i = 1; i < m; i++) {
if (table[i] > table[max]) max = i;
}
return max;
}
O(n^2) time, O(m) space.
Okay. Improve the solution to O(n) time, O(m) space.
Just keep three variables: currentTime, currentNumOfGuest, and maxNumOfGuest.
For each currenTime in [0, m), we are essentially asking: do we have guests entering the room? do we have guests leaving the room?
Process the n inputs, and create two mappings. The first map maps time slot to number of guest entering the room. The second map maps time slot to number of guests leaving the room.
Then scan each time slot and compute num of guest based an previous num of guest, adjusted by num of entries and num of leaves.
The code works:
public class Entry {
public int enterTime;
public int exitTime;
}
public int maxGuest(Entry[] entries, int m) {
int[] map1 = new int[m];
int[] map2 = new int[m];
for (Entry e : entries) {
map1[e.enterTime]++;
map2[e.exitTime]++;
}
int maxGuest = 0, currentGuest = 0;
for (int i = 1; i < m; i++) {
currentGuest += map1[i];
currentGuest -= map2[i];
if (currentGuest > maxGuest)
maxGuest = currentGuest;
}
return maxGuest;
}
One approach using DP:
Maintain two arrays Entry and Exit.
Scan the input and populate these two arrays.
for example:
For input [1,4],[2,7],[3,5]
the values will be Entry: 1,1,1,0,0,0,0
Exit: 0,0,0,1,1,0,1
Num(i) - Number of guests present at time i;
Num(i) = Num(i-1) + Entry(i) - Exit(i-1);
i with Maximum (Num(i) will be the final answer.
Time: O(n) and space O(3n)(~ O(n))
There is the same approach as some of the previous comments, but hopefully more clear.
Assume we have m intervals (e.g. m=57). First, go through all the intervals and check that the arrive time is smaller or equal to the leave time (always check your input).
Create an array of length 2*m (114), and put in the array both the arriving and the leaving times. Keep a bit for each time to know if this is an arriving time, or a leaving time. Sort the array by the time. In case of a tie, ALWAYS put all the arriving times before all the leaving times (only if there is a tie).
This takes O(m*log(m)), but if you know that the times are integers , or that they are in a certain interval, you can do it in O(m) using radix sort, count sort, etc.
Go through this array of length 2*m. For each element which is marked as an ival, add 1 to a counter. For each person that leaves, subtract one. The maximal value of the counter gives you the maximal number of people at the party.
You can also keep a separate stack. When a person comes to the party, you push one element in the stack; when someone leaves, you pop it. The maximum height of the stack is your answer. (This also assumes the existence of the sorted array of length 2*m).
I have a O(n) solution. First we must see that for each interval [a,b], based on specification, the guest doesn't leave at time b, i.e. we count the that guest at time b, we make a modification that the guest leaves at b+1, therefore, the interval becomes [a,b+1].
Next, sort the intervals all together. For example, [1,4], [2,5], [9,12], [5,9], [5,12] becomes 1 2 5 5 5 6 9 10 13 13 (remember we add one to each leaving time). Then we iterate this series, for each number we encounter, if it is entry time, the guest number +1, if it is the leaving time, the guest time -1. We maintain the maximal number along the process. In this example, it is easy to see that the maximal guest number is 3 and it happens at two time spot 5, and, 9.
Here is another one.
1. sort the intervals non decreasingly on start time.
2. maintain a min heap of end times as we scan the sorted intervals sequentially. insert the end time of an interval t(start, end) into the min queue q as follows
while (start > q.min())
q.pop();
q.insert(end);
3. we keep a max size of the min queue during insertion, also the time t for the max size. return t after we are done insertion.
Runtime is O(nlogn). Sorting is O(nlogn), min queue removal and insertion takes O(logn) each. Total scan of intervals also takes O(nlogn). Space is O(n) if all intervals overlap.
Here is the logic for the algorithm. A set of intervals overlap if all the intervals start before the earliest end time of these intervals. The min queue maintains the end time of the current overlapping intervals. Since intervals are sorted on the start time, when we process the next interval t(start, end), if
(a) t starts before any overlapped interval ends, i.e, end < q.min(), then t overlaps with these intervals.
(b) t starts after some overlapped intervals end which means t doesn't overlap with these intervals. In this case, we keep remove q.min() until start <= q.min(), i.e., t overlaps with the intervals whose end time is still in q.
Since the example in the question seems to suggest that we should consider entry time before exit time, I just got an idea from reading Julian's answer that proposes incrementing the exit time. Let's first multiply all the entry/exit time by 2. Furthermore, add 1 to each exit time. So [1, 4] [2, 5] [9, 12] [5, 9] [5, 12] becomes [2, 9] [4, 11] [18, 25] [10, 19] [10, 25].
This has 2 benefits. First we respect the implicit rule that entry should be accounted for before exits. Secondly, we can now use even/odd to indicate whether it's an entry/exit event. So at t=10 we have the max guests, and we simply divide that by 2 to get t=5 as the final answer.
static int timeMax2(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;
int timeMax = 0;
int guests = 0;
for(int time : times) {
if(time%2 == 0) {
guests++;
if(guests > maxGuests) {
maxGuests = guests;
timeMax = time;
}
} else {
guests--;
}
}
return timeMax/2;
}
function getMaximumGuests(entryTimes) {
var hoursArray = new Array(25);
hoursArray.fill(0);
for (var i = 0; i < entryTimes.length; i++) {
var entryTime = entryTimes[i];
hoursArray[entryTime[0]]++;
hoursArray[entryTime[1] + 1]--;
}
var maxSum = 0;
var currentSum = 0;
for (var j = 1; j < hoursArray.length; j++) {
currentSum += hoursArray[j];
currentSum > maxSum ? maxSum = currentSum : "";
}
return maxSum;
}
var entryTimes = [[1, 4], [2, 5], [9, 12], [5, 9], [5, 12]];
console.log("Maximum entry time is ", getMaximumGuests(entryTimes));
function getMaximumGuests(entryTimes) {
var hoursArray = new Array(25);
hoursArray.fill(0);
for (var i = 0; i < entryTimes.length; i++) {
var entryTime = entryTimes[i];
hoursArray[entryTime[0]]++;
hoursArray[entryTime[1] + 1]--;
}
var maxSum = 0;
var currentSum = 0;
for (var j = 1; j < hoursArray.length; j++) {
currentSum += hoursArray[j];
currentSum > maxSum ? maxSum = currentSum : "";
}
return maxSum;
}
var entryTimes = [[1, 4], [2, 5], [9, 12], [5, 9], [5, 12]];
console.log("Maximum entry time is ", getMaximumGuests(entryTimes));
I can think of an nlog(n) solution. Thought is: for each guest, say his time span is [a, b], we reorgnize this data to: [a, in] and [b, out], which means at time a, a guest came in, and at time b, a guest left. Do this for all guests, we have a bunch of data like [x, in] and [y, out]. Sort all these data by the time part in ascending order. Then traverse from the earliest time, if the data is [in], have a counter++; if it is [out], have the counter--. After all, the max of counter is the answer.
- papaya September 11, 2010