Coding Interview Problem: Calendar Conflicts

Jackson walks through a linear (O(n)) complexity solution to the problem of finding conflicts in a calendar represented as a list of start and end times. The video features code written in PHP. It's written in the style of a Google coding interview (or Facebook, Amazon, etc. company).

[@jackson-gabbard]

Whoever gave the dislike -- I understand. PHP should never be inflicted on anyone.

[@DiogoNeves]

You usually start coding almost immediately as you figure out the problem. Is this because you already know the problem? Or is that expected in an interview setting? On Cracking the Coding Interview she always suggests to figure out the whole thing first, but I know Facebook looks for speed, would love to get your input ;)

[@junaid1464]

Hey what If 5 10 6 7 8 9 end should be max(end, a[i][1]) edit: okay now I watched till the end :)

[@winterheat]

my goodness... are you writing in reverse?

[@sumitlahiri209]

@@winterheat No he isn't.

[@DWattify]

Jackson! You gotta keep these videos up :) They're great! The quality of your videos are definitely better than most other KZbinrs who make similar things.

[@keithchong6960]

hey man. thanks for your optimism. and thank you for sharing. im so glad to come across your videos. youre awesome man. i wish i was you. i wish im as good looking too

[@leandronunes85]

First of all thanks for all the good videos Jackson! I was wondering if using a set to store the conflicts wouldn't lead to a cleaner solution? I mean, if we used that we would only need to keep track of the greatest "end time" we've seen so far and for each iteration we would simply add both the current appointment and the previous one to that set if we detect a conflict (the set would make sure only one instance of each event would be retained and that should still be a O(1) operation on something like a Java's HashSet). Would this work or am I missing something?

[@shashankmadan]

can u do a video on the logic of swaping in the sorting programs???

[@rushilpatel2937]

Your videos are great!!!

[@singsai]

Jackson, we need moarrrrr. You're awesome man.

[@singsai]

but uh...please, no more php :D

[@adamhughes9938]

I had a similar question on a coding challenge where the goal was to schedule a day with the most possible events. Kind of the longest path in a graph problem. Seemed like a hard question for an initial tech screening... (np hard problem right). So the first step is to find the conflicts, but the next step is to find the path that has the most events.

[@sandarabian]

question, why not just compare one pair at a time, starting with the first and second, moving the second and third, etc. while walking through the array and pushing conflicts?

[@code2287]

Really awesome video been having this problem I never thought of sorting that's why it was difficult...How would this solution be implemented in a database to check to notify user if he/she can't book for a particular date

[@sharpvik]

Could you please attempt to write an algorithm to count exactly the number of seconds for UNIX Timestamp. You can use python since it has a module time to get current time easily with no need to input it yourself.

[@jayh5992]

You could also just sort the first array after the first number in the 2nd array and then check if only the single event before that does not collide. Seems also quite efficient if the sorting is done right. My solution is probably quite efficient, but only good to use in an interview if you are actually good at that... The sorting could make it unecessairly complicated...

[@radz171]

so if the case is there are 3 conflicts among 3 items (lets say 1-4; 2-5; 3-6, item 1 will conflict item 2, item 1 will conflict item 3, item 2 will conflict item 3) then you count is as just 2 conflicts (item 1 will conflict item 2, item 2 will conflict item 3) ?

[@harshjolu]

you are correct. This algorithm is not correct. There is a nlogn solution here: www.geeksforgeeks.org/given-n-appointments-find-conflicting-appointments/

[@fierce10]

Even if the first event is not in conflict, your code would still find it as a conflicting event? You initialized the first event in $temp_conflicts and then immediately stuck $temp_conflicts in the conflicts in the loop if there is no conflict. I think that's not correct. Maybe I'm missing something?

[@piyush12121]

So, this is basically similar to Activity selection problem from CLRS book. Awesome video though !

[@CrystalKelly1913]

My daughter keeps getting a calendar event set for smoothstack coding challenge she didn't sign up for and it to Jacob Cole how is this happening?

[@cenkuyan488]

Hi Jackson, Congrats on creating novel videos in the algorithm/coding explanation domain . It's really refreshing to watch thoses. I just wanted to point out that, when you have started your solution it wasn't obvious -when exactly it was going to turn into an O(N) soln .. That became known only when you updated the following line by taking the max of..: $open_event_end = max($cal[$ii][1], $open_event_end); which actually geared up your algorithm, and turned into O(N), by using a dynamic programming idiom. But the way you present it, hides that fact away , as if that line only fixes a bug at the last moment. But it really should be advertised as the crux of the algorithm . In my humble opinion that is =>). Thanks Cenk

[@tonysoprano3818]

How did you assume the list was sorted?

[@VivekMahadevanv]

Not sure if Im missing something, but I dont think your algorithm is completely correct - Consider a set of hypothetical events [2,10][10,16],[6,16]. Your algorithm would return all of them as conflicts, since we process 2, 10- > 6,16 and then 10,16 and all are conflicts but in reality only 2,10 and 6,16 are conflicting.

[@vthakkar123]

The question states that the events are in sorted order of start time. So, you can't have [10, 16] and [6, 16] in that order

[@krishna81m]

woah, how do you draw and record like this?

[@marvellousleopard]

Write normally on the glass (from the presenter's perspective), then flip the video horizontally so it is mirrored.

[@sriharijoshi5]

Why did you stop making the videos!??

[@luizfernandocaldeir]

Just wondering why PHP is so ugly. My python solution below looks so simple and easy to read. But I am new to this channel and I really enjoyed it. Clear communication and very good tips. Keep on doing that, mate! def findConflicts(events: list) -> str: last_ev_end = events[0][1] last_ev_id = events[0][2] for ev in events[1:]: if ev[0] < last_ev_end: yield(f'Conflict found between events {last_ev_id} and {ev[2]}.') last_ev_end = ev[1] last_ev_id = ev[2]

[@MihaiAndreiStanimir]

If the array wasn't sorted, you get to O(n log n) and not O(n^2), because quicksort. My idea was to lose indexing and maybe have something like $prevEvent.end and $currentEvent.start.

[@murtaza6464]

So I mostly code in Python, and my understanding is that in python you should never index lists, but always iterate through them as iterables. I know PHP has a foreach loop for similarly looping through arrays, so why isn't this used? I'm not very experienced with PHP, so please someone enlighten me.

[@jackson-gabbard]

Here I needed to do some somewhat tricky things like beginning the iteration at the 1 index rather than 0, which is easier to do with a manually configured loop. That said, you totally could do this with a foreach/as and it would be fine.

[@raxa45]

for i, val in enumerate(array): would be the pythonic way to use the indices

[@kamalsmusic]

Have you received this question in an interview before? Jw. Btw, I really like these videos

[@CODINC]

I have. Variation of this question

[@jyotikumari-bl2kf]

What about checking no events in the calendar. I suppose that should be one of the base cases. Correct me If I am wrong.

[@HairyPixels]

Oh come on now, PHP Is a fine language for doing quick and dirty one-pass scripts where you don't need to worry about memory management and the structure of data.

[@enghossam84]

My Java solution to the problem import java.util.Stack; public class CalenderEvent { private char eventId; private int startTime; private int endTime; public CalenderEvent(char id, int stime, int etime){ setEventId(id); setStartTime(stime); setEndTime(etime) ; } public void setEventId(char id) { eventId = id; } public void setStartTime(int stime) { startTime = stime; } public void setEndTime(int etime) { endTime = etime; } public char getEventId() { return eventId; } public int getStartTime() { return startTime; } public int getEndTime() { return endTime; } public static void main(String[] args) { // TODO Auto-generated method stub CalenderEvent [] calenderArray = new CalenderEvent[8]; calenderArray[0] = new CalenderEvent('a',1,2); calenderArray[1] = new CalenderEvent('b',3,5); calenderArray[2] = new CalenderEvent('c',4,6); calenderArray[3] = new CalenderEvent('d',7,10); calenderArray[4] = new CalenderEvent('e',8,11); calenderArray[5] = new CalenderEvent('f',10,12); calenderArray[6] = new CalenderEvent('g',13,14); calenderArray[7] = new CalenderEvent('h',13,14); Stack conflict = new Stack(); conflict.push(calenderArray[0].getEventId()); int end = calenderArray[0].getEndTime(); for(int i = 1 ; i < calenderArray.length ; i ++) { if(calenderArray[i].getStartTime() >= end) { if(conflict.size()> 1) { System.out.print("Conflict found between event:"); while(!conflict.isEmpty()) System.out.print(conflict.pop()+ " "); System.out.println(); } if(!conflict.isEmpty()) conflict.pop(); conflict.push(calenderArray[i].getEventId()); } else { conflict.push(calenderArray[i].getEventId()); } end = Math.max(end, calenderArray[i].getEndTime()); } if(conflict.size()> 1) { System.out.print("Conflict found between event:"); while(!conflict.isEmpty()) System.out.print(conflict.pop()+ " "); System.out.println(); } } }

[@tusharmaurya1668]

you are right but this is a big code.

[@johnmadsen37]

No OOP here! This is for script kiddies.

[@MateiOprea42]

You should never call count() in a for if you know that that array wont change. $length = count($cal). for ($i=0; $i < $length; $i++). I know that this wasn't the point and you probably know this. But it's a good advice for someone who doesn't know that. :)

[@RealMcDudu]

I agree, though in C# (and maybe other languages) the JIT compiler does it for you anyhow. Still, you should not count on it.

[@thezquad]

/** * Assume that the events are sorted * * @param array $cal * @return array */ function findConflicts(array $cal) { $conflicts = []; for ($i = 0; $i < count($cal) - 1; $i++) { $next = $i + 1; $tmpConflict = [$cal[$i][2]]; //contain a group of conflicts //find conflicts: while next start < current end, keep checking for conflicts while ($next < count($cal) && $cal[$next][0] < $cal[$i][1] ) { $tmpConflict[] = $cal[$next][2]; //append new conflicts $next++; } if (count($tmpConflict) > 1) { $conflicts[] = $tmpConflict; } } return $conflicts; }

[@nimbleninja12]

NO MORE PHP

[@moosegoose1282]

phps no more.

[@Drtsaga]

what is the typical amount of time given for such programming challenges?? My UUUUUUUUUUGLY C code ... but it does the job. (took me too much I think)..... --Start of code-- #include #include typedef struct calItem { int s; int e; char id; struct calItem *next; }ci; typedef struct idItem{ char id; struct idItem *next; }ii; typedef struct conflictGroups { ii *idList; struct conflictGroups *next; }cg; void freeCal(ci **); void viewCal(ci *); void viewConflicts(cg *); int main(int argc,const char **argv){ // fill calindar and view it ci *cal=(ci *)malloc(sizeof(ci)), *p=cal; p->s=1; p->e=2; p->id='a';p->next=(ci *)malloc(sizeof(ci));p=p->next; p->s=3; p->e=5; p->id='b';p->next=(ci *)malloc(sizeof(ci));p=p->next; p->s=4; p->e=6; p->id='c';p->next=(ci *)malloc(sizeof(ci));p=p->next; p->s=7; p->e=10;p->id='d';p->next=(ci *)malloc(sizeof(ci));p=p->next; p->s=8; p->e=11;p->id='e';p->next=(ci *)malloc(sizeof(ci));p=p->next; p->s=10;p->e=12;p->id='f';p->next=(ci *)malloc(sizeof(ci));p=p->next; p->s=13;p->e=14;p->id='g';p->next=(ci *)malloc(sizeof(ci));p=p->next; p->s=13;p->e=14;p->id='h';p->next=NULL; // p->s=13;p->e=14;p->id='h';p->next=(ci *)malloc(sizeof(ci));p=p->next; viewCal(cal); // run algorithm cg *G=NULL, *g=NULL; p=cal; if ((!p) || (!p->next)) printf("No conflicts (too small calendar) "); else{ while (p->next){ ci *h=p, *t=p; while ((t->next) && ((p->e) > (t->next->s))) t=t->next; // point all visible conflicts if (h==t) p=p->next; // no conflict here, move on else{ // determine where to add the conflicting id's g=G; ii *idL=NULL; while (g){ idL=g->idList; while (idL->next) idL=idL->next; if (idL->id==h->id) break; // because the input is sorted, this is enough to determine if the new conflicts belong to an existing group or not. else g=g->next; } if (!g){ // need to create a new group if (!G){ // first group G = (cg *)malloc(sizeof(cg)); g=G; }else{ // go to tail of G and append one g=G;while (g->next) g=g->next; g->next = (cg *)malloc(sizeof(cg)); g=g->next; } // put all id from h to t in g->idList g->idList=(ii *)malloc(sizeof(ii)); ii *iip=g->idList; while (1){ iip->id = h->id; h=h->next; iip->next = (ii *)malloc(sizeof(ii)); iip=iip->next; if (h==t){ iip->id=h->id; iip->next=NULL; break; } } }else{ // ids need to be placed in existing group. Specifically, in g. Moreover, exactly where idL points. idL->next=(ii *)malloc(sizeof(ii)); idL=idL->next; // at this momenet h->id is already inside. So I have to move one step ahead. h=h->next; // this is the step ahead... if (h==t){ // just add one idL->id = h->id; idL->next=NULL; }else{ // add more than one while (1){ //fprintf(stdout,"3 ");fflush(stdout); idL->id = h->id; h=h->next; idL->next = (ii *)malloc(sizeof(ii)); idL=idL->next; if (h==t){ idL->id=h->id; idL->next=NULL; break; } } } } p=t; // shift your attention to t (not p->next) } // else{ } // while (p->next) } // else { // illustrate results viewConflicts(G); // return freeCal(&cal); return 0; } void viewConflicts(cg *G){ printf("Conflics: "); cg *g=G; while (g){ ii *i=g->idList; while(i){ printf("%c ",i->id); i=i->next; } printf(" "); g=g->next; } printf(" "); } void viewCal(ci *cal){ printf("Calendar: "); ci *p=cal; while (p){ printf("(%2d,%2d; %c) ",p->s,p->e,p->id); p=p->next; } printf(" "); } void freeCal(ci **cal){ ci *p=NULL; while (*cal){ p=*cal; *cal=(*cal)->next; free(p); } } --End of code--

[@maryamghorbani1333]

erase! erase! erase! Hahaha

[@ManishAtri]

Would be better if you remove this background work. Thanks for your work.

[@blake8894]

Can anyone come up with a shorter solution? To be fair I'm using python, so any language is ok. times=[[1, 2, 'a'],[3, 5, 'b'],[4, 6, 'c'],[7, 10, 'd'],[8, 11, 'e'],[10, 12, 'f'],[13, 14, 'g'],[13, 14, 'h']] for each in range(0, len(times) ): for beach in range(each-1, 0, -1): if times[beach][1] >= times[each][0] : print times[beach][2] + ' -> ' + times[each][2]

[@Daukashka]

Я человек простой - вижу. код пыхе ставлю дизлайк