Big thanks to Tim for being willing to do this coding interview in front of all of TH-cam! Check out the video we did on his channel here th-cam.com/video/pjJuqWWqEDI/w-d-xo.html, and here are a few timestamps for the coding interview: 0:00 - Introduction 2:09 - Intro chat 3:03 - Interview starts 49:12 - Interview ends (overtime starts) 52:58 - Debrief 59:40 - Conclusion
Hello Clément Mihailescu ! I want to ask something. Don't you think that the candidate over complicated the solution. I know its a bit easy when I am not put right into the test ; but still when I took a first look at the problem ; I found an easy way to it. What we can do is convert all times to minutes. Means that if we have time 00:28 ; we can say that this is eqivalent to minute number 28 in the day. If we have time 1:30 ; we can say this is minute number 90 in the day. Generalization can be for time hh:mm ; minute number : hh*60 + min. And now instead of having time slots as time slots ; they are just n slots of the form l to r ( inclusive ) ; and l and r are integers. Now the time when we could not meet is the union of all intervals ( Union like we do for sets ). So every minute in the day minus this union is the free time ! we just will need to do two things : 1 : Do this union operation properly 2 : Convert back the free minutes into slots of free times. well task 1 is a standard problem ; while task 2 is the reverse of what we did before ! For union operation ; I can suggest that we could declare a bool array and make its size = 24 * 60 = number of minutes in a day. Mark all non-free times using false ; and the times that are still true are free times in the day. So space complexity is O(1) constant = 24 * 60 bytes ( not a lot ) ; and time complexity = O(n * 24 * 60 ) again not much even if one does perform union operation in a naive way ; althogh there are better ways to do the union operation and complexity can surely be improved I think. One way to improve the union operation is to use the difference array ! It allows updates in range sum in O(1). And thus time complexity could be taken down to O(n). Thus using difference array - Space complexity - O(24 * 60 ) Time complexity - O(n) Difference array tutorial can be found here : www.geeksforgeeks.org/difference-array-range-update-query-o1/ What you say of this solution ?
4 ปีที่แล้ว +1
Even a senior developer would not have written in 45 minutes I am sure I am c# developer if get some time with c# developer could you one round of interview like this and even on system design interviews as well please
Just when you are wondering why many programmers are losing lots of Hair..........., And doing coding with thousands of people watching takes guts, Well done Tim!
In my opinion, Tim did well considering his level of experience at the time. I know Tim started coding at like age eleven but coding and system development, (especially on the fly, and for an audience,) are two completely different animals altogether. It was interesting to watch Tim almost come of age in this one “interview.” Nice job, Tim! Great collaboration. Very informative. I admire both of you guys a ton. And, I watch your channels all the time. Tim, Clément, love you! Keep creating great content! 🤜🏼🤛🏾
Yeah because then, in that very moment, you realize it's not about coding at all - it's about the ability to solve problems. Coding is "just" a language.
Ive been told these interviews are: 30% - can you solve this problem in code 70% - how does the candidate problem solve, what is their personally under pressure, can they catch their own mistakes.
@@is1hair Most people getting hired fail to solve the problem in these interview fyi: When I say fail, I mean not doing it the most efficient way but it can also be a complete fail. Tips: Start by solving the problem with a naive approach and then work you way down to optimize. Even if you cant get the most efficient way, the interviewer will see how you can solve a problem. If you just show the best solution first try, the interviewer won't see enough of your thinking and might think you just remembered most interview problems solutions without knowing why they are the better option.
@@is1hair Actually in some cases, interviewers (not necessarily good interviewers) set you up to fail, and see how you handle the process of solving something incorrectly and it going wrong.
For 19 years old, he did really well. At 19, I was just learning basic programming principles. Didn't even have any concept of time or space complexity yet. Good job.
I'm a 22 years old Brazilian student and I've just finished my first semester at CS and I can't do what this guy do yet. That's a shame but I'm jealous of his intelligence. It's really bad feeling like your whole existence is a waste kkkkkk
@@hyanbatista3281 ye in the end it's all experience, and if you do feel down about someone being better than you just simply acknowledge your intelligence, not to bring you or anyone down since this also goes for me but if you think you're lacking knowledge then simply strive to get better and try to fix your problems. In the end even relearning the basics would help you accomplish or solve any problems about the harder ones, again coding is not a simple job where you do the same thing everyday but as time goes by you're building up those experiences, it's like driving for example where you struggle at first but at the end you can even talk with someone while driving or even drive like a maniac and I think it goes for coding as well.
We all know that coding is same as math. We all have different solutions but same answer. The competition just goes into the time complexity of the code
I learnt time and space complexities when I was 17. I understood the logic behind the question and was trying the question myself and actually did the combining od the calendars and comparing times before Clement hinted it but the thing I struggled a little bit with was the actual coding behind it.
I have to say, this video may have helped me get a job at Microsoft. I always froze at the technical interviews focusing SO much on solving the problem mentally, but seeing how Tim takes the time to explain his thought process and then write out his plan, then solve it, I tried that myself and got far more positive reactions even when I wasn't able to compile the code in time. It goes to show, Interviewing is a skill that can be learned and this video is mega useful for learning what people are looking for.
Speak your thoughts, especially if you got stuck. That helps the interviewers know you and guide you toward the solution. This comes really important in real work scenarios.
I’m a CS student and I’m struggling… But honestly it’s validating to stumble upon these videos and watch them around every six months as the coding jargon gradually becomes an intelligible language that makes sense. It’s honestly quite beautiful.
1 year ago when I saw this video, I thought this is way above my head. But now I feel this is so simple and I can spot that logic just on seeing the question. The reason for this is practice, it brings u the confidence that u need to move ahead.
Also, the reason is because once you saw the answer to the problem, it's difficult to forget the core of the solution, and next time you review the problem, it's much easier. The tough part is when you have to figure out a problem you haven't seen before.
Yeah this is not like an interview with an ordinary student, hell not even with an ordinary programmer candidate would look like. He has a nearly flawless and extremely quick thought process when coming up with a solution. Normally there would be much more silence, stumbling and thinking. Not even mentioning coming up with a solution while constantly talking, I am unable to do it properly and I actually work as a Python dev.
gartekk1987 I just finished a semester in college and I really enjoyed working with python. What are some locations or places that I would use python as the main writing language?
@@killerlpacman_1852 If you are asking me about specific locations in like US, where Python is used by a lot of companies, then I am unfortunately not your guy, as I live and work in Poland. If you want to know fields where Python can be used then the big ones are AI/Deep Learning, Big Data/Data Analytics and Web Development, but Python can pretty much be used nearly anywhere, even form embedded programming.
Here's my take on this problem: - Convert the times into integers (minutes, so 2:00 becomes 120) - Calculate the free time (pairs of times just like shown in video) each person has - Make a bit representation of each minute in a day (24*60 bits), if that person has free time in that minute, set that bit to 1, 0 otherwise - Do an AND operation between the bit representations of free time of every person (joining everyone's free time) - Convert that bit representation back to pairs of times. If the time range is greater than 30 minutes, then accept that pair - Profit You can implement that with constant extra space (if you needed to find availability of 3 or more people at the same time), and time complexity is O(n + m): N is for number of calendars being read (2 in that case) and M is the total number of existing meetings
Same, I actually feel like I'm hot garbage straight from the nearest dumpster. I'm 22, one semester away from an associates (transfering to umass lowell for bachelors) and i felt pretty good about myself until i watched this. oh well; congrats to him, his effort has paid off
@@vladventura1928 Mine too. I was thinking that Google is peanut butter but after watching this I understand that I've to do so many things to get that position.👍👍👍👍👍
I would say this is the most realistic coding interview in this channel. Others, who came here (like William lin) were godlike in their algorithm and coding skills, Tim certainly is more relatable candidate. I am about his age, and studying in college (in 2020) too. So, awesome experience for me
how i'd do it: 1. create list of meeting segments with length = meeting time from max(start_times) to min(end_times) 2. start on list 1, cut segments from available list that fall within each unavailable segment 3. repeat for n 4. create available meeting times from joinable meeting segments unless this was server side work in which case i would just redo the oracle so that it could all be done in sql
1st function: find the possible start times and durations for each person based on their schedule and limitation (working day duration etc) 2nd function: find values within the array of starting point of a person falls between starting point plus duration of the meeting (30 min) of the second person starting point and endpoints of second person is greater then first person
I'm going to follow along and pause the video before Tim works on an answer and see how I solve it vs how he did and how long it takes me. Thanks for putting out this content, it is very helpful!!
One note, as you are going through your logic I would recommend as I like to do, building out a scaffold with comments documenting your "thinking out loud" in sudo logic. This way when you get into code mode, it is much easier to retrace your steps. Food for thought! Great video! It was super interesting learning how Google does it.
Good advice. Also: where you write "sudo", you probably mean "pseudo", which is indeed pronounced like "sudo". Not trying to be a know-it-all, just correcting you if you're open to that and if you weren't already aware.
Great Channel. What I appreciate in your "interview" videos is the fact that you concentrate a lot on the interaction between interviewer and interviewee. Making clear the problem is a huge factor, there actually you get your answers for your solution. I hope all the students that are looking for an internship are watching this. Wish you good luck with the channel, very good content!
He mentions his OCD will kick in, and then he put the available time of person2 in the first place, available time of person1 in second place, and in one set he uses double quotes and in another one he doesn't...
Rad Rad there’s google collaboratory, I use it to test short, simple programs in python at work on google chrome bc IT doesn’t let us install anything :/
Because the aim is not to see if the interviewee can write a runnable code because sometimes they mess up the syntax or have typos or whatever, they can always google it even at work. The aim is to check if the candidate can come up with a logical solution that works and has the ability to translate that to an understandable pseudocode, something you'll have to do at the job. Sure, Google can come up with something for that but why invest time and money on something that Google docs does well already.
@@codypatnaude9171 during proper google interviews they turn off spell check and calitalize new lines and all the "auto" features. its essentially a textpad.
I would do it actually a little different: First find the maximum day starting boundary. In this case person 2. Set currentTime to this day boundary From there 1. go to other persons calender 2. check if they have time : (find first meeting ending over your current time. see if according starting time is less then current time) a if they have time a1 get from each calendar the lowest starting time of a meeting >= current time (if no meeting get day end boundary) a2 select the minimum of both as currentEndTime a3 add element currentTime, currentEndTime to available time frames a4 set currentTime = endTime of meeting which started earlier and repeat from 1 b if they have no time go to ending of the meeting currently in and repeat from 1 3. elimate timeframes less then needed time
I'm always impressed by coders intuition, i've tried coding several times and it never quite clicks with me. Props to everyone out there who has the skills for it.
In my opinion, this capacity for intensive critical thinking in a super short time frame comes as a result of lots of testing ones own knowledge. He is a CS college student, so he is constantly being tested on his code and his abilities, and the sheer amount of projects you do and the objectives you try to accomplish manage to pull an impressive amount of intuition out of you. The kind of highly time-sensitive intensive programming skill required at these interviews is something he has likely been developing for years, even without knowing it.
I know this video is old but I found a beautiful solution and I couldn't find any comment showcasing it so I thought I might aswell do so. The algoritm starts by creating 2 arrays (one for each person) that represent the free blocks of time throughout the day. We don't need the elements of the arrays to be pairs of times but rather we can create our own data type that represents a given time and wether or not it is the start or end of a free block (for example time=13:00 start=true). For example if lets say one person is free 12:00-13:30, instead of storing the pair[12:00, 13:30] as an element in the persons "freetime-array" we could store the 2 elements e={time=12:00, start=true} and e2={time=13:30, start=false}. We then sort the array in increasing order with respect to the time variable and get a useful way to represent the "freetime-array". We then create a third array that consists of all elements from both of the previously described arrays (both of those are the same btw, just for the two different people). If we sort the third array, once again increasing order according to time, we get something wonderful. What we have done I basically sort of merged together both persons blocks of free time. Lets call this third array a3. Now comes the clever step. We will look for indices j such that a3[j].start and !a3[j+1].start. The time in-between a3[j].time and a3[j+1].time will be time where both people are free. Its easy to verify this (tip: there are basically 2 different cases. Either both the element at j and j+1 come from the same persons free time-array or they don't)! A little harder to verify is that checking for all possible j:s will give us all such interval where both people are free but tbh its pretty straight forward aswell. Yeah so thats basically it
This reminds me (just a tiny bit) of the interview I've got for a full time job. Except it was a general culture thingy instead of an actual algorithm to create. That was a great video ! :)
Amazing video, really gives a reliable picture of what an interview is all about. I actually paused it and came out with a nice solution to the first approach that Tim suggested. I think that by holding the numbers in a class containing the start/end times (instead of [0] and [1] indexes), and adding some useful functions to it like a function that takes another object of that class and gives you the overlapping time between them as an object of that class - the code may become much more elegant and readable (I believe even more readable than the single list approach) but naturally much more difficult to do in 45 minutes time unless if you're very used to creating those handy classes naturally. Thanks so much for uploading it, and good luck Tim!
This question is a fairly simple question. He is all over the place. The key is first to find the "available time" and focus on it for both parties and change the variable type from string and apply the boundary or rules. Then do the arithmetic by exclusion to remove useless data array entry and inclusion to compare the 2 arrays after the exclusion
sometimes when I'm trying to experiment I just want an output to be error so I know exactly what is "that" capable of doing, so if I get some output I'd expect, I'm just like "fine, whatever", but when I get error or some crazy stuff as output, then I learn much more, because I know what I can't expect from "it" to do. so in my opinion, errors and crazy outputs makes you better programmer.
i didn't have problem with the " hello,world" . but the first time i got a bug was when i was making my first GUI with Tkinter . later i find that the solution was so easy that i was thinking how stupid i was
I think I will forget everything when I get to interview🤣🤣and Here am I who want to work in google but doesn't even know how to print a simple pattern😭😭😭
Quick useful info for comparing time strings when it is in military format, there is no need to convert the string into hours and minutes, one can actually just compare the two strings with normal string comparison operators and the result would be as expected.
Hello everyone! I came across this video today and found the problem very interesting! So what I decided to do, was pause the video after Clement gave Tim the sample input/output and coded it myself (to skip to the point, I attached my Java solution below)! I did everything in a google doc and it took me 45 minutes to write the solution. Once I had written the solution, however, I wanted to check my answer! Thus I moved everything over to my IDE and changed the auto-capitalization from google doc and other errors such as me missing parenthesis and such. But voila! Once I fixed all of the general typing/spelling errors, I ran my code and it succeeded! It produced the same output as the sample output given in the video. I thought that some of you may be interested in seeing a working solution, so here I am providing mine! I wrote my solution in Java and here is the google doc link of the cleaned code. Also, in case you were wondering, I wrote the documentation as I was solving the problem. I did not go back afterward and add the comments. Enjoy! This was an awesome problem to solve! docs.google.com/document/d/1O9oAP24bnS5T4uoVxjcJL7CPtHxjKWalXwen_VVeDRY/edit?usp=sharing P.S. I'm a junior at the University of Washington, double majoring in Computer Science and Comprehensive Physics, just incase you we're wondering what my background is :)
They care more about how you work with the interviewer than how you actually code the problem like anyone can code but not everyone can work together in a team.
if the meeting is in blocks of 30 minutes, then we can create a hashtable upfront between overlapping bounds (say 9am to 6pm in 30 minute increments) then filling each slot by running over each person's calender once. hash["9:00-9:30"] = 1 hash["9:30-10:00"] = 1 hash["10:00-10:30"] = 0 .. for a meeting from 9:00-10:00 then collect all keys with 0s (free times) and build range. This way it is much easier to merge multiple calendars and not just two.
My idea for first question. (Before I watched on) Step 1: Declare a list of all the minutes in the day. (1440 minutes) e.g. List DayMinutes. Get start of day in UTC minutes and have 24x60=1440 consecutive numbers Step 2: Convert the calendar time strings into integer representations of the minutes in the day. Note these should both be UTC formats or similar for compatibility with different days Step 3: For each persons calendar Step 4: For each block in the calendar Step 5: Delete from the list of minutes (DayMinutes), all of the minutes described by the calendar block. (So iterate through DayMinutes. If its equal to the startvalue, delete it and all the next ones until you reach the end value). Also delete all of the minutes outside peoples working hours At this point you will have a reduced list of all the minutes that EVERY participant has free that day. (Could be more than 2 people) Step 6: Write a function that checks for consecutive numbers in that list. (If DayMinutes[n] = DayMinutes[n-1] + 1 its consecutive. Otherwise its a jump) Record the jump positions to work out consecutive block start and end times, and note the length of the current consecutive block Step 7: You are looking for sections of consecutive numbers of length greater than or equal to the meeting length (e.g. 30). If your consecutive numbers are greater than the meeting length, add the start and the end of that consecutive block to your output Step 7: Convert back to time strings You will end up with an output of all the blocks longer than the meeting length, which every participant has available.
A simple solution to the Calender question: The times were given already, first we had to find their time gap blocks, then find the time block in which both were available : ['10:30', '12:00'], ['13:00', '16:00'], ['18:00', '20:00'] - Person1 ['11:30', '12:30'], ['15:00', '16:00'], ['17:00', '18:30'] - Person2 Find the maximum starting time and minimum ending time as Person2's starting time is 11:30 while Person1's starting time is 10:30 similarly the ending time is 12:00 and 12:30 respectively. The common time for both would start with the maximum time that is 11:30 because they both are available during that time block and similarly the ending time must be the minimum time as Person1 does not have time after 12:00. According to this algorithm, We make a new list with the maximum starting time and minimum ending time for all 3 inputs and the output is : ['11:30', '12:00'], ['15:00', '16:00'], ['18:00', '18:30'] Though this is when there is no 30 minutes time block assigned.
What a great problem. I'm going to try to do this in one pass by starting with the person with the earliest start time and then track gap time based on the meeting starts and ends without any internal loops. It was very helpful listening to your discussion/feedback. Algoexpert sounds like something I need to try out.
This problem can be solved very easy in O(n), just create a bool array of 24*60 if the meetings can be scheduled at every minute, or only 24*2 if the time blocks are 30 minutes, iterate through the calendars and convert the starting and the end points to int and mark all the values as 1. After make a for loop starting from max(boundaries_person1_start, boundaries_person2_start) until min(boundaries_person1_end, boundaries_person2_end) and append to the solution list all the free sequences.
I would expect an actual coding interview to generalize the problem to something like this:Given set A contains N segments, each segment is defined as [A[i].l,A[i].r] with -10^9
@@netbotcl586 That is a totally different problem, Clement said that the input format is in military time from the google calendar, no clock has 1e9 : -1e9
@Mihaela Badea I think they are kind of similar because they are both the overlapping subsegments problem type. I don't think the input format matters too much in this case.
As a prospective high school student looking into CS, I really enjoyed this. I think problem solving like this is just so interesting and I could imagine myself pursuing a job that's problem solving heavy like this. Thank you very much, great content!
Interesting question. I am happy to see something different! I am sick of seeing recursion questions. Took maybe 1.5 hours around 100 lines of code used c#. I actually ended up doing what Tim wanted to do originally before you changed his mind. I found it more logical as a human to take this approach! You find the available time with both schedules (inclusive of the day start and end boundaries). These results are passed into a method that finds overlapping available time of the schedules. The overlapping spare times are compared with the meeting length requirements to produce the suggested time slots. Highly re-usable and writing it like this I can compare more than 2 schedules for availability (Even could specify who can and cannot make it during a time slot).
In simple mathematical terms the question is to find the set intersection between two sets of time (free time) and check if it is more than 30 minutes. May sound easy but actually requires a lot of concentration while solving this.
Having watched these mock interviews, it almost feels like that the interviewee has to follow a script- * ask for sample input / output. * then ask the interviewer if your assumptions are correct. ask if this kind of input will be allowed or not allowed * don't stay quiet at all, speak whatever comes to mind. * figure out a naive solution * interviewer will tell you edge cases and perf issues. * then just keep communicating whatever solution (even if you're not sure if it will fully work). * in code, assume helper function and data structures like stack exists. * give complexity analysis in the end. How can mere mortals figure out the right solutions while doing all the above is beyond me. Thank god I do frontend development. Spared for now. BTW thanks for making this video Clement. Keep rocking
I think your "script" isn't too far from the truth, *but* I would argue that it's not so much a script as it is the general ideal way to go about solving this type of coding problem collaboratively. Oh, and mere mortals can figure out the right solutions while doing all this with some practice! (This is where I'd plug in AlgoExpert 😛) I hope you enjoyed it; keep rocking as well!
The questions you ask the interviewer change the process a lot, so it can't really be called a script. But, generally your outline is how you solve any problem, so you're not really adding anything novel.
youre wasting time convertime the string into minutes. remember to not do things that aren't necessary. if the client asks for strings why give them ints. you could easilly turn the ints back into strings but then thats another step. this would be very slow if youre trying to setup a meeting for 100000 plus users
@@kouyang1771 The conversions are necessary to be able to do meaningful comparisons. The scope of the project was not for 100000 plus users. It is for two.
You could create an array of every minutes during a day(1440), and remove items from the array for the unavailable mins for each person and also the out of bound times. In the end you would just create a list of available blocks of times from the remaining items in the array.
It's not that difficult dude.. you just need to practice... Tbh i too easily found a way to do this...but when he mentioned tuples of available time.. it instantly hit me..damn it was so much easier... It's all about practice and tbh some luck too ..if you're able to luckily hit the right idea... Keep working hard ... All the best
My method: Ultimate available time will be [0, 24] Then get rid of all occupied time interval in the [0,24], we will have all free time intervals. Save as two new 2D arrays. Check overlapping time intervals in two arrays, then we have the answer of time to set up meeting. I didn't try to write the code, so, please correct me if my method's impractical, or this algorithm's actually very slow. Thanks.
At 24:00, there is no need to merge the times. Instead of merging the times, just skip the first item in the list. More generally, from the first to the second-to-last element, make an 'availability window' comparing the ending time of the current window with the starting time of the next one. If there is no availability greater than 30 minutes in between (end > next start + 30), don't add a window. Otherwise, add a window containing that time.
Hello Clément thanks for sharing those tricks with us, and please keep making free content like this you are a source of inspiration for many college students and developers in many countries.
when comparing 2 blocks , get the max start time, compare it to the min end time and check if there's enough to have a meeting, if there's enough to have a meeting, add the array of max start time to min end time to the output.
Solved task more universally using arrays of minutes from 0 to 23*60+59 filled by 1/0 - available or not at this minute. Then multiply two arrays per item and find a sequence of 1s greater or equal to needed.
for the calendar, lets assume these are available time: [a1, b1] for person 1 [a2, b2] for person 2 just compare a1 and a2, look for the higher then compare b1 and b2, look for the lower the higher and lower are the time frame available. the student is making things complicated
Will it work tho? This is assuming they have equal length arrays. What if one person has additional meeting slot, resulting in different array of available time length. Meaning person 1 has [a1, b1], [c1, d1], [e1, f1] then person 2 has [a2, b2], [c2, d2], [e2, f2], [g2, h2]. what do you compare g2, h2 with?
I paused this video as soon as you asked him the question and although it took me a while, I managed to solve it. It's funny, I spent ages trying to figure it out in code, then I just drew it out on paint and solved it in a few minutes, then just had to transfer it into code, which was much easier after solving it by drawing it. I'm loving these problems, I think you're getting me addicted to them. Every single video of yours now I'm pausing and doing them. They are really fun questions!
@Clement your mock interview videos are awesome and we love it and we want to see more of it, just a suggestion that you can pick your top performers from AlgoExpert and interview them on TH-cam. I'd love to see this on TH-cam and I'm sure people would too :-)
I really love this video. It is very informative. I also want to say that Tim did so well in nailing the framework of the solution to the problem and finally writing such a code not too complex to understand.
Much simpler solution is just go over all the times boundries in order, and just add 1 for each "beggin" and subtruct 1 for each "end", if you reach 0 its free time for both
1. Convert time values into real numbers. Ex. 10:30 -> 10.5 2. Take the highest of the lower bound time constraints (x), and take lowest of both upper bound time constraints (y). 3. From x to y look for free times for both. 4. Compare times with the real values Value1 =? Value2
1. Break the daily bound timing into 30 minute time intervals. Write base code to break given time to 30 minute intervals. Eg. Daily bound = (1000,1800)=(1000,1030)(1030,1100)(1100,1130),… 2. Compare daily bound timings and person A’s occupied timings, find available timings of person A. 3. Compare daily bound timings and person B’s occupied timings, find available timings of person B. 4. Compare time available for A&B and give the out that matches for both.
don’t you just combine the two calendars into one, find the empty spaces keeping bounds in mind, and check if the blocks are at least the time given for the meeting?
Muhammed Tauqir then you’d have to check minute by minute. If I’m available 10:30 - 11:00 and someone else is available 10:08 - 11:08, solving that would require that I go minute by minute and check the next 30 minutes. You can’t just split everything into blocks of 30 or you’d have 10:08-10:38 and 10:38 - 11:08, neither of which fit the original person’s 10:30-11:00 schedule.
1) get the available time for both 2)check if the available time is enough if not get rid of 3)check if the starting of one's available time is between the other one's available time. 4) if yes then check if there's enough time that is end -other one's start That's it, but pressure is a big thing in a interview
Very nice question. I was screaming “overlapping intervals” at my screen the whole time but then realized the dude is 19 and I was like “I couldn’t even add 2 and 2 at 19 and this guy is solving this question on demand” Very nice video
My algo will be 1. Find the shortest duration for arranging the meeting. For e.g., Person2 accepts meetings between 10 to 18:30 only. 2. Create a master dictionary / list with half hour slots from 10-18:30 3. Delete all slots from dictionary with Person2's meetings in 30 mins slots. (converting string to numbers will help) 4. Now use Person1's booked time and delete master list time slots. Since the master list starts at 1000, anything less than that won't be considered like 900 (for 9am). Similarly greater than 1830 won't be considered. 5. Whatever 30 mins slots are remaining in master list will be the answer
20:15 That time when clement's solution is simpler and much more elegant than mine haha! Thank you Clement, this video helped me a great deal! Will interviewer also give clear hints like clement did?
Glad you found the video helpful! And normally, a good interviewer _should_ give hints when appropriate or necessary, but interviewers come in many flavors, so you never know 😛
my solution is pretty simple: add to a vector the earliest starting point and the latest starting point of each block, where a block is the time between 2 occupied blocks) then, by iterating through the vector, i can find for the start of each block the earliest that both can start an interview(that'd be the greatest of the earliest numbers) and the latest that they can start(that'd be the smaller of the latest of their block), do that for every compatible pair(you'd move on both vectors when a start time is no longer compatible). complexity O(N), where N is the number available blocks(N is between greatest number of blocks and greatest number of blocks+2)
![[LIVE] : ONE ลุมพินี 87 วันนี้!! คู่เอก "ก้องชัย vs โชคปรีชา"](http://i.ytimg.com/vi/YN6e7HVnekw/mqdefault.jpg)
Big thanks to Tim for being willing to do this coding interview in front of all of TH-cam! Check out the video we did on his channel here th-cam.com/video/pjJuqWWqEDI/w-d-xo.html, and here are a few timestamps for the coding interview:
0:00 - Introduction
2:09 - Intro chat
3:03 - Interview starts
49:12 - Interview ends (overtime starts)
52:58 - Debrief
59:40 - Conclusion
Hi , clement. I would like to buy algoexpert after I buying this course is there period of validity ? or once I buy that course i can use it forever ?
@@michaelanggriawan8131 You'll have access to AlgoExpert for 1 year after you buy it; hope to see you on the platform soon!
Hello Clément Mihailescu !
I want to ask something. Don't you think that the candidate over complicated the solution. I know its a bit easy when I am not put right into the test ; but still when I took a first look at the problem ; I found an easy way to it.
What we can do is convert all times to minutes. Means that if we have time 00:28 ; we can say that this is eqivalent to minute number 28 in the day. If we have time 1:30 ; we can say this is minute number 90 in the day.
Generalization can be for time hh:mm ; minute number : hh*60 + min. And now instead of having time slots as time slots ; they are just n slots of the form l to r ( inclusive ) ; and l and r are integers.
Now the time when we could not meet is the union of all intervals ( Union like we do for sets ).
So every minute in the day minus this union is the free time ! we just will need to do two things :
1 : Do this union operation properly
2 : Convert back the free minutes into slots of free times.
well task 1 is a standard problem ; while task 2 is the reverse of what we did before !
For union operation ; I can suggest that we could declare a bool array and make its size = 24 * 60 = number of minutes in a day. Mark all non-free times using false ; and the times that are still true are free times in the day.
So space complexity is O(1) constant = 24 * 60 bytes ( not a lot ) ; and time complexity = O(n * 24 * 60 ) again not much even if one does perform union operation in a naive way ; althogh there are better ways to do the union operation and complexity can surely be improved I think. One way to improve the union operation is to use the difference array ! It allows updates in range sum in O(1). And thus time complexity could be taken down to O(n).
Thus using difference array -
Space complexity - O(24 * 60 )
Time complexity - O(n)
Difference array tutorial can be found here : www.geeksforgeeks.org/difference-array-range-update-query-o1/
What you say of this solution ?
Even a senior developer would not have written in 45 minutes I am sure I am c# developer if get some time with c# developer could you one round of interview like this and even on system design interviews as well please
@@clem sir tell me question..in written form... i am not understanding ur voice ..... plsss write here question... and i like this type videos...
This dude is being interviewed for a job at Google and is using Firefox for the interview! What an absolut madlad!
BrosOfPranks u do realise it says mock interview.
@@dotnetdevni of course I do, I just thought it would be funny anyways
He's also using Linux, firefox is a better choice there.
@@Poison69 firefox is a better choice on microsoft too
I'm watching this on firefox :)
Microsoft Word is my favorite IDE
Mine is sheet of paper
Mine is air
mine is documents rename field
Mine is the TH-cam comment section.
my favorite IDE is cmd
Thanks again for doing the interview Clement! I learned a lot and got some great practice. Hope everyone enjoyed :)
Impressed, You are a genius Tim.
Just when you are wondering why many programmers are losing lots of Hair..........., And doing coding with thousands of people watching takes guts, Well done Tim!
Tech with Tim, I love your channel, I was shocked that I saw your face on another channel
In my opinion, Tim did well considering his level of experience at the time. I know Tim started coding at like age eleven but coding and system development, (especially on the fly, and for an audience,) are two completely different animals altogether. It was interesting to watch Tim almost come of age in this one “interview.” Nice job, Tim! Great collaboration. Very informative. I admire both of you guys a ton. And, I watch your channels all the time. Tim, Clément, love you! Keep creating great content! 🤜🏼🤛🏾
Sooo good
I feel like I would instantly forget everything I ever learned about coding in an interview like this :/
Me Too
I forgot how to write "Hello World", by watching this
I felt the same 😂😅
Yeah because then, in that very moment, you realize it's not about coding at all - it's about the ability to solve problems.
Coding is "just" a language.
That why u do practice interviews
Ive been told these interviews are:
30% - can you solve this problem in code
70% - how does the candidate problem solve, what is their personally under pressure, can they catch their own mistakes.
It would make sense. However, I feel like the 30% is more of a deal breaker if you aren’t actually capable of solving the problem lmao.
@@is1hair Most people getting hired fail to solve the problem in these interview
fyi: When I say fail, I mean not doing it the most efficient way but it can also be a complete fail.
Tips: Start by solving the problem with a naive approach and then work you way down to optimize. Even if you cant get the most efficient way, the interviewer will see how you can solve a problem. If you just show the best solution first try, the interviewer won't see enough of your thinking and might think you just remembered most interview problems solutions without knowing why they are the better option.
@@is1hair Actually in some cases, interviewers (not necessarily good interviewers) set you up to fail, and see how you handle the process of solving something incorrectly and it going wrong.
Johannes Terzis lmao, fair enough, I suppose. Out of curiosity, what are you looking for when you say you’re looking for ‘how’ they solve the problem?
@@drunkenfarmer2513 you are absolutely right , In my last interview he gave me one question which need binary search , I directly answered it,
Why am I watching this I’m a biology student
Same, honestly have no idea wtf goin on
As an bioinformatician I found this useful af xD
@@kennethwiinintendo wtf is that lol
Because the media told us to learn to code.
@@DanielNyong basically analytics using Crispr, MoTor, and other gene sequencing software to locate certain genes within DNA libraries and such.
For 19 years old, he did really well. At 19, I was just learning basic programming principles. Didn't even have any concept of time or space complexity yet. Good job.
I'm a 22 years old Brazilian student and I've just finished my first semester at CS and I can't do what this guy do yet. That's a shame but I'm jealous of his intelligence. It's really bad feeling like your whole existence is a waste kkkkkk
@YoshiPeach Mario 100%. A lot of folks start doing this as literal children. By the time they are in university, it's no longer gibberish to them.
@@hyanbatista3281 ye in the end it's all experience, and if you do feel down about someone being better than you just simply acknowledge your intelligence, not to bring you or anyone down since this also goes for me but if you think you're lacking knowledge then simply strive to get better and try to fix your problems. In the end even relearning the basics would help you accomplish or solve any problems about the harder ones, again coding is not a simple job where you do the same thing everyday but as time goes by you're building up those experiences, it's like driving for example where you struggle at first but at the end you can even talk with someone while driving or even drive like a maniac and I think it goes for coding as well.
We all know that coding is same as math. We all have different solutions but same answer. The competition just goes into the time complexity of the code
I learnt time and space complexities when I was 17. I understood the logic behind the question and was trying the question myself and actually did the combining od the calendars and comparing times before Clement hinted it but the thing I struggled a little bit with was the actual coding behind it.
Just tell me when you want to have the meeting and I'll adjust my schedule....
lol
...drop the mic... leave the room...
my Favorite comment
😂😂😂
you killed me
Sheimy Paz Serpa
😂😂😂
I have to say, this video may have helped me get a job at Microsoft. I always froze at the technical interviews focusing SO much on solving the problem mentally, but seeing how Tim takes the time to explain his thought process and then write out his plan, then solve it, I tried that myself and got far more positive reactions even when I wasn't able to compile the code in time.
It goes to show, Interviewing is a skill that can be learned and this video is mega useful for learning what people are looking for.
Speak your thoughts, especially if you got stuck. That helps the interviewers know you and guide you toward the solution. This comes really important in real work scenarios.
Did you get the job!??
@@brandonnguyen9082 😁
I’m a CS student and I’m struggling… But honestly it’s validating to stumble upon these videos and watch them around every six months as the coding jargon gradually becomes an intelligible language that makes sense. It’s honestly quite beautiful.
Those mock interview are the best thing ever. So useful. Keep up the great work Clement!
Lumanog ikaw ba yan?
1 year ago when I saw this video, I thought this is way above my head. But now I feel this is so simple and I can spot that logic just on seeing the question. The reason for this is practice, it brings u the confidence that u need to move ahead.
how did you practice?
Also, the reason is because once you saw the answer to the problem, it's difficult to forget the core of the solution, and next time you review the problem, it's much easier. The tough part is when you have to figure out a problem you haven't seen before.
Title: "Interview with a college student"
TIM is no ordinary college student, don't believe me watch his videos. He teaches much better than my prof!!
Yeah this is not like an interview with an ordinary student, hell not even with an ordinary programmer candidate would look like. He has a nearly flawless and extremely quick thought process when coming up with a solution. Normally there would be much more silence, stumbling and thinking. Not even mentioning coming up with a solution while constantly talking, I am unable to do it properly and I actually work as a Python dev.
Hetav PANDYA makes me feel a lot better cuz holy heck was he great!
gartekk1987 I just finished a semester in college and I really enjoyed working with python. What are some locations or places that I would use python as the main writing language?
@@killerlpacman_1852 If you are asking me about specific locations in like US, where Python is used by a lot of companies, then I am unfortunately not your guy, as I live and work in Poland. If you want to know fields where Python can be used then the big ones are AI/Deep Learning, Big Data/Data Analytics and Web Development, but Python can pretty much be used nearly anywhere, even form embedded programming.
@@gartekk1987 You just GAVE ME HOPE
"Military time" aka the time the rest of the world uses.
most of the world doesn't actually use military time
@Driipz That's totally incorrect. Most countries in the world use the 24-hour-clock. Only the US and a few other countries do not.
TL Oh I’m sorry, I guess I need to do my research
@@tl469 Exactly!
Aka the good time
Friend: What do you watch in your spare time?
Me: It's complicated
underrated comment
Hahaha what a mood
how exactly is it complicated? If anything it's useful and people could learn something from it
@@sharjeelahmed7913 mate it's a joke
People: If you dont watch movies or shows, what do you watch?
Me: Google coding interviews
wait shit tf am I doing I'm boutta pirate a movie or smthn
mostDEV feel this
my man
Hentai
Love it! You are not alone loll haha
Here's my take on this problem:
- Convert the times into integers (minutes, so 2:00 becomes 120)
- Calculate the free time (pairs of times just like shown in video) each person has
- Make a bit representation of each minute in a day (24*60 bits), if that person has free time in that minute, set that bit to 1, 0 otherwise
- Do an AND operation between the bit representations of free time of every person (joining everyone's free time)
- Convert that bit representation back to pairs of times. If the time range is greater than 30 minutes, then accept that pair
- Profit
You can implement that with constant extra space (if you needed to find availability of 3 or more people at the same time), and time complexity is O(n + m): N is for number of calendars being read (2 in that case) and M is the total number of existing meetings
nice
nice
same idea. nice.
This is a bit overcomplicated of a solution, having to parse every minute isn't very efficient.
I dont understand a single thing you just said. But im intrigued
Well my self esteem has been destroyed
Same, I actually feel like I'm hot garbage straight from the nearest dumpster. I'm 22, one semester away from an associates (transfering to umass lowell for bachelors) and i felt pretty good about myself until i watched this. oh well; congrats to him, his effort has paid off
@@vladventura1928 Mine too. I was thinking that Google is peanut butter but after watching this I understand that I've to do so many things to get that position.👍👍👍👍👍
@@yashpandey350Google hires top talent, ofc it's the ones who put in that extra effort and go the extra mile that get in FANG.
even more so because he's 19 haha
Solving lots of problems should help big time imo
I've landed the job I wanted but I still get super stressed seeing videos like this.
What's your job
@@udbhavtiwari1682 full stack dev, making software for banks
I would say this is the most realistic coding interview in this channel. Others, who came here (like William lin) were godlike in their algorithm and coding skills, Tim certainly is more relatable candidate. I am about his age, and studying in college (in 2020) too. So, awesome experience for me
how i'd do it:
1. create list of meeting segments with length = meeting time from max(start_times) to min(end_times)
2. start on list 1, cut segments from available list that fall within each unavailable segment
3. repeat for n
4. create available meeting times from joinable meeting segments
unless this was server side work in which case i would just redo the oracle so that it could all be done in sql
I think it is funny that the GOOGLE interview is on Linux on firefox and the headphone he is wearing are Apple Airpods
Fun fact, most google employees use linux
Aphotic Of course, their servers run on Linux so it makes way more sense to use a UNIX system vs ChromeOS lol (or Windows)
@@henrylecompte4533 jup makes sense... but they do make Google Pixel buds etc.
1st function: find the possible start times and durations for each person based on their schedule and limitation (working day duration etc)
2nd function: find values within the array of starting point of a person falls between starting point plus duration of the meeting (30 min) of the second person starting point and endpoints of second person is greater then first person
Giorgi Giorgadze english pls
I'm going to follow along and pause the video before Tim works on an answer and see how I solve it vs how he did and how long it takes me. Thanks for putting out this content, it is very helpful!!
That's a great way to extract as much value as possible from these mock coding interview videos!
did u do it?
Sadegh Afshari no it’s been a month now and he’s still working on it
@@efrainmoreno1154 lol
@@efrainmoreno1154 lol
One note, as you are going through your logic I would recommend as I like to do, building out a scaffold with comments documenting your "thinking out loud" in sudo logic. This way when you get into code mode, it is much easier to retrace your steps. Food for thought! Great video! It was super interesting learning how Google does it.
Good advice. Also: where you write "sudo", you probably mean "pseudo", which is indeed pronounced like "sudo". Not trying to be a know-it-all, just correcting you if you're open to that and if you weren't already aware.
@@Ruktiet Well actually sudo is used in unix so they probably just mistakenly used the wrong spelling.
Great Channel. What I appreciate in your "interview" videos is the fact that you concentrate a lot on the interaction between interviewer and interviewee.
Making clear the problem is a huge factor, there actually you get your answers for your solution. I hope all the students that are looking for an internship are watching this.
Wish you good luck with the channel, very good content!
Me in 58 minutes
Printf; ("hello)
Charles Khedia that ones gunna need a bit more work lol
for i in range(1,10000000000000000):
print("I want to learn machine learning and AI")
i+=1
@@abskamo7483 you don't need increment I in a for loop.
Lol
@@abskamo7483 y the increment tho?
He mentions his OCD will kick in, and then he put the available time of person2 in the first place, available time of person1 in second place, and in one set he uses double quotes and in another one he doesn't...
it's just showing off lol
I can confirm CS students deal with a lot of of calendar and comparison problems lol
I feel like Google would benefit from just creating their own collaborative coding environment as a replacement for Google Docs in this situation
Rad Rad there’s google collaboratory, I use it to test short, simple programs in python at work on google chrome bc IT doesn’t let us install anything :/
Tons of environments DO exist for this purpose. I've interviewed at FAANG companies and have never once been asked to code in a word processor
Because the aim is not to see if the interviewee can write a runnable code because sometimes they mess up the syntax or have typos or whatever, they can always google it even at work. The aim is to check if the candidate can come up with a logical solution that works and has the ability to translate that to an understandable pseudocode, something you'll have to do at the job. Sure, Google can come up with something for that but why invest time and money on something that Google docs does well already.
@@nav_pk sure, but you could use an editor that doesnt spell check and capitalize on new lines. Same reason I don't write code on my phone.
@@codypatnaude9171 during proper google interviews they turn off spell check and calitalize new lines and all the "auto" features. its essentially a textpad.
At the beginning i thought, what the hell, isn't this really simple? But to see Tim struggle made me actually think, maybe it's not that easy.
I would do it actually a little different:
First find the maximum day starting boundary. In this case person 2.
Set currentTime to this day boundary
From there
1. go to other persons calender
2. check if they have time : (find first meeting ending over your current time. see if according starting time is less then current time)
a if they have time
a1 get from each calendar the lowest starting time of a meeting >= current time (if no meeting get day end boundary)
a2 select the minimum of both as currentEndTime
a3 add element currentTime, currentEndTime to available time frames
a4 set currentTime = endTime of meeting which started earlier and repeat from 1
b if they have no time
go to ending of the meeting currently in and repeat from 1
3. elimate timeframes less then needed time
“That’ll append our pointers”
Huzzah! A man of culture
@@TheCarmacon I'm guessing that it's because he writes in Python
how pythonic of him
I have an Interview coming up for the Google internship. This is really going to help. Thanks man love the channel
Glad you found the video helpful, and good luck on your interviews!
Baleful Strike how did it go? all good?
20:40 That moment of realisation.
I'm always impressed by coders intuition, i've tried coding several times and it never quite clicks with me. Props to everyone out there who has the skills for it.
stephen _q practice, practice, practice
In my opinion, this capacity for intensive critical thinking in a super short time frame comes as a result of lots of testing ones own knowledge. He is a CS college student, so he is constantly being tested on his code and his abilities, and the sheer amount of projects you do and the objectives you try to accomplish manage to pull an impressive amount of intuition out of you. The kind of highly time-sensitive intensive programming skill required at these interviews is something he has likely been developing for years, even without knowing it.
Easy looking questions with deep algorithms inside.
“This is so easy he can just..... wait no that doesn’t work”
@@Adam-de8jm literally every time i try to solve an algorithm
now tim works in microsoft
few years later
tim : microsoft coding interview with bois
I know this video is old but I found a beautiful solution and I couldn't find any comment showcasing it so I thought I might aswell do so. The algoritm starts by creating 2 arrays (one for each person) that represent the free blocks of time throughout the day. We don't need the elements of the arrays to be pairs of times but rather we can create our own data type that represents a given time and wether or not it is the start or end of a free block (for example time=13:00 start=true). For example if lets say one person is free 12:00-13:30, instead of storing the pair[12:00, 13:30] as an element in the persons "freetime-array" we could store the 2 elements e={time=12:00, start=true} and e2={time=13:30, start=false}. We then sort the array in increasing order with respect to the time variable and get a useful way to represent the "freetime-array". We then create a third array that consists of all elements from both of the previously described arrays (both of those are the same btw, just for the two different people). If we sort the third array, once again increasing order according to time, we get something wonderful. What we have done I basically sort of merged together both persons blocks of free time. Lets call this third array a3. Now comes the clever step. We will look for indices j such that a3[j].start and !a3[j+1].start. The time in-between a3[j].time and a3[j+1].time will be time where both people are free. Its easy to verify this (tip: there are basically 2 different cases. Either both the element at j and j+1 come from the same persons free time-array or they don't)! A little harder to verify is that checking for all possible j:s will give us all such interval where both people are free but tbh its pretty straight forward aswell. Yeah so thats basically it
I am currently having an interview. This was just what I needed!
Perfect timing!
You should probably focus on your interviewer
yeah what are you doing why are you on your phone
So, how did it go?
This reminds me (just a tiny bit) of the interview I've got for a full time job.
Except it was a general culture thingy instead of an actual algorithm to create.
That was a great video ! :)
Amazing video, really gives a reliable picture of what an interview is all about. I actually paused it and came out with a nice solution to the first approach that Tim suggested. I think that by holding the numbers in a class containing the start/end times (instead of [0] and [1] indexes), and adding some useful functions to it like a function that takes another object of that class and gives you the overlapping time between them as an object of that class - the code may become much more elegant and readable (I believe even more readable than the single list approach) but naturally much more difficult to do in 45 minutes time unless if you're very used to creating those handy classes naturally. Thanks so much for uploading it, and good luck Tim!
This question is a fairly simple question. He is all over the place. The key is first to find the "available time" and focus on it for both parties and change the variable type from string and apply the boundary or rules. Then do the arithmetic by exclusion to remove useless data array entry and inclusion to compare the 2 arrays after the exclusion
And then there’s me getting an error in my hello world program 🤣😅
feel you bro
you are not alone
I can't CS to save my life!
sometimes when I'm trying to experiment I just want an output to be error so I know exactly what is "that" capable of doing, so if I get some output I'd expect, I'm just like "fine, whatever", but when I get error or some crazy stuff as output, then I learn much more, because I know what I can't expect from "it" to do. so in my opinion, errors and crazy outputs makes you better programmer.
i didn't have problem with the " hello,world" .
but the first time i got a bug was when i was making my first GUI with Tkinter .
later i find that the solution was so easy that i was thinking how stupid i was
I think I will forget everything when I get to interview🤣🤣and Here am I who want to work in google but doesn't even know how to print a simple pattern😭😭😭
Quick useful info for comparing time strings when it is in military format, there is no need to convert the string into hours and minutes, one can actually just compare the two strings with normal string comparison operators and the result would be as expected.
Thought the same
Hello everyone! I came across this video today and found the problem very interesting! So what I decided to do, was pause the video after Clement gave Tim the sample input/output and coded it myself (to skip to the point, I attached my Java solution below)! I did everything in a google doc and it took me 45 minutes to write the solution.
Once I had written the solution, however, I wanted to check my answer! Thus I moved everything over to my IDE and changed the auto-capitalization from google doc and other errors such as me missing parenthesis and such. But voila!
Once I fixed all of the general typing/spelling errors, I ran my code and it succeeded! It produced the same output as the sample output given in the video.
I thought that some of you may be interested in seeing a working solution, so here I am providing mine! I wrote my solution in Java and here is the google doc link of the cleaned code. Also, in case you were wondering, I wrote the documentation as I was solving the problem. I did not go back afterward and add the comments.
Enjoy! This was an awesome problem to solve!
docs.google.com/document/d/1O9oAP24bnS5T4uoVxjcJL7CPtHxjKWalXwen_VVeDRY/edit?usp=sharing
P.S. I'm a junior at the University of Washington, double majoring in Computer Science and Comprehensive Physics, just incase you we're wondering what my background is :)
wow! I was so excited to resolve this exercise by my own skills, this guy really good
They care more about how you work with the interviewer than how you actually code the problem like anyone can code but not everyone can work together in a team.
When you have been working as a developer for e while and see and student cracking hard questions ....
if the meeting is in blocks of 30 minutes, then we can create a hashtable upfront between overlapping bounds (say 9am to 6pm in 30 minute increments) then filling each slot by running over each person's calender once.
hash["9:00-9:30"] = 1
hash["9:30-10:00"] = 1
hash["10:00-10:30"] = 0
..
for a meeting from 9:00-10:00 then collect all keys with 0s (free times) and build range. This way it is much easier to merge multiple calendars and not just two.
Wouldn't it just be easier to convert everything to minutes and use set theory
More math less coding but gets the problem solved
could you please elaborate?
What I thought, I will try to implement it
so much talking on an easy problem
yup, its just the intersection of two sets, and then a subset of that set
Thats how i solved it. A couple of loops will do most of the job
My idea for first question. (Before I watched on)
Step 1: Declare a list of all the minutes in the day. (1440 minutes) e.g. List DayMinutes. Get start of day in UTC minutes and have 24x60=1440 consecutive numbers
Step 2: Convert the calendar time strings into integer representations of the minutes in the day. Note these should both be UTC formats or similar for compatibility with different days
Step 3: For each persons calendar
Step 4: For each block in the calendar
Step 5: Delete from the list of minutes (DayMinutes), all of the minutes described by the calendar block. (So iterate through DayMinutes. If its equal to the startvalue, delete it and all the next ones until you reach the end value). Also delete all of the minutes outside peoples working hours
At this point you will have a reduced list of all the minutes that EVERY participant has free that day. (Could be more than 2 people)
Step 6: Write a function that checks for consecutive numbers in that list. (If DayMinutes[n] = DayMinutes[n-1] + 1 its consecutive. Otherwise its a jump) Record the jump positions to work out consecutive block start and end times, and note the length of the current consecutive block
Step 7: You are looking for sections of consecutive numbers of length greater than or equal to the meeting length (e.g. 30). If your consecutive numbers are greater than the meeting length, add the start and the end of that consecutive block to your output
Step 7: Convert back to time strings
You will end up with an output of all the blocks longer than the meeting length, which every participant has available.
A simple solution to the Calender question:
The times were given already, first we had to find their time gap blocks, then find the time block in which both were available :
['10:30', '12:00'], ['13:00', '16:00'], ['18:00', '20:00'] - Person1
['11:30', '12:30'], ['15:00', '16:00'], ['17:00', '18:30'] - Person2
Find the maximum starting time and minimum ending time as Person2's starting time is 11:30 while Person1's starting time is 10:30 similarly the ending time is 12:00 and 12:30 respectively.
The common time for both would start with the maximum time that is 11:30 because they both are available during that time block and similarly the ending time must be the minimum time as Person1 does not have time after 12:00.
According to this algorithm, We make a new list with the maximum starting time and minimum ending time for all 3 inputs and the output is :
['11:30', '12:00'], ['15:00', '16:00'], ['18:00', '18:30']
Though this is when there is no 30 minutes time block assigned.
What a great problem. I'm going to try to do this in one pass by starting with the person with the earliest start time and then track gap time based on the meeting starts and ends without any internal loops. It was very helpful listening to your discussion/feedback. Algoexpert sounds like something I need to try out.
This problem can be solved very easy in O(n), just create a bool array of 24*60 if the meetings can be scheduled at every minute, or only 24*2 if the time blocks are 30 minutes, iterate through the calendars and convert the starting and the end points to int and mark all the values as 1. After make a for loop starting from max(boundaries_person1_start, boundaries_person2_start) until min(boundaries_person1_end, boundaries_person2_end) and append to the solution list all the free sequences.
Great :)
I would expect an actual coding interview to generalize the problem to something like this:Given set A contains N segments, each segment is defined as [A[i].l,A[i].r] with -10^9
Was thinking the same.
@@netbotcl586 That is a totally different problem, Clement said that the input format is in military time from the google calendar, no clock has 1e9 : -1e9
@Mihaela Badea I think they are kind of similar because they are both the overlapping subsegments problem type. I don't think the input format matters too much in this case.
As a prospective high school student looking into CS, I really enjoyed this. I think problem solving like this is just so interesting and I could imagine myself pursuing a job that's problem solving heavy like this. Thank you very much, great content!
We had this question as an assignment during our second programming course in comp sci & software engineering :D
My first thought was how is Tim going to gain Clement's Google calendar auth token -_-
what school do you go to?
Interesting question. I am happy to see something different! I am sick of seeing recursion questions. Took maybe 1.5 hours around 100 lines of code used c#. I actually ended up doing what Tim wanted to do originally before you changed his mind. I found it more logical as a human to take this approach! You find the available time with both schedules (inclusive of the day start and end boundaries). These results are passed into a method that finds overlapping available time of the schedules. The overlapping spare times are compared with the meeting length requirements to produce the suggested time slots. Highly re-usable and writing it like this I can compare more than 2 schedules for availability (Even could specify who can and cannot make it during a time slot).
I'm a fan of this two guy . I've been following this channel and also tim
In simple mathematical terms the question is to find the set intersection between two sets of time (free time) and check if it is more than 30 minutes. May sound easy but actually requires a lot of concentration while solving this.
Having watched these mock interviews, it almost feels like that the interviewee has to follow a script-
* ask for sample input / output.
* then ask the interviewer if your assumptions are correct. ask if this kind of input will be allowed or not allowed
* don't stay quiet at all, speak whatever comes to mind.
* figure out a naive solution
* interviewer will tell you edge cases and perf issues.
* then just keep communicating whatever solution (even if you're not sure if it will fully work).
* in code, assume helper function and data structures like stack exists.
* give complexity analysis in the end.
How can mere mortals figure out the right solutions while doing all the above is beyond me. Thank god I do frontend development. Spared for now.
BTW thanks for making this video Clement. Keep rocking
I think your "script" isn't too far from the truth, *but* I would argue that it's not so much a script as it is the general ideal way to go about solving this type of coding problem collaboratively. Oh, and mere mortals can figure out the right solutions while doing all this with some practice! (This is where I'd plug in AlgoExpert 😛)
I hope you enjoyed it; keep rocking as well!
To me that just seems like a very natural way to show how you solve a problem in front of another person.
bro can u tell me this answer in hin hindi
The questions you ask the interviewer change the process a lot, so it can't really be called a script. But, generally your outline is how you solve any problem, so you're not really adding anything novel.
"""Coding challenge to take 2 peoples schedules and find a time for an interview"""
calendar1 = [["9:00", "10:30"], ["12:00", "13:00"], ["16:00", "18:00"]]
bound1 = ["9:00", "20:00"]
calendar2 = [["10:00", "11:30"], ["12:30", "14:30"], ["14:30", "15:00"], ["16:00", "17:00"]]
bound2 = ["10:00", "18:30"]
BLOCK = 30
unavail =[]
avail = []
def s2m(time):
"""convert a string in the format of HH:MM and convert to minutes"""
hour, minute = time.split(":")
minutes = int(hour) * 60 + int(minute)
return minutes
def m2s(time):
"""convert time from minute to HH:MM formated string"""
hour = time // 60
minute = time % 60
return "%02i:%02i" % (hour, minute)
def cal2min(cal_list):
"""converts calendar from text to minutes"""
a_list = []
for item in cal_list:
start = s2m(item[0])
end = s2m(item[1])
a_list.append([start, end])
return a_list
def min2cal(min_list):
"""converts calendar from minutes to str"""
a_list = []
for item in min_list:
start = m2s(item[0])
end = m2s(item[1])
a_list.append([start, end])
return a_list
def get_bounds(bound_list1, bound_list2):
"""determines the earliest and latest times for a meeting"""
start1 = s2m(bound_list1[0])
start2 = s2m(bound_list2[0])
end1 = s2m(bound_list1[1])
end2 = s2m(bound_list2[1])
bounds = [[0, max(start1, start2)], [min(end1, end2), 1440]]
return bounds
def get_avail(unavail_list):
"""finds all of the available times for the meeting"""
start = 0
end = 0
a_list = []
for item in unavail_list:
start = item[0]
if start - end >= BLOCK:
a_list.append([end, start])
end = item[1]
return a_list
bound = get_bounds(bound1, bound2)
newcalendar1 = cal2min(calendar1)
newcalendar2 = cal2min(calendar2)
unavail = bound + newcalendar1 + newcalendar2
unavail.sort()
avail = get_avail(unavail)
str_avail = min2cal(avail)
print(str_avail)
This code will not work for all the cases. That is the nice of this problem!
youre wasting time convertime the string into minutes. remember to not do things that aren't necessary. if the client asks for strings why give them ints. you could easilly turn the ints back into strings but then thats another step. this would be very slow if youre trying to setup a meeting for 100000 plus users
@@kouyang1771 The conversions are necessary to be able to do meaningful comparisons. The scope of the project was not for 100000 plus users. It is for two.
@@albertopatino7244 The cases are provided, and it solves the problem.
@@anthonydickerson4627 I forgot to include test set. Change:
calendar1 = [["9:00", "12:00"], ["12:00", "13:00"], ["16:00", "18:00"]]
#calendar1 = [["9:00", "10:30"], ["12:00", "13:00"], ["16:00", "18:00"]]
You could create an array of every minutes during a day(1440), and remove items from the array for the unavailable mins for each person and also the out of bound times. In the end you would just create a list of available blocks of times from the remaining items in the array.
Yes - also easy to generalize to any number of participants / calendars
wow Clément is a genius, It takes time to interpret and understand code from another person, he did it immediately, even better than Tim, just WOW
Now I know why I can’t work at Google
It's not that difficult dude.. you just need to practice...
Tbh i too easily found a way to do this...but when he mentioned tuples of available time.. it instantly hit me..damn it was so much easier...
It's all about practice and tbh some luck too ..if you're able to luckily hit the right idea...
Keep working hard ... All the best
Its not like its impossible. You need to stop making a big deal out of it.
This is a simple merge interval problem
@@tahaqtr7439 It isn't simple for everyone. No need to be a dick. You didn't start out as a pro...
hahaha I feel you :D
My method:
Ultimate available time will be [0, 24]
Then get rid of all occupied time interval in the [0,24], we will have all free time intervals. Save as two new 2D arrays.
Check overlapping time intervals in two arrays, then we have the answer of time to set up meeting.
I didn't try to write the code, so, please correct me if my method's impractical, or this algorithm's actually very slow. Thanks.
I feel stressed watching this LOL
At 24:00, there is no need to merge the times. Instead of merging the times, just skip the first item in the list. More generally, from the first to the second-to-last element, make an 'availability window' comparing the ending time of the current window with the starting time of the next one. If there is no availability greater than 30 minutes in between (end > next start + 30), don't add a window. Otherwise, add a window containing that time.
Hello Clément thanks for sharing those tricks with us, and please keep making free content like this you are a source of inspiration for many college students and developers in many countries.
My initial thought upon seeing this question was as follows:
A Person = [10:30 - 12:00, 13:00 - 16:00, Append(18:00 - 20:00) ]
Bounds A = [09:00 - 20:00]
B Person = [11:30 - 12:30, 15:00 - 16:00, Append(17:00 - 18:30)]
Duration = 30 minutes
BoundsB = [10:00, 18:30]
Times Those two People are available
---------------------------------------------------------------
A Person =[[10:30 - 11:00][ 11:00 - 11:30] [11:30 - 12:00], [13:00- 13:30],[13:30 - 14:00], [14:00-14:30],[14:30-15:00],[15:00-15:30],[15:30-16:00],[18:00 - 18:30] , [18:30 - 19:00], [19:00 - 19:30] , [19:30 - 20:00]]
B Person = [[11:30 - 12:00],[12:00 - 12:30],[15:00- 15:30], [15:30 - 16:00], [16:30 - 17:00], [17:00 - 17:30], [17:30 - 18:00], [18:00 - 18:30]]
Intersection = [11:30 - 12:00] , [15:00- 15:30], [15:30-16:00], [18:00 - 18:30] ==> Answer
😂
I just looked and saw the answer...but I guess you have to demonstrate all this in the interview
Was subscribed to Tim long time ago happy to see a collab between you ✌🏻☮️
Neeraj Bhatt 💪
when comparing 2 blocks , get the max start time, compare it to the min end time and check if there's enough to have a meeting, if there's enough to have a meeting, add the array of max start time to min end time to the output.
Pro tip: you can disable automatic capitalization in Google Docs.
(You could also use google collab)
Change font to Courier New
Solved task more universally using arrays of minutes from 0 to 23*60+59 filled by 1/0 - available or not at this minute. Then multiply two arrays per item and find a sequence of 1s greater or equal to needed.
for the calendar,
lets assume these are available time:
[a1, b1] for person 1
[a2, b2] for person 2
just compare a1 and a2, look for the higher then compare b1 and b2, look for the lower
the higher and lower are the time frame available.
the student is making things complicated
was thinking pretty much same thing, seems way more complicated than it needs to be
Will it work tho? This is assuming they have equal length arrays. What if one person has additional meeting slot, resulting in different array of available time length. Meaning person 1 has [a1, b1], [c1, d1], [e1, f1] then person 2 has [a2, b2], [c2, d2], [e2, f2], [g2, h2]. what do you compare g2, h2 with?
I paused this video as soon as you asked him the question and although it took me a while, I managed to solve it. It's funny, I spent ages trying to figure it out in code, then I just drew it out on paint and solved it in a few minutes, then just had to transfer it into code, which was much easier after solving it by drawing it. I'm loving these problems, I think you're getting me addicted to them. Every single video of yours now I'm pausing and doing them. They are really fun questions!
@Clement your mock interview videos are awesome and we love it and we want to see more of it, just a suggestion that you can pick your top performers from AlgoExpert and interview them on TH-cam. I'd love to see this on TH-cam and I'm sure people would too :-)
This is a really cool idea! Thanks for the suggestion; I'll see what I can do 😛
I really love this video. It is very informative. I also want to say that Tim did so well in nailing the framework of the solution to the problem and finally writing such a code not too complex to understand.
Google DOCS is my ide starting today.
So much cringe.
Filelor 😂
Much simpler solution is just go over all the times boundries in order, and just add 1 for each "beggin" and subtruct 1 for each "end", if you reach 0 its free time for both
"Military time" aka universal "24-hour time"
i love clement's smile of like proudness when tim get's on the right track its fckn adorable
The whole interview you were staring at his algorithm while tossing your head around.
1. Convert time values into real numbers. Ex. 10:30 -> 10.5
2. Take the highest of the lower bound time constraints (x), and take lowest of both upper bound time constraints (y).
3. From x to y look for free times for both.
4. Compare times with the real values
Value1 =? Value2
The collab i was waiting for!!!How did you read my mind Clement???
Wait, you didn't know? Clement the Mind Reader Mihailescu didn't give it away? 😎
Nice pfp
1. Break the daily bound timing into 30 minute time intervals. Write base code to break given time to 30 minute intervals. Eg. Daily bound = (1000,1800)=(1000,1030)(1030,1100)(1100,1130),…
2. Compare daily bound timings and person A’s occupied timings, find available timings of person A.
3. Compare daily bound timings and person B’s occupied timings, find available timings of person B.
4. Compare time available for A&B and give the out that matches for both.
Clem, please write the full question statement at the beginning so we could try to answer the question more easily.
I'm a third year software engineering student and I wouldn't have known how to do this. Well rip my job hunt in the future
don’t you just combine the two calendars into one, find the empty spaces keeping bounds in mind, and check if the blocks are at least the time given for the meeting?
Yes
didn't they just do that?
Just wanted to know, could they have taken the available slots of 30 mins of both calendars and then found the common one between them.
@@tauqir_admani I thought about that, too. I wonder if that would be less efficient.
Muhammed Tauqir then you’d have to check minute by minute. If I’m available 10:30 - 11:00 and someone else is available 10:08 - 11:08, solving that would require that I go minute by minute and check the next 30 minutes. You can’t just split everything into blocks of 30 or you’d have 10:08-10:38 and 10:38 - 11:08, neither of which fit the original person’s 10:30-11:00 schedule.
Having a guess at the bug: the pointers might be incremented to beyond the length of the corresponding list, but as the while condition is p1
interview: "write me an algorithm to count the number of times I nod in this video"
Let nodCount = 0; On Nod => ( nodCount += 1 );
1) get the available time for both
2)check if the available time is enough if not get rid of
3)check if the starting of one's available time is between the other one's available time.
4) if yes then check if there's enough time that is end -other one's start
That's it, but pressure is a big thing in a interview
Me, an accounting student, who has an exam tomorrow (or today) : I don't know what I'm watching but yes tell me how a Google coding interview works
same here but thinking about switching to computer science.
Very nice question. I was screaming “overlapping intervals” at my screen the whole time but then realized the dude is 19 and I was like “I couldn’t even add 2 and 2 at 19 and this guy is solving this question on demand”
Very nice video
For i in range(1000):
Print("thanks to tim and clement")
My algo will be
1. Find the shortest duration for arranging the meeting. For e.g., Person2 accepts meetings between 10 to 18:30 only.
2. Create a master dictionary / list with half hour slots from 10-18:30
3. Delete all slots from dictionary with Person2's meetings in 30 mins slots. (converting string to numbers will help)
4. Now use Person1's booked time and delete master list time slots. Since the master list starts at 1000, anything less than that won't be considered like 900 (for 9am). Similarly greater than 1830 won't be considered.
5. Whatever 30 mins slots are remaining in master list will be the answer
20:15 That time when clement's solution is simpler and much more elegant than mine haha! Thank you Clement, this video helped me a great deal! Will interviewer also give clear hints like clement did?
Glad you found the video helpful! And normally, a good interviewer _should_ give hints when appropriate or necessary, but interviewers come in many flavors, so you never know 😛
how long did it take when you tried?
my solution is pretty simple: add to a vector the earliest starting point and the latest starting point of each block, where a block is the time between 2 occupied blocks) then, by iterating through the vector, i can find for the start of each block the earliest that both can start an interview(that'd be the greatest of the earliest numbers) and the latest that they can start(that'd be the smaller of the latest of their block), do that for every compatible pair(you'd move on both vectors when a start time is no longer compatible). complexity O(N), where N is the number available blocks(N is between greatest number of blocks and greatest number of blocks+2)
i'd use pairs to represent those values(that may be confusing in my explanation). also, i came up with that in like 10 seconds