## Amazon Interview Question for Software Engineer / Developers

Country: United States

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

``````How about bitmap approach ?

If each slot is 30 minute, so there are 48 slots each day. In this case, long type variable (64 bits) is enough to mark meeting slots in whole day. We can use two long variable for each day. First long variable mark the start slot of one meeting, and second long variable mark the duration slot of that meeting, but keep start slot excluded since it's already marked in first long variable.

Suppose meeting A is from slot n (n is 0-based index) and duration m slots, so

begin_marker      = begin_marker OR (1<<n)
duration_marker  = duration_marker  OR (( (1<<m-1)-1)<<n)

to get bitmap marker for meeting starting from slot n,

meeting_marker = (begin_marker  AND ~( 1<<(n+1) - 1))
meeting_marker = meeting_marker OR (1<<48)   // safeguard
meeting_marker = (meeting_marker XOR (meeting_marker - 1)) >> 1
meeting_marker = meeting_marker XOR (1 << n - 1)
meeting_marker = meeting_marker AND (begin_marker OR duration_marker)

to check if two meetings collide

(meeting_marker_a AND meeting_marker_b) != 0

By this way, only array long[7][2] is required for scheduling meeting within one week

* idea only *``````

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

This is very similar to keeping an array of intervals, except mine is an array of pointers.

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

A very simple idea would be to use an hashset, i.e., O(1) for both insertion and lookup. Time slotting need to be predefined, or it can be hard to nadle collision between a meeting starting at 9:01 vs a meeting starting at 9. So, if we decide resolution is half an hour, meeting 9-->10 would occupy two entries in hashSet (9_930 and 930_10).
Example in java below (well, not really much to do)

``````// slots are represented as string "tStart_tEnd"
private static void meetingSchedule(List<String> l ){
Set<String> calendar = new HashSet<String>();
for (String str: l){
if (calendar.contains(str))
else
}
}``````

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

Oh, I think this is a good idea. Keeping a set of occupied intervals would yield constant time look up, insert and remove. And since we know the size of intervals in advance, that significantly lower the chance having to rehash the set.

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

you have to make sure your key is unique. for example 12_1230 will be the same for AM and PM. Say you want to schedule a meeting from 12:30 to 1:30 PM. So the better keys are : 1230PM, 0100PM

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

True. Or might as well just make it 24-hour format. :)

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

it's not correct.
if we have booked a meeting at 9:00-12:00, and now we want to insert a meeting at 10:00-11:00.

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

How about a heap of start times. Gives O(lg n) insert and deletes. Not as fast as a hash-map though. But you can have meeting of any width.

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

This is the right approach to designing a scheduler as collision between meetings can be frequent. Secondly fixing a constant time for meetings as suggested in other examples is not practical. Retrieval of upcoming meeting is O(1) which will be really quick.

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

C++ implementation of Ankit's way

insert o(lgN)
lookup o(1)
delete o(lgN)

``````class Meeting
{
public:
int start;
int end;
Meeting(){start = end = 0;};
Meeting(int s, int e):start(s),end(e){};
bool operator < (const Meeting& o) const
{
return this->end < o.start;
}
bool operator == (const Meeting& o) const
{
return !(*this < o || o < *this) ;
}
};

class MeetingManager
{
public:
MeetingManager(){};
{
if(setMeeting.find(m) != setMeeting.end())
return false;
setMeeting.insert(m);
mapMeetings[MeetingToKey(m)] = m;
}

bool GetMeeting(int start, int end, Meeting& m)
{
string sKey = MeetingToKey(Meeting(start,end));
if(mapMeetings.find(sKey) == mapMeetings.end())
return false;
m = mapMeetings[sKey];
}

void DeleteMeeting(const Meeting& m)
{
string sKey = MeetingToKey(m);
if(mapMeetings.find(sKey) == mapMeetings.end())
return ;
mapMeetings.erase(sKey);
setMeeting.erase(m);
}

private:
set<Meeting> setMeeting;
unordered_map<string, Meeting> mapMeetings;

string MeetingToKey(const Meeting& m)
{
char buf[255];
sprintf_s(buf, "%d,%d", m.start, m.end);
string s(buf);
return s;
}
};``````

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

``````import java.io.ObjectInputStream.GetField;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class MeetingSchedular {

/**
* @param args
*Design a meeting scheduler. One way is to use an array to represent each interval,
*like every 15 mins. Although it provides O(1) look up, if interval is small,
*it seems like we are wasting a lot of space. Any alternative approach that can save space?
*If we keep a sorted array of meetings sorted by start time, look up will be O(logn),
*but inserting the new meeting in the middle of the array will require shifting elements, which is O(n).
*/

Set<Meeting> meetingShedularSet=new TreeSet<Meeting>();
Map<String,Meeting> map=new HashMap<String,Meeting>();

public static void main(String[] args) {
// TODO Auto-generated method stub
MeetingSchedular ms=new MeetingSchedular();

Meeting meeting=ms.getMeeting(900, 1000);
if(meeting!=null)
{
System.out.println("Meeting is sheduled at : "+meeting.getStartTime());
}
else
{
System.out.println("Meeting does not exist");
}

}

{
if(!meetingShedularSet.contains(meeting))
{
map.put(String.valueOf(meeting.getStartTime()+meeting.getEndTime()), meeting);
}
else
{
System.out.println("Meeting with start time :"+meeting.getStartTime()+" and end time :"+meeting.getEndTime()+" is conflicting with other meeting");
}
}

public Meeting getMeeting(int startTime,int endTime)
{
return map.get(String.valueOf(startTime+endTime));
}

}

class Meeting implements Comparable<Meeting>
{
private Integer startTime;
private Integer endTime;

Meeting(int startTime,int endTime)
{
this.startTime=startTime;
this.endTime=endTime;
}

public Integer getStartTime() {
return startTime;
}

public Integer getEndTime() {
return endTime;
}

@Override
public int compareTo(Meeting o) {

if(o.getStartTime().compareTo(this.endTime)>0)
{
return 1;
}
else if(o.getEndTime().compareTo(this.startTime)<0)
{
return -1;
}
else
{
return 0;
}
}

}``````

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

``````package com.omtest;

import java.util.Date;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Resource{
Meeting m;
Resource(Meeting m){
this.m = m;
}
}
class Attendee extends Resource{
public Attendee(Meeting m) {
super(m);
}
}
class Room extends Resource {
Room(Meeting m) {
super(m);
}
}

class Meeting {
int id;
String description;
Set<Resource> attendes;
Meeting(String description) {
this.description = description;
attendes= new HashSet<Resource>();
}
}

public class SchedulerAssistant {
private Map<Date, Map<Integer, Set<Resource>>> schedulerMap = new HashMap<>();

public Map<Integer, Set<Resource>> getOverlappedResources(Set<Resource> attendees, Date date, int startTime, int duration) {
Map<Integer,Set<Resource>> overlapMap = new HashMap<>();

Map<Integer,Set<Resource>> existingMap = schedulerMap.get(date);
for(int i = startTime; i< startTime + duration; i = i+30) {
overlapMap.put(i, new HashSet<Resource>());
Set<Resource> overlapResources = existingMap.get(i);
for(Resource resource : attendees) {
if(overlapResources.contains(resource)) {
}
}
}
return overlapMap;
}

public boolean scheduleMeeting(Set<Resource> attendees, Date date, int startTime, int duration, String meetingDescription) {
if(getOverlappedResources(attendees, date, startTime, duration).size() > 0) {
return false;
}
Meeting m = new Meeting(meetingDescription);
if(!schedulerMap.containsKey(date)) {
schedulerMap.put(date, new HashMap<Integer,Set<Resource>>());
}

for(int time =startTime; time < startTime+duration; time = time + 30) {
if(schedulerMap.get(date).containsKey(time)) {
} else {
schedulerMap.get(date).put(time, attendees);
}
}
return true;
}

public Meeting getMeeting(Date date, int time, Resource attendee) {
Set<Resource> resources = schedulerMap.get(date).get(time);
for(Resource res : resources) {
if(res.equals(attendee)) {
return res.m;
}
}
return null;
}

public static void main(String[] args) {
// TODO Auto-generated method stub

}

}``````

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.