morning

Morning

mrnng

morning from lovely glasgow

I've got a pair programming interview at lunchtime in Java and I've been practicing algorithmic problems. Just spent ages trying to write a binary chop imperatively! I've rewired my brain to reach for 'reduce' or at the very least recursive fns. Might reimplement it in Java recursively.

what’s a binary chop?

log_2_n search of a sorted list by dividing into successive halves

isn’t that a binary search?

ah, synonym

@glenjamin: yep

imperative approach is unrolling the recursion into a while loop?

Sure is

or i suppose you could use only an index, rather than slicing the list

Actually I'm using an index in a while loop but I'm going to implement a few different ways. In this case the return value is the index of the element in the sorted array so index is easier.

i think i’d have int start, mid, end and keep adjusting them in a loop, if I had to be imperative

My first implementation is just using mid as start and end are fixed as zero and array length then I just adjust mid as required, but as I said I will reimplement a couple of ways. Better than the actual work I have to do 😉

don’t you need to move start and end when you recalc mid?

if (x < arr[mid]) { end = mid; } else { start = mid; }

nope - I'm checking if element at mid is equal to value I want and if it's not then recalc mid like so:

private static int findMiddleIndex(int i, int[] ints, int middleIndex) {
        if (ints[middleIndex] < i)
            return middleIndex + ((ints.length - middleIndex + 1) / 2);
        else
            return middleIndex / 2;
    }

ah, so you need to slice ints each time?

i think you might have just nerd sniped me

Hardest thing is I'm just not used to solving algorithms in Java. I don't practice it and I've virtually never had to do it in work in 19 years!

why’s it part of the interview then? 👿

I don't know what they are going to give me in interview. Just using this for practice.

oh, I see - I assumed you were giving the interview

oh, that midpoint calc is wrong

that’s what I get for doing index maths

in fact, that seems to be very wrong

so I actually had 4 off-by-one errors, and one logic error in that 14-line snippet

but my two testcases passed \o/

ok, back to work

hmmm Java code in the Clojurians Slack… not sure that is approved 😉

an interesting question might be: which type systems could have found those bugs?

‘fraid I don’t know enough about type systems to comment on that… Dunno if there are any Haskell experts around here?

you're gonna need something with dependent-types @glenjamin

i thought that might be the case, should have written more testcases. I’m still surprised the code up there passed the few I did have

@glenjamin: not dissimilar - http://andmkent.com/blog/2014/11/10/quicksort-in-coq/

Back to the recursive version so you can do proof by induction