Hacker News Reader

Comment by Natsu | Hacker News Reader

I looked at that challenge. Is it really that much harder than FizzBuzz? Seems like it requires more string manipulation and about the same level of mathematics as FizzBuzz.

Or am I falling victim to the effect where everything I know how to do looks easy?

View on HN

  ...am I falling victim to the effect where everything I
  know how to do looks easy?

You could try it and find out. :-) I ended up using a third-party library which implements an algorithm I hadn't heard of before. (My response to the challenge is below, with the useful hints X'd out.)

  Hi, guys.  This is not a gungho-serious job application, though I have
  been sniffing around machine learning/coding jobs for a long time and
  could be persuaded in the right circumstances.  I saw justin_vanw
  mention your Code Challenge on HN and decided to give it a go for fun.
  Didn't realize when I started that the upload mechanism at Code Eval
  assumes a single file, so I am mailing it to you for evaluation,
  instead.  I must admit, I don't have much formal algorithms training,
  but after about an hour's thought I just googled "XXX," and the XXX
  algorithm happened to be the top of the list.  I have a PhD in Applied
  Mathematics from MIT, and I have been focusing on Bayesian Data
  Analysis in Computational Biology, so maybe it was just a lucky
  search-engine hit.  But in general, I am a reasonably quick study.  My
  solution is at <http://XXX>, and is tested on python 2.6.5 with scipy
  0.7.0.  Untar the download, go into the XXX directory, run "sudo make
  pyinstall" (I had to add -fPIC to Makefile's CFLAGS assignment to make
  this work), and then the solution program is in
  milo-challenge/solution.py:
  
    met% python solution.py < test-input.txt 2> /dev/null
    XXX
    XXX
  
  BTW, XXX is a C implementation of the XXX algorithm from <http://XXX>,
  and is the reason I couldn't easily go through the Code Eval framework.
  It sends some garbage to stderr, which I haven't bothered to clean up.

An external library? Some sort of linear algebra, I assume? I believe that a very simple algorithm that solves problems like this was featured on HN something like a week ago.

I hope that's not too much of a hint, but anyone who can figure it out from that was probably a good candidate, anyhow.

I should also mention that I did code a solution in Perl, or at least most of one, though I did not submit it. I have a grandmother to care for and that limits me on relocating, even though I would be interested in finding more interesting work.

Assuming I don't eventually go crazy in a futile attempt to explain to corporate that methods which turn a 9/2272 inch rounding error into a piece of glass that's half an inch too big do not qualify as "validation."

Not linear algebra, although the optimization problem can be expressed in terms of linear programming, I think.

I wish you well in caring for your grandmother. That stuff is way more important than programming techniques.

It's weird how full-circle I've gone on this. I went from "the naive solution is easy enough to write" to "I bet there's a more efficient way" to "oh crap, my solution doesn't actually work, because the preferences can have ties."

I did have the fun of coding up the algorithm I saw on HN a while back, though, so it was fun.

Incidentally, I had more time this weekend and found that it gets a lot easier if I use a more suitable algorithm. Considering it as a S-M problem only makes things more complex, because there can be ties (which kills the nice algorithm for solving these) while introducing more complexity than is necessary, given that there's a single cost to be maximized, rather than two distinct preference lists.

Seems like I should have been doing it as an A problem, where you can just use the H algorithm. So I want to say thanks to the guys who posted the challenge: it was a good excuse to teach myself some combinatorial algorithms.

Lest anyone wonder, I'm using those weird abbreviations so as not to spoil the problem. Figuring out which algorithms to use is half the fun and I read about quite a few different types of problems before figuring out which was the most suitable. I'd hate to deny anyone else the same learning experience.

I, too, looked at the challenge and originally had the same thought. However, upon a second reading, it seems that there is a lot of room to misunderstand the requirement, which is almost certainly where the difficulty appears.

For example:

1. "Your task..." is not directly correlated to the outputs requested. 2. Item 3 in the SS ranking isn't clear. Specifically, "besides 1" could mean "besides 1" literally, or "besides 1" - where "1" means "one of the above," or even something else.

I was about to attempt to do it, just for fun, but then decided against it because the challenge itself had too much ambiguity in the requirements. That's very likely intentional - but since I'm not looking for a job, didn't need to waste my time playing "a game!" Maybe the successful answer rests in seeking/understanding the real requirements???

Any ambiguity in item 3 is not a problem, because no matter how you parse it, the number of letters will always be a positive integer.

This is to both you and your parent reply -- have I completely misread statement 3?

'3. If the number of letters in the product's name shares any common factors (besides 1) with the number of letters in the customer's name then the SS is multiplied by 1.5.'

To me, this says that if len(pname) is split into prime factors, and at least one of those is found in the list of prime factors for len(cname), then you multiply your SS by 1.5. The "besides 1" remark is obvious, because 1 is technically a factor for every number. I'm not quite sure how the math pedants come down on that, but this is just common sense.

Negative or positive shouldn't really affect this (I guess it could be construed as "-1" instead of "1" in the factor list, but.. you've really got to bend over backward to make that into a problem), and it's completely not ambiguous. The "besides 1" could not reasonably be taken to mean "besides the first statement", as the two statements deal with very different subject matter.

Am I crazy here? Did I miss something?

I think you're doing the right thing, but you did miss something :)

Oddly enough, I think that the algorithm you need here was also on HN a while back.

Uh, I didn't mention the algorithm at all. As someone else mentioned, the hard part of this problem is finding an optimal solution; there's some minor stuff with keeping information together and building a modular program, but what I said is completely unrelated to that.

As we're entirely just discussing the spec, and not the secret hidden hardness of this problem, could you tell me what I missed? If you're concerned for their confidentiality, then email it to me at carss.w@gmail.com

Disclosure: I'm not planning to apply to this job or to complete this challenge, because I have other things to program for fun, and an internship / school to keep me busy. I'm strictly curious about our different interpretations of what seems (to me) like an unambiguous spec, and I'm prepared to be totally wrong on my reading of it.

I'm referring to yet another algorithm. It probably won't matter for numbers that small, but the ancient Greeks invented a better way.

And yes, even it was discussed on HN recently.

Ah, you mean the algorithm re: factors. Okay, thanks.

You're fine, I'm the crazy one...err...ignorant one! I was just wrong. In viewing some of the other comments on this thread, it's clear to me that milo would have done a fine job of filtering me out! :-)

FWIW, I looked at the problem differently - I interpreted "factors" completely the wrong way. I'm humble enough to say that my bad interpretation is based on my own lack of education in mathematics. I have none! Zero, outside of what you get in high school. I'm definitely not the low-level algorithm guy. My lack of math skills has not held me back professionally, but I get healthy doses of humility, like this, on occasion. "One day" I want to go back and study math and see what I've been missing all these years.

I wanted to give you the respect of a reply since you took the time to comment.

Unless I'm misreading the question, it's actually a good deal trickier than FizzBuzz - the difficult part isn't computing the "sustainability scores" from the input strings, but in maximizing the combination of product offers across the set of offers and customers. It's actually analogous to a rather well studied combinatorial optimization problem (that I won't call out by name here so as to avoid letting potential job applicants look up the answer too easily) that has a fairly non-obvious pseudo-polynomial time dynamic programming solution. The naive solution is exponential time (and still a bit tricky for a novice). I suspect the intent of the question is to find applicants that give the optimal solution rather than the naive one (and to weed out applicants that can't give any correct solution), but I could be mistaken.

I've had a go. It is hard because they don't define what a letter is (a-z, alphanumeric, non-whitespace). I tried with A-Za-z and got the correct answers for the test, but the incorrect answer for the website. Due to the way that the problem works that isn't too unlikely as all the letter function has to do is give the same answers on things like even-ness and whether it has a common factor with another number, things that aren't unlikely given the small amount of test data given.

You can email me your solution at justin@milo.com and I'll take a look. We just started doing the challenge with that site and there are probably kinks in the grading.

I've noticed what I was doing wrong. I'm onto more interesting bits of the challenge, I hope. Thanks for the offer, though.

The problem's description is deceptively simple. It poses at the end a combinatorics problem that is non-trivial. I submitted a correct solution after a bit of research; my first approach was the naive solution.

If, by "non-trivial," you mean NP-hard, I agree. :-)

I was trying to be vague so as not to give hints to those interested in trying the challenge. Evidently, I am utterly guileless.

Given the number of combinatorial optimization problems that are NP-hard, I don't think that gives anything away to anyone who doesn't already know what you're talking about.

How did you submit the solution with a library? Doesn't upload mechanism assume only 1 file?

Reply on news.ycombinator.com