## Google Interview Question for Software Engineers

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

Basic idea is to have two lists, once for the start time, one for the end time

Second 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

Comment hidden because of low score. Click to expand.
1
of 1 vote

Interval tree problem

Comment hidden because of low score. Click to expand.
0
of 0 vote

Could you clarify the output of the function? Do you mean that the function should return a list of all the appointments that overlap with at least 1 other appointment? Thanks.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@hprem991

Can you simply sort the input by end time and find all overlapping intervals based on start time ? Solution would be nlogn time?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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());

Date startDate = new Date();
startDate.setHours(4);
Appointments a2 = new Appointments(startDate, new Date());

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 ) {
}

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

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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());

Date startDate = new Date();
startDate.setHours(4);
Appointments a2 = new Appointments(startDate, new Date());

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 ) {
}

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

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Interval search tree can solve this in nlogn time

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}
}

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<>();
hm.put(i, cals);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Test

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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))
{
dailyAppointments.RemoveAt(0);
}

if(currentAppointments.Count > 0)
{
}
}
}

return collisions;``````

}

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.

### 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.