## Booking.com Interview Question for Software Engineer / Developers

Country: Netherlands
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
6
of 8 vote

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).

Explanation 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

Comment hidden because of low score. Click to expand.
2

i++ should be moved after you assign day

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

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

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

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

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

``````input = [(1,4),(2,5),(10,12),(5,9),(5,12)]
days = {}
for i in input:
for k in range(i[0],i[1]+1):
if k in days:
days[k] += 1
else:
days[k] = 1

print(sorted(days.items(),key=lambda x: x[1],reverse=True)[0][0])``````

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

The question is not very clear because it depends upon the initial no. of people in hotel.

Comment hidden because of low score. Click to expand.
0

Correct

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

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)

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

List<int> periods = new List<int>();
string endChar = "";
while (endChar != "===")
{
if (s == "===")
{
endChar = "===";
break;
}
int[] r = Array.ConvertAll(s.Split(' '), int.Parse);
for (int i = r[0]; i <= r[1]; i ++)
{
}
}
var most = (from i in periods group i by i into grp orderby grp.Count() descending select grp.Key).First();
Console.WriteLine(most);

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

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

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

2 Solutions

1) Use a HashMap. Map the Day with Count. Finally, Days with max-count is the answer.

2) Append all days in Array-list. Sort it. Days with max repetition is the answer.

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

``````<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>``````

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

``````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);``````

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

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

}``````

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

``````/**
* @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) {
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;
}``````

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

``````/**
* @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) {
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;
}``````

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.

### 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.