Technical Interview Preparation Guide | Part1

The road to landing your next big Software Engineering job isn’t as straightforward as ordering a Doordash order. So to make it easier, let’s break down the contents, roadmaps and some resources to get us through this.

Data Structures and Algorithms

We first start by understanding some of the basics of programming — data structures, algorithms and asymptotic analysis. In my opinion, having a good understanding of how each of these data structures work, what are it’s advantages and disadvantages and when it is likely to produce good results really helps in navigating tough problems. Most of problem solving is just two things — breaking down the problem and finding the right tradeoff. We either try to run an algorithm faster by increasing storage or try to keep the space minimum and can wiggle with time complexity.

Data Structures -

1. Arrays and Strings
2. Linked Lists
3. Stacks and Queues
4. Trees and Graphs
5. Hash Table
6. Heaps

Shiran Afergan

Algorithms —

1. Sorting
2. Arrays and Tree: Searching — Binary Search
3. Matrix: Depth-First Search and Breadth-First Search
4. Greedy
5. Recursion and Backtracking

Codebagel

Asymptotic Analysis —

The tricky part of Asymptotic analysis is that firstly, you would need to know the average runtime complexity of most data structures and algorithms. Then you should also be able to answer some challenging questions on top of them, like —

1. What is the worst case runtime of specific data structures and when they might hit that case? For example, did you know that while interviewers love questions that involve solving with a Hash Table, the O(1) data structure for all operations — insert, search, retrieve and delete. The worst case running time in case of a bad hash is O(n)
2. You would also need to show runtime modification when you solve a problem. Most problems don’t fit a standard out of the box solution or just one data structure. You generally break it down and use different data structures and algorithms for different parts of the problem. Hence, it would be necessary to come up with accurate runtime complexity of your solution during the end of the interviews.

Some average and worst case runtime complexities

Check out this amazing resource by Gayle McDowell(password: FB_IPS) — https://vimeo.com/157480836

Private video on Vimeo

Practice LeetCode

Once you are comfortable with the basics, it is now time to hit the practice range. You want to get comfortable applying this knowledge to actualreal world problems. And there is not a better place than LeetCode to practice these. While you might be overwhelmed by the questions, I would suggest a more incremental approach —

1. Leverage LeetCode categorization — Easy/Medium/Hard, Company based questions and discussion sections to understand from previous interviewees on their experience.
2. Another amazing resource is to use the NeetCode.io coding roadmap — https://neetcode.io/roadmap. This way you can build on your knowledge and skill incrementally, and he does a good job of breaking it hierarchically to help you better tackle more complex problem building on prior fundamental knowledge.

NeetCode

Coding Patterns

Firstly, it is amazing if you are on the right track and come this far in your preparation journey. Kudos to you and pat your back for all the efforts you have put in so far. But remember that sometimes this might not be enough, as you might realize giving interview in parallel while you prepare. I believe the icing to all of the preparation so far is to learn coding patterns for LeetCode problems. This is almost a hack so that you can identify what type of a question it is by just looking at it and knowing you already have a hack up your sleeve to solve it in the most effective way.

Let me show you an example of why this might be relevant, take Sliding Window. A common approach for the LeetCode problem — https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Common Brute Force approach like below give you a runtime complexity of O(n*k), which can be several magnitudes large if the value of k is large.*

// BRUTE FORCE : iterate through all windows of size k
for(int i = 0; i < n-k+1; i++){    
    int current_sum = 0;
     
    for(int j = 0; j < k; j++){        
        current_sum = current_sum + arr[i+j];         
    }    
    max_sum = max(current_sum, max_sum);    // pick maximum sum 
}

A simple solution to this is by using a sliding window of size k, which brings down the runtime complexity of the algorithm to just O(n)

int max_sum = 0, window_sum = 0;

/* Calculate sum of 1st window */
for (int i = 0; i < k; i++)  
    window_sum += arr[i]; 

/* Slide window from start to end in array. */
for (int i = k; i < n; i++) { 
    window_sum += arr[i] - arr[i-k]; // Saving re-computation
    max_sum = max(max_sum, window_sum);
}

*Leetcode Pattern 2 | Sliding Windows for Strings

Coding Patterns —

1. Sliding Window
2. Two Pointers
3. Merge Intervals
4. Cyclic Sort
5. In-place reversal of Linked Lists
6. Tree BFS/DFS
7. Modified Binary Search
8. Topological Sort
9. Top K Elements
10. K-way merge

More advanced Patterns —

1. Dynamic Programming
2. 0–1 Knapsack
3. Recursion and Backtracking
4. Monotonic Stack
5. Two Heaps
6. Subsets

Some amazing resources to learn further —

GitHub - armankhondker/best-leetcode-resources: This repository contains resources for technical…

14 Patterns to Ace Any Coding Interview Question

Leetcode Patterns