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 question is not very clear because it depends upon the initial no. of people in hotel.
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();
}}
<script>
var input = [
{in : 1, out: 4},
{in : 2, out: 5},
{in : 10, out: 12},
{in : 5, out: 9},
{in : 5, out: 12}
];
const types = {
in: 1,
out: 0,
}
function maxGuests(arr) {
if(!arr || arr.length === 0) {
return 0;
}
var totalDays = [];
var data = {
max: 0,
day: undefined,
count: 0,
};
for(var i = 0; i < arr.length; i++){
var curr = arr[i];
totalDays.push({key: curr.in, type: types.in });
totalDays.push({key: curr.out, type: types.out });
}
totalDays.sort((a, b) => {
var temp = a.key - b.key;
if(temp === 0) {
return b.type - a.type;
}
return temp;
});
for (let i = 0; i < totalDays.length; i++) {
var temp = totalDays[i];
switch(temp.type) {
case 1: {
data.count++;
if(data.max < data.count) {
data.max = data.count;
data.day = temp.key;
}
break;
}
case 0: {
data.count--;
break;
}
default:
break;
}
}
return data.day;
}
var day = maxGuests(input);
console.log('max guests on day ', day);
</script>
var input = [
{in : 1, out: 4},
{in : 2, out: 5},
{in : 10, out: 12},
{in : 5, out: 9},
{in : 5, out: 12}
];
const types = {
in: 1,
out: 0,
}
function maxGuests(arr) {
if(!arr || arr.length === 0) {
return 0;
}
var totalDays = [];
var data = {
max: 0,
day: undefined,
count: 0,
};
for(var i = 0; i < arr.length; i++){
var curr = arr[i];
totalDays.push({key: curr.in, type: types.in });
totalDays.push({key: curr.out, type: types.out });
}
totalDays.sort((a, b) => {
var temp = a.key - b.key;
if(temp === 0) {
return b.type - a.type;
}
return temp;
});
for (let i = 0; i < totalDays.length; i++) {
var temp = totalDays[i];
switch(temp.type) {
case 1: {
data.count++;
if(data.max < data.count) {
data.max = data.count;
data.day = temp.key;
}
break;
}
case 0: {
data.count--;
break;
}
default:
break;
}
}
return data.day;
}
var day = maxGuests(input);
console.log('max guests on day ', day);
public class Solution {
public static void main(String[] args) {
List<Integer[]> input = provideData();
findBusiestDay(input);
}
private static void findBusiestDay(List<Integer[]> input) {
int min = Integer.MAX_VALUE;
int max = 0;
for (Integer[] range : input) {
int start = range[0];
int end = range[1];
if (start < min) {
min = start;
}
if (end > max) {
max = end;
}
}
int[] ranges = new int[max - min + 2];
for (Integer[] range : input) {
int startI = range[0] - min;
int endI = range[1] - min + 1;
ranges[startI]++;
ranges[endI]--;
}
System.out.println("ranges = " + Arrays.toString(ranges));
int maxDay = 0;
int sum = 0;
int index = -1;
for (int i = 0; i < ranges.length; i++) {
sum += ranges[i];
if (sum > maxDay) {
maxDay = sum;
index = i + min;
}
}
System.out.println("index = " + index);
}
private static List<Integer[]> provideData() {
return Arrays.asList(
new Integer[]{1, 4},
new Integer[]{2, 5},
new Integer[]{10, 12},
new Integer[]{5, 9},
new Integer[]{5, 12}
);
}
}
/**
* @author Omid Ghiasi Tarzi
*/
static int getMaxDay(List<List<Integer>> checks) {
List<Integer> ins = new ArrayList<>();
List<Integer> outs = new ArrayList<>();
for (List<Integer> check : checks) {
ins.add(check.get(0));
outs.add(check.get(1));
Collections.sort(ins);
Collections.sort(outs);
}
int i = 1;
int j = 0;
int count = ins.get(i);
int maxPeople = count;
int maxDay = 0;
while (i < ins.size()) {
if (ins.get(i) <= outs.get(j)) {
count++;
if (count > maxPeople) {
maxPeople = count;
maxDay = ins.get(i);
}
i++;
} else {
count--;
j++;
}
}
return maxDay;
}
/**
* @author Omid Ghiasi Tarzi
*/
static int getMaxDay(List<List<Integer>> checks) {
List<Integer> ins = new ArrayList<>();
List<Integer> outs = new ArrayList<>();
for (List<Integer> check : checks) {
ins.add(check.get(0));
outs.add(check.get(1));
Collections.sort(ins);
Collections.sort(outs);
}
int i = 1;
int j = 0;
int count = 1;
int maxPeople = count;
int maxDay = ins.get(0);
while (i < ins.size()) {
if (ins.get(i) <= outs.get(j)) {
count++;
if (count > maxPeople) {
maxPeople = count;
maxDay = ins.get(i);
}
i++;
} else {
count--;
j++;
}
}
return maxDay;
}
The question is similar to minimum number of plateforms needed for the bus/rail station.
My solution for this very specific question is -
A[] = {1,2,10,5,5} // checkin array D[] = {4,5,12,9,12} // checkout array sort(A) // {1,2,5,5,10} sort(D) // {4,5,9,12,12} count = 1 // first person checked in int i = 1; // to traverse A int j = 0; // to traverse D int max= 0; int day = A[i]; while(i < n && j < n) { if(A[i] <= D[j]) { count++; i++; if(count > max) { max = count ; day = A[i]; } } else { count--; j++; } } return day;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