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日 星期五

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):

System design:
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.

    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: