## 2018年6月21日 星期四

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

## 2018年6月15日 星期五

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

Data structure & algorithm (rusty):

System design:
After:
• Reject.
• Feedback:
• Good at problem understanding
• Good at algorithm
• 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.

## 2018年6月10日 星期日

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

Problems:

## 2018年6月9日 星期六

### [Data Structure] Sliding Window

Problems:

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: