[Python] GetPrimes code snippet

GetPrimes code snippet: (naive)

def GetPrimes(n):
  """
  Get all primes up to n.

  Use sieve of Eratosthenes to generate all primes less or equal to n. For
  example, given n = 10, then returns a list of primes [2, 3, 5, 7].

  Args:
    n: An integer representing the upper bound.

  Returns:
    A list containing all primes <= n in the increasing order.
  """
  sqrt_n = int(math.sqrt(n))
  visited = [False] * (n + 1)
  for i in range(2, sqrt_n + 1):
    if not visited[i]:
      for j in range(i * i, n + 1, i):
        visited[j] = True
  primes = []
  for i in range(2, n + 1):
    if not visited[i]:
      primes.append(i)
  return primes

[Python] ModInverse code snippet

ModInverse code snippet: (depends on ExtendedGcd())

def ModInverse(a, m):
  """
  Modular multiplicative inverse algorithm.

  Computes modular multiplicative inverse of an integer a is an integer x such
  that the product ax is congruent to 1 with respect to the modulus m.

  Args:
    a: An integer.
    m: An integer representing modulus.

  Returns:
    An integer x satisfying ax = 1 (mod m). Otherwise throw an exception if
    there is no such integer x.
  """
  g, x, y = ExtendedGcd(a, m)
  if g != 1:
    raise Exception('modular inverse does not exist')
  return x % m

[Python] ExtendedGcd code snippet

ExtendedGcd code snippet:

def ExtendedGcd(a, b):
  """
  Extended Euclidean algorithm.

  Computes, in addition to the greatest common divisor of integers a and b,
  also the coefficients of Bezout's identity, which are integers x and y such
  that a x + b y = gcd(a, b).

  Args:
    a: An integer.
    b: An integer.

  Returns:
    A tuple (g, x, y) satisfying a x + b y = g.
  """
  if a == 0:
    return (b, 0, 1)
  else:
    g, y, x = ExtendedGcd(b % a, a)
    return (g, x - (b // a) * y, y)

[Python] Factorize code snippet

Factorize code snippet: (depends on GetPrimes())

def Factorize(n, primes):
  """
  Factorize n by primes.

  For every prime p <= sqrt(n), we examine whether n is divided by p. If so, we
  compute the maximal integer value e satisfying that n is divided by p^e and n
  is not divide by p^{e + 1}.

  The factorization is represented by a dict(). It means that all prime factors
  of n are not in order. Consider use collections.OrderedDict() instead of
  dict() to keep the order of prime factors.

  Args:
    n: An integer representing a number to be factorized.
    primes: An integer list representing all possible prime factors <= sqrt(n).

  Returns:
    A dictionary where the key representing a prime factor p and the
    corresponding value representing the maximal integer value e satisfying that
    n is divided by p^e and n is not divide by p^{e + 1}.
  """
  factorization = {}
  d = n
  for prime in primes:
    if prime * prime > d:
      break
    e = 0
    while d % prime == 0:
      d //= prime
      e += 1
    if e > 0:
      factorization[prime] = e
  if d > 1:
    factorization[d] = 1

  if primes[-1] * primes[-1] < d:
    raise ValueError
  return factorization

[Python] GetPrimes code snippet

GetPrimes code snippet:

def GetPrimes(n):
  """
  Get all primes up to n.

  Use sieve of Eratosthenes to generate all primes less or equal to n. For
  example, given n = 10, then returns a list of primes [2, 3, 5, 7].

  Args:
    n: An integer representing the upper bound.

  Returns:
    A list containing all primes <= n in the increasing order.
  """
  sqrt_n = int(math.sqrt(n))
  visited = [False] * (n + 1)
  for i in range(2, sqrt_n + 1):
    if not visited[i]:
      for j in range(i * i, n + 1, i):
        visited[j] = True
  primes = []
  for i in range(2, n + 1):
    if not visited[i]:
      primes.append(i)
  return primes

[Python] ModExponentiation code snippet

ModExponentiation code snippet:

def ModExponentiation(b, e, m):
  """
  Modular exponentiation algorithm of time complexity = O(log(e)).

  Args:
    b: An integer representing the base.
    e: An integer representing the exponent.
    m: An integer representing modulus.

  Returns:
    An integer c = b^e (mod m).
  """
  if e == 0:
    return 1
  y = b
  output = 1
  while e > 0:
    if e & 1 == 1:
      output = (output * y) % m
    y = (y * y) % m
    e >>= 1
  return output

[Note] Totient summatory function in sublinear time

Original post: https://math.stackexchange.com/questions/316376/how-to-calculate-these-totient-summation-sums-efficiently

Background:

• Totient summatory function: Wolfram

Python code snippet:

class TotientSummatoryFunction():
  """Totient summatory function class."""

  def __init__(self, bound, mod):
    """Initialize.

    Args:
      bound: An integer.
      mod: An integer.
    """
    self.mod = mod
    self.small_values = None
    self.small_value_bound = None
    self.big_values = {}
    self.InitSmallValues(bound)

  def InitSmallValues(self, bound):
    """Initialize small values for totient summatory function.

    Args:
      bound: An integer.
    """
    n = 3 * int(math.pow(bound, 2 / 3))
    assert(n**3 >= bound**2)
    print('InitSmallValues({n})'.format(n=n))

    phi = [i for i in range(n + 1)]
    for i in range(2, n + 1):
      if phi[i] != i:
        continue
      for j in range(i, n + 1, i):
        phi[j] = phi[j] // i * (i - 1)

    self.small_values = [0 for i in range(n + 1)]
    self.small_values[1] = phi[1] % self.mod
    for i in range(2, n + 1):
      self.small_values[i] = (self.small_values[i - 1] + phi[i]) % self.mod
    self.small_value_bound = n

  def Get(self, n):
    """Get totient summatory function value.

    Args:
      n: An integer.

    Returns:
      An integer.
    """
    if n <= self.small_value_bound:
      return self.small_values[n]

    if n not in self.big_values:
      result = n * (n + 1) // 2
      m = self.IntegerSqrt(n)
      for d in range(1, m + 1):
        result -= self.Get(d) * (n // d - n // (d + 1))
      for k in range(2, n // (m + 1) + 1):
        result -= self.Get(n // k)
      self.big_values[n] = result % self.mod
    return self.big_values[n]

  def IntegerSqrt(self, n):
    """
    Get the integer part of Sqrt[n].

    Args:
      n: An integer.

    Returns:
      An integer.
    """
    guess = (n >> n.bit_length() // 2) + 1
    result = (guess + n // guess) // 2
    while abs(result - guess) > 1:
      guess = result
      result = (guess + n // guess) // 2
    while result * result > n:
      result -= 1
    return result

[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.

Notes on System Design

Warning: All materials are prepared for Facebook onsite interview but I failed.


Case Study:

• Netflix (mysterious)
• Learning a Personalized Homepage – Netflix TechBlog – Medium (2015): Article
• The Netflix Recommender System: Algorithms, Business Value, and Innovation (2016): Paper
• Benchmarking Cassandra Scalability on AWS — Over a million writes per second (2011): Article
• A Multi-Armed Bandit Framework for Recommendations at Netflix | DataEngConf SF '18 (2018): YouTube
• Google
• Building Software Systems at Google and Lessons Learned (2010): Slide | YouTube
• Google Production Environment (2018): YouTube
• The Google File System - Research (2003): Paper
• MapReduce: Simplified Data Processing on Large Clusters (2004): Paper
• Bigtable: A Distributed Storage System for Structured Data (2006): Paper
• Differential Synchronization (2009): Paper | YouTube
• The Paxos Algorithm (2018): YouTube
• Yahoo
• The Hadoop Distributed File System (2010): Paper
• Analyzing Google File System and Hadoop Distributed File System (2016): Article 
• Youtube
• Deep Neural Networks for YouTube Recommendations (2016): Paper
• RecSys 2016: Paper Session 6 - Deep Neural Networks for YouTube Recommendations (2016): YouTube
• Facebook
• Balancing Multi-Tenancy and Isolation at 4 Billion QPS (2015): YouTube
• TAO: Facebook's Distributed Data Store for the Social Graph - Usenix (2013): Paper
• Finding a needle in Haystack: Facebook's photo storage - Usenix (2010): Paper
• Cassandra - A Decentralized Structured Storage System (2009): Paper
• Instagram
• Scaling Instagram (QCon London 2017): YouTube
• Amazon
• Dynamo: Amazon's Highly Available Key-value Store (2007): Paper
• Slack
• How Slack Works (QCon San Francisco 2016): YouTube
• Uber
• Project Mezzanine: The Great Migration (2015): Article
• Designing Schemaless, Uber Engineering’s Scalable Datastore Using MySQL (2016): Article Part 1 & Part2 & Part3
• The Uber Engineering Tech Stack, Part I: The Foundation (2016): Article
• The Uber Engineering Tech Stack, Part II: The Edge and Beyond (2016): Article
• How Uber Scales Their Real-Time Market Platform (2015): Article

Interview Practices:

• URL shortener system design | tinyurl system design | bitly system design (2018): YouTube
• NETFLIX System design | software architecture for netflix (2018): YouTube
• UBER System design | OLA system design | uber architecture | amazon interview question (2018): YouTube
• Twitter system design | twitter Software architecture | twitter interview questions (2018): YouTube
• Whatsapp System design or software architecture (2018): YouTube

Notes on Coding Interviews

• Search on YouTube.
• Practice. Practice. Practice.
• Practice a lot of problems? Not so effective.
• Effective way: build up your knowledge from Leetcode.
• Organize classical problems into several categories.
• Excellent example: https://cspiration.com/leetcodeClassification#103.
• My 5 categories: (All-in-one)[doc]
• Foundations: [doc]
• Array
• String
• Math
• Data Structure: [doc]
• Stack
• PriorityQueue
• LinkedList
• Binary Search Tree
• Advanced Design: [doc]
• Backtracking
• Dynamic Programming (too many dissimilar problems, and hard to prepare)
• Union Find
• Trie
• Graph Algorithms: [doc]
• Graph
• Tree
• DFS & BFS
• Topological Sort
• Selected Topics: [doc]
• System Design
• Random
• Matrix
• Bit Manipulation
• Computational Geometry
• Read articles in the Discuss.
• Identify all possible solutions
• Different algorithms (from brute force to effective algorithms).
• Same algorithm with different implementations (e.g., segment tree).
• (My documents are not completed. Try to build up your own documents.)
• Could analyze time complexity and space complexity of each solution.
• Analyze line by line.
• Understand all details of build-in libraries.
• Know which solution is the best under certain assumption.
• Official solutions are not always concise (and the best). But it must be correct.
• Improve your code review ability.
• Read codes in the Submission (if possible).
• Not always correct.
• Learn from undocumented solutions. Need more time to understand.
• Write down your concise code in your style.
• About 20 ~ 40 lines in Java.
• Concise but not tricky. Tricky codes are not easy to remember.
• Possible to reproduce in the real interview.
• Lengthy codes might be regarded as messy codes. 
• Just copy or imitate other's code. 
• Not shame.
• Save your time.
• Align to your style (e.g., binary search, naming convention and so on).
• Practice makes perfect.
• Identify your weakness.
• Could prove the correctness of your code.
• Demonstrate your codes line by line.
• Design meaningful test cases.

Notes on BERT

BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding

• Paper: https://arxiv.org/pdf/1810.04805.pdf

Abstract:

Language Representation Model:

• BERT: Bidirectional Encoder Representations from Transformers. 
• Self-supervised. 
• Unlike recent language representation models (ELMo, OpenAI GPT). 
• BERT is designed to pre-train deep bidirectional representations by jointly conditioning on both left and right context in all layers. 
• BERT can be fine-tuned with just one additional output layer to create state-of-the art models for a wide range of tasks without substantial task-specific architecture modifications. 
• BERT is conceptually simple and empirically powerful. 
• BERT obtains new state-of-the-art results on 11 natural language processing tasks at that time.

Related Work:

Feature-Based / Fine-Tuning:

• Learning without Forgetting: https://arxiv.org/pdf/1606.09282.pdf

BERT:

BERT Model Architecture:

• E = Embedding
• Trm = Transformers
• T = Token?

BERT Input Representations:

Transformers: Attention Is All You Need:

• Attention Is All You Need: https://papers.nips.cc/paper/7181-attention-is-all-you-need.pdf 
• The Annotated Transformer: http://nlp.seas.harvard.edu/2018/04/03/attention.html

Transformers: Details:

• Use Encoder only. 
• Use WordPiece embedding, not word2vec. (not quite understand)
• Learn positional embedding, not positional encoding. 
• Also use scaled dot-product attention: Q, K, V = (Queries, Key, Value) 
• Self-Attention in Encoder: Q = K = V. 
• Reference: Key-Value Memory Networks for Directly Reading Documents (not quite understand)
• Also use LayerNorm.
• Also use residual connection.

Pre-training Task #1: Masked LM

• Standard conditional language models can only be trained left-to-right or right-to-left, since bidirectional conditioning would allow each word to indirectly “see itself” in a multi-layered context.
• Solution: skip-gram model (word2vec) or cloze task or denoising autoencoders. (not quite understand)
• Masked Language Model: Mask some percentage of the input tokens at random, and then predicting only those masked tokens.
• Mask 15% of all WordPiece tokens in each sequence at random.
• Only predict the masked words rather than reconstructing the entire input.
• Example:
• Input: the man went to the [MASK1] . he bought a [MASK2] of milk.
• Labels: [MASK1] = store; [MASK2] = gallon

Pre-training Task #1: Downsides

• The first is that we are creating a mismatch between pre-training and fine tuning, since the [MASK] token is never seen during fine-tuning.
• To mitigate this, we do not always replace “masked” words with the actual [MASK] token.
• Rather than always replacing the chosen words with [MASK], the data generator will do the following:
• 80% of the time: Replace the word with the [MASK] token, e.g., my dog is hairy → my dog is [MASK]
• 10% of the time: Replace the word with a random word, e.g., my dog is hairy → my dog is apple
• 10% of the time: Keep the word unchanged, e.g., my dog is hairy → my dog is hairy. The purpose of this is to bias the representation towards the actual observed word.
• The second downside of using an MLM is that only 15% of tokens are predicted in each batch, which suggests that more pre-training steps may be required for the model to converge.

Pre-training Task #2: Next Sentence Prediction

• Many important downstream tasks such as Question Answering (QA) and Natural Language Inference (NLI) are based on understanding the relationship between two text sentences, which is not directly captured by language modeling. 
• In order to train a model that understands sentence relationships, we pre-train a binarized next sentence prediction task that can be trivially generated from any monolingual corpus.
• Example #1:
• [CLS] the man went to [MASK] store [SEP] he bought a gallon [MASK] milk [SEP]
• Label: IsNext 
• Example #2: (negative sampling)
• [CLS] the man [MASK] to the store [SEP] penguin [MASK] are flight ##less birds [SEP] 
• Label: NotNext

Pre-training Tasks:

• We do not use traditional left-to-right or right-to-left language models to pre-train BERT.
• Instead, we pre-train BERT using two novel unsupervised prediction tasks.
• total_loss = masked_lm_loss + next_sentence_loss
• log_probs = tf.nn.log_softmax(logits, axis=-1)
• per_example_loss = -tf.reduce_sum(log_probs * one_hot_labels, axis=[-1]) 
• numerator = tf.reduce_sum(label_weights * per_example_loss) 
• denominator = tf.reduce_sum(label_weights) + 1e-5 
• loss = numerator / denominator

Pre-training Procedure:

• For the pre-training corpus we use the concatenation of BooksCorpus (800M words) and English Wikipedia (2,500M words). 
• Training of BERTBASE was performed on 4 Cloud TPUs in Pod configuration (16 TPU chips total).
• Training of BERTLARGE was performed on 16 Cloud TPUs (64 TPU chips total). 
• Each pre-training took 4 days to complete.
• Pricing? https://cloud.google.com/products/calculator/?hl=zh-TW

Fine-tuning Procedure:

• For sequence-level classification tasks, BERT fine-tuning is straightforward. 
• In order to obtain a fixed-dimensional pooled representation of the input sequence, we take the final hidden state (i.e., the output of the Transformer) for the first token in the input, which by construction corresponds to the the special [CLS] word embedding. 
• We denote this vector as C ∈ R^H. 
• The only new parameters added during fine-tuning are for a classification layer W ∈ R^{K×H}, where K is the number of classifier labels. 
• The label probabilities P ∈ R^K are computed with a standard softmax, P = softmax(CW^T). 

Fine-tuning:

• For fine-tuning, most model hyperparameters are the same as in pre-training, with the exception of the batch size, learning rate, and number of training epochs. 
• The dropout probability was always kept at 0.1.
• The optimal hyperparameter values are task-specific.

Experiments:

Sentence Pair Classification: MNLI:

• MNLI: Given a pair of sentences, the goal is to predict whether the second sentence is an entailment, contradiction, or neutral with respect to the first one.
• The only new parameters introduced during fine-tuning is a classification layer W ∈ R^{K×H}, where K is the number of labels.
• We compute a standard classification loss with C and W, i.e., log(softmax(CW^T)).
• GLUE leaderboard
• #3: BERT
• #2: MT-DNN (Microsoft)
• #1: Human

(Single Sentence Classification Tasks: similar to Sentence Pair Classification Tasks)


Question Answering: SQuAD v1.1:

• SQuAD v1.1: Given a question and a paragraph from Wikipedia containing the answer, the task is to predict the answer text span in the paragraph.
• The only new parameters learned during fine-tuning are a start vector S ∈ R^H and an end vector E ∈ R^H.
• The probability of word i being the start of the answer span is computed as a dot product between Ti and S followed by a softmax over all of the words in the paragraph.

Single Sentence Tagging: NER:

• CoNLL 2003 Named Entity Recognition: Locate and classify named entity mentions in the unstructured text into predefined categories.
• For fine-tuning, we feed the final hidden representation Ti ∈ R^H for to each token i into a classification layer over the NER label set.

Ablation Studies:

Effect of Pre-training Tasks:

Effect of Model Size:

Effect of Number of Training Steps:

Feature-based Approach with BERT:

Conclusion:

• Recent empirical improvements due to transfer learning with language models have demonstrated that rich, unsupervised pre-training is an integral part of many language understanding systems. 
• In particular, these results enable even low-resource tasks to benefit from very deep unidirectional architectures.
• Generalize these findings to deep bidirectional architectures, allowing the same pre-trained model to successfully tackle a broad set of NLP tasks.
• While the empirical results are strong, in some cases surpassing human performance, important future work is to investigate the linguistic phenomena that may or may not be captured by BERT.

References:

• Google Al Blog: https://ai.googleblog.com/2018/11/open-sourcing-bert-state-of-art-pre.html
• Source code: https://github.com/google-research/bert
• The Illustrated BERT, ELMo, and co. (How NLP Cracked Transfer Learning):  https://jalammar.github.io/illustrated-bert/

[Data Structure] Segment Tree

(Ignore some trivial applications.)

Example #1: [Leetcode] Count of Smaller Numbers After Self (315)

Solution: https://docs.google.com/document/d/1kfn4MfnLLXVNFfayX6L6sjAsZSuUy6gJoJit3sngG-E/edit?usp=sharing

• Segment Tree
• Top-Down Recursion
• Top-Down Iteration
• Bottom-Up Iteration

---

Code (Top-Down Recursion):

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        LinkedList<Integer> output = new LinkedList<>();
        Map<Integer, Integer> rankMap = getRankMap(nums);        
        SegmentTreeNode tree = buildTree(0, nums.length - 1);
        for (int i = nums.length - 1; i >= 0; i--) {
            int rank = rankMap.get(nums[i]);
            output.addFirst(sum(tree, 0, rank - 1));
            add(tree, rank, 1);
        }
        return output;
    }
    
    private Map<Integer, Integer> getRankMap(int[] nums) { 
        int[] sorted = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sorted);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < sorted.length; i++) {
            map.put(sorted[i], i);
        }
        return map;
    }
    
    private SegmentTreeNode buildTree(int lower, int upper) {
        if (lower > upper) {
            return null;
        } else {
            SegmentTreeNode node = new SegmentTreeNode(lower, upper);
            if (lower < upper) {
                int mid = lower + (upper - lower) / 2;
                node.left = buildTree(lower, mid);
                node.right = buildTree(mid + 1, upper);
            }
            return node;
        }
    }
    
    private int sum(SegmentTreeNode node, int lower, int upper) {
        if (lower > upper) {
            return 0;
        }
        if (node.lower == lower && node.upper == upper) {
            return node.sum;
        }
        int mid = node.lower + (node.upper - node.lower) / 2;
        if (upper <= mid) {
            return sum(node.left, lower, upper);
        } else if (lower > mid) {
            return sum(node.right, lower, upper);
        } else {
            return sum(node.left, lower, mid) + sum(node.right, mid + 1, upper);
        }
    }

    private void add(SegmentTreeNode node, int x, int val) {
        if (node.lower == x && node.upper == x) {
            node.sum += val;
            return;
        }
        int mid = node.lower + (node.upper - node.lower) / 2;
        if (x <= mid) {
            add(node.left, x, val);
        } else {
            add(node.right, x, val);
        }
        node.sum = node.left.sum + node.right.sum;
    }

    private class SegmentTreeNode {
        public int lower;
        public int upper;
        public int sum;
        public SegmentTreeNode left;
        public SegmentTreeNode right;
        public SegmentTreeNode(int lower, int upper) {
            this.lower = lower;
            this.upper = upper;
            this.sum = 0;
        }
    }
}

---

Code (Top-Down Iteration):

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        LinkedList<Integer> output = new LinkedList<>();
        Map<Integer, Integer> rankMap = getRankMap(nums);        
        int[] tree = new int[4 * nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            int rank = rankMap.get(nums[i]);
            output.addFirst(sum(tree, 1, 0, nums.length - 1, 0, rank - 1));
            add(tree, 1, 0, nums.length - 1, rank, 1);
        }
        return output;
    }
    
    private Map<Integer, Integer> getRankMap(int[] nums) { 
        int[] sorted = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sorted);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < sorted.length; i++) {
            map.put(sorted[i], i);
        }
        return map;
    }
    
    private void add(int[] tree, int node, int lower, int upper, int i, int val) {
        if (lower > upper || i < lower || i > upper) {
            return;
        }
        if (lower == upper) {
            tree[node] += val;
            return;
        }
        int mid = lower + (upper - lower) / 2;
        add(tree, 2 * node, lower, mid, i, val);
        add(tree, 2 * node + 1, mid + 1, upper, i, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    
    private int sum(int[] tree, int node, int lower, int upper, int i, int j) {
        if (lower > upper || j < lower || i > upper) {
            return 0;
        }
        if (lower >= i && upper <= j) {
            return tree[node];
        }
        int mid = lower + (upper - lower) / 2;
        if (j <= mid) {
            return sum(tree, 2 * node, lower, mid, i, j);
        } else if (i > mid) {
            return sum(tree, 2 * node + 1, mid + 1, upper, i, j);
        } else {
            return sum(tree, 2 * node, lower, mid, i, j) + sum(tree, 2 * node + 1, mid + 1, upper, i, j);
        }
    }
}

---

Code (Bottom-Up Iteration):

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        LinkedList<Integer> output = new LinkedList<>();
        Map<Integer, Integer> rankMap = getRankMap(nums);        
        int[] tree = new int[2 * nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            int rank = rankMap.get(nums[i]);
            output.addFirst(sum(tree, nums.length, 0, rank - 1));
            add(tree, nums.length, rank, 1);
        }
        return output;
    }
    
    private Map<Integer, Integer> getRankMap(int[] nums) { 
        int[] sorted = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sorted);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < sorted.length; i++) {
            map.put(sorted[i], i);
        }
        return map;
    }
    
    private int sum(int[] tree, int n, int i, int j) {
        i += n;
        j += n;
        int output = 0;
        while (i <= j) {
            if (i % 2 == 1) {
                output += tree[i++];
            }
            if (j % 2 == 0) {
                output += tree[j--];
            }
            i /= 2;
            j /= 2;
        }
        return output;
    }

    private void add(int[] tree, int n, int i, int val) {
        i += n;
        tree[i] += val;
        for (i /= 2; i > 0; i /= 2) {
            tree[i] = tree[2 * i] + tree[2 * i + 1];
        }
    }
}

---

References:

• https://codeforces.com/blog/entry/18051?locale=ru
• http://hehejun.blogspot.com/2017/11/leetcode-count-of-smaller-numbers-after.html

[Data Structure] Binary Indexed Tree

(Ignore some trivial applications.)

Example #1: [Leetcode] Count of Smaller Numbers After Self (315)

Solution: https://docs.google.com/document/d/1kfn4MfnLLXVNFfayX6L6sjAsZSuUy6gJoJit3sngG-E/edit?usp=sharing

Code:

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int[] tree = new int[nums.length + 1];
        Map<Integer, Integer> rankMap = getRankMap(nums);
        LinkedList<Integer> output = new LinkedList<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            int rank = rankMap.get(nums[i]);
            output.addFirst(sum(tree, rank));
            add(tree, rank + 1, 1);
        }
        return output;
    }
    
    private Map<Integer, Integer> getRankMap(int[] nums) { 
        int[] sorted = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sorted);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < sorted.length; i++) {
            map.put(sorted[i], i);
        }
        return map;
    }
    
    private void add(int[] tree, int x, int val) {
        for (int i = x; i < tree.length; i += lowbit(i)) {
            tree[i] += val;
        }
    }
    
    private int sum(int[] tree, int x) {
        int output = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            output += tree[i];
        }
        return output;
    }
    
    private int lowbit(int x) {
        return x & (-x);
    }
}

Notes:

• Sample input: [5,2,6,1,2,4,2,1]
• Sample output: [6,2,5,0,1,2,1,0]
• rankMap, {1=1, 2=4, 4=5, 5=6, 6=7}, is a kind of a data compression of the input because we only care about the relative partial order of the input.

Example #2: [SPOJ] DQUERY - D-query

Solutions:

• https://www.quora.com/What-is-an-approach-to-solve-the-problem-DQUERY-of-SPOJ-using-BIT-Segment-Tree
• https://stackoverflow.com/questions/18553567/difficulty-in-understanding-the-approach-for-solving-spoj-dquery
• https://blog.csdn.net/riba2534/article/details/81128660

References:

• Problem Set: https://cp-algorithms.com/data_structures/fenwick.html

[Leetcode] Topological Sort

Doc: https://docs.google.com/document/d/1kfn4MfnLLXVNFfayX6L6sjAsZSuUy6gJoJit3sngG-E/edit#heading=h.787pwa54vn0i


Implementation details:

1. Algorithm: DFS. (Kahn's algorithm needs to write codes find in-degrees of all vertices first. Therefore I don't recommend to implement Kahn's algorithm in a limited time. Besides, DFS could detect the cycle in the middle, not in the end.)

L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then return
    if n has a temporary mark then stop   (not a DAG)
    mark n temporarily
    for each node m with an edge from n to m do
        visit(m)
    mark n permanently
    add n to head of L

(Copy from Wikipedia.)

2. Don't forget to reverse L for correct order.

3. If you don't want to reverse L, you might do topological sort on transpose graph instead.

Topics on Leetcode

https://docs.google.com/document/d/1kfn4MfnLLXVNFfayX6L6sjAsZSuUy6gJoJit3sngG-E/edit?usp=sharing