# dennyzhang/code.dennyzhang.com

Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
..
Failed to load latest commit information.

# CheatSheet: Leetcode For Code Interview

Handy CheatSheet for your code interview. Common code templates, typical problems by categories, etc.

https://cheatsheet.dennyzhang.com/cheatsheet-leetcode-A4

## Top 20 Graph Problems

NumProblemCategory/TagSummary
1Graph Connectivity: Count islands in a 2D matrix#dfs, #unionfindLeetcode: Number of Islands, Leetcode: Island Perimeter
2Get the size of the largest island#dfsLeetcode: Max Area of Island
3Whether a graph is a tree#unionfind, #bfsLeetcode: Graph Valid Tree
4Whether an undirected graph has a loop
5Whether a directed graph has a loopLeetcode: Redundant Connection II
6Shortest path for two nodes in a weighted graph - Dijkstra’s Algorithm
7Minimum spanning tree of a weighted graph - Kruskal’s algorithm#unionfindLeetcode: Connecting Cities With Minimum Cost
8Update a specific regionLeetcode: Flood Fill
9Update regions for a given ruleLeetcode: Surrounded Regions
10Mark levelsLeetcode: 01 Matrix
11Duplicate edgesLeetcode: Reconstruct Itinerary
12Find a certain node in a graph#unionfindLeetcode: Find the Celebrity
13Find a certain path from source to destination in a graphLeetcode: Path With Maximum Minimum Value
14Find the minimum steps from point1 to point2Leetcode: Word Ladder, Leetcode: Sliding Puzzle
15Find all minimum paths from point1 to point2Leetcode: Word Ladder II
16All Paths from Source Lead to DestinationLeetcode: All Paths from Source Lead to Destination
17
18dijkstra Dijkstra’s Shortest Path First algorithm
19
20
https://code.dennyzhang.com

## Top 5 Binarysearch Problems

NumProblemCategory/TagSummary
1Find a first failing versionLeetcode: First Bad Version
2Search Insert PositionLeetcode: Search Insert Position, Leetcode: Time Based Key-Value Store
3
4
5

## Top 10 Dynamic Programming Problems

NumProblemCategory/TagSummary
1LIS - Longest increasing subsequence#string, #lisLeetcode: Longest Increasing Subsequence
4LCS - Longest Common Subsequence#editdistance, #lcsLeetcode: Longest Common Subsequence
2Edit distance of two strings#editdistanceLeetcode: Edit Distance
3Maximum subarray problem#maxsubarraysumLeetcode: Maximum Subarray
5
6
7
8
9
10

## Top 10 BinaryTree Problems

NumProblemCategory/TagSummary
1Binary Tree Level Order Traversal#bfsLeetcode: Binary Tree Right Side View
2Height of binary tree#dfsLeetcode: Balanced Binary Tree
3LCA - Lowest Common Ancestor of a binary Tree#dfsLeetcode: Lowest Common Ancestor of a Binary Tree
4Construct binary treeLeetcode: Construct Binary Tree from Preorder and Postorder Traversal
5Check whether a binary tree is a full binary tree#dfs, #bfs
6Right view of a tree
7
8
9
10

## Top 5 String Problems

NumProblemCategory/TagSummary
1Edit distance of two strings#editdistanceLeetcode: Edit Distance
2Remove duplicate letters#greedy, #stackRemove Duplicate Letters
3
4
5

## Top 5 Math Problems

NumProblemCategory/TagSummary
1Check prime - Sieve of Eratosthenes#primeLeetcode: Count Primes
2Check leap year#leapyearLeetcode: Day of the Week
3Rectangle#rectangle
4gcd#gcd
5

## Top 40 General Problems

NumProblemCategory/TagExample
2Two pointers#twosum, #twopointerLeetcode: Two Sum
3Sort one array based on another array#sortbyfunctionLeetcode: Relative Sort Array
5Prefix search from a list of strings#trieLeetcode: Longest Word in Dictionary
6Longest substring with at most K distinct characters#slidingwindow, #atmostkdistinctLeetcode: Longest Substring with At Most K Distinct Characters
7Longest subarray with maximum K 0s#slidingwindowLeetcode: Max Consecutive Ones III
8Get all possibilities of subsets#subset, #backtrackingLeetcode: Subsets II, Leetcode: Subsets
9Choose k numbers from a list#combination, #backtrackingLeetcode: Combination Sum II
10Combination from multiple segments#combination, #backtrackingLeetcode: Letter Combinations of a Phone Number
11Factor Combinations#combination, #backtrackingLeetcode: Factor Combinations
12Permutation without duplicates#permutation, #backtrackingLeetcode: Palindrome Permutation II
13Int to string or string to int#bitmanipulation
14Convert a number into negative base representation#bitmanipulation, #baseconversionLeetcode: Convert to Base -2
16Check whether a linked list has a loop
17Network connectivity#unionfindLeetcode: Friend Circles
18Build relationship among different sets#unionfindLeetcode: Accounts Merge
19Knapsack problem to maximize benefits#knapsackLeetcode: Coin Change
20Find the next greater value#monotoneLeetcode: Daily Temperatures
21Meeting conflict#intervalLeetcode: Meeting Rooms, Leetcode: Course Schedule
22Minimum conference rooms#interval, #overlappingintervalLeetcode: Meeting Rooms II
23TopK problem#heapLeetcode: Top K Frequent Elements, Leetcode: Find K Pairs with Smallest Sums
24Quick slow pointers#twopointerLintCode: Middle of Linked List
25Longest Repeating Character with at most K changes#slidingwindowLeetcode: Longest Repeating Character Replacement
26Count out of boundary paths in a 2D matrix#bfs, #outofboundarypathLeetcode: Out of Boundary Paths
27Prefix and Suffix Search#trieLeetcode: Prefix and Suffix Search
28Remove duplicate letters#greedy, #string, #stackRemove Duplicate Letters
29Next Permutation#greedy, #nextpermutationLeetcode: Next Permutation
30Beautiful array#divideconquerLeetcode: Beautiful Array
31Whether 132 pattern exists in array#stackLeetcode: 132 Pattern
32Travelling salesman problem
33Leetcode: Remove Duplicates from Sorted Array II
34Leetcode: Min Stack
35#minmax, #dynamicprogrammingLeetcode: Predict the Winner, Leetcode: Stone Game
36Topological Sort
37
38
39
40

## Common Tips For Clean Code

NumNameSummary
1Caculate sum of a range quickly#presum,Leetcode: Maximum Subarray
2Move in four directions for a matrixLeetcode: Sliding Puzzle
3Split string by multiple seperatorLeetcode: Brace Expansion
4Add a dummy tailing element to simplify codeLeetcode: Brace Expansion
5Fast slow pointersLintCode: Middle of Linked List
6Deep copy an arrayLeetcode: Combination Sum
7Use arrays instead of hashmaps, if possibleLeetcode: Number of Days in a Month
8Control the order of dfsLeetcode: Subsets II
9Avoid inserting into the head of an arrayLeetcode: Path In Zigzag Labelled Binary Tree
10From right to left, instead of left to rightLeetcode: Merge Sorted Array
11Think the other way around`Add Items` vs `Remove Items`, `Increase Counter` vs `Decrease Counter`
12Avoid uncessary if…else…res[i] = (diff/2 <= k), Leetcode: Can Make Palindrome from Substring
13To get the case of K, solve: at most K - at most (K-1)Leetcode: Subarrays with K Different Integers
14Instead of deleting entry from hashmap, decrease counterLeetcode: Longest Substring with At Most K Distinct Characters
16With helper function vs without helper functionLeetcode: Longest Repeating Character Replacement
17Instead of adding a character, try to delete oneLeetcode: Longest String Chain
18#roudtrippass: from left to right, then right to leftLeetcode: Shortest Distance to a Character
19One pass instead of two pass
20Avoid unnecessary precheck
21Swiping line algorithm
23Hide details which are irrelevant
24Avoid delete element from hashmaps

## Golang Tips

NameSummary
Golang return a tuple`func dfs(root *TreeNode, max *float64) (sum int, cnt int)`, Leetcode: Maximum Average Subtree
Variable Conversion`float64(x_int/y_int)` != `float64(x_int)/float64(y_int)`, Leetcode: Maximum Average Subtree
For a list of objects, pass by value or reference`f(l []*TreeNode)` vs `f(l *[]*TreeNode)`, Leetcode: Lowest Common Ancestor of a Binary Tree

## Resource For Code Problems

NameSummary
Leetcode summaryGitHub: kdn251/interviews
Leetcoder on YouTubelee 215, Aoxiang Cui
Online test websiteshackerrank.com, hackerrank - hard
Online test websitesspoj.com
Online test websitescodeforces.com, poj.org
Online test websitesacm.hdu.edu.cn, acm.zju.edu.cn, acm.timus.ru, uva.onlinejudge.org
Referencegeeksforgeeks.org

## Resource For Code Problems - In Chinese

NameSummary
ReferenceAlgorithm_Interview_Notes-Chinese/C-算法