Hacker News Reader

Comment by pinot | Hacker News Reader

I'm not a programmer but wouldn't

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

work? Assuming time is encoded in epoch format.

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

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

Your cases don't consider [1 start][2 start][2 end][1 end] or the opposite, but your pseudocode still covers those cases.

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.

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

Does anyone really test for specifics like this? I thought the goal was to ensure the candidate understood that dates and times are abstract numbers, anyone that applies a mathematical operator should pass it. Yes this would still filter out a lot of people.

Or just sort by start time, then do the simple check.

Yeah, this is way easy if the two events are sorted by start_time first.

I was thinking along the same lines as you, but it turns out you only need two comparisons and one logical operator.

barrkel has a thorough explanation here:

https://news.ycombinator.com/item?id=14641485

Or, as I realized later, it seems helpful to me if I look at it as a practical problem instead of an abstract one:

https://news.ycombinator.com/item?id=14642059

  a = Appointment 1 start
  A = Appointment 1 end
  b = Appointment 2 start
  B = Appointment 2 end

The only predicates are: a < A, b < B

The complete set of orderings are thus:

  aAbB - no overlap
  bBaA - no overlap
  abAB - partial overlap
  baBA - partial overlap
  abBA - complete overlap of one appointment inside the other
  baAB - complete overlap of one appointment inside the other

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) ... ]

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.

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.

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.

Good point. I didn't think about them not being written down in the list in chronological order by start time.

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│
    └──┴────┴──┘

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

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

To find whether a and b intervals overlap (ends are not included):

  overlap = a.start < b.end and b.start < a.end

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

Reply on news.ycombinator.com