Interview preparation: V

This note tracks my experience of helping my friend V on their preparation for coding interviews. It has been awhile since last time that V solved a coding challenge, and as any other skill if you don't practice it you lose it. I have two purposes for this note: track V's evolution through the preparation and use it as a place to formalize my method on how to improve in problem solving. By method, I mean the result of experiments that I did on myself (2022) after getting back from many years without practice to coding competitions. This is a living document and you might visit it multiple times if you want to follow V's journey.

Table of Contents

Coding Interviews

To best define the preparation required for coding interviews, let's compare (coding) interview problems with problems that we usually see on Computer Science's courses. They require application of knowledge in Data Structure, Algorithms on Graphs and ad-hoc strategies (e.g. Dynamic Programming, Line-Sweeping, Sliding-Window etc). They differ in two aspects: time to solve and difficult. You have many days to solve an assignment exercise, but only have 15-20 minutes to solve an interview problem. Due this difference in time to solve, you can expect interview problems to be easier than most of the assignments that you've done on University.

Due the wide range of topics covered and restriction in time, interview problems are more like final exam's questions on Data Structure and Algorithms courses than assignments. But there is an important difference. While you do your exam alone and in silence, you have to verbalize your thoughts while solving the interview problem. It is definitely an extra challenge, but also an opportunity to engage with the interviewer in case you don't see the solution right away.

The structure and requirements of coding interviews ask for two distinct preparations: studying and performing. You have to quickly find the solution for the problem using the right data structure, algorithm or technique. While doing so, you have to perform the interview routine: come up with a solution, explain your thought process and code it in a clear and concise way. Learning does not need to be time-bounded, since some concepts require time to sink in. But performing should follow as close as possible a real interview with time constraints and feedback.

A popular way to study is using a curated lists like Blind 75. Such lists cover majority of topics that you see in an interview. These problems cover specific data structures, algorithms and techniques that work as building blocks for your future solutions. While these lists are a good start, you might have more success if you discover the kind of problems that your target company asks. It is not that a company uses only one type of questions, but their interviewers might converge to a sub-set of topics due internal culture or type of business. Since during the interview you do not know the problem's type, it is wise to also study without using hints like Array, Graphs, DP etc. To play safe, practice as many topics and problems that you can.

Spaced-repetition

Spaced-repetition is a study-technique commonly used to memorization of factual information. It uses flashcard as way to store and review content. A flashcard has two sides: front and back. A question or prompt goes in the front of the card, and the information to memorize goes on the back. For example, you have a picture of someone in the front of the card and their name on the back. The technique uses the spacing effect to encode information in the long-term memory by spacing the study sessions, and it is known to have better results than cramming (repeat many times in a single session). Difficult cards appear more often while easier ones are less frequent. Anki is a well-know and flexible program to manage cards.

How spaced-repetition can be applied to problem solving. While this technique has proven to be efficient when memorizing facts, it still unclear its impact on other types of study. My bet is that we can use spaced-repetition to prepare for interviews in the following way. After you solve a problem, you create a card that contains the problem statement (or simplify a link to the problem) and put on the back the steps that you should take to solve the problem. By steps, I mean the observation that you found crucial to solve the problem. Building blocks that you used to solve the problem in the correct order. For example:

  • Constraints require a logarithmic solution.
  • One element of the array with its neighbors is enough to decide which side of the array lays the answer.
  • Use a Binary-search for find the answer.

Method

An studying session is divided in two parts: solving new problems and reviewing old problems.

For new problems, you pick one or two problems per day and spend as much time you need to solve them. If you solved the problem, follow the instructions on Creating a new card. Otherwise, give at least one day to try again. On the second day, you can check a solution to the problem. The goal is to understand the solution and find the gaps on your knowledge. There is a data structure that you are not familiar, a particular technique or idea that makes the problem dead easy to solve. After you learned how to solve the problem (congrats!), create a card for it and move on.

For old problems, you open Anki and practice each available card (new and for review). Avoid reviewing cards using "Easy" button since they schedule a new review for too far way. Use the "Good" button if you solved the problem without any issues: recalled the steps to solve it and passed the problem on the first try. The "Hard" button should be used if you had difficult on recalling the steps to solve the problem or when coding it. Reserve the "Again" button for when you couldn't solve the problem at all. Be emotionally ready for that because this might happen more often than you expect.

Creating a new card

The front of the card has a link for the problem. The back of the card has the steps to solve the problem and optionally an example for the solution. You might get stuck trying to write the perfect card. Don't bother with this. You will have many opportunities to improve them after a review session.

FAQ

When should I work in a new problem?

Don't start working in a new problem if you have more reviews than you have time to get them done in a day, or you already have new cards waiting for you. It is easy to get overwhelmed with the number of reviews. Striving for consistency will bring better results than rushing every other day.

Should I code the solution on every review?

Yes! Reconstructing your steps to the solution and writing the code again will cement the building blocks on your memory.

What should I do if I can't solve a problem?

First of all, that is fine and will happen more frequently than you imagine. Give at least one day before looking to solutions. After you read and understand a solution, ask yourself "what steps should I have done to solve this problem?". Create a card with these steps and review it as any other card.

Meetings

December 2, 2022

The goal of this method is to use spaced-repetition to build your intuition to solve coding challenges. The card has the path to solve the problem and this will be internalized after many repetitions. When solving new problems, a thought will scream at you "Binary Search!" or "This is a Graph Problem". In fact, this is not much different of how we learned math. How many times did you verbalize the steps to isolate \(x\) in an equation? You used descriptive knowledge to build the intuition muscle that later on helped you to perform simplification without using much mental energy.

For next session, you will work in 4 problems which you should apply the method: solve them, create and review the cards. We will review your thought process to solve these problems and what worked and didn't work when create and reviewing your cards:

December 9, 2022

Performing a solution

  • Found the worst case but didn't narrow the search for the optimal algorithm to that case.
  • Explain what are chucks and how to use them.
  • Things that will improve over time:
    • Proficiency in the selected Programming Language.
    • Formulate a high-level plan and execute each part in isolation.

Problems

We will start with Blind 75 problems. As we work through them, we will find that few areas should get more attention. For those, I will add problems to increase your proficiency on specific building blocks. Here is the list of problems for this week:

December 14, 2022

Review last week's problems

  • Done well.
    • Read the problem and checked the problem's constraints.
    • Used the problem constraints to define an upper bound for the solution's time complexity.
  • Things to improve:
    • You might think that easy problems are waste of time. They are not. Easy problems help you to solidify building blocks, become proficient in your chosen programming language, focus on recalling the patterns and prompts, and finally explain the problem in a concise way. Leave to the spaced-repetition the task to decide which problem you have to review. Over time, the easy problems will appear less frequently than the challenging ones.
    • You added "Convert list to set" as one pattern in your card. A pattern is word or sentence that abstract the problem or part of it. Here is some examples of patterns: "Binary Balance Tree", "Directed Graph", "String Search", "Searching in Array". Note that they generalize the problem in terms that are easier to associate with. We are going to upse these terms (or sentences) as hooks to grab ideas from previous problems that we solved. You think "Directed Graph", and few seconds later "poof" you think "Are there cycles in this Graph?".
    • While we love functional programming, imperative programming is usually a better choice for problem solving. It is possible to use immutable data structures, lambdas, maps, filters, and etc, but a simple for loop can reduce 10-15 lines of functional programming to 3 lines. Remember that less code means less surface for errors.
  • Questions about the training:
    • Are you doing at least one/two reviews per day?
      • Every two days.
    • Is the number of reviews sustainable?
      • Yes. Problems are small and there is no issue so far.
    • Have you had chance to look the solutions available here?
      • Yes, but didn't understand part of the solution.
    • What insight did you extract after using this method in the last two weeks?
      • Solution for the past problems come to mind after much effort and don't require paper work before start coding.
  • Questions about the problems:
    • What is common in the solution for these problems? We have to use extra memory to solve the searching problem in \(O(1)\). In Improve Performance Using More Memory, I argued why sometimes this is the case for improving performance.

December 30, 2022

  • Review of a card
    • Find Minimum in Rotated Sorted Array
      • Wrote the patterns and prompts as comments in the code.
        • It has can make easier to compare with the card and assess the review.
        • It makes easier to direct focus.
      • Implemented his solution and than the alternative one.
        • The familiarity with the language is noticeable. Good job!
        • It is fine to breakdown the problem in smaller sub problems.
        • There is no problem with writing the recursive version of binary search, but the interviewer will ask you to save memory (stack) by having the iterative version.
        • Is there something that is blocking you to get to the alternative solution from the begin?
        • What is the difference between both approaches?
  • As I mentioned before, I developed this method after 9 years without working on problem solving. This is an example of how I improved by following this method: old solution from Aug 2021 vs new solution from December 2022. I knew that this is a classical problem, but I didn't remember that I solved it on Leetcode. The new solution is shorter and straight to the point, while the old one is unnecessarily complex.

February 3, 2023

Question from V
How do you organize your knowledge about algorithms and techniques?
  • Years ago, it was allowed to bring a booklet as reference material to competition. So, I had my booklet with important algorithms and ideas that I judged useful to bring to the competitions. I didn't include simple algorithms like DFS or BFS, but ones that are hard or trickier to write. For interview preparation, this is not required since you will end up training frequent problems that appear on interviews and they won't use complex algorithms or ideas. Besides that, there is a human need to organize knowledge into hierarchies. You shouldn't fall in this trap. Let the problems tell what topic you have to master, and let the space repetition decide what material you have to master or not.
Question from V
Should we study algorithms or techniques in isolation?
  • I don't think that it is necessary. The review process takes care of exercising all components of the problem solving skill: extract the patterns from the text, recall algorithms/techniques/ideas using the patterns, adapting previous knowledge to the problem and implementing it. If you focus to execute every single step to the perfection, you will not only sharp your algorithms and techniques but the necessary connections to apply them in practice.

February 10, 2023

In this meeting, we discussed the challenges of understanding problems before solving them. We asked questions like what is our state of mind before and after we understand something? Why is it so difficult to hold the urge to start solving the problem while we are reading it? What can we use to improve our reading skills? We discovered that by using active reading techniques, we can enhance our understanding of problems and improve our ability to solve them.

Let's start with an experiment:

  • Take a problem statement or a paragraph from a book that you never read before.
  • Read it as you normally read.
  • Close the book or switch to other tab in your browser and explain what you've read.
  • Do it again 3 to 5 times.

You will find that the recall became better and better with each repetition. The first recall was disorganized and the last one was organized and fluid, like a story. You might have tried to see part of the page with your mind's eye on the first recall. But gradually, it became unnecessary as the chain of thoughts formed after each repetition. You started empty and finished with a piece of knowledge inside yourself.

What did you feel on each repetition and how did it change over time? I bet that recognizing this difference can help us understand when we should spend more time to really understand something. I asked four people to do this experiment and to report what they felt. The answers were essentially about becoming less anxious and disorganized and more calm and organized. And this is the clue that we can use.

Our reading skills have everything to do with our problem solving skills. As stated in the famous book "How To Solve It by George Polya", the first step of solving a problem is understating it. To understand the problem, we have to read it. And let's be honest, we usually read the problem once and try to solve it as we go along.

We tried to address the issue using active reading techniques. Here is the process that we followed:

  1. Read the problem quickly to get an overall idea.
  2. Read the problem in normal speed to discover important parts.
  3. Take a break and focus on the next 10 breathes (yep! like in meditation).
  4. Read the problem slowly to ensure full understand.

After each step, ask yourself "What is this problem about?". V and I tested this method in Leetcode problems and found an impressive improvement in recall quality. The difference was "night and day".

In conclusion, I will incorporate active reading in my training routine and will report back the results in the future.

Cited by 1