## US Interview Question for Computer Scientists

Country: United States
Interview Type: Written Test

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

I'm assuming that there is a Booking class with an interface like

``````public class Booking {
//Returns how many days in the season the guest arrives.
public int getArrivalDate();
//Returns how many days in the season the guest leaves.
public int getDepartureDate();
}``````

I'm also assuming that the departure date must be later than the arrival date.

Here is an O(nlog(n)) solution:

``````boolean doIHaveEnoughRooms(int numberOfRooms, Collection<Booking> bookings) {
return numberOfRooms >= numberOfRoomsNeeded(bookings);
}

int numberOfRoomsNeeded(Collection<Booking> bookings) {
int n = bookings.size();
int[] arrivals = new int[n];
int[] departures = new int[n];
int i = 0;
for (int d : bookings) {
arrivals[i] = d.getArrivalDate();
departures[i] = d.getDepartureDate();
++i;
}
Arrays.sort(arrivals);  // Built in O(nlog(n)) sorting.
Arrays.sort(departures); // Built in O(nlog(n)) sorting.
int aIndex = 0;
int dIndex = 0;
int current = 0;  // Current number of guests.
int max = 0;  // Max number of guests
while (aIndex < n) {
// You need <= instead of < if you can't use a room the same day the guest leaves.
if (arrivals[aIndex] < departures[dIndex]) {
++aIndex;
++current;  // Someone needs a room.
max = Math.max(max, current);
} else {
++dIndex;
--current;  // Someone vacates a room.
}
}
return max;
}``````

Note that the bottleneck is the sorting, everything else is simply O(n). So if you use a linear sorting algorithm instead (counting sort seems like a reasonable choice, especially if the season doesn't have too many days and you expect many people to arrive/leave on the same day), you get an O(n) algorithm.

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

Finding out maximum number of overlapped intervals.
if it is > no. of rooms:
then return no
else return yes

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

for( days in a year)
{
int a=0;
for(bookings)
{
if(day>=arrival day && day<=departure day)
a++
if( a>n)
return false
}
}
return true

it's 365(or 366)*n solution. I think it's count as O(n) solution.

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

A hotel manager has to process n advance bookings of rooms for the next season. His hotel has k identifical rooms. Bookings contain
an arrival date and a departure date. He wants fo find out whether there are enough rooms in the hotel to satify the demand.
Design an algorithm that solves this problem in time O(n logn) . Hint:Consider the set off all arrivals and departures .
Sort the set and process it in sorted order.

``````//assume dates can be represented by an int
boolean enoughRooms(int capacity k; List<Bookings> bookings) {
int[] arrivals = new int[bookings.size()];
int[] departures = new int[bookings.size()];

int i = 0;
for(Booking booking: bookings) {
arrivals[i] = booking.getArrivalTime();
departures[i] = booking.getDepartureTime();
i++;
}
PriorityQueue arrivalQueue = minHeapify(arrivals); //O(n) operation
PriorityQueue departureQueue = minHeapify(departures);

int roomsTaken = 0;
//whole loops is  O(nlogn)
while(!arrivalQueue.isEmpty()) {
if(arrivalQueue.peek() <= departureQueue.peek()) {
arrivalQueue.pop();
roomsTaken++;
if(roomsTaken > k) return false;
} else {
departureQueue.pop();
roomsTaken--;
}
}
return true;

}``````

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.