## 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
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

### Leetcode Live Coding Telegram Group

Join Leetcode Live Coding Telegram group: https://t.me/joinchat/VOy5LhxpFvgV4aJKeMBIRg

Friendly Link to join: https://t.me/livecodingpro