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 *

- KewpieWang February 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Guy February 19, 2014 | Flag
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))
				System.out.println("Meeting already scheduled"); 
			else
				calendar.add(str); 			
		}
	}

- svarvel February 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Guy February 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- maxpayne February 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Guy February 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- weihuaw February 20, 2014 | Flag
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.

- Anonymous February 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Meena November 13, 2014 | Flag
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(){};
	bool AddMeeting(Meeting& m)
	{
		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;
	}
};

- weihuaw February 20, 2014 | Flag Reply
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();
		ms.addMeeting(new Meeting(900, 1000));
		ms.addMeeting(new Meeting(1030, 1100));
		ms.addMeeting(new Meeting(1101, 1130));
		ms.addMeeting(new Meeting(1131, 1245));
		ms.addMeeting(new Meeting(1105, 1145));
		ms.addMeeting(new Meeting(1205, 1345));
		
		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");
		}
		
		

	}
	
	public void addMeeting(Meeting meeting)
	{
		if(!meetingShedularSet.contains(meeting))
		{
		meetingShedularSet.add(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;
		}
	}
	
	
	
	
}

- Ankit Garg February 20, 2014 | Flag Reply
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)) {
					overlapMap.get(i).add(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);
		m.attendes.addAll(attendees);
		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)) {
				schedulerMap.get(date).get(startTime).addAll(attendees);
			} 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

	}

}

Please give me your comments so that I could correct the issues in this code.

- Lakshman April 03, 2018 | 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