Algorithms

Trojan

Just thinking about algorithms, wondering how often developers actually need to analyse the algorithms put to use in everyday coding.

- Are you aware of the algorithms you are using?

- What algorithms do you consider essential for a programmer to know?

- Which (if any) would you test for in a technical interview?

Al.

Baz_

Well I don't think that can be generally answered, it depends on the job.

Me having never done a computer type interview, and never having conducted one, I don't know what is tested for, but obviously the absolute basics are critical (searches, sorts, list manipulation etc.). But even they are included in libraries supplied with your chosen programming environment.

It would be hard to know which are necessary because people going for a particular job will obviously have knowledge of their particular job area (mostly anyway) so they could pretty easily pick up algorithms in relation to the job.

Now the disclaimer, I could have totally misinterpreted your post but that's just what I think, and also I think its more important to be flexible in the type of code you can write.

Void

I wrote a hash table implementation for my game. And I'm looking at using heapsort to order my scene graph (dunno if heapsort is appropriate, the graph isn't a perfect heap). Apart from that, in my work, most of the "sorting" is done with SQL "ORDER BY" statements I suppose.

Algorithms will only come into play for low level languages (C in particular, it lacks standard library implementations of this kind of thing). When I interviewed for Funcom they gave me some interesting stuff in an exam.

Example:
7 lines of 68K assembly code, problem was to find out what it did, easy enough if you know assembly. It was a subtle algorithm to count the number of set (1) bits in a word, using shifts and ANDs.

Other question was to write itoa() in C without using any library calls. Bloody awkward

ecksor

I try to be aware of whether or not I'm using the best algorithm and associated data structure for the job at hand. Usually from the point of view of whether it's a logical way to represent and manipulate the information rather than speed. The language I'm using will often influence my choice also.

Snaggle

The algorithms you're aware of depends on too many factors to answer accurately. If I were writing a program in C from scratch on my own, and assuming I don't use anybody else's libraries bar the standard C libraries, I would know exactly what algorithms are running. If I were writing an application that made remote calls to an SQL databases, I'll have next to no clue, if I was using somebody's custom crypto library, I'd have a vague idea of some of the algorithms, it depends on the situation

Few algorithms are essential for every programmer to know, again it depends on what language they are coding in and what application/part of an application they are coding. If I were to rate somebody on general coding proficiency though I'd expect them to know all the classic algorithms you see in every algorithm book (sorting, searching, data structures like lists and trees)

Be careful about asking tough questions in technical interviews, people are feeling nervous, they don't have the time to think a complex algorithm through, and they'll probably have to demonstrate their code on paper (which is awkward at best)

http://joel.editthispage.com/stories/storyReader$20

has a good article on interviewing programmers

Blitzkrieger

From what I've been hearing from the 80-100 people in my course looking for jobs this year and last, only one company even gave some code and asked what it does. That was AIB who then put everybody they hired to work typing data into a database

[CrimsonGhost]

For anyone interest AIB have an absolutely great graduate recruitment scheme for programmer type people. Offering 15k a year with extensive training (read: you'll get to do some mcse's). AIB seem to not have a clue about the current market trend for IT graduates. I'd steer clear, you can easily earn a lot more elsewhere. Although send them a cv if you want interview practice.

Trojan

Just in that vein, does anyone have any real jobs going? See post on Work if so, I'm looking at the mo.

Cheers,
Al.

satchmo

no, itoa() converts a given number into a string representation of that number, so an input of 28 would give "28". There's also a radix with which the number is specified, so if the radix was 2 then the output would have to be "11100".
Bugger of a question, if you had to do all that.

Snaggle

If they asked you to do it in C, the sly b@stard would

char *itoa (int i) {
char * str = malloc (whatever size);
sprintf(str, "%d", i);
return str;
}

Draco

<font face="Verdana, Arial" size="2">Originally posted by [CrimsonGhost]:
For anyone interest AIB have an absolutely great graduate recruitment scheme for programmer type people. Offering 15k a year with extensive training (read: you'll get to do some mcse's).</font>

Heh - I've hear £25K is the average this year...

[CrimsonGhost]

<font face="Verdana, Arial" size="2">Originally posted by Draco:
Heh - I've hear £25K is the average this year...
</font>

Hmm, not what I heard, least not for graduate recruitment. I'll check though, my fiancee is working in an AIB branch and all job offers are sent to all staff first, i'll ask her to get me details of jobs posted over the last few months and check and get back to you on it.

satchmo

I'm pretty sure sprintf() would count as a library call

Greenbean

itoa() - that mean you had to actually know the asci table of values?

Draco

<font face="Verdana, Arial" size="2">Originally posted by [CrimsonGhost]:
Hmm, not what I heard, least not for graduate recruitment. I'll check though, my fiancee is working in an AIB branch and all job offers are sent to all staff first, i'll ask her to get me details of jobs posted over the last few months and check and get back to you on it.</font>

I didn't mean in AIB, I ment in the recruitment market in general.

ecksor

Sprintf() is a library call, but so is malloc().

Anyway, I wrote one in C for anyone who's interested.

char *itoa(int i, int radix) {
        int negative = 0;
        int count = 0;
        int temp;
        char *buffer;

        if( i < 0 ) {
                count++;
                negative = 1;
                i = abs(i);
        }
        temp = i;
        do {  /* count the digits, save lots of malloc()s and other ****** */
                temp /= radix;
                count++;
        }
        while( temp > 0 ); 

        buffer = malloc(count * sizeof(char) );
        if ( buffer == NULL ) return NULL;

        do {
                buffer[count-1] = (char) (i % radix) + '0';
                i /= radix;
        } while(count--);
        if(negative) buffer[0] = '-';
        return buffer;
}

Snaggle

<font face="Verdana, Arial" size="2">Originally posted by Jazz:
I'm pretty sure sprintf() would count as a library call</font>

Yeah it would, I also wrote one in Haskell using recursive function calls

itoa i = itoa2 i []
where itoa2 i xs = case divMod i 10 of
(0, x) -> chr (x + ord '0') : xs
(i, x) -> itoa2 i (chr (x + ord '0') : xs)

Greenbean

What the frick is Haskell?

[CrimsonGhost]

<font face="Verdana, Arial" size="2">Originally posted by Draco:

Originally posted by [CrimsonGhost]:
Hmm, not what I heard, least not for graduate recruitment. I'll check though, my fiancee is working in an AIB branch and all job offers are sent to all staff first, i'll ask her to get me details of jobs posted over the last few months and check and get back to you on it.</font>

I didn't mean in AIB, I ment in the recruitment market in general.

Ahh, gotcha, anyway got those. AIB are offer 15k ish to graduates. but up to 22-23k with experience, at least at the few offer I've looked at. 25k for graduates seems reasonable.

Keeks

Just out of interest does anyone know on some good resources on Alorithms. I have hundreds somewhere, just too lazi to sort through them.

Slaanesh

Keeks, use a heap sort :P

Keeks

roflmao
I prefer Bubbles!

[This message has been edited by Keeks (edited 03-04-2001).]

jmcc

<font face="Verdana, Arial" size="2">Originally posted by Trojan:
Just thinking about algorithms, wondering how often developers actually need to analyse the algorithms put to use in everyday coding.
</font>

Most of the time, you have to be able to get the thing to work first. For cheap and nasty solutions, algorithms are not the primary concern. When you get to programs that have to do important things, then shaving some cycles by using a more efficient algorithm is important. The most basic algorithms would be loops, sorts, searches, hashes etc. SQL is actually a far more terrifying language than C or TCL. You will learn to fear the words Cartesian Product. :-) But SQL requires you to think declaratively which takes some time to get used to. TCL is a very nifty language. which can be picked up in about 3 hours or so.

<font face="Verdana, Arial" size="2">
- Are you aware of the algorithms you are using?
</font>

Yes but I generally don't think about them because I am just happy/relieved my progs work. ;-) Actually the stuff I am doing at the moment is spider/agent/database work. So it consists of a mix of Perl, TCL and SQL.

Seriously though, some of the algorithms used in crypto [1] are very simple - it is how they are used. Knowing an algorithm and knowing how to implement it can be two very different things. Getting proficient in your programming language of choice (VBasic/Basic excluded) is the first part of the work. It will give you a good basic intro to the various elementary algorithms.

However a knowledge of algorithms is important is where you have to figure out what someone's code actually does. I think the hardest time I had there was working out the algorithm used in the BSkyB smartcards. But that was in a different life. ;-)

There are some good books on algorithms - I think that "Algorithms" is one of them - it is available for Pascal and C. It covers most of the common algos like searching, loops, basic crypto.

After a while you begin to use algorithms without even thinking. A more important thing to worry about would be, from a developer's point of view, how to get from the input data to the results in logical, modular steps. The other thing to do is to keep a lab notebook of nifty code solutions.

Regards...jmcc
[1] I work for NSA - the other NSA.

Greenbean

Theres a book, which I must get the name of, I'm going to be buying it. Its a big white book and its being nicked named "the bible" in college. Its one pretty nifty book - it does EVERYTHING to do with algorithms, syntax, semantics - whatever the hell you want to know about programming and logic - but the main thing isn't the teaching it will give you but instead its ability to reference you the best alogorithms on the spot. Say you're about to sort a set of data, but you need good performance on a list - look at its sorting chapter - there you go: all the sorting algorithms under the sun with reference to what they're good for. Need it for a binary tree structure - it will have the best one.. and so on. I stick the name of it down on this thread if I get the time.