![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Darren New <dne### [at] san rr com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> 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/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
> Darren New <dne### [at] san rr com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |