Fork me on GitHub
#clojure-uk
<
2016-06-15
>
benedek09:06:13

morning from lovely glasgow

agile_geek09:06:18

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.

glenjamin09:06:02

what’s a binary chop?

mccraigmccraig09:06:46

log_2_n search of a sorted list by dividing into successive halves

glenjamin09:06:34

isn’t that a binary search?

glenjamin09:06:32

imperative approach is unrolling the recursion into a while loop?

glenjamin09:06:51

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

agile_geek09:06:53

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.

glenjamin09:06:51

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

agile_geek09:06:49

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 😉

glenjamin09:06:31

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

glenjamin09:06:35

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

agile_geek09:06:23

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;
}
``````

glenjamin09:06:46

ah, so you need to slice ints each time?

glenjamin09:06:26

i think you might have just nerd sniped me

agile_geek09:06:06

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!

glenjamin09:06:58

why’s it part of the interview then? 👿

agile_geek09:06:41

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

glenjamin09:06:59

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

glenjamin09:06:11

oh, that midpoint calc is wrong

glenjamin09:06:36

that’s what I get for doing index maths

glenjamin09:06:19

in fact, that seems to be very wrong

glenjamin10:06:00

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

glenjamin10:06:11

but my two testcases passed \o/

glenjamin10:06:52

ok, back to work

thomas10:06:23

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

glenjamin10:06:27

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

thomas10:06:13

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

mccraigmccraig11:06:14

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

glenjamin11:06:59

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

minimal12:06:12

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