6 ms·

Ask HN: resources for practicing searching/sorting/big O

8 points by shortlived 16y ago

I've been interviewing and recently got my ass kicked by an interview due to my lack of knowledge regarding searching and sorting algorithms and not being able to calculate runtime performance of said algorithms (ala Big O notation). So I want to take this opportunity to learn more about these topics. I'll continue to read Wikipedia articles and some books but I'm more interested to know of good resources for practice problems related to searching/sorting/big O.

ohashi 16y ago
I love this site: http://www.sorting-algorithms.com/ http://www.sorting-algorithms.com/ As far as practice problems, sorry, don't have anything to help out there.
silentbicycle 16y ago
For me, the thing that really made the lightbulb go on was learning OCaml. Working with complex data structures is where ML really excels, and it dispenses with many superfluous details that appear when studying algorithms in C/Java/etc. Working through the exercises in chapters 2-4 of this book (http://caml.inria.fr/pub/docs/oreilly-book/ http://caml.inria.fr/pub/docs/oreilly-book/) should give you a solid intuition for algorithmic performance, as well as an excellent notation. (Though as OCaml books go, http://www.cs.caltech.edu/courses/cs134/cs134b/book.pdf http://www.cs.caltech.edu/courses/cs134/cs134b/book.pdf is probably better overall.) As a reference, volume 3 of Knuth's _Art of Computer Programming_ is quite good. I know a lot of people just namedrop it and haven't read it, but it really is. Volume 3 focuses on searching and sorting algorithms (perhaps the most practical volume). It takes a bit of mathematical sophistication to follow, but you'll need that for algorithmic analysis anyway.
scottyallen 16y ago
I'd start with the bible of algorithms: http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844 http://www.amazon.com/Introduction-Algorithms-Third-Thomas-C... Read that puppy cover to cover, and try your hand at implementing some of the data structures and exercises in it. I studied it in college, and reviewed out of it before I interviewed at Google. Some of the best interview prep I did. One more tip: when you're practicing, practice on a whiteboard, with no reference material, and only try compiling it on a computer after you're absolutely positive it's correct and have tried a number of test cases. Nothing like simulating real interview situations to help you prepare...
shortlived 16y ago
To answer my own question: the best resource I've found so far is the Algorithms course from ArsDigita University (now defunct). They have good videos, problem sets with answers and a lot of other useful notes. http://aduni.org/courses/algorithms/ http://aduni.org/courses/algorithms/

8 points by shortlived 16y ago

ohashi 16y ago

I love this site: http://www.sorting-algorithms.com/ http://www.sorting-algorithms.com/ As far as practice problems, sorry, don't have anything to help out there.

silentbicycle 16y ago

For me, the thing that really made the lightbulb go on was learning OCaml. Working with complex data structures is where ML really excels, and it dispenses with many superfluous details that appear when studying algorithms in C/Java/etc. Working through the exercises in chapters 2-4 of this book (http://caml.inria.fr/pub/docs/oreilly-book/ http://caml.inria.fr/pub/docs/oreilly-book/) should give you a solid intuition for algorithmic performance, as well as an excellent notation. (Though as OCaml books go, http://www.cs.caltech.edu/courses/cs134/cs134b/book.pdf http://www.cs.caltech.edu/courses/cs134/cs134b/book.pdf is probably better overall.) As a reference, volume 3 of Knuth's _Art of Computer Programming_ is quite good. I know a lot of people just namedrop it and haven't read it, but it really is. Volume 3 focuses on searching and sorting algorithms (perhaps the most practical volume). It takes a bit of mathematical sophistication to follow, but you'll need that for algorithmic analysis anyway.

scottyallen 16y ago

I'd start with the bible of algorithms: http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844 http://www.amazon.com/Introduction-Algorithms-Third-Thomas-C... Read that puppy cover to cover, and try your hand at implementing some of the data structures and exercises in it. I studied it in college, and reviewed out of it before I interviewed at Google. Some of the best interview prep I did. One more tip: when you're practicing, practice on a whiteboard, with no reference material, and only try compiling it on a computer after you're absolutely positive it's correct and have tried a number of test cases. Nothing like simulating real interview situations to help you prepare...

shortlived 16y ago

To answer my own question: the best resource I've found so far is the Algorithms course from ArsDigita University (now defunct). They have good videos, problem sets with answers and a lot of other useful notes. http://aduni.org/courses/algorithms/ http://aduni.org/courses/algorithms/