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

• 0

Country: Netherlands
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
4
of 6 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.
0

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,i+1):
if k in days:
days[k] += 1
else:
days[k] = 1

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

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
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; i <= r; 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.

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.