# Several Coding Patterns for Solving Data Structures and Algorithms Problems during Interviews
These are my notes in <b>Javascript</b> from a [course](https://www.educative.io/courses/grokking-the-coding-interview) that categorizes coding interview problems into a set of <b>16 patterns</b>.
| | |
|---|---|
| <b>[Pattern 1: Sliding Window](./â
%20%20Pattern%2001%20:%20Sliding%20Window.md)</b>|<b>[Pattern 9: Two Heaps](./â
%20ð%20Pattern%2009:%20Two%20Heaps.md)</b> |
|<b>[Pattern 2: Two Pointer](./â
%20%20Pattern%2002:%20Two%20Pointers.md)</b>|<b>[Pattern 10: Subsets](./â
%20%20Pattern%2010:%20Subsets.md)</b>|
|<b>[Pattern 3: Fast & Slow pointers](./â
%20%20Pattern%2003:%20Fast%20%26%20Slow%20pointers.md)</b>|<b>[Pattern 11: Modified Binary Search](./â
%20%20Pattern%2011:%20Modified%20Binary%20Search.md)</b>|
|<b>[Pattern 4: Merge Intervals](./â
%20%20Pattern%2004%20:%20Merge%20Intervals.md)</b>|<b>[Pattern 12: Bitwise XOR](./â
%20Pattern%2012:%20%20Bitwise%20XOR.md)</b>|
|<b>[Pattern 5: Cyclic Sort](./â
%20%20Pattern%2005:%20Cyclic%20Sort.md)</b>|<b>[Pattern 13: Top 'K' Elements](./â
%20Pattern%2013:%20Top%20'K'%20Elements.md)</b>|
|<b>[Pattern 6: In-place Reversal of a LinkedList](./â
%20%20Pattern%2006:%20In-place%20Reversal%20of%20a%20LinkedList.md)</b>|<b>[Pattern 14: K-way merge](./%E2%9C%85%20Pattern%2014%3A%20K-way%20merge.md)</b>|
|<b>[Pattern 7: Tree Breadth First Search](./â
%20%20Pattern%2007:%20Tree%20Breadth%20First%20Search.md)</b>|<b>[Pattern 15: 0/1 Knapsack (Dynamic Programming)](./%E2%9C%85%20Pattern%2015:%200-1%20Knapsack%20(Dynamic%20Programming).md)</b>|
|<b>[Pattern 8: Depth First Search (DFS)](./â
%20%20Pattern%2008:Tree%20Depth%20First%20Search.md)</b>|<b>[Pattern 16: Topological Sort (Graph)](./%E2%9C%85%20Pattern%2016%3A%20%F0%9F%94%8E%20Topological%20Sort%20(Graph).md)</b>|
## Additional Resources
Here are a few other resources that I found helpful when learning <b>Data Structures and Algorithms</b> using <b>JavaScript</b>
- [Run JS](https://runjs.app/) - A JavaScript playground
for your desktop
- [Big O CheatSheet](https://www.bigocheatsheet.com/) - Reference for <b>Big-O</b> complexities of common algorithms
- [Blind 75](https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU) - For additional practice, the [Blind75 list](https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU) of interview questions is ð¥. I would approach the questions in [this order](https://www.techinterviewhandbook.org/best-practice-questions) or [this order](https://neetcode.io/) or [create a custom Blind75 study plan](https://www.techinterviewhandbook.org/grind75)
- [Edabit](https://edabit.com/) is a great resource if you need additional <b>Javascript</b> practice before you start using <b>leetcode</b>.
- [LeetCode](https://leetcode.com/problemset/all/) of course
ð
- [Pramp](https://www.pramp.com/) - for mock interviews
- [FreeCodeCamp's Algorithms](https://www.freecodecamp.org/learn/coding-interview-prep/#algorithms) - Extra practice, esp. the <b>Sort Algorithms</b> section.
- [Build 15 JavaScript Projects - Vanilla JavaScript Course](https://www.youtube.com/watch?v=3PHXvlpOkf4) - for extra <b>Vanilla JavaScript/DOM Manipulation</b> practice.
#
#### ð Challenge Questions
#### ð©ð½â𦯠Questions from <b>[Blind 75](https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU)</b>
#### ðð Questions tagged <b>FaceBook/Meta</b>
#### ð´ Questions tagged <b>Amazon</b>
#### ð Questions tagged <b>Google</b>
## [Pattern 1: Sliding Window](./â
%20%20Pattern%2001%20:%20Sliding%20Window.md)
In many problems dealing with an array (or a <b>LinkedList</b>), we are asked to find or calculate something among all the contiguous subarrays (or sublists) of a given size. For example, take a look at this problem:
> Given an array, find the average of all contiguous subarrays of size `K` in it.
Lets understand this problem with a real input:
`Array: [1, 3, 2, 6, -1, 4, 1, 8, 2], K=5`
A <b>brute-force</b> algorithm will calculate the sum of every 5-element contiguous subarray of the given array and divide the sum by 5 to find the average.
The efficient way to solve this problem would be to visualize each contiguous subarray as a sliding window of `5` elements. This means that we will slide the window by one element when we move on to the next subarray. To reuse the sum from the previous subarray, we will subtract the element going out of the window and add the element now being included in the sliding window. This will save us from going through the whole subarray to find the sum and, as a result, the algorithm complexity will reduce to `O(N)`.
## [Pattern 2: Two Pointer](./â
%20%20Pattern%2002:%20Two%20Pointers.md)
In problems where we deal with sorted arrays (or <b>LinkedList</b>s) and need to find a set of elements that fulfill certain constraints, the [Two Pointers](./â
%20%20Pattern%2002:%20Two%20Pointers.md) approach becomes quite useful. The set of elements could be a pair, a triplet or even a subarray. For example, take a look at the following problem:
> Given an array of sorted `numbers` and a `target` sum, find a pair in the array whose sum is equal to the given `target`.
To solve this problem, we can consider each element one by one (pointed out by the first pointer) and iterate through the remaining elements (pointed out by the second pointer) to find a pair with the given sum. The time complexity of this algorithm will be `O(N^2)` where `n` is the number of elements in the input array.
Given that the input array is sorted, an efficient way would be to start with one pointer in the beginning and another pointer at the end. At every step, we will see if the numbers pointed by the <b> two pointers</b> add up to the target sum. If they do not, we will do one of two things:
1. If the sum of the two numbers pointed by the <b> two pointers</b> is greater than the target sum, this means that we need a pair with a smaller sum. So, to try more pairs, we can decrement the end-pointer.
2. If the sum of the two numbers pointed by the <b> two pointers</b> is smaller than the target sum, this means that we need a pair with a larger sum. So, to try more pairs, we can increment the start-pointer.
## [Pattern 3: Fast & Slow pointers](./â
%20%20Pattern%2003:%20Fast%20%26%20Slow%20pointers.md)
The <b>Fast & Slow</b> pointer approach, also known as the <b>Hare & Tortoise algorithm</b>, is a pointer algorithm that uses <b> two pointers</b> which move through the array (or sequence/<b>LinkedList</b>) at different speeds. This approach is quite useful when dealing with cyclic <b>LinkedList</b>s or arrays.
By moving at different speeds (say, in a cyclic <b>LinkedList</b>), the algorithm proves that the <b> two pointers</b> are bound to meet. The <i>fast pointer</i> should catch the <i>slow pointer</i> once both the pointers are in a cyclic loop.
One of the famous problems solved using this technique was [Finding a cycle in a <b>LinkedList</b>](https://github.com/Chanda-Abdul/Several-Coding-Patterns-for-Solving-Data-Structures-and-Algorithms-Problems-during-Interviews/blob/main/%E2%9C%85%20%20Pattern%2003:%20Fast%20%26%20Slow%20pointers.md#linkedlist-cycle-easy). Lets jump onto this problem to understand the <b>Fast & Slow</b> pattern.
## [Pattern 4: Merge Intervals](./â
%20%20Pattern%2004%20:%20Merge%20Intervals.md)
This pattern describes an efficient technique to deal with overlapping intervals. In a lot of problems involving intervals, we either need to find overlapping intervals or merge intervals if they overlap.
Given two intervals (`a` and `b`), there will be six distinct ways the two intervals can relate to each other:
1. `a` and `b`do not overlap
2. `a` and `b` overlap, `b` ends after `a`
3. `a` completely overlaps `b`
4.
没有合适的资源?快使用搜索试试~ 我知道了~
Several Coding Patterns for Solving Data Structures and Al.zip
共35个文件
png:18个
md:17个
需积分: 5 0 下载量 156 浏览量
2024-02-04
10:59:15
上传
评论
收藏 2.02MB ZIP 举报
温馨提示
Several Coding Patterns for Solving Data Structures and Al
资源推荐
资源详情
资源评论
收起资源包目录
Several Coding Patterns for Solving Data Structures and Al.zip (35个子文件)
ahao2
✅ Pattern 01 _ Sliding Window.md 40KB
✅ Pattern 08_Tree Depth First Search.md 23KB
✅ Pattern 05_ Cyclic Sort.md 19KB
✅ Pattern 13_ Top 'K' Elements.md 38KB
✅ Pattern 14_ K-way merge.md 38KB
✅ 🙃 Pattern 09_ Two Heaps.md 26KB
✅ Pattern 15_ 0-1 Knapsack (Dynamic Programming).md 252KB
✅ Pattern 07_ Tree Breadth First Search.md 29KB
✅ Pattern 04 _ Merge Intervals.md 29KB
✅ Pattern 06_ In-place Reversal of a LinkedList.md 13KB
✅ Pattern 16_ 🔎 Topological Sort (Graph).md 35KB
✅ Pattern 10_ Subsets.md 34KB
✅ Pattern 12_ Bitwise XOR.md 13KB
✅ Pattern 03_ Fast & Slow pointers.md 25KB
images
dpselected.png 131KB
subsetsum.png 22KB
knapsack.png 342KB
unbounded.png 182KB
dpnumberfactors.png 140KB
subproblems.png 101KB
topsort.png 45KB
MHT1.png 155KB
MHT2.png 118KB
dpRodCutting.png 140KB
mergeintervals.png 42KB
dpstairs.png 116KB
topsort4.png 149KB
kwaymatrix.png 172KB
topsort2.png 46KB
fib4.png 85KB
cyclicsort.png 103KB
topsort3.png 60KB
✅ Pattern 02_ Two Pointers.md 33KB
✅ Pattern 11_ Modified Binary Search.md 34KB
README.md 17KB
共 35 条
- 1
资源评论
码农阿豪
- 粉丝: 1w+
- 资源: 1750
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功