Repository files navigation

Please press ⭐ button if you like this repo. Thấy ngon thì nhấn star ⭐ ủng hộ mình nha các đồng râm

This repository contains my implementation ofuseful / well-known data structures, algorithms and solutions for awesome competitive programming problems inHackerrank, Project Euler and Leetcode

I create this for faster implementation and better preparation in interviews as well as programming contests

⚠️ This repo is day-by-day updated. Please make sure you have the latest version!

🔥New updates today:Longest Substring Without Repeating Characters^[Leetcode]

Overview of the file:

Here is some tips and tricks to ACE all competitive programming problems and interview questions:

If input array is sorted then    - Binary search    - Two pointersIf asked for all permutations/subsets then    - BacktrackingIf given a tree then    - DFS    - BFSIf given a graph then    - DFS    - BFSIf given a linked list then    - Two pointersIf recursion is banned then    - StackIf must solve in-place then    - Swap corresponding values    - Store one or more different values in the same pointerIf asked for maximum/minumum subarray/subset/options then    - Dynamic programmingIf asked for top/least K items then    - HeapIf asked for common strings then    - Map    - TrieElse    - Map/Set for O(1) time & O(n) space    - Sort input for O(nlogn) time and O(1) space

1. • Binary Search Tree: Original Binary Search Tree Algorithm -O(log(n))
2. • Binary Search Tree: Check a Number: Check if a Number is in a Sorted List using BST Algorithm -O(log(n))
3. • Binary Search Tree: Index of a Number: Find the Index of a Number in a Sorted List using BST Algorithm -O(log(n))

1. • Suffix Array (Manber-Myers Algorithm): Find suffix array of a string S based on Manber-Myers algorithm -O(n.log(n)) , n = |S|
2. • Longest Common Prefix Array (Kasai Algorithm): Find longest common prefix array of a string S with the help of suffix array based on Kasai algorithm -O(n) , n = |S|
3. • Longest Palindromic Substring -O(n)
4. • Pattern Search -O(log(n))

1. • Graph Representation using Adjacency List: Unweighted, Un-/Directed: Create a Unweighted Un-/Directed Graph using Adjacency List
2. • Graph Representation using Adjacency List: Weighted, Un-/Directed
3. • Find All Nodes: Find All Nodes in the Unweighted Graph -O(V+E) for Adjacency List , V, E is the number of vertices and edges
4. • Find All Edges
5. • Find All Paths between 2 Nodes: Find All Paths between 2 Nodes in a Unweighted Graph using BFS -NP-Hard
6. • Disjoint Set (Union-Find): Union by Rank and Path Compression: Create a Disjoint Set (Union-Find) using "Union by Rank and Path Compression" for an Undirected Graph (used to Detect Cycle) -Time = O(small constant), Space = O(V)

7. • Detect Cycle: Disjoint Set: Detect Cycle in an Undirected Graph based on Disjoint Set (Union-Find) using "Union by Rank and Path Compression" -O(V)

8. • Breadth-First Search: Find BFS Path from a Starting Node in Un-/Directed Graph -O(V+E) for Adjacency List; O(V²) for Adjacency Matrix , V, E is the number of vertices and edges
9. • Depth-First Search: Find DFS Path from a Starting Node in Un-/Directed Graph -O(V+E) for Adjacency List; O(V²) for Adjacency Matrix , V, E is the number of vertices and edges

10. • MST: Prim Algorithm^[PDF]: Find Minimum Spanning Tree (MST) of an Undirected Graph using Prim Algorithm -O(E.log(V))
11. • MST: Kruskal Algorithm^[PDF]: Find Minimum Spanning Tree (MST) of an Undirected Graph using Kruskal Algorithm -O(E.log(E)) or O(E.log(V))

12. • Shortest Path: Breadth-First Search: Find the Shortest Path in a Unweighted Un-/Directed Graph based on BFS -O(V+E) for Adjacency List , V, E is the number of vertices and edges
13. • Shortest Path: Dijkstra using Min-Heap^[PDF]: Find Shortest Path of an Non-Negative Un-/Weighted Un-/Directed Graph based on Dijkstra Algorithm using Min-Heap -O(E.log(V))
14. • Shortest Path: Bellman-Ford
15. • Shortest Path: Floyd-Warshall

1. Sherlock and The Beast

• Find the "Decent Number" having n Digits ("Decent Number" has its digits to be only 3's and/or 5's; the number of 3's it contains is divisible by 5; the number of 5's it contains is divisible by 3; and it is the largest such number for its length)

2. Largest Permutation

• Swap 2 digits of a number k times to get largest number -O(n)

Coin Change Algorithms: Given an array of choices, every choice is pickedunlimited times

Knapsack Problems: Given an array of choices, every choice is pickedonly once

1. • Coin Change^[PDF]: How many ways to pay V money using C coins [C1,C2,...Cn] -O(C.V)
2. • Integer Partition^[PDF]: How many ways to partition number N using [1,2,...N] numbers -O(n^1.5)
3. • Minimum Coin Change^[Wiki]: Find Minimum Number of Coins to pay V money using C coins [C1,C2,...,Cn] -O(C.V)

4. • Knapsack 0/1^[Wiki]: Given a List of Weights associated with their Values, find the Founding Weights and Maximum Total Value attained with its Total Weight <= Given Total Weight, each Weight is onlypicked once (0/1 Rule) -O(N.W) , N, W is length of weights array and given total weight
5. • Partition Problem: Subset Sum^[Wiki]: Given an Array containing only Positive Integers, find if it can be Partitioned into 2 Subsets having Sum of elements in both subsets is Equal. -O(N.T) , N, T is the length of numbers array and the target sum (=sum/2)
6. • Partition Problem: Multiway Number Partitioning^[Wiki]:

7. • Max Path Sum Triangle^[PDF]: Find Maximum Path Sum from Top to Bottom of a Triangle -O(R) , R is number of rows of the triangle
8. • Min Path Sum Matrix: Top-Left to Right-Bottom, Right and Down Moves^[PDF]: Find Min Path Sum from Top-Left to Right-Bottom of a Matrix using Right and Down Moves -O(R.C) , R, C is length of row and column of the matrix

Subsequence = Any subset of an array/string

Subarray = Contiguous subsequence of an array

Substring = Contiguous subsequence of a string

9. • Max Subarray Sum (Kadane Algorithm)^[PDF]: Find Maximum Subarray Sum of an Array -O(n)
10. • Max Subarray Sum (Kadane Algorithm - Extended)^[PDF]: Find Maximum Subarray Sum of an Array and its Indices -O(n)
11. • Min Subarray Sum (Kadane Algorithm's Min Varient): Find Minimum Subarray Sum of an Array -O(n)
12. • Subarray Sum Equals K^[Leetcode]: Find the Number of Continuous Subarrays of an Array whose Sum Equals to K -O(n)
13. • Subarray Sum Divisible by K^[Leetcode]: Find the Number of Continuous Subarrays of an Array whose Sum is Divisible by K -O(n)

14. • Longest Common Subsequence (LCS)^[PDF]: Find the longest string S, every character in S is also in S1 and S2 but in order -O(|S1|.|S2|)
15. • Longest Increasing/Decreasing Subsequence (Patience Sorting Algorithm)^[PDF]: Find the Longest Increasing or Decreasing Subsequence of an Array List based on Patience Sorting Algorithm-O(n.log(n))

16. • Longest Common Substring (Longest Common Factor - LCF): Find the Longest Common Substring (Factor) of 2 strings S1 and S2 -O(|S1|.|S2|)
17. • Sum Of Substrings^[PDF]: Find Sum of All Substrings of an Number String S -O(|S|)

1. • Longest Substring Without Repeating Characters^[Leetcode]: Find the Length of the Longest Substring Without Repeating Characters -O(|S|)

1. • Pascal Triangle: Create Pascal Triangle (to Calculate Multiple Large-Number Combinations) -O(n²)
2. • PE #15: Lattice Paths^[PDF] : Find the number of routes from the top left corner to the bottom right corner in a rectangular grid

3. • Factorization: Find All Factors of a Number -O(n^1/2)

4. • PE #1: Multiples of 3 and 5^[PDF]: Find Sum of Multiples of a Number -O(1)

5. • Lexicographic Permutations^[PDF]: Find n-th Lexicographic Permutation of a very long Word -O(n)
6. • Permutation Check: Check if 2 Numbers/Strings are Permutations -O(n) , n = max(|a|,|b|)

7. • "Sieve Method" All Primes: Find All Primes < n -Space = O(n^1/2)
8. • Primality Test (Common Method): Check if n is a Prime Number using "Common Method" -O(n^1/2)
9. • Primality Test (Miller-Rabin): Check if n is a Prime Number using Miller-Rabin Probabilistic Test -O(k.log³n) , k = [1,2,...]
10. • Coprimes Check: Check if 2 Numbers are Coprime -O(log a.b)

11. • Euler Totient Function (Number List): Find ALL Numbers of Coprimes < n based on Euler Totient Function -O((l) + m.loglogm + l.(logm + k)) , k is the number of prime factors of n; m and l is max value and length of the input number list
12. • Euler Totient Function (Single Number): Find the Number of Coprimes < n based on Euler Totient Function -O(n^1/2 + k) , k is the number of prime factors of the input number n
13. • "Sieve Method" Smallest Prime Factors (SPF): Find Smallest Prime Factors for All Numbers < N -O(n.loglogn)
14. • Prime Factorization (Smallest Prime Factor): Find All Prime Factors of a Number using Smallest Prime Factor (SPF) -O(log n) if a list of all Smallest Prime Factors from 0 to n available
15. • Prime Factorization: Find All Prime Factors of a Number -O(n^1/2)

16. • Pythagorean Triplets Perimeter: Find Pythagorean Triplets having Perimeter (or Sum) P -O(P)
17. • Pythagorean Triplets Less or Equal N: Generate all Pythagorean Triplets <= N -O(N.log(N))

18. • Number Spiral Diagonals^[PDF]: Find Sum of Diagonals of Ulam Spiral Matrix

Problem statement: Do something on a given singly-linked List

Hints:

1. Simply convert linked list to 1D array and solve on the array using "ListNode_to_Array"
2. If necessary, convert 1D array back to the linked list using "Array_to_ListNode"

1. • List Node: Create a Singly-linked List using "Node class"
2. • ListNode to Array: Convert ListNode into Array, could be used as print to "see" inside a ListNode -O(n)
3. • Array to ListNode: Convert Array into ListNode -O(n)

Problem statement: Move current position within the matrix along diagonals, up-down-right-left, ...

Hints:

1. Use variable flag = 'up' or 'down' ... to guide the current position to the next position

ifflag=='up':# Do something# Consider to change the flag = 'down' or 'right' or 'something'

2. Pay attention to the matrix boundary when moving

definMatrix(r,c):# R, C is the matrix size# r, c is current positionifr>=0andc>=0andr<Randc<C:returnTrueelse:returnFalse

3. Use variable seen = set() to not move to the seen position or to not start as a current position

if (r,c)notinseen:# Do something

1. • Spiral Matrix^[Leetcode]: Find all elements of the matrix in spiral order -O(R.C)
2. • Diagonal_Traverse^[Leetcode]: Find all the elements of the array in a diagonal order -O(R.C)