[Note] Dynamic programming on ProjectEuler

Latest revised on 2019-10-21

General rule:

Time complexity = Number of states * Number of transitions of one state * Time complexity of transition function

Examples:

• #31: Coin sums
• #67: Maximum path sum II
• #612: Friend numbers
• #618: Numbers with a given prime factor sum
• #655: Divisible Palindromes
• #662: Fibonacci paths
• #679: Freefarea

[FWD] 景氣指標查詢系統

Link: https://index.ndc.gov.tw/n/zh_tw/leading#/

鈍化。趁往下的時候研究股票。

[Leetcode] 1170. Compare Strings by Frequency of the Smallest Character

1. Pre-calculated on words.

2. Counting sort and built-in quick-sort (need to know the average/worst time complexity of quick sort.)

3. Binary search of time complexity O(log(n)). Stick on single implementation.

• left-closed and right-open interval. Same as for loop.
• < in while loop.
• mid = lower + (upper - lower) / 2 to avoid overflow.
• return lower.

You can develop other various implementations based on this one.

---

Source code:

class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] sorted = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            sorted[i] = calculate(words[i]);
        }
        Arrays.sort(sorted);

        int[] nums = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int target = calculate(queries[i]);
            int lower = 0;
            int upper = words.length;
            while (lower < upper) {
                int mid = lower + (upper - lower) / 2;
                if (sorted[mid] <= target) {
                    lower = mid + 1;
                } else {
                    upper = mid;
                }
            }
            nums[i] = words.length - lower;
        }
        return nums;
    }
    
    private int calculate(String word) {
        int[] counting = new int[26];
        for (char c : word.toCharArray()) {
            counting[c - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (counting[i] > 0) {
                return counting[i];
            }
        }
        return 0;
    }
}

Notes on Google interview

Recommended video: How to: Work at Google — Example Coding/Engineering Interview [link].

How Google hire: https://careers.google.com/how-we-hire/

• Apply
• Show your resume in LinkedIn. (Excellent suggestion from my ex-director.)
• Internal referral.
• Interview
• 到龍山寺拜文昌帝君
• Practice LeetCode problems systematically.
• Try to get any feedback after any interview. It will make you better and better.
• Decide
• 文昌帝君會托夢給 hiring committee. 

[FWD] Pi in the sky: Calculating a record-breaking 31.4 trillion digits of Archimedes’ constant on Google Cloud

Notes:

• Google Blog: [blog]
• Method: Chudnovsky formula: [wiki]
• L. Milla: A Detailed Proof of the Chudnovsky Formula: [paper]

[Books] Programming Pearls (2nd Edition)

Bought a Chinese translation of Programming Pearls (2nd Edition).



Super recommend to read!



Quote from this book:

Q: It seems that most columns emphasize the design process. Can you summarize your advice on that topic?

• Work on the right problem.
• Explore the design space of solutions.
• Look at the data.
• Use the back of the envelope.
• Exploit symmetry.
• Design with components.
• Build prototypes.
• Make tradeoffs when you have to.
• Keep it simple.
• Strive for elegance.

Also check this for designing machine learning systems: Hidden Technical Debt in Machine Learning Systems [paper]. 

[FWD] Cost of Living Comparison

Example: Cost of Living Comparison Between Taipei and Singapore

https://www.numbeo.com/cost-of-living/compare_cities.jsp?country1=Taiwan&city1=Taipei&country2=Singapore&city2=Singapore&amount=1%2C000%2C000.00&displayCurrency=TWD

+30% but we can explain the whole details to clarify the correctness of these metrics.