Re: OT: Binary Search - Should They Know It?

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

On Wed, 20 May 2009 19:37:36 -0700, jehugaleahsa@xxxxxxxxx <jehugaleahsa@xxxxxxxxx> wrote:

[...]
It would be nice to find someone who had read these books:

Gang of Four (maybe)
Patterns of Enterprise Architecture (definitely)
Applying UML and Patterns (preferrably)
xUnit Test Patterns (maybe)

I've never read any of those books. In fact, they were all published well after I completed my Computer Science degree and entered the industry (heck, as near as I can tell, most of those were published this century). But I still consider myself a reasonably competent programmer.

As for your more general question, I think it really depends on what kind of person you're trying to hire, and what training they've been through. A graduate from a university degree program absolutely should be familiar with basic data structures such as a hash table, or an algorithm like a binary search. In fact, the very first interview I had as part of the screening for my very first full-time industry job, I had to write a binary search (in 68000 assembly, no less!).

But there are really smart people out there who haven't been through a formal training program. One guy I worked with early on had a PhD in some sort of field of astronomy. I don't know whether he started out knowing what a binary search or hash table was; it's possible when he was first hired, he didn't. But it wouldn't have taken him an hour to get up to speed on either.

Many companies spend too much time filtering on basic credentials, and not enough time on basic intelligence. Of course, in a world where 50% of all people have an IQ under 100, not every company is going to be able to hire the smart people. But hopefully the relative number of higher-intelligence people are in a field like programming, as compared to jobs demanding less-skilled labor. We'd all be a lot better off if the programmers who met the credential requirements (including having been shown a binary search or hash table), but who aren't really all that bright, were refused jobs and sent off to flip burgers, while other folks who can learn everything they need to know about a binary search or hash table in an hour get the programming jobs.

Of course, there is also the question of how important it is for someone to know those kinds of things these days. I can implement a binary search or a hash table, no problem. But is that really an important skill for most programmers now? I don't know. At least in the context of .NET, isn't it more important to know that there _are_ already built-in ways to sort data, or to map from some value to some other value quickly, than to know _how_ all that works?

After all, even in "the olden days" when we all had to learn how to write a binary search or hash table, it wasn't super-critical that a person knew assembly language, never mind microcode, or how the various parts of the computer hardware works. It was still possible to write a correct, functioning, even efficient program without those low-level details.

In the end, what a company needs to do is figure out what they are hiring for, what skills that person needs, and figure out a way to measure those skills in a reliable way. That's all. If those skills involve knowing details like how to write a binary search or hash table, then that sort of thing needs to be verified. If they don't, or the more important characteristic is simply basic intelligence, then measure what you need, and train the person as needed later, taking advantage of the fact that you started by selecting a smart person who can learn quickly.

Pete
.

Relevant Pages

  • [PATCH 2/2] Rewrite jump_label.c to use binary search v2
    ... After the discussion on linux-kernel I decided to rewrite the ... hash table based jump_label.c to use binary search as proposed. ... +static struct jump_entry * ...
    (Linux-Kernel)
  • Re: OT: Binary Search - Should They Know It?
    ... A Real Programmer is able to implement it correctly. ... Triviality is no measure of uselessness. ... On the other hand, it is true that the trivial stuff is tested for much more often than genuine problem-solving skills, simply because it's easier to do. ... Actually, asking someone "show me a binary search" or "what is a class" is more of a test for the interviewer, as they have to be able to interpret the answer and follow up while the interviewee could spit out a memorized response. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: RosAsm jut got a 3X Speedup !!!
    ... > CheckSum64, PointerToFamilyList, ChainPointer ... It does *not* distribute the keys well throughout the hash table. ... suspect that you're using a linear search to resolve collisions. ... but a simple little binary search would work great. ...
    (alt.lang.asm)
  • Re: [PATCH 2/2] Rewrite jump_label.c to use binary search
    ... hash table based jump_label.c to use binary search as proposed. ... Thanks for proposing this patch, ... #ifdef HAVE_JUMP_LABEL ...
    (Linux-Kernel)
  • Re: What are my options for dictionary hashing?
    ... do the insertion verses the cumulative time needed for a linear search ... hash tables will win over binary searches. ... We have experimented both with different hash algorithms and different numbers of linear lists, and are satisfied that what we use now is close to optimum. ... so I'll model the behavior of a binary search and see if the ...
    (comp.lang.forth)