## 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 ]
}
}``````

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

// 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"));

// 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"));

List<ConfRoom> cfs = new ArrayList<>();

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

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

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

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

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 = [];
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() {
var availableRooms = getAvailableRooms(12, 13);
printRoomNames(availableRooms);
bookRoom(availableRooms[0], 12, 14);
availableRooms = getAvailableRooms(12, 13);
printRoomNames(availableRooms);
})();``````

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

}

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

}

}``````

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

``int x=0;``

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

``int x =0;``

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

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

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

test

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.