Google Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Up for this solution. I guess then the interviewer will ask you to code a variant of binary search
Here is the binary search to find the index i such that v[i] is the first that is greater than the value
int Pearl::BS_range(vector<int> t, int x){
int l=0,r=t.size()-1;
if(x<=t[l]) return l;
if(x>=t[r]) return r;
while(l<=r){
int mid=l+(r-l)/2;
if(t[mid]<=x&&x<=t[mid+1]) return mid+1;
else if(t[mid+1]<x) l=mid+1;
else r=mid;
}
return -1;
}
Test Case: 35 41 42 49 56 60 70 81 90 95
value=50
Output: 4
Then we can happily sort the appointments by start time. For each appointment, we BS_range(start_times,finish_time), then we output all the appointment after k.
I'm not sure what the question is asking, but your answer is not correct either. All the apps between the current app and last conflicting app do have intersection with the current app, BUT there are other apps conflicting with current app which you are not counting. These are the apps with start times less than the current app's start time and end time larger than the current app's start time.
:) JuggerNuts, i will leave it to you to discover why this algo will find the conflicting apps that start earlier than current app. if you can not find. let me know and i will explain. good luck.
Thanks for your kind reply __coder. I'm truly flattered by your worthless reply since I already mentioned why your naive algorithm is dead wrong. I'm holding off to providing the correct solution for this problem until you realize where you're wrong. Now, I'll leave it to you to find out why your algorithm doesn't work. (Hint: read what I posted before!)
- @JuggerNuts
I think _coder's is algorithm works. Because the condition you mentioned "the apps with start times less than the current app's start time and end time larger than the current app's start time" has already been considered when you deal with the apps with small start times, you do not need to consider them again.
Hi guys, I don't get the how do you find all the conflicts in this case:
suppose appointments between 9 and 12 (random times)
after sorting you have
9 12
A |------------------------|
B |--------------------|
C |----------------|
D |------------|
E |---------|
F |------|
if you do binary search for each one, how do you find the conflict between A and B ?
(with binary search from A you jump to C)
@__coder, you say "All the apps between current app and last conflicting app is conflicting"
so what do you do, you count them? that will be n^2
thanks
everything between a and f is conflicting. for this sample you will sort then first binary search will return f as the last one which says all of them is conflicting.
@JuggerNuts Can you see a logical problem in your statement ? "I'm not sure what the question is asking, but your answer is not correct either."
"do a binary search to find the largest start time (last conflicting app) which is less than current apps end time."
Your apps are sorted already so why do you need to binarysearch for the largest?
"All the apps between current app and last conflicting app is conflicting"
You have to "touch" the in between apps at some point (perhaps simply to return them) so your algorithm is nlogn+n^2 = O(n^2)
red black tree with additional field start,end time. start time is used as key. each node will maintain latest end time in its sub-tree. search from root. time for search will be O(klogn), k is number of conflicting appointments.
It won't work, I'm afraid.
Suppose you have your tree. Now insert a node that have the earliest start time, but the latest end time of all nodes.
It will be inserted as a leaf node first-from-the-left, right?
And when you do your searching, you'll always end in this node, but you won't find *all* conflicting appointments, just this one.
here the point is what policy we use to define which appointments are conflicting.
there are at least two options:
1. minimize the time interval between two scheduled appointments
2. maximize the total number of scheduled appointments
I guess the last option is more "fair" in a sense that we prefer to have many short
appointments instead of just a few long ones
this problem can be solved by greedy alg in O(nlogn) time.
first sort the appointments by increasing finishing times:
suppose f[1] <= f[2] <= ... <= f[n]
then run the following alg:
A = {1} // the first appointment
j = 1;
for i = 2 to n do
if s[i] >= f[j] then
A = A + {i} // add appointment 'i'
j = 1
end if
end do
accordingly all conflicting are those that are not in A
<pre lang="" line="1" title="CodeMonkey58639" class="run-this">// The last function is the answer
import java.util.*;
public class Intervals
{
// You are given 'n' appointments. Each appointment contains starttime and endtime. You have to return all conflicting appointments efficiently starttime and endtime can range from a few min to few years.
public static class Interval implements Comparable<Interval>
{
Long start_, end_;
public Interval(long start, long end)
{
this.start_ = start;
this.end_ = end;
}
@Override
public int compareTo(Interval interval)
{
if (start_ == interval.start_)
return -end_.compareTo(interval.end_);
return start_.compareTo(interval.start_);
}
@Override
public String toString()
{
return "[" + start_ + "," + end_ + "] ";
}
}
public static void main(String[] args)
{
int n = 6;
Interval[] appointments = new Interval[n];
Random random = new Random();
for (int i = 0; i < n; i++)
{
long start = Math.abs(random.nextInt());
long end = start + Math.abs(random.nextInt());
appointments[i] = new Interval(start, end);
}
printConflicts(appointments);
}
private static void printConflicts(Interval[] appointments)
{
Arrays.sort(appointments);
Interval reference = appointments[0];
for (int i = 1; i < appointments.length; i++)
{
Interval interval = appointments[i];
if (reference.end_ > interval.start_)
System.out.println(reference + "↔ " + interval);
if (interval.end_ > reference.end_)
reference = interval;
}
}
}</pre><pre title="CodeMonkey58639" input="yes">
</pre>
Unless I am missing something, the worst case scenario is O(n^2), assuming we have to print out all the pairs of conflicting appointments. Consider this example: [(1,2),(1,2),(1,2),(1,2),(1,2),(1,2),(1,2),(1,2),(1,2)], where all the meetings have the exact same start and stop time. In this case, the first meeting conflicts with all the rest, the second meeting conflicts with all the rest etc. Even if the pairs of conflicting meetings are unique (i.e. (first, second)=(second,first)), there are still n(n+1)/2 pairs to print, which is O(n^2)
No, for the worse case, we can still achieve O(nlogn) time. Since for each appointment, we can use binary search to find the first appointment that is not in conflict with itself. Therefore,we get the conflicting appointments in O(logn) time for each appointment.
typedef class _Interval
{
public:
int start;
int end;
}Interval;
int compareIntervals(void * _start, void *_end)
{
Interval *start = (Interval *)_start;
Interval *ending = (Interval *)_end;
if (start->start == ending->start)
{
return start->end - ending->end;
}
return start->start - ending->start;
}
void PrintConflicts(Interval *arr, int n)
{
if (n == 0) return;
qsort(arr, n, sizeof(arr[0]), compareIntervals);
Interval *reference = arr;
for (int i = 1; i < n; ++i)
{
if (reference->end < arr[i].start)
{
printf("start:%d end:%d conflicts", arr[i].start, arr[i].end);
}
else if (arr[i].end > reference->end)
{
reference = &arr[i];
}
}
}
I think a thread scheduling algo will work. assuming we want to schedule max number of appointments
1. Sort all appointments by their end times in increasing order.
2. take first one and it's non-conflicting
3. iterate though remaining ones now.
4. if next appointment start time is more than end time selected, this is conflicting.. add it to the conflicting list
5. else update the end time to this one.
In end we will have a list of conflicting appointments.
1. For each appointment fill a Map<Integer,List<String>> e.g. if the first appointment is 1 to 5, put following entries in a map:
1: 1-5
2: 1-5
3: 1-5
4: 1-5
5: 1-5
2. When another appointment arrives, try doing the same thing again.
3. If the map is already having a value, check if there is a conflict (because 5-6 is not conflicting with 1-5 and 5 will have a value in both the cases)
This goes through each appointment once but has to go through the mapped hours multiple times. Not sure if you can call it O(N)?
Please suggest.
worst algorithm is n2. If you sort by start times (nlogn)
- __coder November 14, 2011then for each app(current app), do a binary search to find the largest start time (last conflicting app) which is less than current apps end time. All the apps between current app and last conflicting app is conflicting. so nlogn+nlogn