Amazon Interview Question SDE1s
Country: India
The idea is to sort the given people based on when they entered/exited the conference room.
Since logically a valid data set will have at least one exit time after all the entry times are finished, we sort the entry and exit times. And simply increment/decrement a counter accordingly.
public class People {
public int startHour;
public int endHour;
}
int maxPeopleInConferenceRoom(People[] persons)
{
int[] starts = getSortedTimes(persons, true);
int[] exits = getSortedTimes(persons, false);
int maxPeople = 0, current = 0;
int startIndex = 0, endIndex = 0;
while(startIndex < persons.length) {
if(starts[startIndex] <= exits[endIndex]) {
current++;
if(current > maxPeople) {
maxPeople = current;
}
startIndex++;
} else {
current--;
endIndex++;
}
}
return maxPeople;
}
int[] getSortedTimes(People[] persons, boolean flag) {
int[] res = new int[persons.length];
for(int i = 0; i < persons.length; i++) {
res[i] = flag ? persons.startHour : persons.endHour;
}
Arrays.sort(res);
return res;
}
public List<String> startStop(){
Map<String,List<Integer>> employee = new HashMap<>();
employee.put("A", Arrays.asList(1,4));
employee.put("B", Arrays.asList(3,5));
employee.put("C", Arrays.asList(2,7));
employee.put("D", Arrays.asList(5,10));
int startIndex = 0;
int stopIndex = 1;
int currentTime =24;
int maxCount=0;
List<String> meetingRoom = new ArrayList<>();
for(int i=0; i<currentTime; i++){
for(Map.Entry<String, List<Integer>> emp : employee.entrySet()){
if(emp.getValue().get(startIndex)==i){
meetingRoom.add(emp.getKey());
} if(emp.getValue().get(stopIndex)==i){
meetingRoom.remove(emp.getKey());
}
}
if(maxCount < meetingRoom.size()){
maxCount = meetingRoom.size();
}
System.out.println("At time " + i + " employees " +meetingRoom.toString()+ " are present. Max members " +maxCount);
}
return meetingRoom;
}
Algorithm:
All we need is just the max number of people inside the room, not the actual identity of the people in the room
1) Sort the inputs - start and end taken together and also have a marking whether each of them is a start or an end.
2) If there is a time when are two people who are starting and ending at the same time, the end values should come ahead in the sorted list. Assuming that's what the interviewer wants (clarify this with the interviewer)
3) Use a counter and increment or decrement the counter based on whether its a start or an end time
4) Return the max value the counter can ever get to.
5) Do checks for trivial and special condition viz., empty conf room, indefinite meetings, meeting which run beyond the 24 hr clock and the like.
Will think of the code when I get back time. Please feel free to punch holes in my algo!
Dictionary<string, List<int>> members = new Dictionary<string, List<int>>();
members.Add("A", new List<int>() { 1, 6 });
members.Add("B", new List<int>() { 2, 7 });
members.Add("C", new List<int>() { 3, 5 });
members.Add("D", new List<int>() { 4, 10 });
members.Add("E", new List<int>() { 4, 10 });
int s = 0;
List<int> ll = new List<int>();
for( int i=1;i <=5;i++)
{
foreach (KeyValuePair<string, List<int>> mem in members)
{
if(mem.Value.First().Equals(i) && !mem.Value.Last().Equals(i) )
{
s = s + 1;
}
else if(mem.Value.Last().Equals(i) && !mem.Value.First().Equals(i) )
{
ll.Add(s);
s = s - 1;
}
else if (mem.Value.Last().Equals(i) && mem.Value.First().Equals(i))
{
ll.Add(s);
s = s + 0;
}
}
}
Dictionary<string, List<int>> members = new Dictionary<string, List<int>>();
members.Add("A", new List<int>() { 1, 6 });
members.Add("B", new List<int>() { 2, 7 });
members.Add("C", new List<int>() { 3, 5 });
members.Add("D", new List<int>() { 4, 10 });
members.Add("E", new List<int>() { 4, 10 });
int s = 0;
List<int> ll = new List<int>();
for( int i=1;i <=5;i++)
{
foreach (KeyValuePair<string, List<int>> mem in members)
{
if(mem.Value.First().Equals(i) && !mem.Value.Last().Equals(i) )
{
s = s + 1;
}
else if(mem.Value.Last().Equals(i) && !mem.Value.First().Equals(i) )
{
ll.Add(s);
s = s - 1;
}
else if (mem.Value.Last().Equals(i) && mem.Value.First().Equals(i))
{
ll.Add(s);
s = s + 0;
}
}
}
Here's a solution using a priority queue. Sort the input by start times, then iterate through them with the following idea: Whenever someone new joins the conference room, check who has left by now and remove them from the priority queue, then compare the size of the queue to the max value found until now.
public static int maxConcurrent(int[][] ranges) {
int res = 0;
Arrays.sort(ranges, (range1, range2) -> Integer.compare(range1[0],range2[0]));
PriorityQueue<Integer> currently = new PriorityQueue<>();
for ( int i = 0; i < ranges.length; ++i ) {
int t = ranges[i][0];
currently.offer(ranges[i][1]);
while ( !currently.isEmpty() && currently.peek() <= t ) {
currently.poll();
}
res = Math.max(res, currently.size());
}
return res;
}
@ChrisK is right, however, we can solve the problem by this too:
Start = [1,3,2,5]
End = [4,5,7, 10]
// there can be multiple in same time
starts = mset( Start )
ends = mset( End )
// sorted set of timings
timings = sset( Start )
timings += End
max = 0 ; cur = 0
for ( inx : timings ){
cur += (inx @ starts ? starts[inx] : 0)
cur -= (inx @ ends ? ends[inx] : 0)
max = cur > max ? cur : max
}
println(max)
perl code. Should work as it is. Just need to install List::Util cpan module if not already installed
1 use List::Util qw(max min);
2 my @in = qw (1 3 2 5);
3 my @out = qw (4 5 7 9);
4
5 my $min = min(@in, @out);
6 my $max = max(@in, @out);
7 my %in = map { $_ => 1 } @in;
8 my %out = map { $_ => -1 } @out;
9 my $maxPersons = 0;
10 my $localMax = 0;
11
12 foreach my $i ($min..$max) {
13 if (exists $in{$i}) {
14 $localMax += $in{$i};
15 }
16 if (exists $out{$i}) {
17 $localMax += $out{$i};
18 }
20 $maxPersons = max($localMax, $maxPersons);
22 }
23
24 print "max = $maxPersons\n";
25
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace test_aws
{
/*
* There is a conference room. N people are joining the conference. You have the start time and end time of each of them visiting it.
* You are asked to determine the maximum number of people that can be inside the room.
Example – Four people are visiting the conference
Person A B C D
Start (hour) 1 3 2 5
End (hour) 4 5 7 10
Answer will be – 3
- Raje July 17, 2017 in India | Report Duplicate | Flag
*/
public class conference_max_number
{
public conference_max_number() {
List<roomBooking> lbook = new List<roomBooking>()
{
new roomBooking() { bookingname="A",start=1,end=4},
new roomBooking() { bookingname="B",start=3,end=5},
new roomBooking() { bookingname="C",start=2,end=7},
new roomBooking() { bookingname="D",start=5,end=10}
};
int finalhour = 24;
int finalNumber = 1;
for (int i = 1; i <= finalhour; i++)
{
finalNumber=Math.Max(lbook.FindAll(rooms => rooms.start <= i && rooms.end >= i).Count, finalNumber);
}Console.WriteLine("Total Numbers will be {0}", finalNumber);
}
}
public class roomBooking
{
public string bookingname { get;set;}
public int start { get; set; }
public int end { get; set; }
}
}
int maximumPeopleInARoom(int[] entryTimeArray, int[] exitTimeArray) {
Arrays.sort(entryTimeArray);
Arrays.sort(exitTimeArray);
int maxCount = 0, count = 0;
int entryIndex = 0;
int exitIndex = 0;
while (entryIndex < entryTimeArray.length && exitIndex < exitTimeArray.length) {
if (entryTimeArray[entryIndex] < exitTimeArray[exitIndex]) {
count++;
entryIndex++;
} else if (entryTimeArray[entryIndex] > exitTimeArray[exitIndex]) {
count--;
exitIndex++;
} else {
exitIndex++;
entryIndex++;
}
if(maxCount < count) {
maxCount = count;
}
}
return maxCount;
}
public static void maxPeople() {
int A[] = { 1, 4 };
int B[] = { 3, 5 };
int C[] = { 2, 7 };
int D[] = { 5, 10 };
int Room[][] = { A, B, C, D };
int firstH =0, lastH = 0;
for (int Hrs[] : Room) {
System.out.printf("[%d - %d)\n", Hrs[0], Hrs[1]);
firstH = Math.min(firstH, Hrs[0]);
lastH = Math.max(lastH, Hrs[1]);
}
int nPeople = 0;
for (int i = firstH; i < lastH; ++i) {
int np = 0;
for (int Hrs[] : Room) {
if ( Hrs[0] <= i && Hrs[1] > i)
np++;
}
nPeople = Math.max(nPeople, np);
}
System.out.printf("max People: %d\n", nPeople);
}
Create list of enter and exit events, sort the list by time and apply one by one to the room.
The only uncertainty is if person should count when enter and exit happens at the same time (good manners would be to let person out first :). To simplify this the initiated enter and exit times are all different.
using System;
using System.Collections.Generic;
using System.Linq;
public class Program
{
public static void Main()
{
var reservations = InitDayReservations();
var eventList = new List<ReservationEvent>();
foreach(var r in reservations)
{
eventList.Add(r.Start);
eventList.Add(r.End);
};
var room = new Room();
foreach(var resEvent in eventList.OrderBy(e => e.Hour))
{
if(resEvent is StartEvent)
room.PersonEnters();
else
room.PersonExits();
}
Console.WriteLine("Max NumOf People in the Room: " + room.MaxNumOfPeople);
}
private static IEnumerable<Reservation> InitDayReservations()
{
return new List<Reservation>
{
new Reservation{Name = "A", Start = new StartEvent{Hour = 1}, End = new EndEvent {Hour = 4}},
new Reservation{Name = "B", Start = new StartEvent{Hour = 3}, End = new EndEvent {Hour = 6}},
new Reservation{Name = "C", Start = new StartEvent{Hour = 2}, End = new EndEvent {Hour = 7}},
new Reservation{Name = "D", Start = new StartEvent{Hour = 5}, End = new EndEvent {Hour = 10}}
};
}
private class Room
{
private int _numOfPeople;
private int _maxNumOfPeople;
public void PersonEnters()
{
_numOfPeople++;
if(_maxNumOfPeople < _numOfPeople)
_maxNumOfPeople = _numOfPeople;
}
public void PersonExits()
{
_numOfPeople--;
}
public int MaxNumOfPeople
{
get {return _maxNumOfPeople;}
}
}
private class Reservation
{
public string Name;
public StartEvent Start;
public EndEvent End;
}
private abstract class ReservationEvent
{
public int Hour;
}
private class StartEvent : ReservationEvent
{}
private class EndEvent : ReservationEvent
{}
}
This question's can be seperated into two categories:
a) discrete time:
resolution of time is coarse enough, one can count per "time"
e.g. people entering on a per houre, minute, second, millisecond,
b) continuous time:
e.g. start and end times are floating points
if you have continous time, a good approach is to seperate start
and end times and sort both arrays. Starting at both arrays at the
beginning and using the smallest value of both, incrementing the
number of people in the room if the next smallest value is on start
and decrementing if it's on end times array.
this question has coarse grained descret time, so, per hour just
collect how many are leaving (x) and how meany are entering (y) as
change = y - x and then go through the array and count...
in python 3, assuming time values 0 <= time_value < 24
- Chris July 18, 2017def max_people_in_room(intervals): changes = [0 for i in range(24)] for i in intervals: changes[i[0]] += 1 changes[i[1]] -= 1 people = 0 max_people = 0 for c in changes: people += c max_people = max(max_people, people) return max_people print(max_people_in_room([(1,4), (3,5), (2,7), (5,10)]))