9 ms·

Programming Puzzles

ncmncm 5y ago
A bit off-topic... The best online programming puzzles were the ones ITA Software posted to entice people to apply for jobs there. What was effective about them was that, reading the problem, you wanted to know what a solution would look like, and knew the only way to know was to solve it. Having solved it, you wanted to know how your solution compared to others'. The only way to find out was to send it in. Having sent it, you might get an invitation to visit, and then how could you not? After Google bought ITA, the puzzles were up for a while longer, then seemed to vanish. If they are archived somewhere, I would like to know where.
- georgehm 5y ago
  well there's https://web.archive.org/web/20111012115624/http://itasoftware.com/careers/work-at-ita/hiring-puzzles.html https://web.archive.org/web/20111012115624/http://itasoftwar...
- kristjansson 5y ago
  (from the sibling archive link) > Roll Your Own Chat Server > Implement a simple standalone TCP-based chat server, using the following protocol: > ... > When implementing the server, aim for scalability and robustness. (Many submissions fail due to lack of robustness!) > ... > Please do not use an existing networking framework Oh man. You weren't kidding, that's high-precision nerd-sniping.
  - ncmncm 5y ago
    I suspect the earlier puzzles were most of the better ones. What I sent in was the Add-a-gram (on that page, stashed behind the "Puzzle Archive" link). I sent one solution, and when they called, they admitted others were faster, so I redid it that evening ten times faster and sent that. What they never told me, even after I had been there for years, was that my second solution was faster than theirs or any others they had on file. It looks like they retired it right after I started there, maybe because I had shown it didn't actually require backtracking, which they were trying to filter for–ITA was mostly a Lisp shop, so they wanted people who would always reach for recursion first. My solutions were relentlessly iterative. Some years after I left ITA, they posted the Bitvectors puzzle, which I had to solve, in a fever, but never sent off. (At the time I think it had a different name.) That solution also didn't require backtracking.
    - hoseja 5y ago
      I just don't get how anyone can use recursion for anything serious. Especially when it can always be unrolled into a more comprehensible / representative of what's actually happening iteration.
      - KineticLensman 5y ago
        If you are used to Lisp-like constructs, tail recursion can give solutions that are both idiomatic and efficient. [0] https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call
        ncmncm 5y ago
        I.e., the compiler converts the recursive code you wrote into the iterative form you could have written, and runs that instead because it's faster.
        Jtsummers 5y ago
        I find this argument interesting because, to me, it leads to endorsing a view that we should be using goto and conditional jumps instead of for/while loops and similar structured programming elements. I mean, the former are more explicit, the latter implicit, since the compiler converts the latter into the former. Having maintained a fair amount of unstructured code, I'd rather stick with the higher level languages since they allow me to express my intent more clearly. Which pushes me to using recursion where it's appropriate and the language has appropriate facilities to handle tail call elimination.
        ncmncm 5y ago
        We make languages and compilers the way we do for reasons. But it is a mistake to confuse what automation hides from you, for practical reasons, with fundamental qualities of the universe or of computation. Another common example of the error is describing an algorithm as N log N, assuming that the numbers involved occupy constant space and multiply in constant time. In real-world computation, space tends to log N, and multiply in close to (log N)^2 time and power consumption. We get away with it for the same reason recursion works: the problems we apply our algorithms to usually fit in conveniently constrained space, and our multiplier hardware takes the same time and power for small numbers as for the biggest ones we can conveniently represent.
  - Joker_vD 5y ago
    Mmm, I remember doing this, with select(3) for maximum portability and all... then learning that neither Linux nor Windows actually follow what POSIX says select(3) should do, e.g. how to report a socket with non-blocking connect(3) operation when it finally fails to connect: it should be reported as readable (reading from it would fail immediately and would not block), writeable (same reason), having exceptional condition pending (it has a pending error). Nope, Linux reports it as readable/writeable but not having exceptional condition, while Windows reports it as only having exceptional condition pending but not as readable nor writeable. Beautiful, just beautiful. In the end you have to put sockets in such scenarios into all three sets and check what getsockopt(s, SOL_SOCKET, SO_ERROR) returns for them, that's the portable way.
- ncmncm 5y ago
  BTW, I got one of my best interview questions from a problem I encountered there. Undergraduates solve it in two minutes; people with a BS need 5; MS 20; PhD never, or as fast as an undergraduate. The iterative solution is much simpler than a recursive one, so the question identifies how well-tuned your instincts are to problem spaces. If you go straight for recursion, you'll be there all day. I found that everybody who found the minimal solution used the same hand gesture while describing it.
  - occamrazor 5y ago
    What is the question?
    - ncmncm 5y ago
      That would be telling. I always recited the statistics at the outset, so that the interviewee would know how much complexity to expect in the answer. It never seemed to help them.
allanrbo 5y ago
I, for one, welcome our new AI overlords
umvi 5y ago
Puzzle Repo Here: https://github.com/microsoft/PythonProgrammingPuzzles https://github.com/microsoft/PythonProgrammingPuzzles
___luigi 5y ago
> Based on a small user study, we find puzzle difficulty to correlate between human programmers and the baseline AI solvers. Now that we have AI to solve "LC type of questions", can we stop asking candidates to invert a linked list in an interview.
- ncmncm 5y ago
  Alternatively: ask them to code it, and hire the ones who refuse.
mjlee 5y ago
OT but still vaguely regarding puzzles - Jane Street has a pretty satisfying puzzle every month: https://www.janestreet.com/puzzles/ https://www.janestreet.com/puzzles/

A bit off-topic... The best online programming puzzles were the ones ITA Software posted to entice people to apply for jobs there. What was effective about them was that, reading the problem, you wanted to know what a solution would look like, and knew the only way to know was to solve it. Having solved it, you wanted to know how your solution compared to others'. The only way to find out was to send it in. Having sent it, you might get an invitation to visit, and then how could you not? After Google bought ITA, the puzzles were up for a while longer, then seemed to vanish. If they are archived somewhere, I would like to know where.

georgehm 5y ago
well there's https://web.archive.org/web/20111012115624/http://itasoftware.com/careers/work-at-ita/hiring-puzzles.html https://web.archive.org/web/20111012115624/http://itasoftwar...
kristjansson 5y ago
(from the sibling archive link) > Roll Your Own Chat Server > Implement a simple standalone TCP-based chat server, using the following protocol: > ... > When implementing the server, aim for scalability and robustness. (Many submissions fail due to lack of robustness!) > ... > Please do not use an existing networking framework Oh man. You weren't kidding, that's high-precision nerd-sniping.
- ncmncm 5y ago
  I suspect the earlier puzzles were most of the better ones. What I sent in was the Add-a-gram (on that page, stashed behind the "Puzzle Archive" link). I sent one solution, and when they called, they admitted others were faster, so I redid it that evening ten times faster and sent that. What they never told me, even after I had been there for years, was that my second solution was faster than theirs or any others they had on file. It looks like they retired it right after I started there, maybe because I had shown it didn't actually require backtracking, which they were trying to filter for–ITA was mostly a Lisp shop, so they wanted people who would always reach for recursion first. My solutions were relentlessly iterative. Some years after I left ITA, they posted the Bitvectors puzzle, which I had to solve, in a fever, but never sent off. (At the time I think it had a different name.) That solution also didn't require backtracking.
  - hoseja 5y ago
    I just don't get how anyone can use recursion for anything serious. Especially when it can always be unrolled into a more comprehensible / representative of what's actually happening iteration.
    - KineticLensman 5y ago
      If you are used to Lisp-like constructs, tail recursion can give solutions that are both idiomatic and efficient. [0] https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call
      - ncmncm 5y ago
        I.e., the compiler converts the recursive code you wrote into the iterative form you could have written, and runs that instead because it's faster.
        Jtsummers 5y ago
        I find this argument interesting because, to me, it leads to endorsing a view that we should be using goto and conditional jumps instead of for/while loops and similar structured programming elements. I mean, the former are more explicit, the latter implicit, since the compiler converts the latter into the former. Having maintained a fair amount of unstructured code, I'd rather stick with the higher level languages since they allow me to express my intent more clearly. Which pushes me to using recursion where it's appropriate and the language has appropriate facilities to handle tail call elimination.
        ncmncm 5y ago
        We make languages and compilers the way we do for reasons. But it is a mistake to confuse what automation hides from you, for practical reasons, with fundamental qualities of the universe or of computation. Another common example of the error is describing an algorithm as N log N, assuming that the numbers involved occupy constant space and multiply in constant time. In real-world computation, space tends to log N, and multiply in close to (log N)^2 time and power consumption. We get away with it for the same reason recursion works: the problems we apply our algorithms to usually fit in conveniently constrained space, and our multiplier hardware takes the same time and power for small numbers as for the biggest ones we can conveniently represent.
- Joker_vD 5y ago
  Mmm, I remember doing this, with select(3) for maximum portability and all... then learning that neither Linux nor Windows actually follow what POSIX says select(3) should do, e.g. how to report a socket with non-blocking connect(3) operation when it finally fails to connect: it should be reported as readable (reading from it would fail immediately and would not block), writeable (same reason), having exceptional condition pending (it has a pending error). Nope, Linux reports it as readable/writeable but not having exceptional condition, while Windows reports it as only having exceptional condition pending but not as readable nor writeable. Beautiful, just beautiful. In the end you have to put sockets in such scenarios into all three sets and check what getsockopt(s, SOL_SOCKET, SO_ERROR) returns for them, that's the portable way.
ncmncm 5y ago
BTW, I got one of my best interview questions from a problem I encountered there. Undergraduates solve it in two minutes; people with a BS need 5; MS 20; PhD never, or as fast as an undergraduate. The iterative solution is much simpler than a recursive one, so the question identifies how well-tuned your instincts are to problem spaces. If you go straight for recursion, you'll be there all day. I found that everybody who found the minimal solution used the same hand gesture while describing it.
- occamrazor 5y ago
  What is the question?
  - ncmncm 5y ago
    That would be telling. I always recited the statistics at the outset, so that the interviewee would know how much complexity to expect in the answer. It never seemed to help them.

allanrbo 5y ago

I, for one, welcome our new AI overlords

umvi 5y ago

Puzzle Repo Here: https://github.com/microsoft/PythonProgrammingPuzzles https://github.com/microsoft/PythonProgrammingPuzzles

___luigi 5y ago

> Based on a small user study, we find puzzle difficulty to correlate between human programmers and the baseline AI solvers. Now that we have AI to solve "LC type of questions", can we stop asking candidates to invert a linked list in an interview.

ncmncm 5y ago
Alternatively: ask them to code it, and hire the ones who refuse.

mjlee 5y ago

OT but still vaguely regarding puzzles - Jane Street has a pretty satisfying puzzle every month: https://www.janestreet.com/puzzles/ https://www.janestreet.com/puzzles/