4 ms·

I'm not sure that he does, I thought the same of the ad and didn't say anything but I was glad someone did. Reading in the graph and putting it in a tree struc

by bugsy 16y ago

I'm not sure that he does, I thought the same of the ad and didn't say anything but I was glad someone did. Reading in the graph and putting it in a tree structure is a reasonable problem, but not a 10 minute interview one. Traversing the graph to find the optimal path? Wow, that's known to be a tricky problem. Brute force search will work but will take a while. Now, undoubtedly there must be some very clever proof that discards most of the searches for the special case of a triangle structure. And if you've seen that you're all set. If not, hopefully you have your copy of AoCP at hand to start looking for it. If you are in an interview and haven't seen it, you just need to recreate the conditions from 1 million BC to 1950 or whenever someone had the right insight to come up with a proof. Not really a reasonable assumption. In those circumstances it's only a test of if you've run into this issue before. And figuring out the answer is necessary to determine the email to submit a resume? How foolish that hiring manager is. If he was Google, yeah, you can put the question on a giant billboard ad as a challenge and get some responses. He's not Google. Reasonable question is if someone can parse some data and put it in a tree or graph. Reasonable interview question is to bring this up and talk about approaches. Person mention's Djikstra's algorithm, well he's heard of Djikstra and knew he was big on optimal path searches. Mentions AoCP, he knows a good place to look for clever algorithms. Knows how to solve it on the spot? Probably pretty clever. Finding the optimal 100 node long path in a graph as a screening method to send in a resume? Funny stuff there. Being a bit clever myself though I'll go a bit further here. I'd say you might be the person who posted that ad. But I think more likely is you want to apply for the job and have no idea at all how to solve that problem and are hoping by coming here and pretending it is trivial someone like me will give you some hints. Because if you really knew your stuff, you wouldn't be claiming it was trivial for any competent practitioner to solve and a reasonable screening question. Sure, there is an easy answer out there for doing this search, that's almost certain. That everyone competent would figure it out easily? Nah.

cageface 16y ago
Reading in the graph and putting it in a tree structure is a reasonable problem, but not a 10 minute interview one. Traversing the graph to find the optimal path? Wow, that's known to be a tricky problem. This question wouldn't be appropriate for an interview, but I think it's just right for a pre-screen. It's not hard if you realize they're not asking for the optimal path, just the biggest total. It's not my question, but I did take a second look at this company and I probably wouldn't have based on the rest of the posting. The Quora challenge problem, on the other hand, seems like very hard one: http://www.quora.com/challenges http://www.quora.com/challenges
- bugsy 16y ago
  The biggest total requires the optimal path for the stated constraints, those being the path must yield that biggest total. They aren't asking for a good enough path, but for the best possible path, the one that gives the biggest total. That's the optimal path for this problem. Probably a brute force search is the way to go, I certainly can't think of any way to thin this problem out without doing research, especially given the requirement that the optimal (maximum value) solution is required. 99 levels below the top, each time a binary decision, there's 2^99 = 6.34 * 10^29 paths only, won't take too long relative to the life of the universe since 2^99 nanoseconds is only 20 trillion years. That's the answer, might have a little problem with the sun burning out before the computation completes, but by that time you should be able to relocate using a warp drive. Good luck on the interview. edit: Ah I just figured out the pruning algorithm that will solve it. And that's the answer too, I just gave it to you in the previous sentence if you read carefully. Obvious once you think of it, not until then. I doubt many people would figure it out without a hint. And with a hint only clever ones could get it. As a screening to send in resumes? Pretty useless. If you do get a response who's to say they didn't ask for hints on a message board or pay someone to solve it on rentacoder.
  - cageface 16y ago
    I had this one solved already, but thanks. See, think about it for 10 minutes and it's not hard.
    - bugsy 16y ago
      I don't agree with that at all. Thinking for 10 minutes is not sufficient. There's two insights and neither are obvious until you get them. Assuming candidates will get them is like assuming quick sort will occur to them if they've never seen it before.
      - cageface 16y ago
        The minute you actually sat down and thought about it you got it, as did I, as would any of the better programmers I've worked with in my career. Walk halfway into an algorithm and it's clear. I wouldn't expect the average code schlepper to get this but that's the entire point. This ad suggests to me that's not what they're after.

by bugsy 16y ago

cageface 16y ago

Reading in the graph and putting it in a tree structure is a reasonable problem, but not a 10 minute interview one. Traversing the graph to find the optimal path? Wow, that's known to be a tricky problem. This question wouldn't be appropriate for an interview, but I think it's just right for a pre-screen. It's not hard if you realize they're not asking for the optimal path, just the biggest total. It's not my question, but I did take a second look at this company and I probably wouldn't have based on the rest of the posting. The Quora challenge problem, on the other hand, seems like very hard one: http://www.quora.com/challenges http://www.quora.com/challenges

bugsy 16y ago
The biggest total requires the optimal path for the stated constraints, those being the path must yield that biggest total. They aren't asking for a good enough path, but for the best possible path, the one that gives the biggest total. That's the optimal path for this problem. Probably a brute force search is the way to go, I certainly can't think of any way to thin this problem out without doing research, especially given the requirement that the optimal (maximum value) solution is required. 99 levels below the top, each time a binary decision, there's 2^99 = 6.34 * 10^29 paths only, won't take too long relative to the life of the universe since 2^99 nanoseconds is only 20 trillion years. That's the answer, might have a little problem with the sun burning out before the computation completes, but by that time you should be able to relocate using a warp drive. Good luck on the interview. edit: Ah I just figured out the pruning algorithm that will solve it. And that's the answer too, I just gave it to you in the previous sentence if you read carefully. Obvious once you think of it, not until then. I doubt many people would figure it out without a hint. And with a hint only clever ones could get it. As a screening to send in resumes? Pretty useless. If you do get a response who's to say they didn't ask for hints on a message board or pay someone to solve it on rentacoder.
- cageface 16y ago
  I had this one solved already, but thanks. See, think about it for 10 minutes and it's not hard.
  - bugsy 16y ago
    I don't agree with that at all. Thinking for 10 minutes is not sufficient. There's two insights and neither are obvious until you get them. Assuming candidates will get them is like assuming quick sort will occur to them if they've never seen it before.
    - cageface 16y ago
      The minute you actually sat down and thought about it you got it, as did I, as would any of the better programmers I've worked with in my career. Walk halfway into an algorithm and it's clear. I wouldn't expect the average code schlepper to get this but that's the entire point. This ad suggests to me that's not what they're after.