[ProjectEuler] Problem 621: Expressing an integer as the sum of triangular numbers

Statement:

• Gauss famously proved that every positive integer can be expressed as the sum of three triangular numbers (including 0 as the lowest triangular number). In fact most numbers can be expressed as a sum of three triangular numbers in several ways.
• Let G(n) be the number of ways of expressing n as the sum of three triangular numbers, regarding different arrangements of the terms of the sum as distinct.
• For example, G(9)=7, as 9 can be expressed as: 3+3+3, 0+3+6, 0+6+3, 3+0+6, 3+6+0, 6+0+3, 6+3+0.
• You are given G(1000)=78 and G(10^6)=2106.
• Find G(17526 × 10^9).

Proof of Integer is Sum of Three Triangular Numbers:

• https://proofwiki.org/wiki/Integer_is_Sum_of_Three_Triangular_Numbers

Google Phone Interview

Before:

• Fail on Amazon Phone Interview.
• Lesson learn: should practice leetcode.
• Recruiter prescreen passed.
• Recruiter said you might practice leetcode.

Data structure & algorithm (rusty):

• Problem sets:
• Top google questions: https://leetcode.com/problemset/top-google-questions/
• Books:
• Antti Laaksonen, Competitive Programmer’s Handbook: https://cses.fi/book.pdf

System design:

• The System Design Primer: https://github.com/donnemartin/system-design-primer#index-of-system-design-topics

After:

• Reject.
• Feedback:
• Good at problem understanding 
• Good at algorithm
• Bad at coding
• Wait for next 6 months
• Lesson learn:
• More practice on coding
• No system design problem in the phone interview. Only algorithm and actual coding in google doc.

[Algorithm] Dynamic Programming

265. Paint House II: https://leetcode.com/problems/paint-house-ii/description/

10. Regular Expression Matching: https://leetcode.com/problems/regular-expression-matching/description/

• Recursive: https://leetcode.com/submissions/detail/158364236/
• Dynamic Programming: https://leetcode.com/submissions/detail/158375337/

[Data Structure] Binary Indexed Tree (Fenwick Tree)

Problems:

• 315. Count of Smaller Numbers After Self: https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/
• 421. Maximum XOR of Two Numbers in an Array: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/description/

[Data Structure] Sliding Window

Problems:

• 239. Sliding Window Maximum: https://leetcode.com/problems/sliding-window-maximum/description/
• 480. Sliding Window Median: https://leetcode.com/problems/sliding-window-median/description/

239. Sliding Window Maximum:

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k == 0) {
            return new int[0];
        }
        int[] maxSlidingWindow = new int[nums.length - k + 1];
        int maxSlidingWindowPos = 0;
        Deque<Integer> potential = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            while (!potential.isEmpty() && potential.peekFirst() < i - k + 1) {
                potential.pollFirst();
            }
            
            while (!potential.isEmpty() && nums[potential.peekLast()] < nums[i]) {
                potential.pollLast();
            }
            
            potential.offer(i);
            
            if (i - k + 1 >= 0) {
                maxSlidingWindow[maxSlidingWindowPos++] = nums[potential.peekFirst()];
            }
        }
        return maxSlidingWindow;
    }
}

[Algorithm][Graph] Topological sort

Topological-Sort(G)

1. call DFS(G) to compute finishing times v.f for each vertex v
2. as each vertex is finished, insert in onto the front of a linked list
3. return the linked list of vertices

Problem:

• 269. Alien Dictionary: https://leetcode.com/problems/alien-dictionary/description/

[Data Structure] LRU Cache

Video: https://www.youtube.com/watch?v=q1Njd3NWvlY

Java: HashMap + doubly linked list (custom).

[Algorithm][Geometry] Sweep line algorithm

Problems:

• 218. The Skyline Problem: https://leetcode.com/problems/the-skyline-problem/description/
• 253. Meeting Rooms II: https://leetcode.com/problems/meeting-rooms-ii/description/
• 850. Rectangle Area II: https://leetcode.com/contest/weekly-contest-88/problems/rectangle-area-ii/

---

Articles: https://leetcode.com/articles/rectangle-area-ii/

• Moving the sweep line
• Sweeping algorithms typically manage two sets of data:
• The sweep-line status gives the relationships among the objects intersected by the sweep line.
• The event-point schedule is a sequence of x-coordinates, ordered from left to right, that defines the halting positions of the sweep line. We call each such halting position an event point. Changes to the sweep-line status occur only at event points.
• The sweep-line status is a total preorder T:
• INSERT(T, s): insert segment s into T.
• DELETE(T, s): delete segment s from T.
• ABOVE(T, s): return the segment immediately above segment s in T.
• BELOW(T, s): return the segment immediately below segment s in T.

Any-segments-intersect algorithm:
ANY-SEGMENTS-INTERSECT(S)

1. T -> {}
2. sort the endpoints of the segments in S from left to right, breaking ties by putting points with lower y-coordinates first 
3. for each point p in the sorted list of endpoints
4.     if p is the left endpoint of a segment s
5.     then INSERT(T, s)
6.     if (ABOVE(T, s) exists and intersects s) or (BELOW(T, s) exists and intersects s)
7.         then return TRUE
8.     if p is the right endpoint of a segment s
9.         if both ABOVE(T, s) and BELOW(T, s) exist and ABOVE(T, s) intersects BELOW(T, s)
10.             return TRUE
11.         DELETE(T, s)
12. return FALSE

---

Java:

• TreeMap: https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html
• Example: https://leetcode.com/problems/rectangle-area-ii/discuss/137941/Java-TreeMap-solution-inspired-by-Skyline-and-Meeting-Room
• Segment tree with lazy propagation (custom)
• https://leetcode.com/articles/a-recursive-approach-to-segment-trees-range-sum-queries-lazy-propagation/