Amazon Interview Question for SDE1s


Team: Devices
Country: United States




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

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:

[	0	, 	1	,	2	,	3	,	....	]
[   9-9.30	,  9.30-10 ,10-10.30 , 10.30-11,	....	]

- parikksit.b May 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- guilhebl May 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- yashraithathaCE May 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assumption :
Each conf room can be booked for atleast for one hour

Algo only:
1. create matrix on NX24 all zero element
2. mark with one , which is booked like matrix[5,17] =1 , means conf room 7 is booked for 5PM to 6 PM
3. Search metrix for desired time to book


Create a matrix

- PCS June 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just iterate through each conference and check for overlap of timings using the following logic:

for(Conference conference : availableConferenceRooms)
  if (myMeeting.start <= conference.end && myMeeting.end >= conference.start)
      ++cnt;

- arviman August 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Rohit Kumar February 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- divcode1986 May 17, 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