Grokking LeetCode: A Smarter Way to Prepare for Coding Interviews | DevsDay.ru

IT-блоги Grokking LeetCode: A Smarter Way to Prepare for Coding Interviews

dev.to 25 ноября 2021 г.


To LeetCode or not to LeetCode? What if you don’t want to practice 100s of coding questions before your next coding interview?

There is a part of me that dislikes coding interviews, primarily because it requires me to spend a lot of time preparing for coding questions. Moreover, during an interview, I have to present a reasonable (if not optimal) solution to someone who is evaluating me, something I don’t have to deal with in my everyday life as a software engineer.

Having said that, I do love algorithms and solving coding problems. It is a fun activity for me, it gives me good mental exercise, and I love to spend time on it. In this post, I would like to share some of my learnings and the techniques that I’ve developed over time which makes preparing for coding interviews an exciting and fun activity.

A little about me; my software engineering career spans around 20 years, in which I’ve switched jobs five times. I’ve given around 30 interview loops containing 120+ interviews. I have some experience sitting on the other side of the table too. I’ve taken 300+ coding interviews and 200+ system design interviews.

If you are looking to switch jobs and preparing for coding interviews, you will definitely know LeetCode. It is probably the biggest online repository for coding interview questions and also contains a vibrant community to discuss algorithms with other fellow engineers. Whenever I’m free, I love spending time on LeetCode, trying to solve a new coding question, or learning from other smart solutions that people have developed.

One of the biggest challenges with LeetCode is that it lacks organization; it has a huge set of coding problems, and one feels lost on where to start or what to focus on. What is an ample amount of questions one should go through before considering themselves prepared for their coding interview? I would love to see a streamlined process that can guide me and teach me enough algorithmic techniques to feel confident for the interview. Being a lazy person myself, I wouldn’t say I like to go through 500+ questions.

One technique that people often follow is to solve questions related to the same data structure; for example, focusing on questions related to Arrays, then LinkedList, HashMap, Heap, Tree, or Trie, etc. Although this does provide some organization, it still lacks coherence. For example, many questions can be solved using HashMaps but still require different algorithmic techniques. I would love to see question sets that follow not only the same data structure but also similar algorithmic techniques. The best thing I came across was the problem-solving patterns like Sliding Window, Fast and Slow Pointers, or Topological Sort, etc. Following these patterns helped me nurture my ability to map a new problem to an already known problem. This not only made this whole coding-interview-preparation process fun but also a lot more organized.

I have gathered around 25 of these coding problem patterns, which I believe can help anyone learn these beautiful algorithmic techniques and make a real difference in the coding interviews. The idea behind these patterns is, once you’re familiar with a pattern, you’ll be able to solve dozens of problems with it. For a detailed discussion of these patterns and related problems with solutions, take a look at Grokking the Coding Interview.

Photo by Kelly Sikkema on Unsplash

So, without further ado, let me list all these patterns:

  1. Sliding Window
  2. Two Pointers
  3. Fast & Slow Pointers
  4. Merge Intervals
  5. Cyclic Sort
  6. In-place Reversal of a LinkedList
  7. Tree Breadth-First Search
  8. Tree Depth First Search
  9. Two Heaps
  10. Subsets
  11. Modified Binary Search
  12. Bitwise XOR
  13. Top 'K' Elements
  14. K-way Merge
  15. 0/1 Knapsack
  16. Unbounded Knapsack
  17. Fibonacci Numbers
  18. Palindromic Subsequence
  19. Longest Common Substring
  20. Topological Sort
  21. Trie Traversal
  22. Number of Island
  23. Trial & Error
  24. Union Find
  25. Unique Paths

Following is a small intro of each of these patterns with sample problems:

1. Sliding Window

Usage: This algorithm ic technique is used when we need to handle the input data in specific window size.

Sliding Window Pattern

Sample Problems:

  1. Longest Substring with K Distinct Characters
  2. Fruits into Baskets
  3. Permutation in a String

2. Two Pointers

Usage: In this technique, we use two pointers to iterate the input data. Generally, both pointers move in the opposite direction at a constant interval.

Two Pointers Pattern

Sample Problems:

  1. Squaring a Sorted Array
  2. Dutch National Flag Problem
  3. Minimum Window Sort

3. Fast & Slow Pointers

Usage: Also known as Hare & Tortoise algorithm. In this technique, we use two pointers that traverse the input data at a different speed.

Fast & Slow Pointers Pattern

Sample Problems:

  1. Middle of the LinkedList
  2. Happy Number
  3. Cycle in a Circular Array

4. Merge Intervals

Usage: This technique is used to deal with overlapping intervals. Given two intervals ('a' and 'b'), there will be six different ways the two intervals can relate to each other:

Intervals Overlapping

Sample Problems:

  1. (Intervals Intersection)[https://designgurus.org/path-player?courseid=grokking-the-coding-interview&unit=grokking-the-coding-interview_1628743634893_23Unit]
  2. Conflicting Appointments
  3. Minimum Meeting Rooms

5. Cyclic Sort

Usage: Use this technique to solve array problems where the input data lies within a fixed range.

Sample Problems:

  1. Find all Missing Numbers
  2. Find all Duplicate Numbers
  3. Find the First K Missing Positive Numbers

6. In-place Reversal of a LinkedList

Usage: This technique describes an efficient way to reverse the links between a set of nodes of a LinkedList. Often, the constraint is that we need to do this in-place, i.e., using the existing node objects and without using extra memory.

Image description
Image description
Image description

Sample Problems:

  1. Reverse every K-element Sub-list
  2. Rotate a LinkedList

7. Tree Breadth-First Search

Usage: As the name suggests, this technique is used to solve problems involving traversing trees in a breadth-first search manner.

Binary Tree Breadth-First Search

Sample Problems:

  1. Binary Tree Level Order Traversal
  2. Minimum Depth of a Binary Tree
  3. Connect Level Order Siblings

8. Tree Depth First Search

Usage: As the name suggests, this technique is used to solve problems involving traversing trees in depth-first search manner.

Sample Problems:

  1. Path With Given Sequence
  2. Count Paths for a Sum

9. Two Heaps

Usage: In many problems, where we are given a set of elements such that we can divide them into two parts. We are interested in knowing the smallest element in one part and the biggest element in the other part. As the name suggests, this technique uses a Min-Heap to find the smallest element and a Max-Heap to find the biggest element.

Sample Problems:
1.Find the Median of a Number Stream

  1. Next Interval

10. Subsets

Usage: Use this technique when the problem asks to deal with permutations or combinations of a set of elements.

Sample Problems:

  1. String Permutations by changing case
  2. Unique Generalized Abbreviations

11. Modified Binary Search

Usage: Use this technique to search a sorted set of elements efficiently.

Sample Problems:

  1. Ceiling of a Number
  2. Bitonic Array Maximum

12. Bitwise XOR

Usage: This technique uses the XOR operator to manipulate bits to solve problems.

Sample Problems:

  1. Two Single Numbers
  2. Flip and Invert an Image
  1. Top 'K' Elements Usage: This technique is used to find top/smallest/frequently occurring 'K' elements in a set.

Sample Problems:

  1. 'K' Closest Points to the Origin
  2. Maximum Distinct Elements

14. K-way Merge

Usage: This technique helps us solve problems that involve a list of sorted arrays.

Sample Problems:

  1. Kth Smallest Number in M Sorted Lists
  2. Kth Smallest Number in a Sorted Matrix

15. 0/1 Knapsack

Usage: This technique is used to solve optimization problems. Use this technique to select elements that give maximum profit from a given set with a limitation on capacity and that each element can only be picked once.

Sample Problems:

  1. Equal Subset Sum Partition
  2. Minimum Subset Sum Difference

16. Unbounded Knapsack

Usage: Use this technique to select elements that give maximum profit from a given set with a limitation on capacity and that each element can be picked multiple times.

Sample Problems:

  1. Rod Cutting
  2. Coin Change

17. Fibonacci Numbers

Usage: Use this technique to solve problems that follow the Fibonacci numbers sequence, i.e., every subsequent number is calculated from the last few numbers.

Sample Problems:

  1. Staircase
  2. House Thief

18. Palindromic Subsequence

Usage: This technique is used to solve optimization problems related to palindromic sequences or strings.

Sample Problems:

  1. Longest Palindromic Subsequence
  2. Minimum Deletions in a String to make it a Palindrome

19. Longest Common Substring

Usage: Use this technique to find the optimal part of a string/sequence or set of strings/sequences.

Sample Problems:

  1. Maximum Sum Increasing Subsequence
  2. Edit Distance

20. Topological Sort

Usage: Use this technique to find a linear ordering of elements that have dependencies on each other.

Sample Problems:

  1. Tasks Scheduling
  2. Alien Dictionary

21. Trie Traversal

Usage: Use this technique that involves creating or traversing of Trie data structure.

Sample Problems:

  1. Longest Word in Dictionary
  2. Palindrome Pairs

22. Number of Island

Usage: Use this technique to traverse a two-dimensional array and find a set of connected elements.

Sample Problems:

  1. Number of Distinct Islands
  2. Maximum Area of Island

23. Trial & Error

Usage: Use this technique to traverse an array to find a required optimal element. The traversal process runs in a trial & error manner.

Sample Problems:

  1. Find Kth Smallest Pair Distance
  2. Minimize Max Distance to Gas Station

24. Union Find

Usage: Use this technique to solve problems that require maintaining a given set of elements partitioned into multiple non-overlapping subsets.

Sample Problems:

  1. Number of Provinces
  2. Bipartite Graph

25. Unique Paths

Usage: Use this technique to find different/optimal ways to traverse a multi-dimensional array.

Sample Problems:

  1. Find Unique Paths
  2. Dungeon Game

Conclusion

Like it or not, LeetCode-type questions are a part of almost every programming interview, so every software developer should practice them before an interview. Their only option is to prepare smartly and learn problem-solving by focusing on the underlying problem patterns. Learn more about these patterns and sample problems in Grokking the Coding Interview and Grokking Dynamic Programming for Coding Interviews.

Check Design Gurus for some interesting courses on Coding and System Design interviews.

Источник: dev.to

Наш сайт является информационным посредником. Сообщить о нарушении авторских прав.

career programming tutorial algorithms