Introduction to the design & analysis of algorithms

What Hacker News says

1. hintymadNov 2024
   If one does want to get into FANNG-like companies or whatever those acronyms are, I'd suggest a few practical tips.

   - Use probability as your advantage. Or put it another way, perseverance works. Do recognize that interviewing is a hit-and-miss game. Say with your preparation your chance of getting into any of your top 10 companies is 30% -- a pretty low number just for us to steelman argument. Let's say you can try each companies three times a year (most companies have cool-down period per department instead of per company). Then in 5 years, you can try 30 times. The probability of failing all of them is 0.3^30 ~ 10^-16. That is, practically, zero. Of course, this assumes that each attempt is independent of each other, and we can maximize such assumption by keeping learning the lessons of failures. By the way, this is also a reason why one can see so many so-so engineers in a big companies.

   - Do not cram all of the leetcode questions. That's insane. Remember the quote from Invincibles: "when everyone is a superhero, nobody will be"? It applies to cramming too. Instead, use the time to study fundamentals. Pick up Kleinberg's Algorithm Design, Levitin's Introduction to the Design and Analysis of Algorithms, or Skiena's The Algorithm Design Manual. Note these books are not that academic. They all focus on the process of designing an algorithm from constraints and basic principles.

   - Do not worry about Leetcode Hard. Yes they will be asked from time to time by an interviewer, but see my suggestion #1. If you really want to try Leetcode Hard, at least ignore the ones that require deep ad-hoc analysis or the ones that require an aha-moment. They are talent filters or memory filters or obedience filters, but they won't improve your engineering expertise. Then, why bother? And trust me, it is actually rare for you to get a Leetcode Hard question.

   Show morethread
2. careless_lisperJul 2023
   I'm biased towards more practical books but here you go

   - Designing Data-Intensive Applications by Kleppmann - not in your circle of interest necessarily but not in your circle of non-interest either.

   - Introduction to the Design & Analysis of Algorithms by Levitin - not very popular but a great book. Interestingly, it groups algorithms around design techniques e.g. decrease-and-conquer, divide-and-conquer, greedy, DP.

   - Algorithms by Sedgewick and Wayne - great algorithms book if your main programming language is Java, I keep coming back to it.

   Show morethread
3. sdnlafkjh34rwJan 2020
   Just as one data point - I went through the onsite recently and I personally found that PDF to be unhelpful. While it does list everything you need to know, it also lists way too many things that you probably don't need to know. It's basically an exhaustive list of basically every resource and topic that could possibly show up in the algorithmic interview. In my view you just need to cover Cracking the Coding Interview and then do 50-100 Leetcode questions. If you have a strong grasp of intro algorithms that would work too, except for engineers like me who didn't major in CS and hence never took an algos course.

   --- Here's the actual PDF contents -------

   Algorithm Complexity: ○ Please review complex algorithms, including big O notation. For more information on algorithms, visit the links below and your friendly local algorithms textbook. ■ Online Resources: Topcoder - Data Science Tutorials, The Stony Brook Algorithm Repository ■ Book Recommendations: Review of Basic Algorithms: Introduction to the Design and Analysis of Algorithms by Anany Levitin, Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Algorithms For Interviews by Adnan Aziz and Amit Prakash, Algorithms Course Materials by Jeff Erickson, Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

   ● Sorting: ○ Know how to sort. Don't do bubble-sort. ○ You should know the details of at least one nlog(n) sorting algorithm, preferably two (say, quicksort and merge sort). Merge sort can be highly useful in situations where quicksort is impractical, so take a look at it.

   ● Hash Tables: ○ Be prepared to explain how they work, and be able to implement one using only arrays in your favorite language, in about the space of one interview.

   ● Trees and Graphs: ○ Study up on trees: tree construction, traversal, and manipulation algorithms. You should be familiar with binary trees, n-ary trees, and trie-trees at the very least. You should be familiar with at least one flavor of balanced binary tree, whether it's a red/black tree, a splay tree or an AVL tree, and you should know how it's implemented. ○ More generally, there are three basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list), and you should familiarize yourself with each representation and its pros and cons. ○ Tree traversal algorithms: BFS and DFS, and know the difference between inorder, postorder and preorder traversal (for trees). You should know their computational complexity, their tradeoffs, and how to implement them in real code.

   ○ If you get a chance, study up on fancier algorithms, such as Dijkstra and A

   (for graphs). ● Other data structures: ○ You should study up on as many other data structures and algorithms as possible. You should especially know about the most famous classes of NP-complete problems, such as traveling salesman and the knapsack problem, and be able to recognize them when an interviewer asks you them in disguise.

   ● Operating Systems, Systems Programming and Concurrency: ○ Know about processes, threads, and concurrency issues. Know about locks, mutexes, semaphores and monitors, and how they work. Know about deadlock and livelock and how to avoid them. ○ Know what resources a processes needs, a thread needs, how context switching works, and how it's initiated by the operating system and underlying hardware. ○ Know a little about scheduling. The world is rapidly moving towards multi-core, so know the fundamentals of "modern" concurrency constructs.

   ● Coding: ○ You should know at least one programming language really well, preferably C/C++, Java, Python, Go, or Javascript. (Or C# since it's similar to Java.) ○ You will be expected to write code in your interviews and you will be expected to know a fair amount of detail about your favorite programming language. ○ Book Recommendation: Programming Interviews Exposed; Secrets to landing your next job by John Monagan and Noah Suojanen (Wiley Computer Publishing)

   ● Recursion and Induction: ○ You should be able to solve a problem recursively, and know how to use and repurpose common recursive algorithms to solve new problems. ○ Conversely, you should be able to take a given algorithm and prove inductively that it will do what you claim it will do. ● Data Structure Analysis and Discrete Math: ○ Some interviewers ask basic discrete math questions. This is more prevalent at Google than at other companies because we are surrounded by counting problems, probability problems, and other Discrete Math 101 situations. ○ Spend some time before the interview on the essentials of combinatorics and probability. You should be familiar with n-choose-k problems and their ilk – the more the better.

   ● System Design: ○ You should be able to take a big problem, decompose it into its basic subproblems, and talk about the pros and cons of different approaches to solving those subproblems as they relate to the original goal. ○ Google solves a lot of big problems; here are some explanations of how we solved a few to get your wheels turning. ■ Online Resources: Research at Google: Distributed Systems and Parallel Computing ■ Google File System ■ Google Bigtable ■ Google MapReduce

   ● Development Practices and Open-Ended Discussion: ○ Sample topics include validating designs, testing whiteboard code, preventing bugs, code maintainability and readability, refactor/review sample code. ○ Sample topics: biggest challenges faced, best/worst designs seen, performance analysis and optimization, testing and ideas for improving existing products.

   Show morethread
4. mavelikaraOct 2017
   I enjoyed reading Anany Levitin's Introduction to the Design and Analysis of Algorithms. Algorithms in this book are organized around problem-solving techniques - Decrease-and-Conquer, Divide-and-Conquer, Transform-and-Conquer etc - rather than application areas. I found this style very useful to develop an arsenal of techniques I can employ when I come across a new problem.

   Also, for practicing programers, studying data structures is more important than algorithms. I often refer to Sally Goldman's book A Practical Guide to Data Structures and Algorithms Using Java for this.

   Show morethread
5. meadoriJan 2016
   Having owned and read through "Introduction to Algorithms" for years I agree that it is a good book. However, recently I have been feeling like it is recommended way too often without thought.

   It is not the best when it comes to explaining things in an intuitive manner. It is a great reference book with lots of algorithms and proofs.

   In recent years I have been drawn more towards Levitin's "Introduction to the Design and Analysis of Algorithms".

   Anyone else have similar feelings about "Introduction to Algorithms"?

   Show morethread
6. vital101Oct 2010
   Introduction to the Design and Analysis of Algorithms (http://www.amazon.com/Introduction-Design-Analysis-Algorithm...) is a good refresher.
   thread