A friend was cleaning our their bookshelf and gave me their spare copy of this book. If you are interested in turning machines, intractability, P = NP or P != NP this is probably the textbook for you. Not having a formal compute science background I had a hard time following some sections.

GoodReads

Chapter Notes & Quotes

1. Regular Languages
   • Pretend to be an automaton, you receive and input string and must determine whether it is a member of the language the automaton is supposed to recognize. You see the symbols in the string one by one and after each, you must decide whether the string so far is in the language.
   • Deterministic finite automaton (DFA) - When the machine is in a given state and given the next symbol we know with 100% certainty what the next state will be.
   • Nondeterministic finite automaton (NFA) - When the machine is in a given state and given the next symbol several choices may exist for the next state.
   • After an NFA reads a symbol it splits into multiple copies of itself and follows all possible paths in parallel. Each copy proceeds as before, and if there are subsequent choices, it splits again. If the next symbol doesn’t appear on any of the arrows exiting this path’s state, the copy dies. If any copy are in the accept state then the input string is considered accepted.
   • NFAs are like a parallel computation where several processes are running concurrently.
   • Every deterministic finite automaton is automatically a nondeterministic finite automaton.
   • Every NFA can be converted into an equivalent DFA.
2. Context-Free Languages
   • Pushdown automata - Like a nondeterministic finite automata but have a stack.
3. The Church-Turing Thesis
4. Decidability
   • Certain problems are algorithmically solvable and others are not.
   • Knowing a problem is unsolvable is useful because you know it must be simplified or altered before you can find a solution.
   • Even some ordinary problems that people want to solve turn out to be computationally unsolvable.
5. Reducibility
   • Primary method for proving that a problem is computationally unsolvable.
   • Reduction - Converting one problem to another problem so the solution to the first problem can be used to solve the second. Ex: Problem of measuring rectangle’s area reduced to measuring its width and height.
6. Advanced Topics in Computability Theory
   • Any incompressible string has roughly an equal number of 0s and 1s.
7. Time Complexity
   • Exponential time algorithms typically arise when we search through a space of solutions (brute-force search).
   • Polynomially Equivalent - The algorithm can simulate another with only a polynomial increase in running time.
   • Polynomially Verifiablity - Verifying the answer can be done in polynomial time.
   • If a polynomial time algorithm exists for an NP-complete problem then all problems in NP would be polynomial time solvable.
   • P = membership can be decided quickly.
   • NP = membership can be verified quickly.
8. Space Complexity
9. Intractability
10. Advanced topics in complexity theory
    • Optimization problems seek to find the best solution among a set of possible solutions.
    • Fermat test provides a probabilistic test for primality. We call a number pseudoprime if it passes all Fermat tests.
    • Gain evidence of a code’s security by showing that the complexity of breaking the code is linked to a the complexity of some other problem for which there is compelling evidence of intractability.
    • Private-Key Cryptosystem - The same key is used for both encryption and decryption.
    • Public-Key Cryptosystem - The private decryption key is different than the public encryption key.

If I had to pick one book to prepare for coding interviews with it would be this one.

I’m largely self-taught and I this book was as great at both providing patterns to approach different problems and explaining the recommended solutions. I purchased this book along with “Elements of Programming Interviews” and while I strongly suggest purchasing both books, I feel this one is better for people without a formal computer science background.

I was a bit discouraging when I first started practising with these books but as I worked through them I started to enjoy the process. You eventually start seeing common patterns, become familiar with common algorithms/data structures, and get comfortable ‘running’ code in your head. These are more than just useful interview skills. Estimating how code scales lets you judge when it’s worth increasing code complexity to optimize or when a simple brute force is ‘good enough’ and once you are in the habit of ‘running’ code in you head potential errors will start to jump out at you while reading code. I’d recommend both these books for anyone interested in becoming a better software engineer.

Goodreads

• Good choice for entry level positions and for companies that are not doing “program a whiteboard” style interviews.
• Coding problems are fairly simple compared to other interview books.
• Good selection of behavioural/talk about x style questions.

Goodreads

Not having a formal computer science background I found working through this book difficult but well worth the time. If you are also largely self-taught I’d recommend working through “Cracking the Coding interview” in parallel. I found the problems in CTCI a bit easier with better explanations which helped me to tackle the problems in this book.

This is a fairly dense book so I’d recommend buying it well before you intend to start interviewing and try doing a question or two a day.

I was a bit discouraged when I first started practising with these books but as I worked through them I started to enjoy the process. You eventually start seeing common patterns, become familiar with common algorithms/data structures, and get comfortable ‘running’ code in your head. These are not just useful interview skills. Estimating how code scales lets you judge when it’s worth increasing code complexity to optimize or when a simple brute force is ‘good enough’ and the habit of ‘running’ code in you head causes potential errors to jump out at you while reading code. I’d recommend both these books for anyone interested in being a better software engineer.

Goodreads