8 ms·

I'm not a programmer but wouldn't if (endtime[1] > starttime[2]){status=conflict} work? Assuming time is encoded in epoch format.

by pinot 9y ago

dragonwriter 9y ago
And assuming that "1" and "2" refer to the appoints in order of start time, but they may not be given in that order.
rezashirazian 9y ago
also if (endtime[2] > starttime[1]){status=conflict}
dcwca 9y ago
That's half of it, but doesn't account for the case when starttime[1] is later than endtime[2] and they don't intersect.
- pinot 9y ago
  Good point. I didn't think about them not being written down in the list in chronological order by start time.
- hoosieree 9y ago
  It works if you assume that appointment 1 starts before appointment 2 starts (or if you explicitly sort them by start time). e.g. in J: 'a b c' =: 50 60 3 4;3 50 49 99;2 10 10 12 NB. 3 different sets of appointments 3 :'ok`nope{~0>*./-~//./:~_2]\ y' every a;b;c ┌──┬────┬──┐ │ok│nope│ok│ └──┴────┴──┘
deleted 9y ago
[deleted]
aldarn 9y ago
This is close but you need to ensure the start time is before the other ends, and test for the second one starting before the first also. There's four cases: [appointment 1 start] [1 end] <-- some time --> [appointment 2 start] [2 end] (case 1 - no overlap, appointment 1 first) [appointment 1 start] [appointment 2 start] <-- some time --> [1 end] [2 end] (case 2 - overlap, appointment 1 first) [appointment 2 start] [appointment 1 start] <-- some time --> [2 end] [1 end] (case 3 - overlap, appointment 2 first) [appointment 2 start] [2 end] <-- some time --> [appointment 1 start] [1 end] (case 4 - no overlap, appointment 2 first) So you need to do: if (appointment1.end > appointment2.start AND appointment1.start < appointment2.end) OR (appointment2.end > appointment1.start AND appointment2.start < appointment1.end) // conflict
- kornish 9y ago
  > if appointment1.end > appointment2.start OR appointment2.end > appointment1.start // conflict This actually isn't correct. Consider the events (0, 3) and (4, 6). The end of the second (6) comes after the beginning of the first (0), but they don't conflict. You want `and`, not `or`. EDIT: oops, just saw you edited it. Good catch :)
- jon_richards 9y ago
  Your cases don't consider [1 start][2 start][2 end][1 end] or the opposite, but your pseudocode still covers those cases.
  - aldarn 9y ago
    True, I didn't include those cases as they are not unique in terms of why there is / isn't a conflict. But you're right, worth including for completion.
  - tzs 9y ago
    > Your cases don't consider [1 start][2 start][2 end][1 end] or the opposite [...] Your notation there, where instead of a pair of start/end pairs you have a list of tagged times, reminds me of a good approach if one is doing a generalized version of the problem: given a list of N appointments, find conflicts. Make a list of tagged times, where a tagged time is a triplet (time, 1, name) if appointment named "name" starts at time "time", and is (time, -1, name) if appointment named "name" ends at "time". Sort the tagged time list with time ascending as the primary sort key, and the start/stop tag ascending as the secondary key. Now to find conflicts you simply scan through the tagged times list, keeping a running total of the start/end tag values. If the running total is greater than 0 when you begin to process a given entry, that entry has a conflict with an earlier appointment, and the running total is how many earlier appointments it conflicts with. As described above, this lets you print a list of what appointments have conflicts with earlier appointments, but it doesn't give an easy way to say which earlier appointments conflict. If you want to do that, it is straightforward. Just add a set data structure, and during the scan of tagged times add "name" to the set when you encounter an appointment's start, and remove "name" when you encounter an appointment's end. When you find a conflict, the set contains the names of all of the earlier appointments the present appointment conflicts with. The above assumed that two appointments do not conflict if the ending time of the first is the same as the starting time of the second. If that should be counted as a conflict, just change the sort so that the secondary key is sorted descending instead of ascending.
d0mine 9y ago
To find whether a and b intervals overlap (ends are not included): overlap = a.start < b.end and b.start < a.end
- d0mine 9y ago
  Why is it downvoted? The formula is correct and it is simple -- if you don't understand it, just ask.
e12e 9y ago
I'd say so. The "assuming time encoded"-bit is important though - I rather think starting with the data is valuable: Can I assume the times are in a sane date format/datatype? If not, start with e1 = toSaneDateFormat(endtime1), s2 = toSaneDateFormat(startime2) (Fill in if interviewer is interested). Then, as you say, a check for overlap is easy - but maybe one wants to be more fancy, like: if (timeDelta(e1, t2) < timeToWalkFromAtoB, or < 5 minutes -- they should be considered an overlap? If they are on different continents, maybe < 24 hours should be an overlap? At any rate, I'm guessing (hoping) this leads to discussions about representing dates, and what the business logic is (eg: physical meetings - you can't teleport from one location to another). [ed: And as others have touched on, if you deal with timestamps/raw number types - be careful that you don't end up with appointments in "wrong" order - I'd say a sort() aware of date-objects might be your friend here. ed2: In fact, if you can assume a sane date-type, and timeDelta, you could probably assume an "interval" type, and simply ask for overlap?(appointment1, appointment2) ... ]
- aldarn 9y ago
  This is a great example of why the OPs question could be a good or terrible interview question -- it's not clear if they want the obvious technical solution (comparing datetimes) or a wider discussion about "what is a date time and how is the data represented", "what are the real world / business implications", "here is existing technology using intervals that will solve it" etc as you mentioned. In my experience interviewers are usually looking for the technical solution despite the business oriented solution usually being much more applicable (and thus relevant) in the day to day role. Key thing to remember here as an interview candidate is to clarify with the interviewer the scope of the question and the nature of the answer they're looking for. If for instance the interviewer starts with the simple technical solution and then probes the business aspects this might be a nicely rounded question.
  - Benjammer 9y ago
    My company asks a question during engineering interviews that is overly simple, but a bit vaguely defined on purpose. The main objective is to see if they can ask clarification questions to determine precise requirements, which is something that every engineer does daily on the job.

I'm not a programmer but wouldn't if (endtime[1] > starttime[2]){status=conflict} work? Assuming time is encoded in epoch format.

by pinot 9y ago

I'm not a programmer but wouldn't if (endtime[1] > starttime[2]){status=conflict} work? Assuming time is encoded in epoch format.

dragonwriter 9y ago

And assuming that "1" and "2" refer to the appoints in order of start time, but they may not be given in that order.

rezashirazian 9y ago

also if (endtime[2] > starttime[1]){status=conflict}

dcwca 9y ago

That's half of it, but doesn't account for the case when starttime[1] is later than endtime[2] and they don't intersect.

pinot 9y ago
Good point. I didn't think about them not being written down in the list in chronological order by start time.
hoosieree 9y ago
It works if you assume that appointment 1 starts before appointment 2 starts (or if you explicitly sort them by start time). e.g. in J: 'a b c' =: 50 60 3 4;3 50 49 99;2 10 10 12 NB. 3 different sets of appointments 3 :'ok`nope{~0>*./-~//./:~_2]\ y' every a;b;c ┌──┬────┬──┐ │ok│nope│ok│ └──┴────┴──┘

deleted 9y ago

[deleted]

aldarn 9y ago

This is close but you need to ensure the start time is before the other ends, and test for the second one starting before the first also. There's four cases: [appointment 1 start] [1 end] <-- some time --> [appointment 2 start] [2 end] (case 1 - no overlap, appointment 1 first) [appointment 1 start] [appointment 2 start] <-- some time --> [1 end] [2 end] (case 2 - overlap, appointment 1 first) [appointment 2 start] [appointment 1 start] <-- some time --> [2 end] [1 end] (case 3 - overlap, appointment 2 first) [appointment 2 start] [2 end] <-- some time --> [appointment 1 start] [1 end] (case 4 - no overlap, appointment 2 first) So you need to do: if (appointment1.end > appointment2.start AND appointment1.start < appointment2.end) OR (appointment2.end > appointment1.start AND appointment2.start < appointment1.end) // conflict

kornish 9y ago
> if appointment1.end > appointment2.start OR appointment2.end > appointment1.start // conflict This actually isn't correct. Consider the events (0, 3) and (4, 6). The end of the second (6) comes after the beginning of the first (0), but they don't conflict. You want `and`, not `or`. EDIT: oops, just saw you edited it. Good catch :)
jon_richards 9y ago
Your cases don't consider [1 start][2 start][2 end][1 end] or the opposite, but your pseudocode still covers those cases.
- aldarn 9y ago
  True, I didn't include those cases as they are not unique in terms of why there is / isn't a conflict. But you're right, worth including for completion.
- tzs 9y ago
  > Your cases don't consider [1 start][2 start][2 end][1 end] or the opposite [...] Your notation there, where instead of a pair of start/end pairs you have a list of tagged times, reminds me of a good approach if one is doing a generalized version of the problem: given a list of N appointments, find conflicts. Make a list of tagged times, where a tagged time is a triplet (time, 1, name) if appointment named "name" starts at time "time", and is (time, -1, name) if appointment named "name" ends at "time". Sort the tagged time list with time ascending as the primary sort key, and the start/stop tag ascending as the secondary key. Now to find conflicts you simply scan through the tagged times list, keeping a running total of the start/end tag values. If the running total is greater than 0 when you begin to process a given entry, that entry has a conflict with an earlier appointment, and the running total is how many earlier appointments it conflicts with. As described above, this lets you print a list of what appointments have conflicts with earlier appointments, but it doesn't give an easy way to say which earlier appointments conflict. If you want to do that, it is straightforward. Just add a set data structure, and during the scan of tagged times add "name" to the set when you encounter an appointment's start, and remove "name" when you encounter an appointment's end. When you find a conflict, the set contains the names of all of the earlier appointments the present appointment conflicts with. The above assumed that two appointments do not conflict if the ending time of the first is the same as the starting time of the second. If that should be counted as a conflict, just change the sort so that the secondary key is sorted descending instead of ascending.

d0mine 9y ago

To find whether a and b intervals overlap (ends are not included): overlap = a.start < b.end and b.start < a.end

d0mine 9y ago
Why is it downvoted? The formula is correct and it is simple -- if you don't understand it, just ask.

e12e 9y ago

I'd say so. The "assuming time encoded"-bit is important though - I rather think starting with the data is valuable: Can I assume the times are in a sane date format/datatype? If not, start with e1 = toSaneDateFormat(endtime1), s2 = toSaneDateFormat(startime2) (Fill in if interviewer is interested). Then, as you say, a check for overlap is easy - but maybe one wants to be more fancy, like: if (timeDelta(e1, t2) < timeToWalkFromAtoB, or < 5 minutes -- they should be considered an overlap? If they are on different continents, maybe < 24 hours should be an overlap? At any rate, I'm guessing (hoping) this leads to discussions about representing dates, and what the business logic is (eg: physical meetings - you can't teleport from one location to another). [ed: And as others have touched on, if you deal with timestamps/raw number types - be careful that you don't end up with appointments in "wrong" order - I'd say a sort() aware of date-objects might be your friend here. ed2: In fact, if you can assume a sane date-type, and timeDelta, you could probably assume an "interval" type, and simply ask for overlap?(appointment1, appointment2) ... ]

aldarn 9y ago
This is a great example of why the OPs question could be a good or terrible interview question -- it's not clear if they want the obvious technical solution (comparing datetimes) or a wider discussion about "what is a date time and how is the data represented", "what are the real world / business implications", "here is existing technology using intervals that will solve it" etc as you mentioned. In my experience interviewers are usually looking for the technical solution despite the business oriented solution usually being much more applicable (and thus relevant) in the day to day role. Key thing to remember here as an interview candidate is to clarify with the interviewer the scope of the question and the nature of the answer they're looking for. If for instance the interviewer starts with the simple technical solution and then probes the business aspects this might be a nicely rounded question.
- Benjammer 9y ago
  My company asks a question during engineering interviews that is overly simple, but a bit vaguely defined on purpose. The main objective is to see if they can ask clarification questions to determine precise requirements, which is something that every engineer does daily on the job.