Tricky interview puzzle: get longest sequence by flipping 1 bit

7

1

A friend of mine got this question during an interview. The interview ended with no luck for him, but still, we're very curious to hear the solution. The question is as follows:

Modify the code below (change 3 lines maximum) so the function will return the length of the longest sequence of the same bit, if you would flip one bit in the given array. Note: the method's parameter is a bits array.

For example: take the bits array: "11001001010". By flipping the 5th bit from "1" to "0", we'll get: "11000001010" and the result would be: 5.

private static int solution(int[] a) {

    int n = a.length;
    int result = 0;
    int i;

    for (i = 0; i < n - 1; i++) {

        if(a[i] == a[i + 1])
            result = result  + 1;
    }
    int r = 0;
    for (i = 0; i < n; i++) {

        int count = 0;
        if(i > 0)   {
            if(a[i - 1] != a[i])
                count = count + 1;
            else
                count = count - 1;
        }
        if(i < n - 1)   {
            if(a[i + 1] != a[i])
                count = count + 1;
            else
                count = count - 1;
        }

        if(count > r)
            r = count;
    }

    return result + r;
}

ofirbt

Posted 2015-07-20T08:49:34.263

Reputation: 171

Question was closed 2015-07-20T09:55:00.980

5

Why is this off topic? This looks exactly like what the the tag wiki describes for for [tag:programming-puzzle]. And we've had programming puzzles that are just solved, without additional scoring like fewest bytes.

– xnor – 2015-07-20T10:28:52.433

I would like to join to @xnor's question - why is this off topic? – ofirbt – 2015-07-20T10:37:59.883

2I voted "unclear". What counts as changing a line? It seems that in principle this would allow dropping in a one-liner solution and using none of the supplied code at all. And what do you mean by "the length of the longest sequence of the same bit, if you would flip one bit in the given array"? I presume we have to interpret the int[] as a bit[] and maximise the longest sequence over each case of "flip bit X", but what endianness (or endiannesses - in some contexts it's different for the 4 bytes in an int and the 8 bits in a byte) should we use to interpret the int[] as a bit[]? – Peter Taylor – 2015-07-20T11:16:55.883

@PeterTaylor - I think that it's common sense not to do that in a one liner... Think of the real world - if you would go to a job interview right now, would you dare writing a one liner?? Regarding the int vs bit array - you're right. I've added an example and changing right now the description. – ofirbt – 2015-07-20T11:36:36.800

@xnor There is no objective primary winning criterion, as stated in the close reason under the question. – Doorknob – 2015-07-20T11:37:56.330

3@Doorknob Isn't [tag:programming-puzzle] relieved from that requirement, just like [tag:popularity-contest]? – orlp – 2015-07-20T11:47:51.787

1@orlp Popularity-contest is absolutely not relieved from that requirement (most votes is the primary objective winning criterion), nor is programming-puzzle to the best of my knowledge. Do you have a meta post or a tag wiki that is the source of that rule? – Doorknob – 2015-07-20T11:50:16.190

3@Doorknob It would be rather strange if a site called "Programming Puzzles and Code Golf" does not actually allow programming puzzles. – xnor – 2015-07-20T19:54:56.947

1

@xnor Of course we allow them. It would also be rather strange for a certain question to be arbitrarily able to bypass a rule we've had in place since almost the very beginning of the site. (Please post on meta if you think the policy should be changed.)

– Doorknob – 2015-07-20T20:23:56.480

1@ofirbt. You could edit your question to a suitable challenge by asking for a working function with the minimum number of changes. Be precise about specifying what counts as a +1 change. Add some testcases - inputs & expected outputs. A shame it is language specific. – gnibbler – 2015-07-20T20:44:04.913

@Doorknob OK, meta post, though I don't necessarily think the policy should be changed, it's just a strange contradiction between policy and practice.

– xnor – 2015-07-20T21:14:03.730

This need more clarification about what is valid and what is not. If the answer cannot be one-liner, it is still not clear whether 3 statements on the same line, or if(false) equivalents are valid. The "common sense" thing discourages creative ideas. – jimmy23013 – 2015-07-20T23:36:31.320

@gnibbler - The question is not about getting any solution, but understanding this specific one. And although it's written in Java, I think it's perfectly understandable - this code looks like pseudo! Plus, it's taken from Codility and it's a legitimate programming puzzle. – ofirbt – 2015-07-21T07:50:35.453

No answers