Amazon Interview Question
SDE-3sCountry: United States
Interview Type: In-Person
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;
}
}
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;
}
}
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);
})();
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);
}
}
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);
}
}
There are two separate infinite sources of data. Data is arriving
"simultaneously" into our system as two streams via two channels:
Channel 1 and Channel 2. The data could be of three types: R, G and B.
Each data element should have two properties: channelNumber and
uniqueID. These three types of Data are arriving in a random
sequence on the two channels. Write a program which creates pairs
of "same types" arriving on two channels in their "order of arrival".
Example:
If a sample sequence is as follows:
Channel 1: R1_1 R1_2 R1_3 B1_4 B1_8 G1_5
Channel 2: B2_6 B2_8 R2_9 G2_10 B2_7 R2_20
output is:
(R1_1, R2_9) (B1_4, B2_6) (B1_8, B2_8) (G1_5, G2_10) (R1_2, R2_20)
- NoOne October 06, 2016