## Booking.com Interview Question

Software Engineer / Developers**Country:**Netherlands

**Interview Type:**Phone Interview

```
public static int getFullestDay(List<Schedule> schedules) {
if (schedules == null || schedules.size() == 0) {
return -1;
}
final HashMap<Integer, Integer> dayAndCapacity = new HashMap<>();
for (Pair<Integer, Integer> schedule : schedules) {
for (int day = schedule.check-in; day <= schedule.check-out; day ++) {
dayAndCapacity.put(day, dayAndCapacity.get(day) + 1);
}
}
int fullestDay = 0;
int highestCapacity = 0;
for (Entry<Integer, Integer> entry : dayAndCapacity.entrySet()) {
if (entry.getValue() > highestCapacity) {
highestCapacity = entry.getValue();
fullestDay = entry.getKey();
}
}
return highestDay;
}
public class Schedule {
public int check-in;
public int check-out;
}
```

Incrementing each day in a range (initialize it with 0 when first occurs) and then find the max by iterating:

```
import java.util.*;
public class MaxNumOfTravelers {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
Map<Integer, Integer> numberOfTravelers = new HashMap();
for(int n = 0; n < N; n++){
int start = scanner.nextInt();
int finish = scanner.nextInt();
for(int i = start; i <= finish; i++){
numberOfTravelers.putIfAbsent(i,0);
numberOfTravelers.put(i, numberOfTravelers.get(i)+1);
}
}
int maxTravelers = Integer.MIN_VALUE;
int maxDay = -1;
for(Map.Entry<Integer, Integer> entry : numberOfTravelers.entrySet()){
if(entry.getValue() > maxTravelers){
maxTravelers = entry.getValue();
maxDay = entry.getKey();
}
}
System.out.println("Max day - " + maxDay);
}
}
```

The problem stated does not look like a real one. In real world if one person leaves on day 5 and to persons arrive on day 5, there are only 2 guests in the hotel on that day. Because visitors usually leave before new visitors arrive.

According to this amendment my solution would be

```
import heapq
def high_day(guests):
schedule = []
for arrive, leave in guests:
heapq.heappush(schedule, (arrive, 1))
heapq.heappush(schedule, (leave, -1))
current_guests = max_day = max_day_guests = 0
while (schedule):
day, inout = heapq.heappop(schedule)
current_guests += inout
if current_guests > max_day_guests:
max_day = day
max_day_guests = current_guests
print max_day
if __name__ == "__main__":
guests = [
(1, 4),
(2, 5),
(10, 12),
(5, 9),
(5, 12),
]
high_day(guests)
```

Complexity is O(n * log n). This is the time it takes to build a heap from list of guests and also the time it takes to iterate over heap. And O(2 * n * log n) is equivalent to O(n * log n)

List<int> periods = new List<int>();

string endChar = "";

while (endChar != "===")

{

string s = Console.ReadLine();

if (s == "===")

{

endChar = "===";

break;

}

int[] r = Array.ConvertAll(s.Split(' '), int.Parse);

for (int i = r[0]; i <= r[1]; i ++)

{

periods.Add(i);

}

}

var most = (from i in periods group i by i into grp orderby grp.Count() descending select grp.Key).First();

Console.WriteLine(most);

Console.ReadLine();

{{ int[] A = { 1, 2, 10, 5, 5 }; // checkin array

int[] D = { 4, 5, 12, 9, 12 }; // checkout array

A = A.OrderBy(a => a).ToArray<int>();// {1,2,5,5,10}

D = D.OrderBy(d => d).ToArray<int>(); // {4,5,9,12,12}

int[] result = new int[Math.Max(A[A.Length - 1], D[D.Length - 1])];

for (int i = 0; i < A.Length; i++)

{

int min = A[i];

int max = D[i];

for (int j = min - 1; j < max; j++)

{

result[j] += 1;

}

}

int maxi = result.Max();

int day = result.ToList().IndexOf(maxi) + 1;

Console.WriteLine(day);

Console.ReadKey();

}}

The question is similar to minimum number of plateforms needed for the bus/rail station.

My solution for this very specific question is -

The time complexity will be O(nlogn).

- azambhrgn February 01, 2017Explanation is below -

C - checkin

D - checkout

count - number of people at same time in hotel

Day ---- C/D ------ count

1 C 1

2 C 2 // Increase count on checkin

4 D 1 // Decrease count on checkout

5 C 2

5 C 3 // maximum number of people in hotel -- return the day

9 D 2

12 D 1

12 D 0