Data-Structures-and-Algorithms

Top Coder Competitive Programming Tutorial - https://www.topcoder.com/community/competitive-programming/tutorials

Sites for Internship/Placement Quant test preparation

https://lofoya.com/ https://www.indiabix.com/aptitude/questions-and-answers/

Basic Maths for Competitive Programming

1. https://www.hackerearth.com/practice/math/number-theory/basic-number-theory-1/tutorial/
2. https://www.geeksforgeeks.org/mathematical-algorithms/

Learning STL

1. https://www.topcoder.com/community/competitive-programming/tutorials/power-up-c-with-the-standard-template-library-part-1/
2. https://www.topcoder.com/community/competitive-programming/tutorials/power-up-c-with-the-standard-template-library-part-2/
3. https://www.youtube.com/watch?v=g-1Cn3ccwXY
4. https://www.youtube.com/watch?v=qOHXdhtxyyQ

Data Structures

0. Abdul Bari's Course on C++ and Datastructures on Udemy are very good.
1. Stacks: https://www.youtube.com/watch?v=P1bAPZg5uaE&list=PL_z_8CaSLPWdeOezg68SKkeLN4-T_jNHd
2. Heaps: https://www.youtube.com/watch?v=hW8PrQrvMNc&list=PL_z_8CaSLPWdtY9W22VjnPxG30CXNZpI9
3. Graphs: From these two courses
   3.1 NPTEL Design and Analysis of Algorithms. Good course: https://www.youtube.com/watch?v=gY0MwGLq9W8&list=PLEAYkSg4uSQ1YxqcmBjCdK9oX1m-JDEx2
   3.2 Abdul Bari's Youtube playlist: https://www.youtube.com/watch?v=0IAPZzGSbME&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O
   3.3 https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/
   3.4 William Fiset's playlist. Excellent!!!: - https://www.youtube.com/playlist?list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P
   

Algorithms

1. Dynamic Programming: https://www.youtube.com/watch?v=nqowUJzG-iM&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go
   
2. Binary Search: https://www.youtube.com/watch?v=j7NodO9HIbk&list=PL_z_8CaSLPWeYfhtuKHj-9MpYb6XQJ_f2
   
3. Divide and Conquer: https://www.geeksforgeeks.org/divide-and-conquer/
   
4. Backtracking: https://www.geeksforgeeks.org/backtracking-algorithms/
   
5. Greedy Algorithms: https://www.geeksforgeeks.org/greedy-algorithms/
   
6. Pattern Searching: https://www.geeksforgeeks.org/algorithms-gq/pattern-searching/
   6.1 Abdul Bari's course has KMP and Rabin-Karp
   
7. Binary Indexed Trees or Fenwick Trees: https://www.youtube.com/watch?v=DPiY9wFxGIw&ab_channel=Luv
   https://www.youtube.com/watch?v=DPiY9wFxGIw&ab_channel=Luv
   https://www.hackerearth.com/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/tutorial/

Range update and range query using BIT -> https://www.geeksforgeeks.org/binary-indexed-tree-range-update-range-queries/
Upper bound on prefix sum -> https://codeforces.com/blog/entry/61364 2D BIT -> https://www.geeksforgeeks.org/two-dimensional-binary-indexed-tree-or-fenwick-tree/
Binary Lifting in BIT -> https://www.youtube.com/watch?v=nuUspQ7ORXE Sparse tables -> https://aquarchitect.github.io/swift-algorithm-club/Sparse%20Table/ https://www.youtube.com/watch?v=2EpX9LkO2T0

• BIT easy to use compared to Segment trees.
• BIT can be used only for functions whose inverse can be calculated s.t f(0, r) * f(0, l) = f(l, r) where * operation is the inverse. Useful for sum, product, XOR etc.
• Sparse tables can be used for range query problems given that we don't have updates. NlogN build, O(logn) query. However if the function is idempotent i.e. f(a, a) = a then query can be done in O(1) time.
• Segment trees can handle all of the above but are difficult to implement compared to above.

Competitive Programming topics

44. Fast Fourier Transformation - https://codeforces.com/blog/entry/43499 Hindi explanation playlist - https://www.youtube.com/watch?v=ER7EtbhNBXg&list=PLiINLbWPTveq8TuXDjsISg7fPHCrTO0oy&index=5 https://cp-algorithms.com/algebra/fft.html

45. Centroid Decomposition - https://www.youtube.com/watch?v=2izuGA8T8IE https://medium.com/carpanese/an-illustrated-introduction-to-centroid-decomposition-8c1989d53308 https://medium.com/carpanese/an-illustrated-introduction-to-centroid-decomposition-8c1989d53308 https://codeforces.com/blog/entry/81661

https://drive.google.com/file/d/1J2x8pIYQ3MXANgvzOgBciWd3d79j_Exa/view https://vjudge.net/.

46. Heavy-light decomposition - https://codeforces.com/blog/entry/81317

47. Binary Exponentiation - https://cp-algorithms.com/algebra/binary-exp.html

48. DP on trees and Binary Lifting in this -> https://www.youtube.com/watch?v=qPxS_rY0OJw&list=PLb3g_Z8nEv1j_BC-fmZWHFe6jmU_zv-8s&index=8
    LCA queries in log(n) also given.

49. How to solve multi state DP problems - https://www.hackerearth.com/practice/algorithms/dynamic-programming/state-space-reduction/tutorial/
    

50. https://www.geeksforgeeks.org/pattern-searching-using-suffix-tree/

51. Max-flow Ford fulkerson + BFS = EdmondKarp Algorithm https://www.youtube.com/watch?v=GiN3jRdgxU4
    Good video(NPTEL): https://www.youtube.com/watch?v=yxHDqjT6OQw&list=PLyqSpQzTE6M9DKhN7z2fOpKTJWu-639_P&index=52
    Can be used to solve maximum number of edge disjoin paths between two given nodes. https://www.geeksforgeeks.org/find-edge-disjoint-paths-two-vertices/
    Can be used to solve minimum s-t cut problem. "Minimum s-t cut capacity is equal to max flow capacity". https://www.geeksforgeeks.org/minimum-cut-in-a-directed-graph/
    Can be used to solve Job assignment problems(Maximum Bipartite Matching) -> https://www.youtube.com/watch?v=GhjwOiJ4SqU&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=34
    

52. Z-algorithm tutorial -> https://www.youtube.com/watch?v=uFPSFsOlklE&list=PLX4N9vQU5pGaEiXOnX1PE_UFvCO-Qkpav&index=2
    

53. Suffix array playlist -> https://www.youtube.com/watch?v=OptoHwC3D-Y&list=PLDV1Zeh2NRsCQ_Educ7GCNs3mvzpXhHW5&index=6
    

54. Convex Hull https://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
    https://www.youtube.com/watch?v=B2AJoQSZf4M
    https://leetcode.com/discuss/general-discussion/547798/Static-Comparator-function-for-sort-(Reasons-as-to-why)
    

55. Matrix Exponentiation - https://codeforces.com/blog/entry/80195 https://codeforces.com/blog/entry/43225

Good discussions and problems

1. Best leetcode discussions: https://leetcode.com/discuss/general-discussion/618186/best-leetcode-discussions-for-interview-preparation
   

2. Number of Islands followup: https://leetcode.com/problems/number-of-islands/discuss/640295/Optimized-by-memory-(follow-up-question-what-if-matrix-is-too-big)
   

3. DSW Balance BST algorithm: https://leetcode.com/problems/balance-a-binary-search-tree/discuss/541785/C%2B%2BJava-with-picture-DSW-O(n)orO(1)
   

4. Egg drop Interesting approach : https://leetcode.com/problems/super-egg-drop/discuss/158974/C%2B%2BJavaPython-2D-and-1D-DP-O(KlogN)
   

5. Next permutation best explaination : https://www.youtube.com/watch?v=quAS1iydq7U
   

6. https://leetcode.com/discuss/interview-question/790428/facebook-phone-interview-questions
   

7. Cherry pickup discussions - https://leetcode.com/problems/cherry-pickup/discuss/329945/Very-easy-to-follow-%3A-step-by-step-recursive-backtracking-with-memoization-N4.
   https://leetcode.com/problems/cherry-pickup/discuss/109903/Step-by-step-guidance-of-the-O(N3)-time-and-O(N2)-space-solution
   

8. Median of 2 sorted arrays : https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2471/Very-concise-O(log(min(MN)))-iterative-solution-with-detailed-explanation
   This question can also be done by using kth largest element given two sorted arrays. General form of this is -> https://www.youtube.com/watch?v=Q3JUfHpffIg

9. Tiling problem : https://www.geeksforgeeks.org/tiling-problem-using-divide-and-conquer-algorithm/

10. Sliding window maximum : https://www.youtube.com/watch?v=5VDQxLAlfu0
    https://leetcode.com/problems/sliding-window-maximum/discuss/65884/Java-O(n)-solution-using-deque-with-explanation Sliding window model(discusses various variants) : https://www.youtube.com/watch?v=MK-NZ4hN7rs

11. Amazon question, binary expression tree : https://leetcode.com/discuss/interview-question/804632/amazon-phone-minimal-removal-to-reach-target-for-expression-tree

12. Skyline problem : https://www.youtube.com/watch?v=Cv0ft2dFz80
    https://www.youtube.com/watch?v=GSBLe8cKu0s

13. Graph and string problem(remove minimum number of chars from string so that a property is satisfied): https://www.youtube.com/watch?v=EE_9U798nvQ

14. Largest histogram question variation : https://leetcode.com/discuss/interview-question/815454/amazon-oa-question-sde-1

15. https://leetcode.com/discuss/interview-experience/810079/google-l3-bangalore-august-2020-offer #TODO

16. Rabin-Karp algo question https://leetcode.com/problems/longest-duplicate-substring/

17. https://leetcode.com/discuss/interview-question/822153/apple-redacted-developer-technology-engineer-cupertino-ca-austin-tx-10-yoe-reject
    

18. https://leetcode.com/discuss/interview-experience/821453/goldman-sach-virtual-interview

19. Weighted job scheduling https://leetcode.com/problems/maximum-profit-in-job-scheduling/discuss/409031/C%2B%2B-Sort-and-DP-O(NlogN)

20. How to use Leetcode effectively: https://docs.google.com/document/d/1IES8uw9f4w9iCsIoArUioYB8ctVRR-TaA1Qu4YhcQ9U/preview?pru=AAABdKyjdc0*nWdrLI3O3Bm7xUG8OV_xPQ

21. https://leetcode.com/discuss/interview-experience/842389/10-companies-15-interviews-and-4-offers-my-story

22. Amazon leadership principles - https://www.youtube.com/watch?v=Ta9tCwcMbXs

23. Gap method to merge two sorted arrays : https://www.youtube.com/watch?v=hVl2b3bLzBw -> Uses shell sort

24. Buy Sell 4 -> https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/ great question https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/Most-consistent-ways-of-dealing-with-the-series-of-stock-problems

25. Optimal BST - https://www.youtube.com/watch?v=vLS-zRCHo-Y https://www.youtube.com/watch?v=hgA4xxlVvfQ

26. Minmax algorithm - https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-1-introduction/

27. Square sorting interesting O1 - https://leetcode.com/discuss/interview-question/351341/Google-or-Onsite-or-Squares-of-a-Sorted-Array/318306

28. https://leetcode.com/discuss/interview-question/882062/google-onsite-phone-interviews

29. Minimum number of refuelling stops - https://leetcode.com/problems/minimum-number-of-refueling-stops/discuss/149858/Simple-Java-Solution-Using-PriorityQueue-O(nlogn)
    

30. https://www.geeksforgeeks.org/program-for-mean-and-median-of-an-unsorted-array/ Order statistics, Mode also

31. Finding all cycles in a graph https://www.youtube.com/watch?v=BIZ1rmO29QU
    First find MST of the graph. Then when we add other edges we will get a cycle. Let the nodes of this edge by u,v. Then find the LCA of these nodes in the graph. Cycle will be the path from LCA to u, u and v edge, v to LCA.
    https://comeoncodeon.wordpress.com/2010/06/07/number-of-cycles-in-a-graph/

32. https://www.geeksforgeeks.org/vertex-cover-problem-set-2-dynamic-programming-solution-tree/ Vertex cover Binary tree cameras -> https://leetcode.com/problems/binary-tree-cameras/discuss/211223/C%2B%2B-Naive-DFS-%2B-Memo These are slightly different problems.
    

33. https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/189039/Detailed-intuition-behind-Deque-solution
    https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/834626/C%2B%2B-All-3-approaches

34. Reconstruct a queue -> https://leetcode.com/problems/queue-reconstruction-by-height/discuss/427157/Three-different-C%2B%2B-solutions.-from-O(n2)-to-O(nlogn).-faster-than-99.

35. kth smallest instruction : https://leetcode.com/problems/kth-smallest-instructions/discuss/918396/Python-Math-solution-Introduction-to-Combinatorics

36. Nice trick : https://www.geeksforgeeks.org/minimum-number-increment-operations-make-array-elements-equal/
    https://practice.geeksforgeeks.org/problems/dice-throw5349/1#
    https://leetcode.com/problems/count-binary-substrings/discuss/108625/JavaC%2B%2BPython-Easy-and-Concise-with-Explanation
    

#TODO
https://www.hackerrank.com/challenges/team-formation/editorial
https://discuss.codechef.com/t/twofl-editorial/18922
https://www.geeksforgeeks.org/count-derangements-permutation-such-that-no-element-appears-in-its-original-position/
https://www.youtube.com/watch?v=rbB8knrTxK0&feature=youtu.be
https://webcache.googleusercontent.com/search?q=cache:tsUBbCsU5MkJ:https://leetcode.com/articles/maximum-distance-in-array/+&cd=2&hl=en&ct=clnk&gl=in&client=firefox-b-d
https://www.codechef.com/AUG15/problems/CHINSM/
https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/avoid-traps-0b92455e/
https://www.hackerrank.com/challenges/jeanies-route/problem

https://leetcode.com/problems/get-the-maximum-score/
https://leetcode.com/problems/prefix-and-suffix-search/

https://www.geeksforgeeks.org/maximum-sum-lengths-non-overlapping-subarrays-k-max-element/
https://www.geeksforgeeks.org/maximum-sum-two-non-overlapping-subarrays-of-given-size/
https://www.geeksforgeeks.org/number-groups-formed-graph-friends/
https://www.geeksforgeeks.org/minimize-the-sum-of-differences-of-consecutive-elements-after-removing-exactly-k-elements/?ref=rp
https://www.geeksforgeeks.org/find-all-cliques-of-size-k-in-an-undirected-graph/
https://www.geeksforgeeks.org/find-length-of-longest-substring-with-at-most-k-normal-characters/

• https://www.hackerrank.com/challenges/turn-off-the-lights/forum
• https://www.geeksforgeeks.org/stable-marriage-problem/?ref=rp
• https://www.geeksforgeeks.org/snake-ladder-problem-2/?ref=rp
• https://www.geeksforgeeks.org/double-knapsack-dynamic-programming/
• https://www.geeksforgeeks.org/extended-knapsack-problem/
• https://leetcode.com/problems/count-all-possible-routes
• https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/jenny-and-water-7-d0337cc3-ec2c1136/submissions/

#Gamescraft questions

• GCD groups - https://www.hackerrank.com/contests/hourrank-1/challenges/gcd-groups/problem

• Test1 - Reconstructing array, Sorted Arrangement, Xor subsequences https://imgur.com/a/IwowOAK

• Test2 - Paths to a goal https://imgur.com/doI1Dz3 https://leetcode.com/discuss/interview-question/881527/paths-to-a-goal-hackerrank

• City attractions and Can you make palindrome https://leetcode.com/discuss/interview-question/515737/sap-labs-oa
  

• Shared interest problem : https://github.com/Jayaram-p-7/Shared-Interest-Hackerank-problem
  

• Connected Sum https://www.chegg.com/homework-help/questions-and-answers/atlassian-university-software-x-h-hacker-rank-ha-h-ackerrankcom-test-51013iphbgr-questions-q43765379
  

• Product of Palindromes https://leetcode.com/discuss/interview-question/202924/Product-of-Palindromes/
  

• Travelling is Fun https://leetcode.com/discuss/interview-question/202553/Traveling-is-Fun/
  

• Count distinct substrings : https://www.geeksforgeeks.org/count-distinct-substrings-string-using-suffix-array/

• https://www.geeksforgeeks.org/minimum-number-of-distinct-elements-after-removing-m-items-set-2/

• https://www.geeksforgeeks.org/find-length-longest-subsequence-one-string-substring-another-string/

• String formation : https://www.geeksforgeeks.org/count-the-number-of-ways-to-construct-the-target-string/ - Corrected code - https://ide.geeksforgeeks.org/W8i48JP9o8

• https://leetcode.com/problems/longest-string-chain/

• Same as Travelling is fun https://leetcode.com/problems/graph-connectivity-with-threshold/

• Same as Sorted arrangements - https://leetcode.com/problems/create-sorted-array-through-instructions/

• Kth ancestor of a node : https://leetcode.com/problems/kth-ancestor-of-a-tree-node/

• Photo album and Regex question - ~~https://imgur.com/a/lOIStDo

• Lifting Weights(0-1 knapsack simple) - ~~https://www.chegg.com/homework-help/questions-and-answers/2-lifting-weights-ollie-new-gym-figuring-maximum-weights-lift-maximum-capacity-barbell-giv-q56805037

• https://leetcode.com/problems/minimum-operations-to-make-array-equal/
  

• Build offices - https://leetcode.com/discuss/interview-question/221639/
  

• paypal (split arrays and build offices) - https://drive.google.com/drive/folders/1gT3RDRSRIqyrRg8JINAvJojocGgrEbag
  

• questions (binary manipulation, build offices, intelligent substring) - https://imgur.com/a/vMn9egS
  solutions - https://imgur.com/a/szcwQrG

• Bob navigates path(not understood) : https://leetcode.com/discuss/interview-question/708638/sap-labs-oa-bob-navigates-a-maze
  Bob navigates a Maze and number of palindromic substrings(proper question) - https://imgur.com/a/TzAfeH5
  

• Count derangements - https://www.geeksforgeeks.org/count-derangements-permutation-such-that-no-element-appears-in-its-original-position/
  

• Connecting special nodes - https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/jenny-and-water-7-d0337cc3-ec2c1136/submissions/

• List inheritance - https://imgur.com/a/MHEuICx

• Count triplets with sum less than given value - https://www.geeksforgeeks.org/count-triplets-with-sum-smaller-that-a-given-value/

• Load balancing and Paint the ceiling https://imgur.com/a/zKmjS89

• Opening hospitals - https://imgur.com/a/7aL2Ggx (similar to binary tree cameras)

• Given an array of numbers and a target number, find number of triplets in array such that at least two numbers of the triplet are adjacent, and their product is equal to the target number. Two triplets are distinct if index of at least one number is different. Constraints: 3 <= size of array < 10^5. -10^10 < Tarm get Number < 10^10. Desired answer, target number were of type long and numbers in array were of type int. Example: array = [1,3,5,3,5] and target = 15. Ans = 4. Brute force will give TLE, O(n) solution was required.

• Given the locations of all the cars parked in an array and an integer k, minimum no of cars to be covered by shelter, return the minimum length of shelter needed to cover k cars. Eg: [6 2 12 7] and k=3, min length is 6 (from 2 to 7)

• Minimum sum - https://leetcode.com/discuss/general-discussion/680333/minimum-sum-with-k-operations

• https://stackoverflow.com/questions/48448432/fragment-of-missing-code-in-the-solution-movie-titles-complete-a-challenge-more

• https://leetcode.com/problems/longest-uncommon-subsequence-ii/

• Postman - https://leetcode.com/discuss/interview-question/370770/postman-hackerearth-software-engineering-intern-bengaluru-india

• https://www.geeksforgeeks.org/rail-fence-cipher-encryption-decryption/

https://leetcode.com/problems/paint-house-iii/ https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/ https://leetcode.com/problems/minimum-number-of-days-to-disconnect-island/ https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/ https://leetcode.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/ https://leetcode.com/problems/string-compression-ii/ https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/ https://leetcode.com/problems/maximum-number-of-non-overlapping-substrings/ https://www.geeksforgeeks.org/minimum-steps-reach-target-knight/ https://leetcode.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/ https://leetcode.com/problems/parallel-courses-ii/ https://leetcode.com/problems/allocate-mailboxes/ https://leetcode.com/problems/cherry-pickup-ii/ https://leetcode.com/problems/palindrome-partitioning-iii/ https://leetcode.com/problems/minimum-time-to-collect-all-apples-in-a-tree/ https://leetcode.com/problems/shortest-path-to-get-all-keys/ https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/ binary manipulation - https://stackoverflow.com/questions/54812971/programming-minimum-steps-required-to-convert-a-binary-number-to-zero https://www.geeksforgeeks.org/count-number-of-paths-with-k-turns/

Given an array of size N. Q queries given L, R, X (L, R 1-indexed), Return the maximum number between indices(both inclusive) L and R which have X set bits in binary representation. Ex: A = [1, 2, 3, 4, 5] Q = 1, => [3, 5, 2] => 3, 4, 5 fall in L, R. 3 & 5 have 2 set bits, maximum of which is 5. Return 5.
https://ide.geeksforgeeks.org/ZmGxP0pHsn

Postman : HACKER RANK AND THERE WERE THREE PROGRAMMING QUESTIONS 1.RECYCLING CARTRIDGE. 2.PAINT THE CEILING. 3. FILE I/O QUESTIONS

Will you follow @sugoi_kunstler on Instagram? Thanks :)