> find :: (Ord y) => (x -> y) -> y -> IArray x -> (Int,Int) -> Maybe x
 > find field target array (base,size)
 > | size < 0 = error "invalid subrange size"
 > | size == 0 = Nothing
 > | size == 1 = if field (array ! base) == target then Just (array !
 > base) else Nothing
 > | otherwise =
 > let size2 = size `div` 2
 > in find field target array (base, size2) `mappend` find field target
 > array (base + size2, size - size2)

I don't know Haskell, but my best guess at understanding this code looks 
like you're always recursing into both sides, without actually doing the 
comparison of the center element to the target element. So you're not 
saving any time, and you would get faster results with a linear search. 
But maybe I just don't understand the language well enough to see the 
comparison.

  - Slime

Post a reply to this message

Darren New <dne### [at] sanrrcom> writes:

> Warp wrote:
> I usually ask them to print out the prime numbers less than 100 or something.

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 91, 97]
for prime in prime:
    print prime

Post a reply to this message

Slime wrote:
>  > find :: (Ord y) => (x -> y) -> y -> IArray x -> (Int,Int) -> Maybe x
>  > find field target array (base,size)
>  > | size < 0 = error "invalid subrange size"
>  > | size == 0 = Nothing
>  > | size == 1 = if field (array ! base) == target then Just (array !
>  > base) else Nothing
>  > | otherwise =
>  > let size2 = size `div` 2
>  > in find field target array (base, size2) `mappend` find field target
>  > array (base + size2, size - size2)
> 
> I don't know Haskell, but my best guess at understanding this code looks 
> like you're always recursing into both sides, without actually doing the 
> comparison of the center element to the target element.

Oh... my god... >_<



I blame Warp. I was so busy making sure that there's no off-by-one 
errors that I totally forgot to actually, you know, IMPLEMENT THE RIGHT 
ALGORITHM!

Post a reply to this message

OK, 3rd time lucky: let's see if I can actually implement this thing 
correctly. :-P

find :: (Ord y) => (x -> y) -> y -> IArray x -> (Int,Int) -> Maybe x
find field target array (base,size)
   | size <  0 = error "invalid subrange size"
   | size == 0 = Nothing
   | size == 1 = if field (array ! base) == target then Just (array ! 
base) else Nothing
   | otherwise =
     let
       size2 = size `div` 2
       base2 = base + size2
     in
       case compare (field (array ! base2)) target of
         EQ -> Just (array ! base2)
         GT -> find field target array (base, size2)
         LT -> find field target array (base + size2, size - size2)

Now, finally, it should work. (But I've said that twice before already...)

Damnit, no wonder nobody loves me. :-(

Post a reply to this message

Invisible wrote:
> Damnit, no wonder nobody loves me. :-(

Implementing a binary search in Haskell is now a prerequisite for love? 
That's news to me :-)

-- 
Vincent

Post a reply to this message

>> Damnit, no wonder nobody loves me. :-(
> 
> Implementing a binary search in Haskell is now a prerequisite for love? 
> That's news to me :-)

I meant the fact that I'm mentally retarded rather than specifically 
that I wrote this program wrong.

Post a reply to this message

> I don't think this is unique to programming. From what I've seen, most 
> managers get hired based on their ability to spout impressive-sounding BS 
> rather than their ability to actually manage a department.

It all comes down to how competent the people are that are interviewing.  If 
a company is already full of BS managers then of course they are going to 
employ more BS staff and the problem will never improve (I know two people 
that work at a company like this).  Alternatively, if you have a good set of 
people already in charge, interviewing and making hiring decisions, you are 
not going to employ any BS managers (or programmers) in the first place.

> I would imagine that quite a few of then know damned-well that they can't 
> program, and expect to be able to just con somebody into hiring them. I 
> imagine this is the same for every profession.

Exactly.  At said company I mentioned before, it's usually the one who asks 
for the least money that gets hired (or who already knows one of the 
managers well), nothing to do with how skilled they are or how much 
experience they have.

> If the interviewer asks you to solve the Travelling Salesman Problem so 
> that it can find a route between 500 cities in just a few seconds, you 
> probably don't want to work for them. ;-)

If I were interviewing I'd ask which languages they know, lock them in a 
room with a machine with a language installed they don't know (plus relevant 
learning material), and see how many project euler problems they can 
complete in 24 hours :-)

>>   Take 100 experienced, competent programmers and give them the task of
>> implementing binary search on paper in the programming language they are
>> most fluent with, and perhaps 5 of them will give you a correct
>> implementation. (The rest will fail in some cases mostly due to 
>> off-by-one
>> errors.)

I can believe that, but then does that make someone a bad programmer if they 
can't get an algorithm like that exactly right on paper first time? 
Personally I would prefer someone who "gets" the idea and could roughly code 
it very quickly, then test it and quickly identify modifications needed to 
get it working.  The alternative is someone who either spends 30 minutes 
painstakingly figuring it out in their head, or the one who just recites it 
because he's done it before recently.  I would follow it up with some subtle 
modification requests (eg how to make it more cache friendly, or how to 
efficiently deal with data sets bigger than RAM) to see their thought 
process for something new.

Post a reply to this message

scott wrote:
>> I don't think this is unique to programming. From what I've seen, most 
>> managers get hired based on their ability to spout impressive-sounding 
>> BS rather than their ability to actually manage a department.
> 
> It all comes down to how competent the people are that are 
> interviewing.

Yeah, that seems to be it.

Or perhaps how seriously the management take the interviewer's opinion. 
I've heard of people getting hired even though the person who 
interviewed them said they were rubbish. Obviously, this shouldn't ever 
happen. (Why did you bother interviewing them??)

> If a company is already full of BS managers then of 
> course they are going to employ more BS staff and the problem will never 
> improve.

This appears to be how the entire world works, as best as I can tell.

> Alternatively, if you have a good set of people already in charge, 
> interviewing and making hiring decisions, you are not going to employ 
> any BS managers (or programmers) in the first place.

I haven't seen that happen yet, but I live in hope.

>> I would imagine that quite a few of then know damned-well that they 
>> can't program, and expect to be able to just con somebody into hiring 
>> them. I imagine this is the same for every profession.
> 
> Exactly.

Like I said, I think the difference is that in something abtract like 
programming, it's easier to pretend that you know what you're doing. If 
somebody asks you to build a wall and you can't, it's pretty obvious. ;-)

> At said company I mentioned before, it's usually the one who 
> asks for the least money that gets hired (or who already knows one of 
> the managers well), nothing to do with how skilled they are or how much 
> experience they have.

Ouch. Management short-sightedness appears to be without limit.

> If I were interviewing I'd ask which languages they know, lock them in a 
> room with a machine with a language installed they don't know (plus 
> relevant learning material), and see how many project euler problems 
> they can complete in 24 hours :-)

Ooo, that's harsh, man! Some of those are wicked-hard...

I'm trying to think of a language you could actually throw at me that I 
don't know, but then I realised it's actually not hard: C, Perl, Python, 
PHP, Bash, Ruby, VB, C#, F#, Erlang, any of those would fit the bill. o_O

>>>   Take 100 experienced, competent programmers and give them the task of
>>> implementing binary search on paper in the programming language they are
>>> most fluent with, and perhaps 5 of them will give you a correct
>>> implementation.
> 
> I can believe that, but then does that make someone a bad programmer if 
> they can't get an algorithm like that exactly right on paper first time? 
> Personally I would prefer someone who "gets" the idea and could roughly 
> code it very quickly, then test it and quickly identify modifications 
> needed to get it working.

Mmm, true... It's especially hard to code on paper, without a real 
computer to test it with.

Post a reply to this message

> Darren New <dne### [at] sanrrcom> writes:
>> I usually ask them to print out the prime numbers less than 100 or something.
> 
> primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 91, 97]
> for prime in prime:
>     print prime

primes = f [2..] where f (p:xs) = p : [ x | x <- xs, x `mod` p > 0]
print (take 100 primes)

It's pretty much a standard incantation that most Haskellers will know 
off the top of their heads. Of course, it's horrifyingly inefficient for 
generating large numbers of primes, but for just the first 100...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

>> Alternatively, if you have a good set of people already in charge, 
>> interviewing and making hiring decisions, you are not going to employ any 
>> BS managers (or programmers) in the first place.
>
> I haven't seen that happen yet, but I live in hope.

Funny, the companies I've worked at, plus the customers I've dealt with all 
seem to work this way.  I guess the ones that are rubbish don't get much 
business, or if they do nobody comes back!

> Like I said, I think the difference is that in something abtract like 
> programming, it's easier to pretend that you know what you're doing. If 
> somebody asks you to build a wall and you can't, it's pretty obvious. ;-)

Personally I think it's pretty obvious if someone asks you to write a 
program to show the first 1000 prime numbers, and you can't.  Even a 
non-programmer would recognise that it wasn't working.

> Ooo, that's harsh, man! Some of those are wicked-hard...

Yeh I'm just getting back in to doing some more of them.  Funny how just 6 
or 12 months later you come back and some that seemed wicked hard are 
suddenly easy!

> I'm trying to think of a language you could actually throw at me that I 
> don't know, but then I realised it's actually not hard: C, Perl, Python, 
> PHP, Bash, Ruby, VB, C#, F#, Erlang, any of those would fit the bill. o_O

I guess it also depends on what sort of job you want the person to do.  Do 
you want them to be a C++ code-monkey for their entire career at your 
company, or are you looking for someone to do a bit more.  This will 
determine whether you simply test their C++ skills or find some other way to 
test them with unfamiliar languages and problems.

Post a reply to this message