Hacker News Reader

Comment by mjburgess | Hacker News Reader

I may be missing something, but isnt the obvious answer just to scan-and-compare 4 chars/time ? (Noting that != is XOR).

    int main(void) {

        char *c = 0, *data = "nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg";

        for (
            c = data; 
            !((c[1] != c[0]) &&
            ((c[2] != c[1]) && (c[2] != c[0])) &&
            ((c[3] != c[2]) && (c[3] != c[1]) && (c[3] != c[0])));
            c++
        );

        printf("%ld", c-data+4);
    }

View on HN

Sure, but now do 11 at a time with a similar algorithm (which was part 2 of the problem).

I've just submitted in order to see the second part, which just says "now look for 14 unique".

I dont see the problem here, if you want a notation to express it, a macro for something like,

    0 != 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
    1 != 0, 2, 3, 4, 5, 6, 7, ...

is straightforward, and could be parameterised on the window size.

That's fine, but it's O(n) in the window size whereas the xor trick is O(1).

The window size is always constant in the problem, so it's O(1)

There shouldnt be a loop over the window size in solutions to this (particular) problem

TFA's implementation is using a loop over the window size to compare each character to all the other characters, to see if they're unique. So, the article's O(N * W²) is correct, but I agree, the window size is fixed and small; it's fair to boil it down to just O(N).

(I never even considered doing a for loop like that to determine if the window is unique; I just histogram the window, and then check if all the values in the histogram are 1. If yes, unique. If I had been cleverer, I wouldn't rebuild the histogram as the window shifts, but there was no need for that. This is essentially the next solution TFA presents.)

Part 1 and part 2 are the same, only the window size varies. But within a part, the window size is constant. For most, it should have just meant that, if you hard-coded the window size during part 1, that you need to make it a parameter.

But for both parts, the naïve solution should be O(N * W), where N is the input length, and W is the window size. Like a sibling says, since within a part the window size is fixed, it is acceptable to call it O(N).

Edit: ah, I see what his solution is doing. It is correct. I need to adjust my definition of naïve, I guess. His is O(N * W²). You can still reasonably consider W² constant, though, I think. And he gets to what I would call the "naïve" solution.

(Previously.) ~The "naïve solution" in the OP does not appear to be correct. Or at least, if it does work,~ it appears to do far more computation that it needs to.

The "xor trick" is O(N), too. (There cannot be a more efficient solution, as the entire input must be considered in the worst case. TFA is correct that its final form omits W, though.)

If you consider W the window size, and N the input size, this is still O(N * W²), as TFA states. (TFA's implementation is generic over W, yours is constant and essentially -funroll'd in place. But it's the same, for big-O; as you mention in your reply later, you could even make a macro, generic over W.)

2nd part is a window of length 14.

Reply on news.ycombinator.com