Not sure if I'm overlooking something obvious, but given the possibility to reduce dates/times into simple integers (doable according to the example), you should be much faster sorting the data and using and intelligent comparing than allocating a tree with O(n•logn) nodes. Those heap allocation should slow you down drastically, at least for any problem size where linear work is still efficient enough.

I do not understand the problem you linked to of finding "conflicting appointments". It does not usefully define what a "conflict" is, only saying that "An appointment is conflicting, if it conflicts with any of the previous appointments in array". It does not say what "conflict" means for appointments.

A natural assumption is that two appointments conflict if their times overlap.

The example instance of the problem gives this as input:

> Input: appointments[] = { {1, 5} {3, 7}, {2, 6}, {10, 15}, {5, 6}, {4, 100}}

The problem spoke of "appointments in array" and this is an array, so apparently {1, 5} {3, 7}, {2, 6}, {10, 15}, {5, 6}, {4, 100} are the appointments themselves. So we have 6 appointments.

So I'd guess that {1, 5} means an appointment that starts at time 1 and ends at time 5. That {4, 100} concerns me, though...if the numbers are times there is no obvious unit of time for which all of these appointments make sense.

They give this as the expected output for the above input:

  Output: Following are conflicting intervals
  [3,7] Conflicts with [1,5]
  [2,6] Conflicts with [1,5]
  [5,6] Conflicts with [3,7]
  [4,100] Conflicts with [1,5]

OK...all of those ARE conflicts under my guessed interpretation of the notation. But under that interpretation, {2, 6} should conflict with {3, 7}, and {4, 100} should conflict with everything else.

So that means my interpretation of the notation {x, y} on input meaning an appointment from time x through time y is not right.

Another idea is that {x, y} means person x and person y have an appointment together, and two appointments conflict if the same person is involved in both. Nope...that doesn't give the sample output either.

OK...maybe the sample output is wrong. So now I grabbed their code and compiled it on my Mac and ran it. It produced this output:

  Following are conflicting intervals
  [3,7] Conflicts with [-1960454340,32767]
         [2,6] Conflicts with [-1960454340,32767]
         [10,15] Conflicts with [-1960454340,32767]
         [5,6] Conflicts with [-1960454340,32767]
         [4,100] Conflicts with [-1960454340,32767]

WTF? OK...so I take it to a Linux box, and try it there, and it gives the output given at the site. Hmmm. I do see that I got a compiler warning on the Mac and not on Linux, about control reaching the end of a non-void function. The function newNode is missing a return! Putting "return temp;" at the end gets rid of the warning, and then the Mac produces the same output as Linux. (Raising the question of why gcc on my Linux box did not warn about the missing return...).

Anyway, I see that there is a function in there to determine if a pair of appointments overlap:

  // A utility function to check if given two intervals overlap
  bool doOVerlap(Interval i1, Interval i2)
  {
      if (i1.low < i2.high && i2.low < i1.high)
          return true;
      return false;
  }

OK...looking at that, it sure looks to me like it should say that {2, 6} and {3, 7} overlap. A quick test confirms that {2, 6} and {3, 7} in fact do overlap according to doOVerlap. So why isn't it figuring that out?

Putting a printout in doOVerlap to see how it is getting used:

  // A utility function to check if given two intervals overlap
  bool doOVerlap(Interval i1, Interval i2)
  {
    cout << "check " << i1.low << "," << i1.high
        << " against " << i2.low << "," << i2.high << "\n";
    if (i1.low < i2.high && i2.low < i1.high)
        return true;
    return false;
  }

changes the output to this:

  Following are conflicting intervals
  check 1,5 against 3,7
  [3,7] Conflicts with [1,5]
  check 1,5 against 2,6
  [2,6] Conflicts with [1,5]
  check 1,5 against 10,15
  check 3,7 against 10,15
  check 1,5 against 5,6
  check 3,7 against 5,6
  [5,6] Conflicts with [3,7]
  check 1,5 against 4,100
  [4,100] Conflicts with [1,5]

OK...so it is not finding that {2, 6} and {3, 7} overlap because it is never even checking them against each other.

I'll leave it to someone more curious than I to figure out what is wrong with their "solution".

PS: here is a quick and dirty Perl program to do it. I did not bother matching the output format exactly, as I just wanted to get the algorithm right. This should be O(n log n) where n is the number of appointments, assuming that the built-in sort is O(n log n) and that the built-in hash implementation is O(n log n) or better.

    my @appt = ([1, 5], [3, 7], [2, 6], [10, 15], [5, 6], [4, 100]);

    my %active;
    my @endpoints;

    for (my $i = 0; $i < @appt; ++$i)
    {
        my($start, $end) = @{$appt[$i]};
        push @endpoints, [$start, 1, $i];
        push @endpoints, [$end, 0, $i];
    }
    @endpoints = sort {$a->[0]*2+$a->[1] <=> $b->[0]*2+$b->[1]} @endpoints;

    foreach (@endpoints)
    {
        my($time, $side, $which) = @$_;
        if ($side == 0) {
            delete $active{$which};
        } else {
            print "$which overlaps $_\n" foreach sort {$a <=> $b} keys %active;
            $active{$which} = 1;
        }
    }

Idea behind this: make list of all the appointment endpoints, tagged by whether they are a start or end time and which appointment they came from. Sort this by time, with end times coming ahead of start times if a given time occurs more than once. You can then scan this list, keeping track in a hash which appointments you have seen a start time for without yet seeing the corresponding end time.

When you see an end time, you can delete the appointment from the hash. When you see a start time, the appointment that supplied it overlaps with all the appointments currently in the hash.

What happens when you're asked to solve a problem that hasn't been solved before? By definition something you CANNOT google for

That's what I was looking for as a hiring manager.

Generally you end up doing a review of relevant literature and a few days/weeks/months of research and development. I'm not sure answering a question under pressure that has just been asked is that relevant to making ground in new areas of research.

The point is that solving problems, either by inventing new computer science, or more likely formulating a hybrid of known algorithms requires some semblance of problem solving.

A genuine interviewer (and I realize several/many may not be genuine) is solely trying to figure out if the candidate has these types of reasoning skills.

Let me phrase it this way: By asking a common CS question, you'll get people who simply memorize answers/algorithms. By asking something obscure that is rarely known, you can try to get a glimpse into someone's thought process, which is infinitely more valuable than rote memorization.

Right but there are lots of ways to test problem solving skills that don't involve asking people to both solve a surprise (and obscure) problem and come up with code at the same time whilst under stress. The latter three things are probably clouding your results in a way it's not really possible to account for. It seems like a lot of people setting interviews lack a bit of empathy.

The grandparent seems like the problem solving equivalent of yelling "think fast" whilst tossing a basketball at someone's face to test reflexes.

Okay, give us a generalized example? everyone who (appears) to care about being empathetic while at the same testing for these skills is continually asking for better options.

If you're hiring a point guard, isn't testing their reflexes by tossing them a basketball a reasonable approach?

Ask a simple, standard question that the candidate could reasonably answer in 10 or so minutes, confirm it works with them, and then change the parameters to invalidate their solution?

This is the closest I can get to actual project work in 45 minutes.

The second the interviewer changed the parameters people would start complaining that they were "Setup to fail." These threads commonly illuminate that interviewers simply cannot win, regardless of how genuine they are.

That's why I recommend confirming that the candidate's first solution was right. Use lots of positive feedback: ok, looks good, that's right, that's how I would do it; I see where you're going with this; etc. Then introduce the change, with a justification e.g. the team providing the input data changed their format/guarantees/technology, and we have to blah blah blah.

Why bother? You still fail to detect candidates who memorized the answer.

My standard coding question is a funny-looking prime sieve. If someone isn't familiar with one, we can work it through together and I'll have a much better idea of their learning potential & what they'll be like to work with than the intern straight out of their Algorithms final.

Personally, I don't bother. I went the route of requesting candidates go through a work sample project that I spent a considerable amount of time trying to standardize across all the languages relevant to the role. In the end though, management wasn't for me, and so I ended changing roles for something non-managerial