US Interview Question for Computer Scientists

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
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();
  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]) {  
      ++current;  // Someone needs a room.
      max = Math.max(max, current);
    } else {
      --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.

- djmclaugh September 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

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

- jigs September 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

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

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

- k September 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
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.
Made in Merge Sort

//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();
		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()) {
				if(roomsTaken > k) return false;
			} else {
		return true;


- Anonymous September 03, 2014 | Flag Reply

Add a Comment

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.


is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More


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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More