Amazon Interview Question for SDE-3s


Country: United States
Interview Type: In-Person




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

// ZoomBA
//gitlab.com/non.est.sacra/zoomba/wikis/09-samples#book-meeting-room

// find meeting rooms 
def find_meetin_rooms( start_time, end_time ){
  possible_rooms = dict( rooms ) :: {
      room = $.o
      continue ( empty(room.schedules) ) { [ room.name , 0 ] } 
      continue( end_time <= room.schedules[0][0] ){  [ room.name , 1 ]  }
      // only when more than 1 at least 
      sorta(room.schedules) :: { $.o.0 < $.o.1 } 
      pos = index ( [1: #|room.schedules|] ) :: {  cur_inx = $.o 
          room.schedules[cur_inx-1].1 <= start_time && end_time <= room.schedules[cur_inx].0  
      }
      continue ( pos < 0 )
      [ room.name , pos ]
   } 
}

- NoOne October 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution:
1. convert hour String in int minutes. 1 day = 24 * 60 = 1440 min - Intervals from 0 to 1440. e.g - Interval from 1PM to 1:30PM would be
1 PM = 13 * 60 = 780, 1:30 PM = 13 * 60 + 30 = 8103
PM to 4PM = start : 15 * 60 - end : 16 * 60 = 900 - 960
this will allow minute precision.
calculate for each room, any available interval such that:
src.start <= target.start && src.end >= target.end

return available rooms found:

public class CountAvailableIntervals {

	public static void main(String[] args) {		
		// Room 1 - 10:30AM - 11AM, 4PM - 5 PM
		ConfRoom rc1 = new ConfRoom("room 1");
		Interval rc1i2 = new Interval(convertHourStringToMinutes("10:30 AM"), convertHourStringToMinutes("11:00 AM"));
		Interval rc1i3 = new Interval(convertHourStringToMinutes("4:00 PM"), convertHourStringToMinutes("5:00 PM"));
		rc1.addInterval(rc1i2);
		rc1.addInterval(rc1i3);
		
		// Room 2 - 10AM - 11AM, 2:30PM - 4PM
		ConfRoom rc2 = new ConfRoom("room 2");		
		Interval rc2i1 = new Interval(convertHourStringToMinutes("10:00 AM"), convertHourStringToMinutes("11:00 AM"));
		Interval rc2i2 = new Interval(convertHourStringToMinutes("2:30 PM"), convertHourStringToMinutes("4:00 PM"));
		rc2.addInterval(rc2i1);
		rc2.addInterval(rc2i2);

		// Room 3 - 9AM - 9:30AM, 5PM - 6PM
		ConfRoom rc3 = new ConfRoom("room 3");		
		Interval rc3i1 = new Interval(convertHourStringToMinutes("9:00 AM"), convertHourStringToMinutes("9:30 AM"));
		Interval rc3i2 = new Interval(convertHourStringToMinutes("5:00 PM"), convertHourStringToMinutes("6:00 PM"));
		rc3.addInterval(rc3i1);
		rc3.addInterval(rc3i2);
		
		List<ConfRoom> cfs = new ArrayList<>();
		cfs.add(rc1);
		cfs.add(rc2);
		cfs.add(rc3);
				
		// check for any available room for 9 AM - 9:30AM
		printAvailableRooms(getAvailableRooms(cfs, new Interval(convertHourStringToMinutes("9:00 AM"), convertHourStringToMinutes("9:30 AM"))));
		
		// check for any available room for 3PM - 4PM
		printAvailableRooms(getAvailableRooms(cfs, new Interval(convertHourStringToMinutes("3:00 PM"), convertHourStringToMinutes("4:00 PM"))));

		// check for any available room for 3PM - 4PM
		printAvailableRooms(getAvailableRooms(cfs, new Interval(convertHourStringToMinutes("4:00 PM"), convertHourStringToMinutes("5:00 PM"))));
	}
	
	private static int convertHourStringToMinutes(String hour) {		
		int idxOfMin = hour.indexOf(":");
		int idxOfSpace = hour.indexOf(" ");		
		int hours = Integer.parseInt(hour.substring(0, idxOfMin != -1 ? idxOfMin : idxOfSpace));
		int mins = idxOfMin != -1 ? Integer.parseInt(hour.substring(idxOfMin+1, idxOfSpace)) : 0;		
		String ampm = hour.substring(idxOfSpace + 1);		
		hours += ampm.equalsIgnoreCase("am") ? 0 : 12;			
		return hours * 60 + mins;
	}
	
	private static void printAvailableRooms(List<ConfRoom> cfs) {
		for (ConfRoom confRoom : cfs) {
			System.out.print(confRoom.name);
		}
		System.out.println();
	}

	/*
	 * Iterate over each available timeslot and check if interval fits
	 */
	public static boolean isRoomAvailable(ConfRoom cf, Interval interval) {		
		List<Interval> itvs = cf.intervals;
		for (Interval interval2 : itvs) {
			if (isIntervalAvailable(interval2, interval)) {
				return true;
			}
		}
				
		return false;
	}

	// does target fit in src
	public static boolean isIntervalAvailable(Interval src, Interval target) {
		return (src.start <= target.start && src.end >= target.end);		
	}

	public static List<ConfRoom> getAvailableRooms(List<ConfRoom> cf, Interval interval) {
		List<ConfRoom> result = new ArrayList<>();
		for (ConfRoom confRoom : cf) {
			if (isRoomAvailable(confRoom, interval)) {
				result.add(confRoom);
			}
		}
		return result;
	}	
}

class ConfRoom {
	String name;
	List<Interval> intervals;
	public ConfRoom(String name) {
		this.name = name;
		intervals = new ArrayList<>();
	}	
	public void addInterval(Interval it) {
		if (intervals != null) {
			intervals.add(it);	
		}	
	}	
}

class Interval {
	int start;
	int end;
	public Interval(int start, int end) {	
		this.start = start;
		this.end = end;
	}		
}

- guilhebl September 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This could not tell whether the ConfRoom is booked or not? if I were you, i would have added this to ConfRoom and Intervals.

public class ConfRoom{
		String name;
		String description;
		Set<Intervals> intervals;		
		ConfRoom(String name, String description, Set<Intervals> intervals){
			this.name = name;
			this.description = description;
			this.intervals = intervals;
		}
		boolean isRoomAvailable(int s, int e){
			for(Intervals i: intervals){
				if(i.isBooked == false && s >=i.start && e <= i.end)
					return true;
			}			
			return false;
		}
	}
	public class Intervals{
		int start;
		int end;
		boolean isBooked;
		Intervals(int start, int end){
			this.start = start;
			this.end = end;
			this.isBooked = false;
		}		
	}

- Weldino Eritrawi October 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The code below implements booking and querying for availability, release is not implemented but you can get the idea from booking... (It is in JavaScript and you can test it in coderpad.io)

var roomList = [];
function addRoom(roomName) {
  roomList.push({
    name: roomName,
    availability: [{time:9, type: "start"}, {time: 18, type: "end"}]
  });
}

function findAvailableStartIndex(room, startTime, endTime) {
  //it is searching sequentially for now, since it is sorted, we can implement binary search...
  var availability = room.availability, i, start, end, isAvailable;
  for (i = 0; i < availability.length && !isAvailable; i++) {
    start = availability[i];
    if(start.type === "start") {
      if(start.time <= startTime) {
        end = availability[i+1];
        isAvailable = end.time >= endTime;
      } else {
        break;
      }
    }
  }
  return isAvailable ? i -1 : -1;   
}

function isRoomAvailable(room, startTime, endTime) {
  return findAvailableStartIndex(room, startTime, endTime) !== -1;
}

function bookRoom(room, startTime, endTime) {
  var availability = room.availability;
  var startIndex = findAvailableStartIndex(room, startTime, endTime);
  var endIndex;
  if(availability[startIndex].time === startTime) {
    availability.splice(startIndex, 1);
    endIndex = startIndex;
  } else {
    availability.splice(startIndex + 1, 0, {time: startTime, type: "end"});
    endIndex = startIndex + 2;
  }
  if(availability[endIndex].time === endTime) {
    availability.splice(endIndex, 1);
  } else {
    availability.splice(endIndex, 0 , {time: endTime, type: "start"});
  }
}

function getAvailableRooms(startTime, endTime) {
  var i, room, availableRoomList = [];
  for(i = 0; i < roomList.length; i++) {
    room = roomList[i];
    if(isRoomAvailable(room, startTime, endTime)) {
      availableRoomList.push(room);
    }
  }
  return availableRoomList;
}

function printRoomNames(rooms) {
  var i, output = [];
  for(i =0; i< rooms.length; i++) {
    output.push(rooms[i].name);
  }
  console.log(output.join(", "));
}
(function test() {
  addRoom("Tehran");
  addRoom("Shiraz");
  addRoom("Isfahan");
  var availableRooms = getAvailableRooms(12, 13);
  printRoomNames(availableRooms);
  bookRoom(availableRooms[0], 12, 14);
  availableRooms = getAvailableRooms(12, 13);
  printRoomNames(availableRooms);
})();

- Takhti October 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Meeting rooms are stored in an arrayList and each node will have 1440 integer arrays which will be filled when someone tries to book a meeting room.

import java.util.ArrayList;
import java.util.Scanner;

public class MeetingRoom {

	int roomId;
	int[] meetingSlotsinMinutes = new int[1440];

	public MeetingRoom(int room) {

		roomId = room;

	}

	private int[] bookMeetingRoom(int startTime, int endTime,
			MeetingRoom bookingMeetingRoom) {

		boolean slotAvailable = true;

		// Check slots
		for (int i = startTime; i <= endTime; i++) {

			if (bookingMeetingRoom.meetingSlotsinMinutes[i] == 1) {
				slotAvailable = false;
			}
		}

		// Fill the slots
		if (slotAvailable) {
			System.out.println("\nSlot available for booking and booked\n");
			for (int i = startTime; i <= endTime; i++) {
				bookingMeetingRoom.meetingSlotsinMinutes[i] = 1;
			}
		} else

			System.out.println("\nSlot booked by someone\n");

		
		//Return filled slots and update MeetingRoom in Arraylist
		return bookingMeetingRoom.meetingSlotsinMinutes;
		
	}

	public static void main(String args[]) {

		ArrayList<MeetingRoom> rooms = new ArrayList<MeetingRoom>();
		
		
		//Loop for demonstration
		int check=0;
		while(check !=5){
		
		
		MeetingRoom bookingMeetingRoom = null;
		int startTime, endTime, bookingRoom;

		@SuppressWarnings("resource")
		Scanner inputScan = new Scanner(System.in);

		System.out.println("Enter meeting room number :");
		bookingRoom = inputScan.nextInt();
		System.out.println("Enter start time of meeting : ");
		startTime = convertToMinutes(inputScan.next());
		System.out.println("Enter end time of meeting room :");
		endTime = convertToMinutes(inputScan.next());

		for (MeetingRoom currrentRoom : rooms) {
			if (currrentRoom.roomId == bookingRoom) {
				bookingMeetingRoom = currrentRoom;
			}
		}
		if (bookingMeetingRoom == null) {
			bookingMeetingRoom = new MeetingRoom(bookingRoom);
			rooms.add(bookingMeetingRoom);

		}

		// This function will check and schedule meeting
		bookingMeetingRoom.meetingSlotsinMinutes = bookingMeetingRoom
				.bookMeetingRoom(startTime, endTime, bookingMeetingRoom);

		// Reset current meeting room to null
		bookingMeetingRoom = null;
		
		check++;
		}
		
		

	}

	public static int convertToMinutes(String input) {

		String[] splits = input.split(":");
		int hour = Integer.parseInt(splits[0]);
		int minute = Integer.parseInt(splits[1]);

		if (splits[2].toLowerCase().equals("pm") && hour <12)
			hour += 12;

		// Converting all to minutes
		return ((hour * 60) + minute);

	}

}

- satishkv.pesit October 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int x=0;

- Anonymous October 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int x =0;

- Anonymous October 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Booking a meeting creates room reservations for each time slot (one per minute). These are kept in a map. Method is also used to check before booking the meeting and returning success or failure on the booking attempt.

import java.util.*;
import java.util.stream.Stream;

import static java.lang.System.out;

public class MeetingRoomBooker {
    public static void main(String[] args) {
        MeetingRoomBooker booker = new MeetingRoomBooker();

        booker.bookMeeting("Client!", MeetingRoom.EXEC_BOARDROOM, 930, 60);
        booker.bookMeeting("Scrum!", MeetingRoom.ENG_3, 945, 15);
        booker.bookMeeting("Planning", MeetingRoom.ENG_2, 1000, 60);
        booker.bookMeeting("Demos!", MeetingRoom.ENG_1, 1100, 60);


        out.println("\nFrom 9:30 to 11:00 (ENG 1)-- ");
        booker.findAvailableRooms(930, 1100).forEach(out::println);

        out.println("\nFrom 10:00 to 11:00 (ENG 1 and 3) -- ");
        booker.findAvailableRooms(1000, 1100).forEach(out::println);

        out.println("\nFrom 10:30 to 11:00 (ENG 1 and 3, EXEC) -- ");
        booker.findAvailableRooms(1030, 1100).forEach(out::println);

        out.println("\nFrom 11:00 to 12:00 (ENG 2 and 3, EXEC)-- ");
        booker.findAvailableRooms(1100, 1200).forEach(out::println);

        out.println("\nBooking ENG 2 at 11:15...");
        out.println(booker.bookMeeting("1:1", MeetingRoom.ENG_2, 1115, 30).bookingSucceeded());

        out.println("\nFrom 11:00 to 12:00 (Again) (ENG 3, EXEC) -- ");
        booker.findAvailableRooms(1100, 1200).forEach(out::println);

        out.println("\nTry to book ENG 2 again at 11:15...");
        out.println(booker.bookMeeting("Another 1:1", MeetingRoom.ENG_2, 1115, 30).bookingSucceeded());
    }

    private class Meeting {
        private String description;
        private int startTime;
        private int durationInMinutes;
        private boolean bookingSucceeded;

        public Meeting(String description, int startTime, int durationInMinutes) {
            this.description = description;
            this.startTime = startTime;
            this.durationInMinutes = durationInMinutes;
        }

        public void setBooked() {
            bookingSucceeded = true;
        }

        public boolean bookingSucceeded() {
            return bookingSucceeded;
        }
    }

    private enum MeetingRoom {
        EXEC_BOARDROOM,
        ENG_1,
        ENG_2,
        ENG_3
    }

    private class Reservation {
        private final Meeting meeting;
        private final MeetingRoom room;

        public MeetingRoom getRoom() {
            return room;
        }

        public Reservation(Meeting meeting, MeetingRoom room) {
            this.meeting = meeting;
            this.room = room;
        }
    }

    private final Map<Integer, Set<Reservation>> reservations = new HashMap<>();

    private void addReservation(final Integer timeslot, final Reservation reservation) {
        if (!reservations.containsKey(timeslot)) {
            reservations.put(timeslot, new HashSet<>(Arrays.asList(new Reservation[]{reservation})));
        }
        if (!reservations.get(timeslot).contains(reservation)) {
            reservations.get(timeslot).add(reservation);
        }
    }

    private Stream<MeetingRoom> findAvailableRooms(final int startTime, final int endTime) {
        final Set<MeetingRoom> unavailable = new HashSet<>();

        for (int i = startTime; i < endTime; i++) {
            if (i % 100 < 60) {
                if (reservations.containsKey(i)) {
                    for (Reservation reservation : reservations.get(i)) {
                        if (!unavailable.contains(reservation.getRoom())) {
                            unavailable.add(reservation.getRoom());
                        }
                    }
                }
            }
        }
        return Stream.of(MeetingRoom.values()).filter(r -> !unavailable.contains(r));
    }

    private Meeting bookMeeting(final String description, final MeetingRoom room,
                                final int startTime, final int durationInMinutes) {
        final Meeting meeting = new Meeting(description, startTime, durationInMinutes);
        final int endTime = findEndTime(startTime, durationInMinutes);

        if (findAvailableRooms(startTime, findEndTime(startTime, durationInMinutes))
                .noneMatch(r -> r.equals(room))) {
            return meeting;
        }
        for (int i = startTime; i < endTime; i++) {
            if (i % 100 < 60) {
                addReservation(i, new Reservation(meeting, room));
            }
        }
        meeting.setBooked();
        return meeting;
    }

    private int findEndTime(final int startTime, final int durationInMinutes) {
        final int startHour = (startTime / 100) * 100;
        final int startOffset = startTime % 100;
        if (startOffset + durationInMinutes < 60) {
            return startTime + durationInMinutes;
        }
        return startHour + ((startOffset + durationInMinutes) / 60 * 100)
                         + ((startOffset + durationInMinutes) % 60);
    }
}

- Tokai October 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- PM October 03, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

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