Monthly Essay: Cracking the Coding Interview vs Elements of Programming Interviews
Hello people, welcome once again to this blog. Today, I would like to share with you my learnings about 2 brilliant books for programmers, Cracking the Coding Interview VS Elements of Programming Interviews. I am going to write about my main takeaways and ideas of the books, also about the most important differences between the two, and in which order should you study these books (in my personal opinion). Let’s begin.
Before starting, the quick response about where to start is Cracking the Coding Interview, this book goes into enough detail, explains everything very clear, gives you examples through exercises and figures and so much more. Due to this, in my opinion, you should go first over Cracking the coding interview, but after reading the introduction chapters, go also through the introduction of EPI. After getting a great notion in Cracking the Coding interview and practicing as much as you want, then go to EPI. There are three versions of EPI for three different languages, Java, C++, and Python. Once you have chosen the language in which you feel more comfortable, choose your EPI book and go through it. EPI is more about giving you problems to solve along with possible solutions, approaches, and methodologies to go through the problems for each topic. Nevertheless, you will find in each chapter a quick refresher on each concept, but not as extended as in Cracking the Coding Interview.
The interview process and more
Both books start with the main things you should take into account prior to going straight forward to the technical stuff. That is, what does a technical interview involve? What do we need to know?
Interviewing about data structures and algorithms allows interviewers to try to understand:
- Analytical and coding skills.
- Technical knowledge and CS fundamentals.
- Experience, and communication skills.
All of these skills are very important to work as a software engineer. That is the reason why interviews are about these topics. Interviews will not evaluate these skills 100 % correctly, however, they will give a good approach.
The first important thing, talk out loud! Practice talking about the things you are thinking to get to the solution of a problem, this will reflect your communication skills and will allow your interviewer to follow you and make suggestions if necessary.
In the 2 books, the first things that are discussed are these. The point of going through this is, knowing what the interviewer is expecting to see, what topics are the most important ones, and what should you do depending on the enterprise you are interested in.
If you want to go into detail about FAANG companies and other special cases, navigate through the first chapters of Cracking the Coding Interview, on the other part, if you want to go to the point while getting a very good understanding go to EPI. My advice for understanding these non-technical things? First, go through the first chapters of Cracking the Coding Interview, and then go for EPI.
At the beginning of the book, you will find a road map you should follow depending on the time that you have.
After reading those chapters, you will have a good approach of what to expect, how to create a good résumé, and on which topics concentrate even more. This will depend on your level of experience, whether you are a recent graduate or a senior developer, among other facts.
Main things to remember
Get the right experience:
- Take the big project classes.
- Get an internship.
- Start something, build a project.
- Shift work responsibilities more towards coding.
- Use your nights and weekends.
- A résumé needs to address HR staff
- The points that differentiate you from everyone else, the most important points, should go first.
- Had friends review your resume.
- Practice with Mock interviews.
Complexity — Big O
Understanding this topic is a must. Even if you have already studied it before, my advice is to learn about it again and go through different exercises. So, which book should you use to study this concept?
EPI will not go into too much detail for this topic, nevertheless, Cracking the Coding Interview does more than a great job explaining this subject through a whole chapter and with several examples and exercises.
Working the chapter Vl of Big O in Cracking the Coding Interview is a must.
Big O time is the language and metric we use to describe the efficiency of algorithms in terms of time and space. Not understanding it deeply can really affect you when developing algorithms.
Some of the most common runtimes are O(1), O(log N), O(N log N), O(N), O(N ^ 2), and O(2 ^ N).
Big O uses the called wost case to describe an algorithm, that is the worst runtime we will get in the case that the worst thing happens, for example, if we use linear search to look for an element in an unsorted list, if the element is at the last index or if it is not there the algorithm will perform O(N) runtime at most.
Time is not the only thing that matters in the algorithm, we also care about the amount of memory (space) required by an algorithm. This knowledge will allow us to understand how to do different trade-offs depending on our resources.
So the main things to take into consideration are:
- Space complexity, how is memory used on each call?
- Drop the constants, if we have a for loop going over a data set and performing an operation it would take O(N). Also if we have two non-nested for loops going over the same data set and performing an operation we would describe it as O(2N), and dropping constants O(N).
- Drop the non-dominant terms, for example, O(N + log N) becomes O(N). This is because of the rate at which the operations grow, O(N) grows way faster than O(log N).
- Multipart algorithms: If your algorithm performs a task, finishes, and then does another, you add the runtimes (like non-nested for loops). If your algorithm performs a task for each time you do something else, then you multiply the runtimes (like 2 nested for loops).
- Amortized time, allows us to describe that although a worst-case happens once in a while, once it happens it will not happen again for so long that the cost is amortized.
In addition to those things, it would be interesting to understand log N runtimes, recursive runtimes (check also memorization technique to optimize exponential time recursive algorithms) and then go through examples and exercises (Cracking the Coding Interview has great content for this).
Data structures, Algorithms, and Solving Principles
I have reviewed some data structures in past blog posts, nevertheless, I would like to give you my main takeaways on this. My recommendation is, start going through these topics on the Cracking the Coding Interview book, in parallel consult other resources to have a better idea while you study. Then, you can practice them in that same book or go through very interesting problems in the EPI books, where you will also find a refresher to solidify your knowledge. Here I share a summary that you will found in the EPI book.
According to both books, important things to take into consideration about data structures are:
Primitive types: Know about how int, char, double, etc. are represented in memory and the primitive operations on them.
Arrays: Fast access for an element at an index, slow lookups (unless sorted), insertions and deletions. Notions of iteration, resizing, partitioning, merging, etc.
Strings: Know about its representation in memory. Know the basic operators such as comparison, copying, matching, joining, splitting, etc.
Lists: Know the trade-offs with respect to arrays. Be comfortable with iteration, insertion, and deletion within singly and doubly-linked lists. Know how to implement a list with dynamic allocation (ArrayList for example), and with arrays.
Stacks and Queues: Recognize where the semantics of LIFO (last-in, first-out) for stacks, and FIFO (first-in, first-out) for queues, are applicable. Know array and linked list implementations.
Binary trees: Used for representing hierarchical data. Know about depth, height, leaves, search path, traversal sequences, successor/predecessor operations.
Heaps: Key benefit is O(1) lookup find-max, O(log N) insertion, and O(log N) deletion of max. Node and array representations. Min heap variant.
Hash tables: O(1) insertions, deletions, and lookups. The main disadvantages: not suitable for ordered queries (since they are unordered by definition), the need for resizing, and poor worst-case performance. Know the implementation using an array of buckets and collision chains (collision handling).
Binary search trees: Key benefit is O(log N) insertions, deletions, lookups, find min and max, successor, predecessor when the tree is height-balanced. Understand nodes and pointers, be familiar with the notion of balance, and operations maintaining balance.
Sorting: Uncover a structure by sorting the input.
Recursion: If the structure of the input is defined in a recursive manner, design a recursive algorithm that follows the input definition.
Divide and conquer: Divide the problem into two or more, smaller independent sub-problems and solve the main problem by using the solutions to the subproblems.
Dynamic programming: Compute solutions for smaller instances of a given problem and use these solutions to construct a solution to the problem. That includes the use of cache for performance.
Greedy algorithms: Compute a solution in parts or stages, then make choices that are locally optimum at each step; these choices are never undone.
Invariants: Identify an invariant and use it to rule out potential solutions that are suboptimal/dominated by other solutions.
Graph modeling: Describe a problem using a graph and solve it by using an already existing graph algorithm.
Concrete examples: Manually solve concrete examples and then build a general solution (very important and useful). Try small inputs.
Case analysis: Split the input/execution into a number of cases and solve each case in isolation.
Iterative refinement: Most problems can be solved using a brute-force approach. Find such a solution and improve upon it.
Reduction: Use a known solution to some other problem as a subroutine.
Adding more to this, in Cracking the Coding Interview we can read about a Problem-Solving Flow Chart, that consists of:
- Listen: Pay close attention to details while the problem is being exposed and save mental notes on the key consideration. Those key aspects might be necessary to take into account to construct an optimal algorithm.
- Example: As mentioned before examples are of great help, nonetheless, you must debug your example to consider special cases and different sizes of input.
- Brute force: Work to get a brute-force solution, do not worry about efficiency yet. Do not code yet, but find it as soon as possible so you can also start thinking about improvements.
- Optimize: Go through your brute-force solution using the BUD optimization (bottlenecks, unnecessary work, duplicate work). That is, look for unused info. Solve manually by using an example and then reverse engineer your thought process. Solve it incorrectly and think about why the algorithm fails. Make time vs space tradeoffs.
- Walkthrough: If you get an optimal solution go through your approach in detail, making sure that you have understood every part before start coding.
- Implement: Modularize your solution and write clean code.
- Test: Walk through your code as you would in a code review, check unusual code, hot spots, create small test cases, review special cases, and edge cases.
More important topics
As explained above depending on your experience and the job, your interview might have more material on some topics than on others. Some important topics to review that are present in these books are:
- Object-oriented design, design patterns. Other programming paradigms.
- System design, and scalability (find good design problems in the EPI book).
- Testing, types of testing, styles of programming (TDD, BDD).
- Language questions (if you know you will be interviewed for a specific language). Here the Elements of Programming Interviews book can help a lot in an included section design for this (remember you can find a book for Java, C++, or Python).
- Common tools: Databases, version control systems, networking, etc.
Both books are amazing and brilliant resources to prepare you for your coding interview, it is up to you to decide whether go for one or the other (or the two). If you ask me, go for the two and do them in the order I told you above, if you only want to go for one book:
- If you need a big refresher on the topics before beginning working on problems go for Cracking the Coding Interview, if you cannot remember enough or if you know just a little of complexity and big O, go again for the same book.
- If you want to go more specific over a language (Java, C++, or Python) and you already have experience with the concepts but need to work on problems go for the EPI.
One thing that I really like about the books is that they have paths to follow according to the time you have to study. I really like especially how EPI does this.
As a bonus, remember to practice using tools such as Hackerrank, Leetcode, and others!
Thank you once again for reading up to this point, I hope you found this review useful and that you learned a lot!
See you in my next blog.