Google Interview Question Software Engineers
Country: United States
@Daniel, I had O(nlog) solution and I was almost there.. Everytime I got something, he was pointing out another edge cases to the point that he himself was confused at times..
I haven't read you full solution but I can tell you one thing that during conversation, when I was stuck at one use case, he asked me burte force solution, which I gave instantaneous and it is O(n2) which he agreed to solve the problem but we both were trying to improvise.
So your above solution may not be challenging.
Another solution is you can insert all the start and end time individually in a list and have a flag for whether it is an end time or start. Then sort the array based on time ( or if it's start time if equal). Then loop through and if you encounter two start values , that implies they both overlap .
For ex:.
(3,6) (1,7 ) (9 ,10)
Insert into a single array :
3S 6E 1S 7E 9S 10E ( where S denotes start and E denotes end)
Sort in ascending order. If they are equal , have the S time one first
1S 3S 6E 7E 9S 10E
Now looking through, you encounter two start times (1 and 3) without any end implying they are collisions.
So ur ans would be (1 7) (3 6)
I have an idea.
(1) You can sort the list by starting time O(NlogN).
(2) Then do an interval merge (there is a leetcode question). That will be O(N) time.
(3) Then, you can scan through all appointments again and find which merged interval they belong to (put eggs into buckets).
So, that will be O(NLogN). It's just the sorting time. The third step is possibly abundant but we can always optimize this if the idea is correct.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Date;
public class TestOverlap {
public static void main(String[] args) {
ArrayList<Appointments> appArr = new ArrayList<>();
ArrayList<Appointments> collArr = new ArrayList<>();
Appointments a1 = new Appointments(new Date(), new Date());
appArr.add(a1);
Date startDate = new Date();
startDate.setHours(4);
Appointments a2 = new Appointments(startDate, new Date());
appArr.add(a2);
Collections.sort(appArr);
Date startRange = appArr.get(0).getStartTime();
Date endRange = appArr.get(0).getEndTime();
for (int i = 1; i < appArr.size(); i++) {
Date startDateI = appArr.get(i).getStartTime();
Date endDateI = appArr.get(i).getEndTime();
// Overlap condition
if (!startDateI.before(startRange) && !startDateI.after(endDateI)) {
if (collArr.size() == 0 ) {
collArr.add(appArr.get(i-1));
}
collArr.add(appArr.get(i));
endRange = endRange.before(appArr.get(i).getEndTime()) ? appArr.get(i).getEndTime() : endRange;
} else {
startRange = startDateI;
endRange = endDateI;
}
}
//Now the collArr will have have all the
}
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.Date;
public class TestOverlap {
public static void main(String[] args) {
ArrayList<Appointments> appArr = new ArrayList<>();
ArrayList<Appointments> collArr = new ArrayList<>();
Appointments a1 = new Appointments(new Date(), new Date());
appArr.add(a1);
Date startDate = new Date();
startDate.setHours(4);
Appointments a2 = new Appointments(startDate, new Date());
appArr.add(a2);
Collections.sort(appArr);
Date startRange = appArr.get(0).getStartTime();
Date endRange = appArr.get(0).getEndTime();
for (int i = 1; i < appArr.size(); i++) {
Date startDateI = appArr.get(i).getStartTime();
Date endDateI = appArr.get(i).getEndTime();
// Overlap condition
if (!startDateI.before(startRange) && !startDateI.after(endDateI)) {
if (collArr.size() == 0 ) {
collArr.add(appArr.get(i-1));
}
collArr.add(appArr.get(i));
endRange = endRange.before(appArr.get(i).getEndTime()) ? appArr.get(i).getEndTime() : endRange;
} else {
startRange = startDateI;
endRange = endDateI;
}
}
//Now the collArr will have have all the
}
}
We can use interval search tree.
For purposes of an interview, we can sort the ranges by start time and then find overlaps:
class Range {
public:
Range(int start, int end, int id)
{
s_ = start;
e_ = end;
id_ = id;
}
bool operator<(Range const &other) const
{
if (s_ == other.s_) {
return e_ < other.e_;
}
return s_ < other.s_;
}
bool overlaps(Range const &other) const
{
return (s_ >= other.s_ && s_ < other.e_) ||
(other.s_ >= s_ && other.s_ < e_);
}
int s_, e_, id_;
};
vector<Range> GetOverlapping(vector<Range> a)
{
sort(a.begin(), a.end());
vector<Range> out;
unordered_set<int> out_seen;
int max_start_seen = numeric_limits<int>::min();
for (int i = 0; i < a.size(); ++i) {
Range &r = a[i];
for (int j = i + 1; j < a.size() && r.e_ > max_start_seen; ++j) {
Range &r2 = a[j];
max_start_seen = r2.s_;
if (r.overlaps(r2)) {
if (out_seen.find(r.id_) != out_seen.end()) {
out.push_back(r);
out_seen.insert(r.id_);
}
if (out_seen.find(r2.id_) != out_seen.end()) {
out.push_back(r2);
out_seen.insert(r2.id_);
}
}
}
}
return out;
}
An obvious solution is sorting the elements and compare yielding O(nlogn) complexity. I tried to do it in O(n), but it takes O(m) space where m = end time - start time of all cals. The algo is simple - add all units of intervals to a map with it's id. Then walk down this map and collect all entries that have more than 1 cal.
class Calendar {
int id;
int start;
int end;
}
public List<Calendar> findOverlappingCalendars(List<Calendar> list) {
Map<Integer, List<Calendar>> hm = new HashMap<>();
Set<Calendar> result = new HashSet<>();
prepareMap(list, hm);
for (Map.Entry<Integer, List<Calendar>> entry: hm.entrySet) {
if (entry.getValue().size() > 1) {
// overlapping cals - add them to the set
result.addAll(entry.getValue());
}
}
return result.toList();
}
private void prepareMap(List<Calendar> list, Map<Integer, List<Calendar>> hm) {
for (Calendar c: list) {
for (int i = c.start; i <= c.end; i++) {
List<Calendar> cals = hm.contains(i) ? hm.get(i) : new ArrayList<>();
cals.add(c.id);
hm.put(i, cals);
}
}
}
This was my job for a year. There's only four types of overlap - A totally overlaps B, B totally overlaps A, A overlaps only start of B, A overlaps only end of B. Hence what you actually end up doing for most of the time this problem arises is simply coding it into SQL testing for any of those conditions. In code, given a format which procedurally generates appointments from a template, you can also just write a class which represents an interval of time and then subtract appointments from that interval, although that doesn't satisfy the exact constraint here of finding individual overlapping appointments.
Single line version: appointments.select{|x| (x.start < new.start && x.end > new.start) || (x.start < new.end && x.end > new.end) || (x.start < new.start && x.end > new.end) || (x.start > new.start && x.end < new.end)}
This should work. Basically go through each minute of the day and keep track of what appointments are currently going on. I've included some rough code for a function that finds all the collisions within a single day.
AppointmentCollisions FindCollisionsOverDay(List<Appointments> currentAppointments, List<Appointments> pendingAppointments, int day)
{
var collisions = new AppointmentCollisions();
var dailyAppointments = pendingAppointments.Where(x => x.StartTime.Day == day).OrderBy(x => x.StartDate);
for(int hour = 0; hour < HoursInDay; hour++)
{
for(int minute = 0; minute < MinutesInHour; minute++)
{
var ending = currentAppointments.Where(x => IsCurrentTime(x.EndTime));
currentAppointments.RemoveAll(ending);
while(dailyAppointments.Any() && IsCurrentTime(dailyAppointments.First().StartTime))
{
currentAppointments.Add(dailyAppointments.First();
dailyAppointments.RemoveAt(0);
}
if(currentAppointments.Count > 0)
{
collisions.AddCollision(currentAppointments, day, hour, minute);
}
}
}
return collisions;
}
Basic idea is to have two lists, once for the start time, one for the end time
- Anonymous February 22, 2018Second step is to sort those two lists O(n log n)
Third step is to iterate on the two lists, and increment the count of overlapping appointment when you iterate more than one from the start list compared to the end list