Had a 45 minute phone interview given the following question:
The input is a table with the name and the availability intervals for each person
e.g.
| Name | Start | End |
|---|---|---|
| Amanda | 10 | 100 |
| Alex | 30 | 40 |
| Frank | 50 | 120 |
| George | 70 | 90 |
| Henry | 100 | 110 |
| Susan | 120 | 140 |
| Thomas | 80 | 110 |
| Output the following table with every possible intervals and the people who are available during that interval | ||
| Start | End | Names |
| ------- | ----- | ---------------------------- |
| 10 | 30 | Amanda |
| 30 | 40 | Alex, Amanda |
| 40 | 50 | Amanda |
| 50 | 70 | Amanda Frank |
| 70 | 80 | Amanda Frank George |
| 80 | 90 | Amanda Frank George Thomas |
| 90 | 100 | Amanda Frank Thomas |
| 100 | 110 | Frank Henry Thomas |
| 110 | 120 | Frank |
| 120 | 140 | Susan |
| Only came up with a brute force approach: i.e. sorting the input start and end times in ascending order then for each consecutive interval, loop through the availabilities again to see which person are available during those intervals: | ||
| Any Ideas for optimization? |
import java.util.*;
public class Availabilities {
private static class Availability {
String name;
int start;
int end;
Availability(String name, int start, int end) {
this.name = name;
this.start = start;
this.end = end;
}
}
public static Map<List<Integer>, List<String>> findAvailabilities(List<Availability> availabilities) {
SortedSet<Integer> timeSet = new TreeSet<>();
for(Availability a : availabilities) {
timeSet.add(a.start);
timeSet.add(a.end);
}
List<Integer> times = new ArrayList<>(timeSet);
List<int[]> intervals = new ArrayList<>();
for(int i = 0; i < times.size() - 1; i++) {
intervals.add(new int[] {times.get(i), times.get(i + 1)});
}
Map<List<Integer>, List<String>> finalSchedule = new LinkedHashMap<>();
for(int[] interval : intervals) {
int start = interval[0], end = interval[1];
List<Integer> key = Arrays.asList(start, end);
for(Availability a : availabilities) {
if(start >= a.start && end <= a.end) {
finalSchedule.putIfAbsent(key, new ArrayList<>());
finalSchedule.get(key).add(a.name);
}
}
}
return finalSchedule;
}
public static void main(String[] args) {
List<Availability> availabilities = new ArrayList<>();
availabilities.add(new Availability("Amanda", 10, 100));
availabilities.add(new Availability("Alex", 30, 40));
availabilities.add(new Availability("Frank", 50, 120));
availabilities.add(new Availability("George", 70, 90));
availabilities.add(new Availability("Henry", 100, 110));
availabilities.add(new Availability("Susan", 120, 140));
availabilities.add(new Availability("Thomas", 80, 110));
Map<List<Integer>, List<String>> finalSchedule = findAvailabilities(availabilities);
for(Map.Entry<List<Integer>, List<String>> entry : finalSchedule.entrySet()) {
int start = entry.getKey().get(0);
int end = entry.getKey().get(1);
List<String> names = entry.getValue();
System.out.print("start " + start + " ");
System.out.print("end " + end + " ");
for(String name : names) {
System.out.print(name + " ");
}
System.out.println();
}
}
}
Comments (14)


