Thursday, December 31, 2020

Optimal Algorithm for a Problem

 “The ultimate goal in designing algorithms and data structures is to find an optimal algorithm for a problem, that is, an algorithm whose worst-case runtime complexity matches the intrinsic complexity of the problem it solves.”


Martin Erwig. “Once Upon an Algorithm: How Stories Explain Computing.” 

Problem Simplification

 “Problem simplification is often a crucial step toward solving a problem.”

Martin Erwig. “Once Upon an Algorithm: How Stories Explain Computing.” 

Relationship Between the Complexity of the Problem and Solution

 The distinction between the complexity of a problem and the complexity of its solutions helps us understand the notion of an optimal solution.


 Martin Erwig. “Once Upon an Algorithm: How Stories Explain Computing.” 

Precomputing

 In this case, even if the sorting takes linearithmic time, it is worth the effort, since it saves precious class time. This is an example of precomputing, where some data needed for an algorithm is computed before the algorithm is executed.

“This strategy of computing information ahead of time is called precomputation.”

“The crucial aspect of precomputation is that computational effort is expended at one time and the computed result is used at a later time. The precomputed result is preserved in a data structure”

“Situations in which one can expect to make use of a data structure repeatedly provide a strong incentive to expend the precomputing effort because the cost can be amortized over several uses.”

“ There are many situations, however, when it’s not clear whether the precomputation effort will pay off.”

“In cases like these, the value of acting early, or precomputing, is called into question by uncertainty about the future. Since the benefit of precomputation depends on a specific outcome of future events, it reflects a rather optimistic computation attitude with a confident outlook on the future.”

“A skeptical attitude toward the future calls for a radically different strategy for scheduling computation, namely, a strategy that tries to delay costly operations as much as possible until they cannot be avoided anymore. The hope or expectation is that something might happen that makes the costly operation obsolete and thus saves its runtime (and potentially other resources). In real life this behavior would be called procrastination; in computer science it is called lazy evaluation. ”

“Lazy evaluation can save computation effort whenever the information that would have been obtained by the saved computation is not needed anymore.”

“While lazy evaluation seems attractive in its promise to not waste effort, it is problematic when an action that becomes unavoidable takes longer than it would have under precomputing, or worse, longer than there is time available. In particular, when several delayed actions become due at the same time, this might present a serious resource problem. Therefore, an overall more sensible strategy is to distribute work evenly over time. While this might waste some effort on precomputing, it avoids crises that a lazy evaluation strategy might bring on.”

Martin Erwig. “Once Upon an Algorithm: How Stories Explain Computing.” 

Tuesday, December 29, 2020

Problem Sequence

 

  1. Contains Duplicate

  2. Missing Number

  3. Find All Numbers Disappeared in an Array

  4. Single Number

  5. Climbing Stairs

  6. House Robber

  7. Best Time to Buy and Sell Stock

  8. Maximum Subarray

  9. Range Sum Query - Immutable

  10. Linked List Cycle

  11. Middle of the Linked List

  12. Palindrome Linked List

  13. Remove Linked List Elements

  14. Remove Duplicates from Sorted List

  15. Reverse Linked List

  16. Merge Two Sorted Lists

  17. Meeting Rooms

  18. Binary Search

  19. Find Smallest Letter Greater Than Target

  20. Peak Index in a Mountain Array

  21. Binary Tree Level Order Traversal II

  22. Average of Levels in Binary Tree

  23. Minimum Depth of Binary Tree

  24. Same Tree

  25. Path Sum

  26. Diameter of Binary Tree

  27. Merge Two Binary Trees

  28. Maximum Depth of Binary Tree

  29. Lowest Common Ancestor of a Binary Search Tree

  30. Subtree of Another Tree

  31. Invert Binary Tree

  32. Two Sum

  33. Squares of a Sorted Array

  34. Backspace String Compare

  35. Longest Word in Dictionary

  36. Index Pairs of a String

  37. Majority Element

  38. Product of Array Except Self

  39. Find the Duplicate Number

  40. Find All Duplicates in an Array

  41. Set Matrix Zeroes

  42. Spiral Matrix

  43. Rotate Image

  44. Word Search

45. Letter Case Permutation 46. Subsets
47. Subsets II
48. Permutations

49. Permutations II
50. Combinations
51. Combination Sum
52. Combination Sum II 53. Combination Sum III 54. Generate Parentheses 55. Target Sum

56. Palindrome Partitioning
57. Letter Combinations of a Phone Number
58. Generalized Abbreviation
59. House Robber II
60. Coin Change
61. Maximum Product Subarray
62. Longest Increasing Subsequence
63. Longest Palindromic Substring
64. Word Break
65. Combination Sum IV
66. Decode Ways
67. Unique Paths
68. Jump Game
69. Palindromic Substrings
70. Number of Longest Increasing Subsequence
71. Partition Equal Subset Sum
72. Partition to K Equal Sum Subsets
73. Best Time to Buy and Sell Stock with Cooldown
74. Counting Bits
75. Linked List Cycle II
76. Add Two Numbers
77. Remove Nth Node From End Of List
78. Sort List
79. Reorder List
80. Clone Graph
81. Pacific Atlantic Water Flow
82. Number of Islands
83. Graph Valid Tree
84. Number of Connected Components in an Undirected Graph 85. Reverse Linked List II
86. Rotate List
87. Swap Nodes in Pairs
88. Odd Even Linked List

89. Kth Smallest Element in a Sorted Matrix 90. Find K Pairs with Smallest Sums
91. Merge Intervals
92. Interval List Intersections

93. Non-overlapping Intervals
94. Meeting Rooms II
95. Task Scheduler
96. Minimum Number of Arrows to Burst Balloons 97. Find Minimum in Rotated Sorted Array

98. Find Peak Element
99. Search in Rotated Sorted Array

  1. Search in Rotated Sorted Array II

  2. Search a 2D Matrix

  3. Search a 2D Matrix II

  4. Find K Closest Elements

  5. Minimum Size Subarray Sum

  6. Fruit Into Baskets

  7. Permutation in String

  8. Longest Repeating Character Replacement

  9. Kth Smallest Element in a BST

  10. K Closest Points to Origin

  11. Top K Frequent Elements

  12. Sort Characters By Frequency

  13. Kth Largest Element in an Array

  14. Reorganize String

  15. Course Schedule

  16. Course Schedule II

  17. Minimum Height Trees

  18. Binary Tree Level Order Traversal

  19. Binary Tree Zigzag Level Order Traversal

  20. Populating Next Right Pointers in Each Node

  21. Populating Next Right Pointers in Each Node II

  22. Binary Tree Right Side View

  23. All Nodes Distance K in Binary Tree

  24. Path Sum II

  25. Path Sum III

  26. Lowest Common Ancestor of a Binary Tree

  27. Maximum Binary Tree

  28. Maximum Width of Binary Tree

  29. Construct Binary Tree from Preorder and Inorder Traversal

  30. Validate Binary Search Tree

  31. Implement Trie (Prefix Tree)

  32. 3 Sum

  33. 3 Sum Closest

  1. Subarrays with Product Less than K

  2. Sort Colours

  3. Maximum XOR of Two Numbers in an Array

  4. First Missing Positive

  5. Longest Consecutive Sequence

  6. Sudoku Solver

  7. N-Queens

  8. Reverse Nodes in k-Group

  9. Merge k Sorted Lists

  10. Smallest Range Covering Elements from K Lists

  11. Insert Interval

  12. Employee Free Time

  13. Count of Range Sum

  14. Sliding Window Maximum

  15. Longest Substring Without Repeating Characters

  16. Minimum Number of K Consecutive Bit Flips

  17. Count Unique Characters of All Substrings of a Given String

  18. Minimum Window Substring

  19. Substring with Concatenation of All Words

  20. Rearrange String k Distance Apart

  21. Course Schedule III

  22. Maximum Frequency Stack

  23. Alien Dictionary

  24. Sequence Reconstruction

  25. Binary Tree Maximum Path Sum

  26. Serialize and Deserialize Binary Tree

  27. Word Search II

  28. Find Median from Data Stream

  29. Sliding Window Median

  30. Trapping Rain Water

  31. Container With Most Water

  32. Concatenated Words

  33. Prefix and Suffix Search

  34. Palindrome Pairs

  35. Design Search Autocomplete System

  36. Word Squares

  37. Sort Items by Groups Respecting Dependencies

  38. Median of Two Sorted Arrays

Tuesday, December 08, 2020

SMIQ

When it comes to preparing for coding interview, what is the single biggest challenge/frustration/question you are running into right now?

Thursday, December 03, 2020

Types of Dynamic Programming

For coding interviews, the most common types of DP problems are: 1. Knapsack - 0-1 - Bounded - Unbounded 2. LCS 3. LIS 4. Matrix chain multiplication 5. DP on grid 6. Kadane's algorithm etc Advanced Dynamic Programming 1. Kth lexicographical string 2. DP on Tree 3. DP + bitmasking 4. DP + BIT/Segment tree 5. DP + convex hull Mostly, this is for competitive programming.

Wednesday, December 02, 2020

Monday, November 30, 2020

Edit Distance - Dynamic Programming










 

Data Structure Operations Cheat Sheet


 

Sorting Algorithms Cheat Sheet


 

Look for Similarities Between Problems

 It is always a good idea to look for similarities between problems. By studying the differences and similarities between two problems, one usually gains insight into both problems. Given a new problem, the first question should be in almost all cases, "Is this problem similar to a known problem?" Sometimes, the similarities between two problems become apparent only after complicated reductions are exhibited. The reductions between matrix and graph algorithms are especially interesting.  

Eulerian Graphs







Longest Increasing Subsequence










Binary Search in a Cyclic Sequence



 

The Knapsack Problem













Finding the Maximum Consecutive Subsequence

 









The Skyline Problem

 





The Celebrity Problem