Hacker News Reader

Comment by verst | Hacker News Reader

This solution was developed by a SWE 2 candidate in the FAANG on-site interview loop. /s

(Just joking but some interviews indeed feel that way)

And the candidate was ultimately not hired by the said FAANG.

"This is clever, but I don't think it will work in practice and I don't believe it is O(n * log(n)) and will assert it is O(n*n) until I die."

"It outperforms any of the solutions I've seen but the code isn't as readable, next!"

“Sorry Dr. Knuth, we’re looking for someone with more algorithm experience.”

"Yes, yes. I meant PRACTICAL algorithm experience."

Programming MIX? Do you have any relevant experience, Dr. Knuth?

I get the sarcasm [0], but: Having watched a few of Dr. Knuth's lectures [1], I'm convinced he'd wipe the floor with FAANG interviewers.

[0] I mean, this has happened for real: Bram Cohen (BitTorrent co-inventor) / brew's (package manager for macOS) co-developer couldn't get past Google interviews: https://news.ycombinator.com/item?id=9695102

[1] https://hn.algolia.com/?query=knuth%20christmas

You joke, but real world problems have been solved in analogous scenarios, such as homework assignments where the author simply didn't know the problem was yet unsolved and banged their head until they got it.

> In 1939, a misunderstanding brought about surprising results. Near the beginning of a class, Professor Neyman wrote two problems on the blackboard. Dantzig arrived late and assumed that they were a homework assignment. According to Dantzig, they "seemed to be a little harder than usual", but a few days later he handed in completed solutions for both problems, still believing that they were an assignment that was overdue.[4][6] Six weeks later, an excited Neyman eagerly told him that the "homework" problems he had solved were two of the most famous unsolved problems in statistics.

https://en.wikipedia.org/wiki/George_Dantzig

Does anybody have more examples?

Not homework, but this comes to mind: https://www.wired.com/story/how-an-anonymous-4chan-post-help...

Huffman coding was invented when Huffman's professor, Robert Fano, gave a class the option of either taking a regular final exam or solving the optimal encoding problem which (unknown to the students) he and Shannon had been failing to solve for some time.

In a class of his that I took he told us that even crumpled up the paper with the solution threw it away then went back and retrieved it and realized it was right

Does anyone know what the two unproven theorems he proved were?

They appear to be published in these two articles, as described and cited by Snopes[1]:

Dantzig, George B. “On the Non-Existence of Tests of ‘Student’s’ Hypothesis Having Power Functions Independent of Sigma.” Annals of Mathematical Statistics. No. 11; 1940 (pp. 186-192).

Dantzig, George B. and Abraham Wald. “On the Fundamental Lemma of Neyman and Pearson.” Annals of Mathematical Statistics. No. 22; 1951 (pp. 87-93).

[1] https://www.snopes.com/fact-check/the-unsolvable-math-proble...

Not exactly this as far as official sources say, but the Karatsuba algorithm (long multplication in n^1.6) was the result of Kolmogorov (already a foundational figure, but only beginning his work in what would come to be called algorithmic complexity) starting a seminar with the goal of showing that long multiplication can’t be done in less than n^2 time (because nobody was able to do it faster in thousands of years) and a student (Karatsuba) coming in after a couple of meetings to prove him wrong (the catch being that the constant factors make the result not worth it for values of n people historically worked with by hand).

(The algorithm boils down to the observation that (Xb + Y)(Zb + W) = XZ b^2 + [(X + Y)(Z + W) - XZ - YW] b + YW, for a total of three unique base-b products, plus what is nowadays a routine exercise to see that calculating these products recursively in base b/2 yields complexity n ^ log_2 3.)

Reminds me how once I had a math test in college about simplifying trigonometric expressions (cos(a + b) kind of formulas) and I made a cheat sheet with all the formulas because I couldn’t remember them all. Obviously I forgot one formula and as fate would have it it was on my test. Took me about 15 min, but eventually I derived it and put it all on the test paper. My gosh the math professor was proud of me, probably one of the top 10 moments of my life when he kept boasting about it when he announced the test results. Many years later I kept thinking I should tell him the full story, but alas he died not too long ago. RIP ‘Stakan Stakanovich’

Not quite the same scenario, but Dantzig had the roles reversed on him by John von Neumann. From Wikipedia

> When George Dantzig brought von Neumann an unsolved problem in linear programming "as I would to an ordinary mortal", on which there had been no published literature, he was astonished when von Neumann said "Oh, that!", before offhandedly giving a lecture of over an hour, explaining how to solve the problem using the hitherto unconceived theory of duality.

Not quite the same thing...

> George Pólya, whose lectures at ETH Zürich von Neumann attended as a student, said "Johnny was the only student I was ever afraid of. If in the course of a lecture I stated an unsolved problem, the chances were he'd come to me at the end of the lecture with the complete solution scribbled on a slip of paper."

> https://en.wikipedia.org/wiki/John_von_Neumann#Cognitive_abi...

I was wondering about the morality of using candidates' solutions in your products. Does the hiring company own the test results? Does the candidate? What if the candidate gets hired, who owns the solution, then?

The candidate does not get paid to solve the interview test, but it could be seen as a collaborative effort on both the company and the candidate, since both put time and engineering resource in it.

Is algorithm copyright-able?

If it can be regarded as an intellectual property, does that mean that the company would be infringing on the candidate’s right?

XOR certainly was patented for use to display mouse cursors.

It is immoral to use candidate answers in your product, assuming you don’t hire them.

If you do hire them then I guess it becomes fine, but otherwise definitely immoral.

The problem is that we’re fleshy meatbags and easily influenced. It’s possible we internalise answers to interview questions and then “spontaneously” come up with them later, without _knowingly_ stealing the idea.

This happens sometimes in comedy, and the comedian apologises. You can usually tell the difference in comedy between plagiarism and accidental theft because the joke is delivered much differently but has the same core. It would be harder with interview answers.

> If you do hire them then I guess it becomes fine

Not that anything will stop companies from doing this, and not that I think it ever really happens, but for it to be morally OK I think you’d have to both get their permission and compensate them fairly.

Before I work for you, my ideas are mine even if I write them on your whiteboard.

Sure, but if I ask you an interview question and your answer is good enough that I want to use it: you'll probably be the one implementing the solution.

Why would I trust the answer more than the person?

>Why would I trust the answer more than the person? //

Why wouldn't you? The truth of statements is not a function of the people making them (though of course that can often be a strong indicator of truth).

If you’re hiring, and your candidate produces a solution to a real problem, and your interviewers actually want to use their solution, that person is getting an offer unless they were absolutely obnoxious and terrible to work with. Failure to do so is just bad recruitment.

Or, put differently: if I’m the candidate and they end up “stealing” my solution, that’s a small price to pay to avoid working in what is likely a terrible environment.

That assumes the interviewer is ethical. In my experience, most people in SW do not have a strong cultural basis for ethical behavior of this sort.

It's not a work for hire and there is no copyright assignment so copyright will remain with the candidate.

However some whiteboard scribbles are not the same as working code, so it is likely easy to make an implementation that does not infringe in most cases. Not that it really matters because it's highly unlikely that anyone is going to sue over it.

There is no copyright on algorithms.

To ask interviewees a question about an actual issue you have and see what solutions they come up with is clever. You get more input for free and you may find someone you want to hire.

I don't see a problem as long as you are really looking to hire someone and not advertising fake job openings.

The real question is, what on earth is a candidate doing in a few hours of interview processes that's worth stealing?

I've had candidates use useful Python libraries that I didn't know about in tech tests before, but that's pretty much the extent to which I've learned anything helpful when recruiting

About coding maybe, but I find interviewing really informative to learn about what other companies are doing and how they have architected stuff.

Reply on news.ycombinator.com