Skip to content

Instantly share code, notes, and snippets.

@junjunparkpark

junjunparkpark/InterviewPrep.md

Last active October 12, 2019 16:47
Show Gist options
  • Save junjunparkpark/912ff1bce74170d92c77063129c615db to your computer and use it in GitHub Desktop.
Save junjunparkpark/912ff1bce74170d92c77063129c615db to your computer and use it in GitHub Desktop.
Download ZIP
Software Engineering Interview Prep
Raw
InterviewPrep.md

Software Engineering Interview Prep

High Level Roadmap:

Data Structures (Time/Space Complexity and their guarantees):

Data Structure Algorithms (Time/Space Complexity and their guarantees):

  • Binary search (implement it both iteratively and recursively)

  • Randomized quicksort (pay extra attention to the partition subroutine, as it’s useful in a lot of places)

  • Mergesort

  • Breadth-first search in a graph

  • Depth-first search in a graph (augment it to detect cycles)

  • Breadth-first/Depth-first search through a matrix

  • Tree traversals (pre-order, in-order, post-order)

  • Topological sort (using Tarjan’s algorithm)

  • Dijkstra’s algorithm (without decrease-key)

  • Longest common subsequence (using dynamic programming with matrices)

  • Knapsack problem (also dynamic programming)

  • Know the Time/Space complexities of these algorithms and data structures

  • Know the difference between amortized, average, and worst-case time guarantees.

Optional:

  • Heap sort
  • Quickselect
  • Median of Medians

Bit Manipulation:

  • Be able to explain what AND, OR, and XOR do.
  • Know what a signed integer is.
  • Know that there are 8 bits in a byte.
  • Know what assembly is (from a high level)
  • Get a sense of the basic operations that hardware exposes.

Databases:

  • SQL Databases:
    • Learn how to design a SQL database schema; it comes up in interviews often.
    • Read about ACID, the CAP theorem, and BASE
      • (you don’t need to memorize the terms, just understand the concepts at a high level.)
    • Understand why joins can become unscalable.
    • Learn the basics of NoSQL databases.
  • NoSQL Databases

Caching:

  • Read about caches and cache efficiency.
  • Know what a cache miss is.
  • Know that reading from registers is lightning-fast
  • Reading from the various caches is pretty fast
  • Reading from memory is slow
  • Reading from the hard disk is abysmally slow.
  • Read how to implement an LRU cache
    • Write one that gets and sets in worst-case O(1) time.
    • This is a weirdly common interview problem.

Networking:

General Web Development:

  • Learn the standard ways to speed up a slow website:
    • Adding database indices to optimize common queries
    • Better caching
    • Loading front-end assets from a CDN
    • Cleaning up zombie event listeners

Toy Problem Circuit Training:

  • First, work through the first 3 problems on every relevant section of Cracking the Coding Interview.

    • Skip sections like Java or C++ if you don’t know those languages
    • Skip testing
    • Skip concurrency unless you have experience writing concurrent programs. Do read about it though.

  • Write out your solutions in code. Make sure they work. Check edge cases.

  • After you’ve written a good 30+ solutions, stop coding every single solution.

    • You should be developing your high-level intuition how to determine the optimal approach to a problem.
    • The rest is pattern recognition.

  • Continue working through the rest of Cracking the Coding Interview.

    • But from here on out, instead of actually writing code, just write a high-level description of the algorithm you’d use to solve the problem.
    • Example: “First sort the array, then repeatedly binary search through it on each subsequent query. This should take nlog(n) pre-processing and log(n) for each query.”

  • Once you’ve written your high-level solution, check it against the solution in the book.

    • If your solution is suboptimal, write a description of the optimal solution
    • Make sure it makes sense to you. If it even slightly doesn’t make sense and you’re not confident you could write the code, then code it up, test for edge cases, etc.

  • With this workflow, you should be coding only a small percentage of the remaining problems. You should be able to work through many more problems a day now.

Make sure you have your solutions collected into files so that you can review them easily. In your solutions files, you should also have the problem statement along with any solution you have written/described.

Whenever you review them (which you should at weekly intervals), here’s how you should review: read the problem statement only, decide how you’d solve the problem in your head, and then check it against the algorithm you have written down. Again, reaffirm to yourself why the correct answer is correct.

Once you make it through the entire book, spend the remainder of your study time grinding problems on LeetCode.

LeetCode is an online coding platform like HackerRank or CodeWars that gives you a problem statement and lets you write code against test cases.

I recommend LeetCode particularly because it has the most accurate problem set I’ve seen for what most algorithms interviews are like. It also has an awesome feature that it tags programming problems by companies where the problem was asked. (If the company has fewer than 2000 employees, then it’s unlikely to be tagged anywhere.)

So any time you have an interview at a big company, do every single problem that company is tagged with on LeetCode. You have to pay for a subscription to see the tags, but it’s worth it.

GlassDoor is also a good source of company-specific problems to grind on. (You can also try CareerCup, but their accuracy tends to be a bit more dubious.)

After all that, there’s one last piece that’s missing—actual interview practice. One of the chief principles of learning is practice like performance. That is, make the way you practice as close to the actual performance as possible. In this case, the actual performance will be standing in front of a whiteboard and getting verbally interviewed by someone.

Practice for it.

Find someone to mock-interview you in front of a whiteboard (and reciprocate for them afterward). Have them ask you questions you’ve never seen before. Practice all of your interviewing skills, including introducing yourself, clarifying the problem, making jokes, everything that you plan to do in a real interview. Treat it as though it’s the real thing. Be willing to struggle and look stupid. Don’t let yourself break character.

This is also really the only way to practice architecture-oriented interviews. Have your interviewer ask you about the request-response cycle or how you’d architect Twitter, or other standard interview favorites.

A great resource is interviewing.io, which allows you to anonymously interview and get interviewed by other people and practice programming problems. They’re in private beta right now, but check them out.

If you actually implement every part of this workflow, you should become an algorithms beast within a few months. Your performance on a coding interview will be comparable if not superior to the average CS graduate.

There’s nothing magical about any of this. It’s all just practice. All of the information you need to pass a coding interview is out there, freely available. It’s up to you to put the time in.

Okay.

You’re clearly awesome at algorithms now, so let’s keep going.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment