Hacker News new | past | comments | ask | show | jobs | submit login
Ask HN: Help... I just can't get excited about data structures.
3 points by resdirector on Sept 5, 2013 | hide | past | favorite | 9 comments
I have an interview with a large Bay Area company coming up. They are big on asking data structure and algorithm questions (I've heard). I come from a physics background so I never learnt them in the first place and never had to in a couple of decades of programming.

I've just spent the last twenty five minutes studying data structures and algorithms and I'm bored out of my mind.

Can anyone suggest any materials that bring to light the inner beauty of data structures and algorithms (over and above explaining the theory)?

It's common to be bored studying material that you have no background in, and no motivation for. These things seem unmotivated, disconnected, and completely arbitrary.

In general, I find the best way to study these sorts of things is to have a puzzle to solve, to work through it, and then have a mentor demonstrate a little piece of magic that makes me feel stupid for not having thought of it. Here's an example that you may not know, but most people here will.

In the Pollard Rho method of factoring you compute f(x) repeatedly, and need to find somewhere that it repeats. So you start with x[0] = x0, then compute x[n+1]=f(x[n]). Question - find i and j such that x[i]=x[j].

You can think of this as an implicit linked list between integers, and you're given a starting point and asked to find a loop. How can you do this with fixed, limited additional storage?

Yes, there is an algorithm to do that.

Here's another. Suppose you have a vector of key/value pairs and you need to sort on the key. More, if two keys are equal, their positions in the result must be the same as their positions in the original. Can you do that? Many library sorts don't offer that option - can you find a way?

Having found some of these sorts of problems in the real world and puzzled over them, only to find that (a) they've been done, (b) they've been done better than you thought possible, and (c) there is a touch of magic about the answer, then you might become more engaged with the topic.

Otherwise, maybe the job isn't really for you.

Hi Colin, thanks for your advice.


> In general, I find the best way to study these sorts of things is to have a puzzle to solve, to work through it, and then have a mentor demonstrate a little piece of magic that makes me feel stupid for not having thought of it

(Actually, I could quote your entire comment, thanks, very much appreciated!)

Agreed - context matters, as does having banged your head for hours and then finding a better route, by people who banged their heads for days some years ago.

What's even better is the repeat - where you smile and realise there is no head banging needed :-)

If you have enough time, the Robert Sedgewick's course[1] could be the answer you're looking for. It's much more engaging to watch video lectures and discuss the material with other students than it is to read articles on Wikipedia or some boring textbook.

[1] https://www.coursera.org/course/algs4partI

In addition to vukmir's suggestion of Robert Sedgewick's Coursera video lectures (which have some animations to help visualize the data structures operations), I find "The Algorithm Design Manual" very useful for interviews. The chapters dealing with data structures are concise and contain just enough information to be useful during an interview.

Since you have a physics background, you might be interested in this book: Think Complexity http://www.greenteapress.com/compmod/

The book teaches concepts of Algorithm and Data Structure in the context of Complex System Sciences.

Though it's a bit light-weight, but it might be a good starting point.

I think this is one of those things you either care about or you don't. Personally I don't - I'm quite happy to let smarter/insaner/beardier people do the proper deep worrying about data structure and algorithms; I'll just use what they suggest when they're done.

[edit: not particularly helpful, sorry!]

In their book The Practice of Programming, Kernighan and Pike explain the really important stuff in about 30 pages, chapter 2 in the book. They cover four data structures: array, list, tree and hash table, and two kinds of algorithms: sorting and searching. They say that just these are enough for most common situations.

Thanks everyone here for taking time out to post suggestions, very much appreciated.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact