mathematical mindset notes

Books by Keith Devlin
A mathematician grappling with his century
Flannery 2002 - how the puzzles with her dad helped her math


KENKEN puzzles
Youcubed.org -> number sense/ Fluency without fear/
Mark Driscoll's books, Ruth Parker's mathematics problems, 2 curricula from England 1) Points of Departure 2) SMILE (Secondary mathematics individualized learning experience)
Multilink cubes
Given 36 sides, find shape with largest enclosure area, fencing, how does sin(x) help here. sin(10), circle.
Book ref - What's math got to do with it?

Don't seem useful: Apps and Games(All are paid seems like) - Motion Math, Number Rack(Math Learning Center), mathbreakers.com, Wuzzit Trouble,

biggest streak of good numbers

Given a list of bad numbers and lo and hi range, find the biggest streak of good numbers.

class Solution {
    public int driver() {
        int[] bad = new int[]{1,15,27};
        int lo = 27;
        int hi = 30;
        return bigStreak(bad, lo, hi);
    }
   
    private int bigStreak(int[] bad, int lo, int hi) {
        int max = 0;
        int i = 0;
        for(; i<bad.length-1; i++) {
            int curr = 0;  
            if (hi < bad[i]) {
                   curr = hi - lo + 1;
                   if(curr > max) max = curr;
                   break;
            } else if (hi == bad[i]) {
                curr = hi - lo;
                if (curr > max) max = curr;
                break;
            } else if (hi > bad[i] && hi <= bad[i + 1]) {
                if (lo < bad[i]) {
                    int s1 = bad[i] - 1 - lo + 1;
                    int s2 = hi - (bad[i] + 1) + 1;
                    if (hi == bad[i + 1]) --s2;
                    curr = Math.max(s1, s2);
                } else if (lo == bad[i]) {
                    curr = hi - (bad[i] + 1) + 1;
                    if (hi == bad[i + 1]) --curr;
                } else if (lo > bad[i]) {
                    curr = hi - lo + 1;
                    if (hi == bad[i + 1]) --curr;
                }
                if (curr > max) max = curr;
                break;
            } else if (hi > bad[i + 1]){
                if (lo <= bad[i]) {
                    int s1 = bad[i] - lo;
                    int s2 = bad[i + 1] - bad[i] - 1;
                    curr = Math.max(s1, s2);
                    lo = bad[i + 1] + 1;
                } else if (lo > bad[i] && lo <= bad[i + 1]) {
                    curr = bad[i + 1] - lo;
                    lo = bad[i + 1] + 1;
                } else if ( lo > bad[i + 1]) {
                   ;
                }
                if (curr > max) max = curr;
            }
        }
       
        if ( i == bad.length - 1) {
            int curr = hi - lo + 1;
            if ( curr > max ) max = curr;
        }
        return max;
    }
}

hotstar peak handling how

1. WC 2019 IND vs NZ Semifinal resulted in 25.3M concurrent users. Usage of around 10Tbps bandwidth which is 70% of India's capacity.

2. Scale proactively - can't scale in real time. Autoscaling results in insufficient capacity errors at times.

3. Graceful degradation - turn off less critical services when there is too much traffic. Reduce video quality for users. If auth system is having issues(DB in the backend is slow) - allow users to watch without login.

4. Peak traffic shift - as soon as Dhoni got out people went to the home screen. Home screen calls a lot of APIs - recommendation/watch history/general content.

5. Push notifications result in a traffic peaks.

6. Prewarm infra before match time.
7. No dumb clients - clients should add jitter to requests so as not to overwhelm the backend in case of issues.
8. Reject early - drive away a lot of spurious traffic - don't let it come to your backend.

Video

Blog

Facebook live streaming - split input feed into smaller chunks and deliver via hierarchy of cache servers. Don't let too many requests come to the origin server. First request will be a cache miss and rest will be held until the first one comes back.

reservoir sampling

good answer by sumitra narayan

Algorithm R from wikipedia:

(* S has items to sample, R will contain the result *)
ReservoirSample(S[1..n], R[1..k])
// fill the reservoir array
for i = 1 to k
   R[i] := S[i]
// replace elements with gradually decreasing probability
for i = k+1 to n
   j := random(1, i) // important: inclusive range
   if j <= k R[j] := S[i]

String search algorithms - Naive vs Rabin Karp vs KMP

Naive algorithm is O(n) in average as the probability of a random match is very low and even low for 2 consecutive character matches : 26^2. For 1 million char text and 1000 char word 1.04 million comparisons in average case. Worst case O(m*n) so if the above example 1 billion comparisons.

Rabin karp - used in plagiarism detection. Uses rolling hash - for e.g. if the text is ABCD, and we want to search a word of size 3 then we first compare the hash of ABC which is a*7^0 + b*7^1 + c*7^2. If it doesn't match the hash of the word then we move forward like this 1. first drop A => prev_hash - a*7^0. 2. Then divide the balance by 7 => (prev_hash - a*7^0)/7. 3. Then add D => (prev_hash - a*7^0)/7 + D*7^2. Worst case O(m*n)

KMP - Knuth Morris Pratt - uses a pre-computed table to decide from where to resume search in case of failure. Worst case O(n).