Google technical phone screen

Anonymous User
2369
Jan 26, 2023
Jan 26, 2023

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.

NameStartEnd
Amanda10100
Alex3040
Frank50120
George7090
Henry100110
Susan120140
Thomas80110
Output the following table with every possible intervals and the people who are available during that interval
StartEndNames
----------------------------------------
1030Amanda
3040Alex, Amanda
4050Amanda
5070Amanda Frank
7080Amanda Frank George
8090Amanda Frank George Thomas
90100Amanda Frank Thomas
100110Frank Henry Thomas
110120Frank
120140Susan
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)