5 ms·

OK, but I got this question: http://www.geeksforgeeks.org/given-n-appointments-find-conflicting-appointments/ http://www.geeksforgeeks.org/given-n-appointments

by nissimk 10y ago

OK, but I got this question: http://www.geeksforgeeks.org/given-n-appointments-find-conflicting-appointments/ http://www.geeksforgeeks.org/given-n-appointments-find-confl... It requires the simple comparison you mentioned, but is far more complex to come up with an efficient algorithm. Needless to say, I totally failed that one. Never heard of an interval tree until I looked it up after the interview. It took me just a moment to look it up with my awesome google skills and if I had to actually use that, I could copy paste that code in an instant :-) Even better, I could find a library and not even have to copy paste. One time I was working on a language translator at my actual job. I was storing formulas for excel columns in a database and they had to be translated from their representation in the database to the excel formula language. It turns out that the columns had dependencies on one another and they had to be processed in dependency order. This required something called a topological sort. Again, something I had never heard of before I encountered this problem at work (I do have a CS degree). But I found the solution by a quick google search and employed a library that was already in use in my client's software that contained that algorithm. That's the actual skill that's valuable: translating your requirements into a bunch of search terms that will quickly give you the name of the algorithm you need. (and obviously building the inputs / working with the outputs of that algorithm). Yeah, I guess if you already have all of those in your in your brain already you might save some time, but what about when you encounter a problem you don't know how to solve?

rnovak 10y ago
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.
- meheleventyone 10y ago
  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.
  - rnovak 10y ago
    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.
    - meheleventyone 10y ago
      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.
      - rnovak 10y ago
        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?
        falsedan 10y ago
        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.
btschaegg 10y ago
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.
tzs 10y ago
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".

by nissimk 10y ago

rnovak 10y ago

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.

meheleventyone 10y ago
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.
- rnovak 10y ago
  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.
  - meheleventyone 10y ago
    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.
    - rnovak 10y ago
      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?
      - falsedan 10y ago
        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.

btschaegg 10y ago

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.

tzs 10y ago

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