Amazon Interview Question
SDE1sTeam: Devices
Country: United States
Enables for minute precision interval booking, a user can book a meeting in any length given in minutes.
solution:
1.transform day length in int minutes. 1 day = 24 * 60 = 1440min-Intervals from 0 to 1440
calculate for each room, any available interval such that:
src.start <= target.start && src.end >= target.end
public class CountAvailableIntervals {
public static void main(String[] args) {
// Room 1 - 8AM - 9AM, 10:30AM - 11AM, 4PM - 5 PM
ConfRoom rc1 = new ConfRoom();
Interval rc1i1 = new Interval(480, 540);
Interval rc1i2 = new Interval(630, 660);
Interval rc1i3 = new Interval(960, 1020);
rc1.addInterval(rc1i1);
rc1.addInterval(rc1i2);
rc1.addInterval(rc1i3);
// Room 2 - 10AM - 12PM, 2:30PM - 4PM
ConfRoom rc2 = new ConfRoom();
Interval rc2i1 = new Interval(600, 720);
Interval rc2i2 = new Interval(870, 960);
rc2.addInterval(rc2i1);
rc2.addInterval(rc2i2);
// Room 3 - 7AM - 8:30AM, 5PM - 6PM
ConfRoom rc3 = new ConfRoom();
Interval rc3i1 = new Interval(420, 510);
Interval rc3i2 = new Interval(1020, 1080);
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 8 AM - 9AM
System.out.println(isAvailableRooms(cfs, new Interval(480, 540)));
// check for any available room for 3:30 PM - 5PM
System.out.println(isAvailableRooms(cfs, new Interval(930, 1020)));
// count available rooms from 10:30AM - 11AM
System.out.println(countAvailableRooms(cfs, new Interval(630, 660)));
}
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 boolean isAvailableRooms(List<ConfRoom> cf, Interval interval) {
for (ConfRoom confRoom : cf) {
if (isRoomAvailable(confRoom, interval)) {
return true;
}
}
return false;
}
public static int countAvailableRooms(List<ConfRoom> cf, Interval interval) {
int roomsAvailable = 0;
for (ConfRoom confRoom : cf) {
if (isRoomAvailable(confRoom, interval)) {
roomsAvailable++;
}
}
return roomsAvailable;
}
}
class ConfRoom {
List<Interval> intervals;
public ConfRoom() {
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;
}
}
// output:
// true
// false
// 2
class Meeting{
int start; // 0 to 23
int end; // 0 to 23
}
Map<String,List<Meeting>> roomMeetingsMapper=new HashMap<String,List<Meeting>> ();
int findAvailableRooms(Meeting newMeeting){
int count=0;
boolean flag;
for(Key key:roomMeetingsMapper){
flag=true;
List<Meeting> meetings=roomMeetingsMapper.get(key);
for(Meeting meet:meetings){
if(newMeeting.start >= meet.start && newMeeting.start <= meet.end ){
flag=false;
}
}
if(flag){
count++;
}
}
return count;
}
It should be implemented as Parking space problem.
Decide minimum time span, such as 15 mins or 30 mins.
and add all the time span for the given day in hashmap. with some Id formed by meeting room and start+end time
Further it can be serialized to save and can be prototyped for a new day. where it doesnt found map in db for future dadays.
Just when ever some one books room cheeck in avialable rooms HashMap and shift it to Reserved...
Its just an idea.
/* Assumptions: Conference room data is provided as a list of sorted disjoint interval objects. Meeting time of interest (m) is an interval object.
Brute-force: Iterate through each list of interval objects representing conference rooms. For each list, do a linear search for the presence of an interval that overalps with (m).
Time complexity: O(nm) where n is the number of conference rooms and m is the size of the longest list of disjoint intervals.
Better appraoach: Same as brute force but instead of linear search use binary search. Time complexity: O(nlogm)**/
public class Interval
{
int start;
int end;
}
public int countOpenings(ArrayList<ArrayList<Interval>> ls, Interval m)
{
if(ls==null||ls.isEmpty()||m==null)
{
return 0;
}
int c=0;
for(int i=0;i<ls.size();i++)
{
if(isAvailable(ls.get(i),m))
{
c++;
}
}
return c;
}
private boolean isAvailable(ArrayList<Interval> ls, Interval n)
{
int start=0;
int end=ls.size()-1;
while(start<=end)
{
int mid=(start+end)/2;
if(isOverlap(ls.get(mid),n))
{
return false;
}
if(ls.get(mid).end<=n.start)
{
start=mid+1;
}else
{
end=mid-1;
}
}
return true;
}
private boolean isOverlap(Interval m, Interval n)
{
return(m.start>=n.start && m.start<n.end)||(n.start>=m.start && n.start<m.end);
}
They've asked for an algorithm, so I'm assuming coding isn't required. I'll mention the logic.
Assumptions:
1. Meeting times start from 9 AM through 5 PM = 8 hours.
2. Minimum meeting time = 30 minutes.
3. From above 2, every conference room will have 16 time slots. (You can lower the intervals to 15 or 10 as you like, figure out the total slots accordingly).
4. So if every conference room were to be an array of 16 elements, then each element represents 30 minutes.
Let us say we have 100 conference rooms, then if we would like to book a meeting for time slot 10.00 AM to 10.30 AM, then we only look for the 2nd element of the array (array starts from 0-15) for all conference rooms or until we find an empty slot.
This solution is O(n) in time.
Detailed understanding of how the arrays are structured as per time slots:
- parikksit.b May 18, 2016